ИТМиВТ - Институт точной механики и вычислительной техники С. А. Лебедева РАН
Институт точной механики и вычислительной техники им. С. А. Лебедева РАН - научно-исследовательский институт в области информационных технологий, вычислительной техники и микроэлектроники
English
Главная страница Контактная информация Карта сайта и поиск
Об институте Решения Проекты Образование

Исследование возможностей управления распределением вычислений по вычислительным модулям

А.Климов, А.Окунев, А.Степанов

Аннотация

Поднимаются проблемы, которые будут возникать в вычислительной системе массового параллелизма [1] с ростом числа процессорных модулей, когда предположение об однородности (симметричности) коммуникационной среды перестанет соответствовать действительности. Предлагается отказаться от автоматического хеширования токенов в пользу управляемого программистом распределения. Утверждается (и показывается на примерах), что это может значительно сокращать затраты на коммуникации, и при этом не создает заметных дополнительных трудностей в программировании, и более того, что в рамках модели вычислений dataflow этих трудностей будет меньше, чем в аналогичных ситуациях при традиционном программировании. Кроме того, этот же механизм позволяет распараллеливать некоторые конструкции входного языка системы (групповые узлы), которые ранее считались принципиально последовательными.

Введение

В работах [1,5] была предложена архитектура вычислительной системы массового параллелизма, основанная на управлении данными (data driven computation). Это система массового параллелизма, состоящая из большого числа модулей, соединенных коммуникационной сетью. По сети осуществляется обмен информацией посредством передачи особых сообщений - токенов. Токены, направленные на один и тот же виртуальный узел, встречаются и тем самым активизируют порцию вычислений, которая посылает новые токены и так далее. Предполагалось, что виртуальные узлы распределяются по физическому адресному пространству псевдослучайным образом посредством хеш-функции. Главной целью распределения считалось обеспечение как можно более равномерной нагрузки на физические элементы системы. При этом неявно предполагалось, что времена передач мало зависят от координат источника и получателя, что общая производительность коммуникационной среды практически не зависит от распределения, и что, тем самым, она не может рассматриваться в качестве предмета оптимизации при выборе функции распределения. Однако, системы с большим (более 1000) числом процессорных элементов, уже не будут удовлетворять этому предположению. Уже в силу необходимости рассредоточения в пространстве, некоторые элементы будут близкими, а некоторые далекими. Соответственно, время передачи между далекими элементами может быть существенно больше, чем между близкими. Более того, и пропускная способность каналов связи между дальними элементами, как правило, будет меньше, чем между близкими (что может приводить к еще большему замедлению дальних передач). Поэтому от того, как виртуальные вычислительные элементы распределяются между физическими, может сильно зависеть нагрузка на коммуникационную сеть, а, следовательно, и общая эффективность прохождения задачи.

В данной статье мы исследуем, на примере ряда задач, возможности целенаправленного распределения виртуальных узлов по физическим модулям и его влияние на общую производительность. Предлагается языковое средство для управления распределением. Оно используется, после того как программа написана, отлажена и, в принципе, работает. Включение в программу средств распределения должно влиять только на эффективность, но не на логику и результаты работы самой программы.

Для демонстрации примеров программ нам потребуется ввести здесь базовые понятия об архитектуре, ее модели вычисление и о языке написания программ для нее.

Вычислительная модель

Всякая вычислительная систему массового параллелизма с неизбежностью будет распределенной по физическому пространству. То, что на ней выполняется, будем называть распределенным вычислительным процессом. Он должен быть как-то распределен по элементам системы, рассредоточенным по физическому пространству. При этом данные, потребляемые в каком-то одном месте, производятся в этом же или в других местах. Отсюда с неизбежностью возникает потребность в коммуникации (обмене информацией) между различными элементами оборудования, находящимися в разных местах физического пространства.

На этом уровне абстракции мы можем ввести понятие вычислительного кванта - это такая порция вычислений, производимых в каком-то отдельном элементе оборудования, которая между своим началом и концом не требует дополнительной информации от других элементов. Всякий распределенный вычислительный процесс можно представить разбитым на вычислительные кванты (см. Рис.1). Каждый отдельный квант уже не является распределенным. Будем говорить, что он выполняется в некотором месте физического пространства.

Рис.1. Распределенный вычислительный процесс как совокупность вычислительных квантов

С учетом физических расстояний передача данных из одного места в другое может занимать значительное время, которое может быть даже больше, чем собственно вычисления. Поэтому в интересах повышения эффективности передачи данных и сигналов следует рассматривать как односторонние, не требующие ответа или подтверждения. В тех случаях, когда необходим ответ, его следует рассматривать как отдельный акт коммуникации, а само получение ответа - как отдельный вычислительный квант.

Выполнение вычислительного кванта, согласно его определению, может быть инициировано в каком-то месте только тогда, когда в этом месте собрана вся информация, необходимая для работы кванта. Эта информация либо может поступить извне, либо может быть получена от других квантов. Соответственно, результатами работы кванта могут быть порции данных, предназначенные либо для других квантов, либо для передачи наружу в качестве результата всего вычислительного процесса.

Некоторая часть информации, используемой квантом, может быть сохранена в том же месте, где производится вычисление. Этот случай не выводит нас за рамки предположения, что всякая информация «либо может поступить извне, либо может быть получена от других квантов». Просто хранимую информацию считаем произведенной тем квантом, который вносил в нее изменение последним. Внесение изменения в нашей схеме концептуально есть изготовление новой, измененной копии. В реализации, с учетом размера изменяемых данных и монопольного доступа к ним со стороны текущего кванта, может быть произведено «изменения на месте». Иное (не монопольное) использование изменяемых данных приводит к недетерминизму и потому нашей моделью вычислений не поддерживается.

Каждый вычислительный квант должен исполняться согласно некоторому заранее заданному шаблону, определяющему правила его работы. Таких шаблонов-правил должно быть ограниченное число, их совокупность и составляет программу данного вычислительного процесса. При этом каждый шаблон выполняется, вообще говоря, большое число раз, в разных местах, в разное время, с разными данными.

В языке нашей модели программные шаблоны вычислительных квантов называются описаниями узлов, или просто узлами. Вычислительные кванты - активациями (или экземплярами) узлов. По одному шаблону может быть активировано много разных экземпляров узла. Порции данных, передаваемые от одних квантов другим, называются токенами. Описание узла специфицирует типы и форматы принимаемых токенов, условие активации и программу вычислений, производимых при активации узла. Оператор посылки токена включает само данное и адресную часть, по которой коммуникационная сеть способна доставить токен в то место, где он будет использован для других активации узлов. Адресная часть (или просто адрес) включает имя (описания) узла и некоторый дополнительный код - контекст, позволяющий идентифицировать конкретный экземпляр узла.

Адрес в токене - это не физический адрес места. В программе мы имеем дело с адресами, связанными с содержательными понятиями задачи. Поэтому эти адреса мы называем виртуальными. Виртуальное адресное пространство, вообще говоря, может быть очень большим, много больше физического адресного пространства, определяемого структурой вычислительной системы и ее геометрией. Но, чтобы токены доставлялись в нужные места (причем токены с одинаковыми виртуальными адресами должны доставляться в одно и то же место), в системе должно быть определено некоторое отображение виртуальных адресов в физические. Адресуемая физическая единица - модуль - должна уметь соединять токены с одинаковыми виртуальными адресами, запускать программу узла и при ее выполнении создавать и посылать новые токены.

