Файл: 551-668.pdf

. Вычислительные системы с управлением вычислениями от потока данных  6 2 1

-

 операнд

N;

- вершина/дуга 1;

- ...

-

 вершина/дуга К.

Каждому кадру в памяти команд/данных соответствует кадр в управляющей

памяти, содержащий биты наличия для всех операндов и всех полей «вершина/

дуга». Бит наличия операнда устанавливается в единицу, если этот операнд досту-

пен, то есть если токен, содержащий данный операнд, уже поступил по входной

дуге графа. Для поля «вершина/дуга» установленный бит наличия означает, что

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

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

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

обновления, который в соответствии с полученным результатом изменяет содер-

жимое памяти действий.

Основное преимущество рассматриваемой модели потоковых вычислений за-

ключается в упрощенном механизме обнаружения активированных узлов. К со-

жалению, статическая модель обладает множеством серьезных недостатков [55].

Во-первых, данный механизм не допускает параллельного выполнения независи-
мых итераций цикла. Другой нежелательный эффект — колебания трафика токе-
нов. Наконец, в современных языках программирования отсутствует поддержка
описанного режима обработки данных. Несмотря на это, несколько образцов ста-

тических ВС все-таки были созданы или, по крайней мере, спроектированы.

Архитектуру первой системы, строго соответствующей модели потоковых вы-

числений типа «единственный-токен-на-дугу», предложил Деннис (рис. 15.10).

. По изначальной идее, система представляла собой кольцо из процессорных эле-

ментов и элементов памяти, в котором информация передается в форме пакетов.

Рис. 15.10. Статическая потоковая архитектура по Деннису

0 2 2 Глава 15. Потоковые и редукционные вычислительные системы

Процессорные элементы должны были получать так называемые

 пакеты действий

(activity templates) в виде: Код операции • Операнды • Адресат. Здесь точка обозна-

чает операцию составления целого слова из его частей, «Код операции» определя-
ет подлежащую выполнению операцию, «Операнды» — используемые в операции
числа, а «Адресат» — указывает место, куда должен быть направлен результат опе-
рации. Отметим, что в полях операндов задаются не адреса ячеек памяти, а непо-
средственно числа, которые должны участвовать в операции. Это имеет свои пре-

имущества и недостатки. Первое состоит в том, что в каждый момент времени

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

Пакет результата

 имеет вид: Значение • Адресат, где в поле «Значение» содер-

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

 ячейки команды

 блока

памяти, а именно в указанные в их поле «Адресат». Когда получены все входные

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

Затем пакет операции маршрутизируется к одному из процессорных элементов
(ПЭ). Если все процессорные элементы идентичны (гомогенная система), может

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

В несколько усовершенствованном варианте рассмотренная ВС была спроек-

тирована под руководством того же Денниса в Массачусетсском технологическом

институте (MIT). Система состояла из пяти основных подсистем: секции памяти,

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

В качестве других примеров статических потоковых ВС можно упомянуть: LAU

System [80,81], TI's Distributed Data Processor [82], DDMI Utah Data Driven Ma-

chine [85], NEC Image Pipelined Processor [73], Hughes Dataflow Multiprocessor [218].

Динамические потоковые

вычислительные системы

Производительность потоковых систем существенно возрастает, если они в состо-

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

 реентерабельные про-

цедуры,

 когда в памяти хранится только одна копия кода процедуры, но эта копия

является повторно входимой (реентерабельной). Это означает, что к процедуре

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

обеспечения дополнительного уровня параллелизма решается в динамических по-

Вычислительные системы с управлением вычислениями от потока дaнных  6 2 3

токовых ВС и реализуется двумя вариантами архитектуры потоковой ВС:

 архи-

тектуры с помеченными токенами

 и

 архитектуры с явно адресуемыми токенами.

Архитектура потоковых систем с помеченными токенами

В архитектуре с помеченными токенами (tagged-token architecture) память хра-
нит один экземпляр потокового графа. Каждый токен содержит

 тег

 (фишку), со-

