Файл: 551-668.pdf

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

Рис. 15.3. Движение маркеров при вычислении А/В + В х С: а — после подачи входных данных;

б — после копирования;

 в

 — после умножения и деления; г — после суммирования

-двухвходовая операционная вершина

 — узел с двумя входами и одним выходом.

Операции производятся над данными, поступающими с левой и правой вход-
ных дуг, а результат выводится через выходную дугу;

- одновходовая операционная вершина —

 узел с одним входом и одним выходом.

Операции выполняются над входными данными, результат выводится через
выходное ребро;

- вершина ветвления —

 узел с одним входом и двумя выходами. Осуществляет

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

 т

 выходов;

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

Рис. 15.4. Примитивы узлов:

 а —

 двухвходовая операционная вершина;

 б —

 одновходовая

операционная вершина;

 в

 — вершина ветвления; г— вершина слияния; д — TF-коммутатор;

е — Т-коммутатор; ж — F-коммутатор;

 з —

 вентиль;

 и

 — арбитр

-

 вершина слияния —

 узел с двумя входами и одним выходом. Данные поступают

только с какого-нибудь одного из двух входов. Входные данные без изменения

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

с

 т

 входами;

- вершина управления

 — существует в перечисленных ниже трех вариантах:

- TF

-коммутатор —

 узел с двумя входами и одним выходом. Верхний вход —

это дуга данных, а правый — дуга управления (логические данные). Если

значение правого входа истинно (Т — True), то входные данные выводятся
через левый выход, а при ложном значении на правом входе (F — False) дан-

ные следуют через правый выход;

D

 вентиль —

 узел с двумя входами и одним выходом. Верхний вход — дуга дан-

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

ления данные выводятся через выходную дугу;

-

 арбитр —

 узел с двумя входами и двумя выходами. Все дуги являются дуга-

ми данных. Первые поступившие от двух входов данные следуют через ле-
вую дугу, а прибывшие впоследствии — через правую выходную дугу. Акти-
вация вершины происходит в момент прихода данных с какого-либо одного

входа.

Процесс обработки может выполняться аналогично конвейерному режиму: пос-

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

довательности использования входов.

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

вторяться

 с

 различными данными, особенно в программных циклах. Программ-

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

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

после каждого прохода тела цикла. Последний завершается, когда переменная цикла

достигает определенного значения. Метод применим и при потоковой обработке,

как это показано на рис. 15.5.

Рис. 15.5. Циклы при потоковой обработке

Все известные потоковые вычислительные системы могут быть отнесены к двум

основным типам:

 статическим

 и

 динамическим.

 В свою очередь, динамические

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

 архитектуре с поме-

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

 и

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

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

В потоковых ВС программа вычислений соответствует потоковому графу, кото-

рый хранится в памяти системы в виде таблицы. На рис. 15.6 показаны пример
графа потоковой программы и содержание адекватной ему таблицы [2].

Принципиальная схема потоковой вычислительной системы (рис. 15.7) вклю-

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

Блоки CS и FS работают асинхронно и параллельно, обмениваясь многочислен-

ными

 пакетами команд

 и результатами их выполнения. В

 пакете результата,

 по-

ступающем из блока FS, содержится значение результата (val) и адрес команды,

для которой пакет предназначен (des). На основании этого адреса блок CS проверяет

возможность обработки команды. Команда может быть однооперандной или

двухоперандной. В последнем случае необходимо подтверждение наличия обоих

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

Рис. 15.6. Пример формы хранения потоковой программы: а — потоковый граф;

б

 — память функционального блока

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

операндов (орг 1 и орг 2), и для этого устанавливается специальный признак. Блок
управления загрузкой (LC) каждый раз при активировании определенной функ-
ции загружает из памяти программ код этой функции.

Для повышения степени параллелизма блоки CS и F5 строятся по модульному

принципу, а графы потоковой программы распределяются между модулями с по-

мощью мультиплексирования [89].

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

Статические потоковые вычислительные системы

Статическая потоковая архитектура,

 известная также под названием «единствен-

ный-токен-на-дугу» (single-token-рег-агс dataflow), была предложена Деннисом

в 1975 году [89]. В ней допускается присутствие на ребре графа не более чем одного
токена. Это выражается в правиле активации узла [90]: вершина активируется, когда
на всех ее входных дугах присутствует по токену и ни на одном из ее выходов токенов
нет. Для указания вершине о том, что ее выходной токен уже востребован последую-
щим узлом (узлами) графа, в ВС обычно прибегают к механизму подтверждения с
квитированием связи, как это показано на рис. 15.8. Здесь процессорами в ответ на
инициирование узлов графа посылаются специальные контрольные токены.

Рис. 15.8. Механизм подтверждения с квитированием

Типовую статическую потоковую архитектуру иллюстрирует рис. 15.9.

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

Память действий

 (узел потоковой машины, хранящий потоковый граф и цир-

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

- код операции;
- операнд 1;