Адресуемой виртуальной единицей при посылке токена является экземпляр узла. По приходу на данный экземпляр определенного числа токенов узел может быть активирован, в результате чего выполняется программа узла. Мы не требуем, чтобы каждая вычислительный квант имел уникальный адрес. Если приняты меры, исключающие нежелательное смешение токенов от разных активаций, то один и тот же экземпляр узла может быть активирован многократно.

Условием запуска экземпляра узла на выполнение является приход всех необходимых для этого токенов. Можно ввести понятие входа узла, и говорить, что на каждый вход должен прийти ровно один токен. Но могут быть и другие условия готовности. Например, должны (на какой-то из входов) прийти заданное количество токенов определенного вида. Или это количество указывается другим токеном. Излишнее число токенов (если оно допускается) может удерживаться для последующих активаций. Возможны условные схемы, когда разные наборы приводят к готовности, в зависимости от того, какой набор образуется раньше.

Часто одна и та же информация используется многократно различными квантами или узлами. Будет расточительным посылать на каждый квант отдельный токен, особенно в случае, когда все получатели достаточно удалены от отправителя, но между собой лежат компактно. Поэтому важно иметь возможность послать один токен на множество узлов-получателей (мультикастинг), задавая множественный адрес и/или указывая кратность использования токена (конечную или бесконечную). Коммуникационная среда доставляет такие токены по заданным местам, гарантируя доставку во все те узлы, адреса которых входят в заданный множественный адрес.

[1] Например, существуют такие абстракции, как система взаимодействующих последовательных процессов (CSP). Для перевода в нашу схему надо разрезать программу каждого процесса на куски в местах написания операторов ввода из канала (и вывода в канал, если он блокирующий). Каждый такой кусок и будет узлом. Он использует в качестве входов как данные, передаваемые по каналам от других процессов, так и локальные переменные своего процесса. Будем считать, что все состояния локальных переменных передаются между соседними кусками в форме отдельного токена. Продолжение процесса активируется тогда, когда токен «локальное состояние» встречается с токеном «операция с каналом», выданным другим процессом.

Вычислительная модель, которая используется для программирования или для построения компиляторов, не обязана буквально следовать вышеназванным базовым принципам [1]. Но если модель отражает эти принципы, то и проблем с ее реализацией и, соответственно, с эффективностью, скорее всего, будет меньше.

Некоторым препятствием к построению и использованию модели, приближенной к аппаратуре, может быть следующее противоречие. Всякая аппаратура имеет фиксированные количественные параметры, такие как объемы памяти, число функциональных устройств, размеры КЭШей разных уровней, число регистров, их разрядность и т.п. Но для одних приложений желательно иметь одни количественные характеристики, для других другие. Для некоторого приложения может не хватать чего-то одного, тогда как другое остается в избытке. С точки зрения программирования нам нужна модель, в которой виртуально никаких таких ограничений нет. И основная задача разработчиков системы состоит в том, чтобы отобразить неограниченную виртуальную модель на ограниченную реальную машину так, чтобы исчерпание или переполнение того или иного ресурса приводило не к аварийному останову, а лишь к мягкой деградации производительности. Ситуация подобна той, которая решается в обычных системах такими средствами как кэш, виртуальная память, динамическая память, мультизадачность, многопоточность и т.п. Разница в том, что в параллельной системе число различных ограничителей, которые нужно демпфировать, значительно больше.

Общий принцип демпфирования ограничений в различных существующих вычислительных системах состоит в том, что ограниченные физические ресурсы разделяются во времени. Например, кэш или виртуальная память работают устойчиво благодаря тому, что строки КЭШа или локальная память автоматически разделяются во времени между различными элементами основной или внешней памяти. Аналогично, стоящие в очереди задачи или программные треды конкурируют за аппаратные треды, пользуясь ими в режиме разделения времени. С динамической памятью дело обстоит несколько сложнее, но все равно гибкость выигрывается ценой некоторых потерь во времени работы. В системе, ориентированной на нашу модель вычислений, мы в основном следуем этому же принципу. Однако детали соответствующих механизмов выходят за рамки данной статьи.

Таким образом, особенности нашей вычислительной модели вытекают непосредственно из общих свойств распределенных вычислительных систем. С другой стороны, вычислительная система, предназначенная для выполнения программ, построенных в рамках этой модели, должна будет обладать рядом специфических качеств, обеспечивающих устойчивость выполнения программ по отношению к разного рода ограничениям, присущим всякой физической системе. Создание таких качеств и будет основной задачей проектирования и реализации таких систем.

Определение модели

Теперь мы переходим к изложению конкретных особенностей модели вычислений и ее языка. В рамках этой статьи излагается модель, максимально приближенная к разработанной в проекте ИПИ РАН [1,5].

Язык модели

Для программирования используется специальный язык - DFL. Программа представляет собой набор описаний узлов. Описание узла состоит из заголовка и тела. Заголовок указывает имя, несколько входов, обычно один или два, и контекст. Узел это аналог процедуры, а входы - ее параметры. Кроме входов есть еще один параметр - контекст. Контекст служит как бы расширением имени узла. Имя узла вместе с контекстом будем называть ключом. Ключ будем называть виртуальным адресом узла. Все параметры (входы и контекст) передаются «по значению» (обычно они имеют фиксированный размер - 64 бита, но, вообще говоря, это ограничение не существенно). Входы и контекст могут иметь типы, обычно это числа или структуры. Тело узла представляет собой программу (обычно очень маленькую) на простом языке программирования, похожим на Паскаль. В качестве аргументов она может использовать только входные данные и контекст, то есть, никаких глобальных переменных нет. Могут использоваться глобальные константы и вызываться вспомогательные процедуры-функции. Вот пример описания узла, выполняющего умножение двух чисел и направляющего результат на другой узел. В зависимости от четности единственного поля исходного контекста результат направляется на первый или второй вход виртуального узла R с четным контекстом, чем обеспечивается дальнейшее попарное соединение результатов.

Другие примеры описаний узлов можно найти ниже в основной части.

Помимо обычных операторов, в программе узла могут находиться операторы посылки токенов. Токен содержит данное (являющееся числом или структурой), ключ (содержащий имя узла и контекст), и некоторые дополнительные атрибуты. Будем говорить, что токен направлен в узел с указанным в нем именем. Среди атрибутов обычно есть указание имени (номера) входа. Чтобы узел был активирован и начал выполняться, должны появиться токены для всех его входов, причем их ключи должны совпадать. Результатом выполнения программы узла является создание (посылка) нескольких новых токенов (быть может, ни одного). Пример оператора посылки (конкретный синтаксис может отличаться):

send v to N.a {k};

Здесь v - данное, N - имя узла, a - имя входа (предполагается, что оно использовано в заголовке узла N), k - контекст. И v и k могут быть вычисляемыми выражениями.