стоящий из адреса команды, для которой предназначено заключенное в токене
значение, и другой информации, определяющей вычислительный контекст, в ко-
тором данное значение используется, например номера итерации цикла. Этот кон-
текст называют «цветом значения», а токен соответственно называют «окрашен-
ным»-, в силу чего метод имеет еще одно название —

 метод окрашенных токенов.

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

 вершина

активируется, когда на всех ее входных дугах присутствуют токены с идентичны-

ми тегами.

Типовая архитектура потоковой системы с помеченными токенами показана

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

Рис.  1 5 . 1 1 . Структура процессорного элемента типовой потоковой системы

с помеченными токенами

6 2 4 Глава 15. Потоковые и редукционные вычислительные системы

Чтобы учесть возможные ситуации — циклы, элементы массивов, функции и

рекурсии, — тег каждого токена должен включать в себя три поля: Уровень итера-

ции • Имя функции• Индекс.

В каждом поле может содержаться число, начиная с нуля. Поле «Уровень ите-

рации» хранит порядковый номер текущей итерации цикла; поле «Имя функции»
идентифицирует вызов функции; поле «Индекс» указывает на определенный эле-
мент массива. Первые два поля могут быть объединены в одно.

Индивидуальные поля тега трактуются как числовые значения, пересылаемые

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

еся в каждом поле, или установить в любом поле иное значение. Например, опера-

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

с входным, за исключением указанного поля, куда заносится значение, заданное

в данной операции в виде литерала. Применительно к полю «Уровень итерации»
могут быть предусмотрены операции инкремента и декремента.

Рис. 15.12. Архитектура манчестерской потоковой вычислительной системы

На рис. 15.12 приведена структура динамической потоковой ВС с архитекту-

рой окрашенных токенов, созданной в Манчестерском университете Гурдом и Ват-
соном в 1980 году [114]. В этой ВС используется конвейерная кольцевая архитек-
тура, и вычислительные функции отделены от функций согласования токенов
и тегов. Каждый процессор обрабатывает пакеты длиной в 166 бит, содержащие

два численных операнда, тег, код операции и один или два адреса следующей ко-

манды или команд. С каждым пакетом ассоциирован флаг «Система/Вычисление»-,
позволяющий отличить выполняемый пакет (пакет, который должен быть обра-

ботан процессором) и пакет, несущий системное сообщение, такое, например, как

«Загрузить команду в память». Численными операндами могут быть 32-разряд-

ные целые числа, либо числа в формате с плавающей запятой.

Обработав выполняемый пакет, процессор генерирует один или два пакета (то-

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

Вычислительные системы с управлением вычислениями от потока данных  6 2 5

результата поступает на ключ, обеспечивающий либо ввод данных от внешнего

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

жащую узловые команды, и формируется полный выполняемый пакет. Выполня-

емые пакеты по возможности направляются в свободный процессор в массиве из

15 процессоров!

В качестве других примеров динамических потоковых вычислительных сис-

тем следует упомянуть: SIGMA-1 [ 123,124], PATTSY Processor Array Tagged-Token

System [171], NTT's Dataflow Processor Array System [206], DDDP Distributed Data
Driven Processor [143], SDFA Stateless Data-Flow Architecture [198].

Основное преимущество динамических потоковых систем — это более высо-

кая производительность, достигаемая за счет допуска присутствия на дуге множе-

ства токенов. При этом, однако, основной проблемой становится эффективная

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

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

вило, достаточно велико. По этой причине в большинстве вычислительных систем

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

производится с привлечением хэширования, что несколько снижает быстродей-

ствие.

В последнее время все более популярной становится другая организация дина-

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

Архитектура потоковых систем

с явно адресуемыми токенами

Значительным шагом в архитектуре потоковых ВС стало изобретение механизма

явной адресации токенов

 (explicit token-store), имеющего и другое название —

 не-

посредственное согласование

 (direct matching). В основе этого механизма лежит

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