Лекция 14. Потоковые и редукционные вычислительные системы.

План лекции.

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

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

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

4. Динамические потоковые вычислительные системы.

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

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

7. Макропотоковые вычислительные системы.

8. Гиперпотоковая обработка.

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

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

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

• команда выполняется после того, как выполнена предшествующая ей ко-манда последовательности;

• команда выполняется, когда становятся доступны ее операнды;

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

Первый метод соответствует традиционному механизму с управлением по-следовательностью команд; второй механизм известен как управляемый данными(datadriven) илипотоковый(dataflow); третий метод называется механизмомуправления по запросу(demanddriven).

Рис. 14.1. Возможные вычислительные модели: а– фон-неймановская;б– потоковая;в– макропотоковая;г– редукционная

Общие идеи нетрадиционных подходов к организации вычислительного процесса показаны на рис. 14.1.

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

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

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

Рис. 14.2. Граф потоков данных для выражения A / B + B  C

На рис. 14.2 показан простой потоковый граф для вычисления выражения f=A/B + B  C. Входами служат переменныеA,B, иC, изображенные вверху гра-фа. Дуги между вершинами показывают тракты узловых операций. Направление вычислений – сверху вниз. Используются три вычислительные операции: сло-жение, умножение и деление. Вершина «Копирование» предназначена для фор-мирования дополнительной копии переменнойB, так как она требуется в двух узлах.

Данные (операнды, результаты), перемещаемые вдоль дуг, содержатся в опознавательных информационных кадрах, маркерах специального формата – «токенах» (иначе «фишках» или маркерах доступа). Рис. 14.3 иллюстрирует дви-жение токенов между узлами. После поступления на граф входной информации маркер, содержащий значениеA, направляется в вершину деления; токен с пере-меннойB– в вершину копирования; токен с переменнойC– в вершину умно-жения. Активирована может быть только вершина «Копирование», поскольку у нее лишь один вход и на нем уже присутствует токен. Когда токены из вер- шины «Копирование» будут готовы, узлы умножения и деления также получат все необходимые маркеры доступа и могут быть инициированы. Последняя вершина ждет завершения операций умножения и деления, то есть когда на ее входе появятся все необходимые токены.

2.

Рис. 14.3. Движение маркеров при вычисленииA / B + B  C: а – после подачи входных данных; б – после копирования; в – после умножения и деления; г – после суммирования

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

Рис. 14.4. Примитивы узлов: а– двухвходовая операционная вершина;б– одновходовая операционная вершина;в– вершина ветвления;г– вершина слияния;д–TF-коммутатор;е–T-коммутатор;ж–F-коммутатор;з– вентиль;и– арбитр

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

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

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

• вершина слияния– узел с двумя входами и одним выходом. Данные по-ступают только с какого-нибудь одного из двух входов. Входные данные без изменения подаются на выход. Комбинируя такие узлы, можно стро- ить вершины слияния сm входами;

• вершина управления– существует в перечисленных ниже трех вариантах:

• TF-коммутатор– узел с двумя входами и одним выходом. Верхний вход – это дуга данных, а правый – дуга управления (логические дан-ные). Если значение правого входа истинно (T–True), то входные дан-ные выводятся через левый выход, а при ложном значении на правом входе (F–False) данные следуют через правый выход;

• вентиль – узел с двумя входами и одним выходом. Верхний вход – дуга данных, а правый – дуга управления. При истинном значении на входе управления данные выводятся через выходную дугу;

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

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

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

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

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