Начальные данные поступают в систему из внешней среды в виде таких же токенов. Результаты также являются токенами, направляемыми по внешним адресам.

Семантика языка может быть определена несколькими разными способами.

Способ 1: распределенный

Вводится виртуальное пространство узлов. В нем каждому описанию узла М, имеющему заголовок

node M(a,b,...) {i,j,...}

соответствует подпространство, элементами которого (называемые вычислительными элементами) являются экземпляры узла с адресами, образованными всевозможными значениями контекста, например M{3,5,...}. Токен, посылаемый оператором

send v to M.a {i,j};

через какое-то неопределенное время появляется на входе a вычислительного элемента M{i,j}. Когда на всех входах узла имеется (хотя бы) по одному токену, фиксируется готовность узла к выполнению. Обнаруженные токены одновременно забираются со входов (ровно по одному с каждого входа) и формируется заявка на выполнение программы узла с приписыванием каждому входу значения данного из соответствующего токена. Через какое-то неопределенное время программа узла выполняется и порожденные ею токены направляются в другие узла.

Способ 2

Текущее динамическое состояние системы характеризуется двумя множествами токенов и некоторым множеством активных (работающих) узлов. Одно множество токенов будем называть верхним, другое - нижним. Когда токен «посылается», он помещается в верхнее множество. В систему могут поступать также входные токены извне, и они тоже помещаются в верхнее множество. Некоторые новые создаваемые токены будут иметь в ключе внешний адрес. Такой токен будет выходным. Таким образом, система в целом принимает некоторый поток входных токенов и выдает некоторый поток выходных токеном. При этом изменяется текущее внутреннее состояние системы.

Система логически работает следующим образом. Если множество верхних токенов пусто, и работающих узлов нет, работа прекращается. Пока множество верхних токенов не пусто, в цикле выбирается один из верхних токенов и сопоставляется со всеми нижними. В зависимости от типа узла (тип определяется заголовком), к которому направлен токен, и от некоторых дополнительных атрибутов токена, среди нижних токенов отбираются токены, подходящие для образования пары. Обычно это токены с совпадающим значением ключа. Учитывается также вход: токены, посланные на один и тот же вход некоторого двухвходового узла (не симметричного) друг друга «не видят». Далее с каждым из отобранных токенов выполняется спаривание. Но: если узел одновходовой, то парного токена не требуется, и такой токен активирует свой узел самостоятельно.

Парных токенов может быть нуль, один или много. В последнем случае говорят о множественном оклике. Если парных токенов не было, то обычно верхний токен просто переходит в нижнее множество (более точно - см. ниже про кратность). В общем случае с каждым отобранным токеном производится спаривание. В результате спаривания может образоваться новый активный узел. Каждое спаривание концептуально считается неделимым актом.

Программы активных узлов выполняются совершенно независимо друг от друга. По ходу выполнения каждый вновь созданный токен добавляется к верхнему множеству.

Способ 3.

Текущим состоянием системы является единое множество токенов T, в которое входящие токены добавляются по мере их поступление. Каждый токен добавляется через некоторое неопределенное время после своего образования (отражающее неопределенную задержку в коммуникационной среде).

Время от времени в множестве Т производится поиск на предмет нахождения в нем полных наборов токенов, поступивших на входы некоторого узла. При обнаружении такового выполняется атомарная транзакция по изъятию токенов набора из множества Т, а затем производится активизация программы узла с отобранными значениями на входах. Если токены имели кратность, то в рамках атомарной транзакции изъятия из кратности каждого токена вычитается 1, после чего токен удаляется из множества Т, если получится нуль или сохраняется в нем (с уменьшенной на 1 кратностью) в противном случае.

Этот вариант отличается от предыдущего лишь тем, что нет разделения на верхние и нижние токены, есть единое множество токенов, в которое добавляются входящие токены по мере их поступления. В некоторые моменты времени производится поиск внутри этого множества на предмет нахождения в нем полных наборов токенов, поступивших на какой-либо узел.

Семантика1.

При использовании токена для активизации узла он не удаляется сразу из множества токенов на входах данного узла, но из его кратности вычитается 1, и если получится нуль, то токен удаляется, иначе сохраняется.

Семантика2.

При каждом спаривании из кратностей обоих токенов вычитается единица. (Это типовой случай, для специальных токенов схема может отличаться). После спаривания нижний токен удаляется, если его кратность стала нулевой. Если у верхнего токена после очередного спаривания кратность стала нулевой, то процесс спариваний прекращается, верхний токен уничтожается, а если остались отобранные, но необработанные, нижние, то они сохраняются в нижнем множестве неизменными. Если после всех спариваний кратность верхнего по-прежнему ненулевая, то он помещается в нижнее множество.

Другие элементы языка

У каждого токена есть особый атрибут - кратность. Чаще всего (и по умолчанию) это 1. Кратность записывается в двойных угловых скобках в виде:

send v <> to N.a {k};

Кратность говорит о том, что данный токен может быть использован для активизации узла указанное число раз. Подробнее см. семантику.

Кратность токена может быть бесконечной - тогда количество активизаций не ограничено:

send v <> to N.a{k};

Может показаться, что токен с конечной кратностью равносилен такому же количеству своих однократных копий. Но это не всегда так. Например, если встречаются два токена с неединичной кратностью, то у нас образуется всегда одно спаривание, и оба токена остаются с уменьшенной на 1 кратностью. Если же их «разложить на однократные», то число спариваний будет равно меньшей из двух кратностей. В спарившихся токенах имена и контексты обычно совпадают (в общем случае ключи складываются логически). В результате спаривания происходит активация узла с заданным именем и контекстом. Данные из токенов становятся фактическими значениями параметров-входов, и программа помещается в начальное состояние, перед первым оператором. Новый узел добавляется к множеству активных узлов.

Некоторые операторы посылки могут содержать знак ‘*’ на месте некоторых полей контекста. В самом токене это выражено в виде специального атрибута - маски. Такому токену безразлично, что будет находиться в этом поле у парного токена, и он будет спарен при любом значении. Обычно такие токены должны иметь кратность, равную числу ожидаемых парных токенов, или бесконечную, хотя это решает программист.

В разных версиях семантики по разному решается вопрос о поведении этих токенов.

Семантика 1. Токены со знаком ‘*’ рассылаются всем вычислительным элементам, контекст которых получается из контекста токена заменой знаков ‘*’ на некоторые конкретные значения.

Есть категории специальных токенов. Например, это токены удаления, которые при спаривании ничего не активируют, а просто удаляют парный токен, будь то верхний или нижний. Есть два вида удаляющих токенов: записываемые и не записываемые (в нижнее множество). Первые могут предшествовать удаляемому токену. Последние служат для завершающей чистки.

Особый тип токена - косвенность. Он посылается оператором вида

send-link ( R ) to N {k};

Здесь R - имя узла (одновходового!), на который будет перенаправлен парный токен (который, естественно, был или будет направлен на узел N{k}). Кратность перенаправляемого токена игнорируется (хотя здесь возможны варианты).

Еще один тип токена - счетчик. Он активирует узел только в случае, когда кратность (у парного ему токена, хотя тут возможны варианты) стала равной нулю.

Распределение токенов по модулям

Исполняющую систему предполагается строить из модулей, соединенных коммуникационной сетью и работающих параллельно. В каждом модуле имеется сопоставляющая память (СП), в которой хранится какая-то часть нижних токенов. Каждый токен с конкретным ключом (без ‘*’) попадает в свой модуль, номер которого зависит от ключа и только от ключа (рис. 2). Таким образом токены с конкретными ключами непременно спарятся, если они должны это сделать концептуально. Токены со звездочками, как правило, должны копироваться во все модули.

Вычислительные исполнительные устройства (ИУ) есть в каждом модуле, и нам совершенно безразлично, где именно будет выполняться программа того или иного узла. Поэтому из соображений эффективности будем считать, что исполнение происходит в том модуле, где произошло спаривание. Вопрос балансировки вычислительной нагрузки будем считать привязанным к балансировке распределения токенов.

Рис.2. Общая структура системы. Модули обмениваются токенами через коммутатор. Номер (адрес) модуля вычисляется на основе ключа токена. Глобальные токены рассылаются во все модули.

Однако есть проблема токенов с масками. Их можно было бы посылать всегда во все модули (по крайней мере концептуально), но мешает возможность посылки двух таких токенов навстречу друг другу. В последнем случае вместо одной встречи получится встреча в каждом модуле, что некорректно. Поэтому этот случай в языке DFL допускается только в так называемом групповом узле. Для таких узлов тот факт, что в токенах будут маски и где именно, задается в заголовке узла: при описании контекста такие поля заключаются в квадратные скобки. И система в этом случае направляет все адресованные ему токены в один модуль, зависящий только от полей вне масок (по правилу, что модуль зависит не от всего ключа как такового, а от ключа с обнуленными полями под маской). И токены, направленные в него, спариваются независимо от того, что в них указано в таких полях, будь то конкретное значение или ‘*’.

В то же время в языке допускается и просто послать токен с ‘*’ в любом поле контекста на любой узел. В этом случае он считается глобальным и посылается на все модули. Однако, такие токены не могут встречаться друг с другом (это считается программной ошибкой), кроме случая, когда один из них - стирающий.

Конкретный способ распределения токенов по модулям с точки зрения результата несуществен. Поэтому выбор распределения можно направлять на другие цели, например на обеспечение равномерности нагрузки на модули, прежде всего в части объемов хранимых токенов. С точки зрения этой цели, хорошим решением будет использование хеш-функции, тем более что это может делаться системой автоматически. Этот подход, восходящий к [4], до сих считался основным. Однако, он ведет к тому, что практически все связи между разными узлами становятся дальними, причем почти всегда почти максимально дальними. Но в больших вычислительных системах (например, как [1]), пропускная способность сетей разного уровня с ростом уровня заметно снижается. Различие между совсем локальными и самыми глобальными уровнями может доходить до 2-х порядков. А следовательно, полагаясь на чисто случайное разбрасывание, мы может терять производительность в десятки раз!

[2] В традиционных кластерных вычислительных системах с числом процессоров до 1000 системы программирования обычно не предусматривают каких либо средств для дискриминации процессорных модулей по степени их удаленности друг от друга.

Очевидно, что эта проблема возникает не только в нашей модели вычислений, она общая, и потому во всех (больших [2]) системах так или иначе приходится делать так, чтобы большая часть коммуникационных потоков (90% и выше) замыкалась на более локальных уровнях. Понятно, что это ведет к значительным издержкам в программировании, поскольку программисту приходится явно учитывать многие характеристики конкретной вычислительной системы: число уровней, размеры кластеров разного уровня, характеристики пропускной способности и латентности каждого уровня и т.п., - и подстраивать программу под все эти характеристики.

Наша модель вычислений тоже потребует решать все эти проблемы. Однако, представляется, что в ней это будет сделать проще. И главные ее свойства, которые обеспечат нам преимущество таковы:

  • предельно мелкая гранулированность (вплоть до отдельных операций)
  • предельно асинхронное выполнение
  • наличие у всякого вычислительного атома его уникального виртуального адреса (ключа).

Наша цель двоякая: упрощения программирования и эффективность. Для ее достижения желательно, чтобы в языке программирования были по возможности разделены следующие две части:

  • математически корректное описание алгоритма, не учитывающее распределения узлов по модулям
  • дополнительное указание (в форме прагма-предложений) распределения виртуальных узлов по физическим модулям

Чтобы задать распределение, нужно задать отображение, или функцию, которая вычисляет номер модуля, исходя из виртуального адреса узла (раньше эту роль играла хеш-функция). Такую функцию надо вычислять для каждого токена при его посылке - поэтому она должна быть быстрой. А значит надо реализовать ее аппаратно, зафиксировав некоторый ограниченный язык (например, состоящий из сдвиговых и поразрядных логических операций).

Модуль, в который посылается токен, осуществляет операцию спаривания его с парным ему токеном. Поэтому важно, чтобы оба парные токена были направлены в один и тот же модуль. Этот модуль определяется на основе ключа, а точнее - основы токена, которая определяется как ключ, в котором под маской все поля обнулены. Основа - это в сущности виртуальный адрес узла: для неглобальных токенов необходимым условием спаривания является равенство основ. Поэтому, чтобы гарантировать попадание в один модуль всех токенов, направленных в один узел, достаточно, чтобы функция, вычисляющая для токена номер модуля, зависела только от основы ключа.

Конечно, не всякий записанный на DFL алгоритм допускает возможность эффективно управлять распределением. Более того, написание алгоритмов, обладающих таким качеством, составляет дополнительную трудность в и без того сложном деле программирования на DFL. Но если мы упростим программирование в принципе путем поднятия уровня языка, то и эта дополнительная трудность также разрешится.

Тот факт, что программисту придется думать о локальности (точнее об управлении локальностью) не является специфической чертой нашей модели, это придется делать в любой (см. например, [2]). Но наша модель, в силу упомянутых выше ее качеств, позволяет делать это в более удобных терминах, тем самым, облегчая сопровождение программ и их мобильность.

Дело в том, что при разработке алгоритма в терминах DFL, программисту так или иначе приходится вводить некое виртуальное пространство узлов с присущей ему метрикой, соответствующей интенсивности информационных потоков между узлами. Эта метрика, как правило, программисту хорошо известна, поскольку она выводится из его первичного представления об алгоритме. Однако, из готовой программы извлечь ее может быть затруднительно, тем более автоматически. Поэтому все, что нужно теперь - это предоставить программисту возможность выразить свое понимание метрики в некоторой языковой форме. Семантикой (смыслом) этой формы будет некоторое отображение виртуальных адресов в «физические», которое сохраняет метрику, то есть переводит близкие виртуальные узлы в близкие (в смысле коммуникационной способности) физические номера модулей.

Пример 1. Суммирование «пирамидкой»

Рассмотрим в качестве примера задачу суммирования «пирамидкой» (см. [5]). Виртуальный dataflow-граф и его раскладка по виртуальным адресам может быть такой как на рис.3. Такая раскладка удобна с точки зрения простоты формулы для вычисления в каждом узле адреса преемника: t shift 1 Программа в целом имеет вид:


Здесь число слагаемых посылается на вторые входы узлов типа T, а сами слагаемые - на их первые входы.

Естественная метрика на данном графе состоит в том, что два узла «близки», если они принадлежат одному поддереву, причем, чем меньше размер общего поддерева, тем «ближе» узлы. Поэтому при распределении узлов, скажем, по 2-м модулям, будет целесообразно разрезать дерево на 2 поддерева, растущие из узлов 2 и 3, а старший узел (1) отнести к одному из них, скажем к левому. Аналогично, при распределении по 4-м модулям и т.д.

Рис.3. Виртуальный граф для суммирования «пирамидкой». Сбоку от каждого суммирующего узла указан его адрес: слева десятичным числом, справа он же - двоичным. Пунктирные линии задают распределение графа по модулям. Рисунок взят из [5].

Для узлов типа T распределение задается простой функцией: (i-1)/4. Для узлов типа S уже будет не так просто. Нам понадобится функция norm(n,p), которая «нормализует» число n, сдвигая его влево до тех пор, пока старшая единица не выйдет за левый край, и берет старшие p разрядов результата. Тогда формула для номера модуля будет иметь простой вид: norm(t,2).

В программе распределение узлов по модулям задается оператором вида distribution(<выражение>) после заголовка узла. Выражение может содержать константы и поля контекста. Оно будет вычисляться при посылке токена на данный узел.

Программа с заданным в ней распределением будет иметь вид:

Можно описывать распределение не в каждом узле, а один раз при определении типа контекста. Используя способность компилятора производить константные вычисления можно параметризовать код количеством процессорных модулей.

Возможно, при какой-то другой раскладке формулы будут проще (правда, переход к преемнику может оказаться сложнее). Выбор подходящей удобной раскладки - задача творческая. Здесь мы только демонстрируем принцип. И поскольку нас сейчас интересует прежде всего вопрос экономии коммуникационных потоков, то не страшно, что ради этого возможно придется идти на некоторые жертвы в части объемов вычислений.

Пример 2. Умножение матриц

В материалах отчета [3] приводится решение задачи умножения матриц при помощи двойных групповых узлов. Оно эффективного использует аппаратуру (ассоциативную память) и обеспечивает достаточно высокий параллелизм. Но с точки зрения объемов пересылаемых данных оно весьма расточительно, а именно - требует O(N3) пересылок. В то же время, согласно анализу, проведенному в [2], более эффективным с этой же точки зрения является блочный метод, требующий только N2d пересылок, где  при разбиении на блоки по всем трем измерениям, или  при разбиении на блоки только по измерениями выходной матрицы (здесь K - число процессорных модулей).

В следующем разделе мы вернемся к идее использования групповых узлов, а пока рассмотрим другой вариант, в котором вычисляющие узлы соответствуют элементам результирующей матрицы. При этом нужно каждый элемент исходной матрицы так или иначе доставить до каждого элемента некоторой строки (для второй матрицы - столбца) результирующей матрицы. Посылать его сразу в виде N токенов нерационально - будут те же O(N3) пересылок. В идеале надо сделать так, чтобы каждый элемент посылался в каждый модуль, где он нужен, только один раз. При блочном разбиении выходной матрицы по модулям, потребуется сделать только  посылок каждого элемента. Исходные матрицы при этом условно разбиваются на полосы: матрица A разбивается на  горизонтальных полос, а матрица B - на столько же вертикальных. И на каждом из K процессоров выполняется умножение одной полосы матрицы A на одну полосу матрицы B и вычисляется одна клетка матрицы результата.

Конечно, если иметь в виду только экономию пересылок, то можно просто в каждом модуле, ввести один узел-станцию, на которую и направлять все передачи для данного модуля, а уж он потом распределит их дальше по рабочим узлам внутри модуля. Но такое решение будет чересчур зависеть от конфигурации системы, чего хотелось бы избежать.

Наш алгоритм должен в минимальной степени зависеть от количества наличных модулей и их связанности. Вся зависимость должна быть сосредоточена в дополнительных операторах distribution, управляющий распределением узлов по модулям.

Предлагаемый метод опирается на решетку узлов, соответствующих элементам выходной матрицы. Нам по-прежнему придется посылать каждый элемент исходный матрицы на каждый узел выходной строки, то есть N раз. Но важно, что большая часть этих посылок будет локальной. А если считать межмодульные пересылки, то их будет около  .

Будем считать, что все матрицы квадратные. Можно работать и с прямоугольными, если aspect ratio не выше 2 и сворачиваемое измерение является наибольшим. В противном случае надо сделать предварительное разбиение на блоки.

Итак, имеем решетку узлов M{i,j}, 0<=i,j< N. Пошлем каждый элемент матрицы А на вход a узлa M, но не «своего», а со сдвигами: первую строку пошлем на свое место, а каждую последующую строку будем посылать на соответствующую строку узлов со сдвигом «влево» на 1 больше, чем предыдущую. Аналогично элементы матрицы B пошлем на входы b по столбцам: 1-й столбец на свое место, а каждый следующий - со сдвигом «вверх» на 1 больше, чем предыдущий. Все сдвиги циклические, с длиной цикла N, то есть «выползающие» элементы будем подавать с другого конца.

В узлы М подадим также нули на третий, суммирующий вход s (пока так говорим, потом от многовходовых узлов избавимся). В каждом ячейке решетки выполним следующее:

  • перемножим a и b
  • сложим произведение с s
  • перешлем элемент a на одну позицию влево
  • перешлем элемент b на одну позицию вверх

Всего выполним это N раз. Тогда на входах s будет результирующая матрица С = AB. Чтобы это понять, достаточно увидеть, что в каждой клетке на каждой шаге некоторый элемент строки матрицы А умножается на некоторый элемент столбца матрицы В с тем же порядковым номером. И за N шагов через клетку (i,j) пройдут все элементы строки Ai и соответствующие им элементы столбца Bj.

Описанный вариант имеет тот недостаток, что каждая итерация должна полностью завершиться перед началом следующей. Чтобы этого избежать, введем в виртуальное пространство дополнительное измерение (k). Тогда каждый виртуальный узел M{i,j,k} будет умножать два числа, складывать произведение с накопленной суммой и передавать все (сумму и оба сомножителя) на следующий слой, причем только один раз. Результат будем снимать (асинхронно) со входов s (N+1)-го слоя.

Ниже приводится полный текст программы (все узлы двухвходовые, а N и K-константы):

Чтобы программа не зациклилась, надо ее остановить на слое N. Для этого используется установочный оператор g_erase M {*,*,N}. С ним связана определенная проблема. Этот глобальный токен должен дойти до каждого модуля СП заведомо прежде, чем в нем объявится соответствующий токен узла M. Чтобы это гарантировать, надо дождаться завершения рассылки и только после этого запускать процесс посылкой начальных нулей. (Можно сделать это независимо в каждом модуле, если посылку нуля в S в своем модуле привязать к приходу токена g_erase). Элементы матриц могут посылаться асинхронно в любое время.

В первой строке кода содержится указание distribution (zip(i/d, j/d));. Здесь и только здесь имеет место зависимость от числа модулей K. В формуле используется встроенная функция zip(i,j), которая «скрещивает» два числа в битовом представлении, помещая биты первого на четные места, а биты второго на нечетные. Это очень полезная функция отображает двумерные координаты в одномерный номер так, чтобы близкие узлы на двумерной решетки (почти всегда) имели близкие номера. В результате ячейки решетки будут распределены строго по клеткам размера d x d (см. рис.4).

Рис.4. Решетка из 16х16 узлов распределена среди 16 модулей P0-P15 клетками 4х4.

Рассмотрим работу программы с точки зрения выполняемых коммуникаций. Каждый слой разбит на квадратные клетки: одна клетка - один модуль. На каждой итерации все элементы смещаются (циклически) на одну ячейку влево или вверх. При этом большая часть посылок замыкается внутри модуля-клетки, и только крайние элементы с одной из сторон посылаются к другому модулю. Поэтому, если сторона клетки равна  , то только каждая d-я посылка пройдет через границу клетки. В целом же за время выполнения программы каждый элемент будет переслан между модулями-клетками в среднем без малого  раз. С учетом начальной рассылки  +1 раз. Согласно расчетам из [2] это на 1 больше точного минимума (в нашем алгоритме на последних итерациях числа будут посылаться «понапрасну» в те клетки, где они уже были в начале). Таким образом получается, что наша программа работает почти оптимально в смысле объема пересылок между модулями, и с ростом K относительное отличие от оптимума будет стремиться к нулю.

Если мы изменим K, то произойдет перераспределение, и оно будет по прежнему почти оптимальным. Оказывается, оно будет почти оптимальным и в случае иерархической коммуникационной сети, как в Merrimac. В этом случае модулем уместно считать один кластер (у нас ему соответствует одно элементарное «кольцо»). В системе всего 256К кластеров, то есть будет K=5122=262144. При выполнении на всей системе одного умножения матриц размера 4096x4096 матрицы разобьются на клетки размера 8х8. В одном чипе 16 кластеров, то есть в системе всего 16К чипов. Заметим, что наше распределение по кластерам таково, что оно будет одновременно столь же оптимальным и для чипов: в каждый чип попадет клетка размера 32x32. То же можно сказать и о платах и о стойках. Таким образом на всех 4 уровнях сеть будет нагружена почти оптимально. Мы заботились об одноуровневой сети, а получилось хорошо сразу на всех уровнях! А произошло это во многом благодаря тому, что программа записана в терминах предельно мелкозернистого параллелизма. Если бы это было не так, то нам пришлось бы строить код на всех уровнях с учетом размеров каждого уровня. У нас же основной код совершенно не зависит от таких параметров системы, как число уровней и размеры каждого уровня.

Расщепление групповых узлов

В начале предыдущего раздела упоминался метод умножения матриц на двойных групповых узлах (см. отчет [5]). Один такой узел позволяет на одном процессорном модуле выполнить эффективно умножение столбца на строку с получением матрицы результата. Умножение матриц общего вида сводится к N таким умножениям с последующим сложением результирующих матриц.

Узел объявлен групповым, если в его контексте часть полей заключена в квадратные скобки. По этим полям узел «сгруппирован». Будем называть их связанными. При сопоставлении токенов различие ключей в связанных полях игнорируется. Поэтому адресом узла в этом случае является ключ с обнуленными связанными полями. В каждом токене, посылаемом на групповой узел на месте некоторых связанных полей может стоять звездочка, причем в правильном полном наборе токенов каждое такое поле должно быть задано не звездочкой ровно один раз (иначе - ошибка).

Двойным групповым узлом называется узел, у которого два поля контекста связаны, причем в токене на первом входе задано одно из них (а на месте другого - звездочка), а на втором - другое. Обычно на один вход посылаются n токенов кратности m (или более), а на другой - m токенов кратности n (или более). В этом случае каждый из первых обязательно спарится с каждым из вторых. При спаривании формируется общий контекст, в котором все поля (в том числе связанные) заданы. Таким образом, программа узла будет выполнена для всех возможных сочетаний m*n раз.

Если номер модуля не зависит от связанных полей (а именно так и делалось при использовании хеш-функции), то вся эта работа производится в одном модуле. Поэтому основной проблемой этого решения является ограниченный параллелизм. Модуль памяти, реализующий такой узел работает, в сущности, последовательно: когда поступает элемент A[i], он «спаривается» со всеми ранее поступившими элементами B[j], а элемент A[i] записывается. Аналогично для элемента B[j], который «спаривается» со всеми ранее поступившими элементами A[i]. Весь параллелизм при умножении матриц достигается лишь благодаря наличию N таких узлов. И к тому же возникает мощный поток токенов произведений для суммирования, которых насчитывается порядка N3, причем почти все они будут нелокальными.

Но что мешает распределить работу одного такого узла на много модулей? Наверно единственная причина - это принцип, что номер модуля определяется ключом, в котором связанные поля обнулены. Но в исходных токенах к этому узлу есть еще и замаскированные поля, по которым узел «свернут». Замаскированные поля в основу не входят и, согласно постулату, в выработке номера модуля не должны участвовать.

Смысл сворачивания был в том, чтобы избежать глобальных рассылок токенов с одной или другой стороны, заменив их посылками групповыми с кратностями. Без сворачивания нужно каждый токен посылать глобально, что нагружает много и понапрасну коммуникационную среду, и сопоставляющую память. Но это было необходимо, когда номер модуля по адресу узла определялся хеш-функцией. Теперь же, когда у нас есть средства управляемого распределения узлов по модулям, мы можем частично «развернуть» узел обратно. А чтобы избежать глобальных рассылок, потребуем, чтобы транслятор/исполнитель мог вычислить, для каждого группового токена, на какие модули его надо, а на какие не надо посылать. В следующем разделе этот вопрос обсудим подробнее. Пока же просто считаем, что для групповой посылки транслятор может вычислить некоторое множество адресов, на которое будет рассылаться токен. При этом всякий адрес, куда может прийти парный токен, должен входить в это множество. Обратное не требуется (то есть в множестве адресов для рассылки токена могут быть лишние адреса, на которые не придет ни одного парного токена).

Расщепление групповых узлов может выглядеть, например, так:

Аргумент distribution, как и раньше, задает номер модуля в зависимости от полей контекста. Но в данном случае в число параметров формулы попало поле, по которому узел свернут. Это означает, что токены, отличающиеся этим полем, будут посылаться в разные модули, хотя формально они относятся к одному и тому же узлу.

Заголовок узла учитывается (компилятором) при отправке токена в этот узел. При отправке на групповой вход:

send b to M.y {i,j}

создается токен с контекстом {i,[j]} (поле j задано, но замаскировано), который посылается на модуль, номер которого вычисляется по формуле из distribution от ключа {i,j}.

Отметим, что если для группового узла распределение не задано явно, то для определения номера модуля будет использована хеш-функция, вычисляемая от ключа с обнуленными полями под маской. Тем самым данный групповой узел будет создан в каком-то одном модуле. При явном же указании распределения обнуления не производится, поскольку использование тех или иных полей ключа в функции распределения находится под контролем программиста. И потому групповой узел оказывается расщепленным на много модулей.

При отправке токена на одиночный вход:

send a to M.x {i,*}

создается токен с контекстом {i,[0]}, копия которого посылается в каждый модуль, номер которого может быть получен по формуле из distribution от ключа {i,j} при каком-либо значении j. Такие токены будем называть расщепленными (split). Для расщепленных токенов, как и для глобальных, кратность по умолчанию считается бесконечной.

Для двойного группового узла, определяемого заголовком вида

node M(x,y) { [i],[j]}; distribution (zip(i/d,j/d);

обе посылки делаются групповыми. При этом один токен посылается оператором

send a to M.x {i,*},

а другой - оператором

send b to M.y {*,j}

и при этом первый токен a{[i],0} размножается во все модули, которые отвечают, какому либо ключу вида {i,*} (где на месте * может быть любое значение из допустимых), а второй токен b{0,[j]} - во все модули, отвечающие какому-либо ключу вида {*,j}.

Почему такое изменение в семантике не приведет к нарушению работы программы? Вопрос не прост, особенно для двойных групповых узлов. В таком узле должно произойти строго однократное спаривание каждого левого токена с каждым правым.

Попытаемся найти условия, при которых все будет правильно. Пусть M(i,j) - функция распределения из атрибута distribution. Она задает разбиение на множестве пар (i,j). Каждому элементу разбиения взаимно однозначно соответствует один модуль. На плоскости (I,J) выберем произвольную точку (i,j) и проведем через нее вертикальную и горизонтальную прямые. Множество модулей, на которые посылается токен a{i,0}, должно «покрыть» (соответствующими элементами разбиения) вертикальную прямую. Для токена b{0,j}, соответственно - горизонтальную. Корректность означает, что эти два покрытия имеют единственный общий элемент, который накрывает пересечение двух прямых - точку (i,j). Это должно быть верно для любой пары индексов (i,j). Можно доказать, что для этого необходимо, чтобы все элементы разбиения были «прямоугольниками», точнее декартовым произведением своих проекций на оси I и J. Рис.1 иллюстрирует случай, когда это условие не выполняется, что и приводит к некорректности.

Для доказательства допустим, что у нас «все корректно», и рассмотрим две произвольные пары (i1 , j1) и (i2 , j2), лежащие в одном элементе разбиения - A. Докажем, что тогда и пары (i1 , j2) и (i2 , j1) будут принадлежать этому же элементу. Пусть это не так, и, скажем, (i1 , j2) принадлежит другому элементу - B. Тогда окажется, что два токена: a12{i1,0} и b12{0,j2} - встретятся дважды: и в модуле А, и в модуле В, что противоречит предположению о корректности.

Рис.5. Пример, когда необходимое условие не выполняется: есть «непрямоугольные» элементы. Тогда можно найти точку (i,j) такую, что соответствующие два встречных токена будут встречаться дважды: в элементах разбиения (= модулях) 1 и 2.

Условие «прямоугольности» элементов покрытия необходимо, но не достаточно для корректности. Чтобы оно стало достаточным, можно наложить дополнительное требование на рассылки копий: они не должны посылаться в лишние модули. То есть в правиле «копии токена a{i,0} посылаются в те, модули, которые отвечают хотя бы одному из ключей вида {i,*}» надо добавить: «и только в них».

Пример 3. Умножение матриц (на двойных групповых узлах)

Рассмотрим пример программы из отчета [5] :

Текст программы слева - в точности как в отчете [5]. Справа - дополнительный прагма-комментарий, касающийся распределения посылаемых токенов по модулям. Указание "local" в заголовке узла S означает, что это «локальный» узел, т.е. любой (не глобальный) токен, посылаемый в S из некоторого узла, посылается в тот же модуль, в котором была порождена пара, активизировавшая этот узел (в паре содержится этот номер). Вместо "local" в данном случае можно было бы написать "distribution (zip(i/d, j/d))". Результат был бы тот же, но пришлось бы при каждой посылке в S вычислять номер модуля, соответствующий указанному распределению.

Программа работает следующим образом. В узлах А и В исходные матрицы посылаются, соответственно, на левый и правый вход узла-умножителя M. Узел M свернут по индексу i по левому входу и по индексу j по правому. Сначала рассмотрим случай, если оператора distribution нет. Тогда для каждого k есть один узел M, на который поступают элементы k-го столбца матрицы А слева и элементы k-й строки матрицы В справа. Узел осуществляет спаривание по принципу «каждый с каждым» и посылает результаты на суммирующие узлы. Всего имеется 2*N2 исходных токенов и N3 произведений, посылаемых не локально. Лишь каждый K-й токен в среднем будет посылаться локально (K - число модулей). Поэтому общее число пересылок между модулями составит N2*(N+2)*(1-1/K).

Теперь посмотрим, что получается с операторами distribution. Каждый узел теперь имеет K копий, реализуемых на K разных модулях. Здесь K=(N/d)2, причем в каждую копию поступает кусок столбца и кусок строки (каждый длины d). Суммирующие узлы распределены так же (той же функцией от i и j), откуда следует, что токены - произведения посылаются локально в своем модуле. Следовательно, пересылок произведений теперь нет вовсе, а пересылок исходных элементов теперь несколько больше -  . А в целом число пересылок между модулями сократилось в  раз (это верно при K>1, при K=1 межмодульные пересылки отсутствуют в обоих вариантах). При больших N и K это будет примерно d/2.

Этот пример показывает, что двойной групповой узел является мощным алгоритмическим инструментом, имеющем встроенную эффективно распараллеливаемую реализацию. Его удобно использовать всегда, когда нужно выполнить некоторое действие логически единовременно для всех пар элементов двух массивов. Но без управляемого распределения нельзя было и подумать о его параллельном исполнении. Теперь мы видим, что параллельная реализация есть и очень эффективна. Настолько, что трудно представить себе что-либо более эффективное.

Заключение

В DFL введен (псевдо-)оператор управления распределением - distribution. Его использование может значительно сокращать затраты на коммуникацию за счет того, что большинство часть пересылок становятся близкими. При этом вычисления выполняются распределенно, а значит параллельно. И что особенно важно - это управление выполняется как бы «поверх» существующей и правильно работающей программы. И правильное распределение не нарушает правильности программы.

Для обычных узлов эффект достигается за счет более рационального распределения, учитывающего метрику алгоритма. А вот для групповых узлов появляется принципиально новое качество: если раньше он принципиально мог находиться и выполняться только в одном модуле, то теперь он становится расщепленным (распределенным) и работающим параллельно во многих модулях. И если раньше он считался просто удобным и мощным средством программирования, то теперь к этим достоинствам добавляется еще и эффективность (потенциальная распараллеливаемость).

Еще один новый полезный эффект - виртуализация и/или расширение адресного пространства. С одной стороны, теперь разные задачи или разные части одной задачи могут идти параллельно, даже если они используют одни и те же ключи, при условии, что они распределены на непересекающиеся множества модулей. А с другой стороны, поле номера модуля в токене теперь может рассматриваться как расширение виртуального адреса.

Направления дальнейшей работы

1. Мы здесь «расчистили дорогу» масштабированию системы в направлении роста числа модулей и увеличения ее неоднородности, когда дальняя связь становится более дорогой. Для этого были введены средства управления распределением и локализацией вычислений, которые помогают большую часть связей сделать ближними. Но теперь, чтобы более эффективно использовать это новое качество, следует подумать о том, чтобы процесс, локализованный в одном модуле шел как можно быстрее и эффективнее. Особенно это касается фрагментов графов, вычисляющих скалярные формулы. В них обычно аргументы долго не ждут партнера, и потому для этой части работы будет полезен специальный небольшой, но быстрый кэш с адресным доступом. Он может быть проще, чем сопоставляющая память общего назначения, поскольку эти токены предназначаются для спаривания только с такими же другими с конкретными адресами и единичной кратностью. И здесь можно отказаться от сложной и медленной аппаратуры, поддерживающей более сложные формы сопоставления: групповые, кратные и т.п. Чтобы быть направленными в этот кэш, токены должны быть помечены особым образом как «быстрые». И кроме того, для таких «быстрых» токенов можно применить стратегию упреждающей подкачки программного кода: код программы узла выбирается (и закачивается в программный кэш) не после спаривания, а по приходу лишь одного, первого токена.

2. Задаваемая в операторе distribution формула должна вычисляться при отправке каждого токена. Это накладывает высокие требования на эффективность этого вычисления. Поэтому крайне желательно, чтобы данную формулу можно было вычислять специальным аппаратным механизмом, не останавливая полезной работы. С другой стороны, эта формула не должна быть слишком сложной: компилятор должен уметь проверить ее корректность, что особенно важно для двойных групповых узлов (условие «прямоугольности»). Поэтому надлежит выделить простой набор допустимых для использования функций и правил написания формулы, допускающих как требуемый анализ, так и эффективную (аппаратную) реализацию.

3. При расщеплении групповых узлов непонятно, что делать с кратностью групповых токенов. Если кратность бесконечна, то проблемы нет, просто каждая копия тоже должна иметь бесконечную кратность. Если же кратность конечная, то по смыслу надо как-то разделить ее между копиями, причем ровно так, как будут распределены встречные токены. В некоторых случаях это мог бы сделать компилятор, но для этого ему надо передать некоторую дополнительную информацию. В других случаях это может быть невозможно, и тогда компилятор должен выдавать предупреждение.

4. Мы можем говорить об описанном, как об управлении пространством. Но есть еще и другая проблема: разные части вычислительного графа могут значительно «разойтись по времени», что приведет к тому, что токены убежавших вперед частей будут часто подолгу висеть в ожидании парных токенов из отстающих частей, и как следствие - к переполнению или неэффективному использованию сопоставляющий памяти (в случае умножения матриц «времени» соответствует номер слоя k). Чтобы этого избежать нам нужны средства управления временем, в чем-то схожие с рассмотренными средствами управления пространством.

Экспериментальные результаты

В программную модель старой архитектуры были внесены следующие изменения:

  • ИУ и МАП’ы были сгруппированы «попарно» (образуя, тем самым, модули системы). Передача пар, сформированных в МАП, - только в «свое» ИУ. Передача токенов - через коммутатор.
  • Изменен способ моделирования коммутационной среды. В модели реализована возможность внесения пользователем в коммутационную среду неоднородности. Для этой цели задается квадратная матрица nxn, где n - число модулей. На пересечении i-той строки с j-тым столбцом указывается время передачи токена из i-того модуля в j-тый (в условных «тактах»).
  • В модель введены необходимые средства для имитации аппаратного выполнения функций распределения, с возможностью их настройки под задачу.

Приведем здесь некоторые из полученных результатов моделирования на программной модели.

Моделировалось выполнение задачи «Умножение матриц». Размерность матрицы: 128x128, конфигурация системы - 128 модулей.

Эксперимент 1.

Сначала мы ставим систему в «идеальные» условия, когда коммутационная среда однородна и время любой передачи токена равно 1-му такту. Распределение вычислений по модулям - при помощи хеш-функции. Другими словами, мы моделируем прохождение задачи «Умножение матриц» примерно так, как это делалось и раньше. Результат: время счета - 548039 тактов, загрузка исполнительных устройств - 96,1%.

Эксперимент 2.

Вносим в коммутационную среду неоднородность следующим образом:

Приведенный выше рисунок - это условное изображение некоторой аппаратной иерархии, порождающей неоднородность коммутационной среды. В данном эксперименте не существенно, имеем ли мы 8 плат, каждая с 4-мя чипами, в каждом из которых размещено 4 модуля, или же - одну большую плату с восемью чипами, в каждом из которых есть своя внутренняя иерархия и размещено по 16 модулей и т.п. Для эксперимента существенным является только сам характер внесенной неоднородности.

Моделируем прохождение задачи «Умножение матриц» по-прежнему с использованием хеш-функции.

На диаграмме показана статистика распределения токенов по возможным 4-м временам передачи этих токенов. Внутри модуля передается только 0,08% от всего количества посланных токенов. Преобладают пересылки между модулями, причем на наиболее дальние расстояния. Система, явно не справляется с большими задержками, возникающими при посылке токенов, на что указывает увеличение времени счета примерно в 3 раза по сравнению с «идеальным» случаем и уменьшение загрузки ИУ до 36%.

Эксперимент 3.

Этот эксперимент отличается от предыдущего тем, что вместо хеш-функции используется функция распределения, названная "Distribution_Zip".

Из диаграммы видно, что подавляющее большинство (95%) пересылок токенов происходило внутри модулей. Это означает, что функция распределения "Distribution_Zip" очень хорошо выделяет локальность в данной задаче и при отображении виртуального вычислительного пространства задачи в физическое пространство сохраняет локальность способом, близким к оптимальному. Время счета (548552 такта) и загрузка ИУ (96%) оказались практически теми же, что и в «идеальном» случае (548039 тактов и 96,1%).

Ссылки

  1. Бурцев В.С. Система массового параллелизма с автоматическим распределением аппаратных средств суперЭВМ в процессе решения задачи // Cб. Вычислительные машины с нетрадиционной архитектурой. СуперЭВМ. - Вып. 2. - М.: ВЦКП РАН, 1994. - С.3-37.
  2. Dally,W. et al, Merrimac: Supercomputing with streams. http://merrimac.stanford.edu/publications/sc03_merrimac.pdf
  3. А.В. Климов, А.С. Окунев, А.М. Степанов «Распределение вычислений по модулям в вычислительной системе массового параллелизма» (в печати).
  4. А.В. Климов, А.С. Окунев, А.М. Степанов «Проблемы развития модели вычислений dataflow и особенности ее архитектурной реализации».(в печати).
  5. Степанов А.М. Отчет по экспериментальному программированию (отчет ИПИ РАН).
  6. Da Silva, J.G.D., Watson,I. 1983. Pseudo-associative store with hardware hashing. IEEE Proceedings, Pt E 130, 1, 19-24
  7. Dennis J., Data Flow Supercomputers // Computer. - Vol.13. - No.11. Nov, 1980. - P.48-56
  8. Charles Koelbel, High Performance Fortran in Practice. http://www.science.unitn.it/~iori/f90/hpf-tutorial.html

 

© 1948—2016 «ИТМиВТ»
Версия для печати Контактная информация