1.6.Потоковая (data flow) архитектура
Большинство современных вычислительных машин, будь то суперкомпьютер Fujitsu K, обычный персональный компьютер или даже калькулятор, объединяет общий принцип работы, а именно модель вычислений, основанная на потоке управления (control flow). Однако, эта модель не является единственно возможной. В некотором роде ее противоположностью является модель вычислений, управляемая потоком данных.
Потоковая (data flow) обработка информации и соответствующие способы организации процесса вычислений известны уже около 50 лет (первая работа, [1]). Ее важнейшие принципы – это:
-
асинхронность вычислений, позволяющая выполнять операции сразу же при готовности операндов;
-
функциональный характер вычислений, обеспечивающий отсутствие побочных эффектов.
-
отсутствие счетчика команд и общей переиспользуемой памяти, препятствующих параллельному выполнению программ.
Усилия исследователей в прошедшие десятилетия были сосредоточены в основном на следующих направлениях:
-
создание адекватной математической модели вычислений;
-
разработка архитектур, реализующих эти модели;
-
поддержка процесса вычислений на уровне языков программирования.
Известны две основные модели вычислений. Более раннюю можно назвать «чистым потоком данных». Программа в этих моделях имеет вид ориентированного графа, состоящего из именованных узлов (соответствующих командам) и дуг, задающих зависимости по данным между командами. Данные циркулируют вдоль дуг в форме токенов (tokens), состоящих из значения и тега. Известны две основные разновидности потоковых компьютеров, основанных на модели «чистого потока данных»:
-
статические;
-
динамические.
В статических моделях вычисления граф потока данных (data flow graph) представляется набором заготовок команд, содержащих код операции, поля для хранения поступающих операндов и поля адресов назначения, по которым должен быть отправлен вырабатываемый командой результат. Таким образом, каждая дуга графа может содержать одновременно не более одного токена. Выходные дуги вершин графа не должны содержать выработанный, но еще не потребленный другой вершиной результат. Вследствие этого необходимо введение подтверждающих сигналов, распространяющихся вдоль дополнительно введенных дуг в направлении, противоположном движению токенов.
Среди проектов статических потоковых можно назвать машину Д. Денниса (Jack Dennis), реализованную в Массачусетском технологическом институте (MIT, США) [2-5], системы LAU (Тулуза, Франция) [6, 7], DDP (Distributed Data Processor) фирмы Texas Instruments (США) [8], DDM1 (Data Driven Machine), построенную в Университете штата Юта (США), а также первый потоковый микропроцессор uPD7281 фирмы NEC Electronics (Япония), предназначенный для обработки изображений [10].
Статическая модель принципиально крайне проста, но при ее реализации возникает немало проблем, препятствующих эффективному использованию (фактическое удвоение объема циркулирующей в системе информации, невозможность реализации современных языковых концепций и др.). Практически в ней достижим только конвейерный эффект распараллеливания.
Динамическая модель потоковых вычислений явилась попыткой устранить эти проблемы. Она предполагает возможность параллельного исполнения различных итераций цикла концептуально это приводит к необходимости формирования в реентерабельном виде многих копий подграфов исходного графа потока данных. Однако такое копирование является сугубо виртуальным, поэтому возникает необходимость хранить в токенах дополнительную информацию контекст их использования (colour). Теперь каждая дуга графа может содержать множество токенов, и команда выполняется, как только становятся доступными все токены одного цвета.
Пусть необходимо произвести вычисления по формуле:
,
где x и y это некоторые ранее вычисленные значения, а a и b константы.
Слева на рис. 1.11 приведен фрагмент написанной на некотором автокоде программы, вычисляющей значение переменной z. Справа на рис. 1.11 показан соответствующий фрагмент графа потока данных. Если этот фрагмент требуется выполнять в цикле, то формула примет следующий вид:
,
то необходимо сопоставлять токены, относящиеся к одной итерации цикла.
Рис. 1.11. Фрагмент программы и граф потока данных
Такая модель была впервые разработана в Манчестерском университете (Англия) И. Ватсоном (I. Watson) и Д. Гурдом (J. Gurd) [11-13], и, независимо, в Калифорнийском университете (Ирвин, США) под руководством д-ра Арвинда (Arvind) [14, 15]. Известны и другие проекты динамических потоковых ВС [16-19] и др.
Основная проблема при создании динамических потоковых систем – разработка устройства, «собирающего» токены одного цвета, которое требует наличия ассоциативной памяти очень большого объема. Компромиссом являются различные виды хеширования, которые снижают потенциальную производительность.
Более поздние разработки стали все дальше отходить от «чистого потока данных», используя самые разные гибридные подходы. Именно сочетание свойств потоковой и последовательной обработки данных представляется многим экспертам одним из наиболее перспективных путей создания вычислительных систем сверхвысокой производительности [20]. Основной вопрос, который при этом требует решения выбор соотношения свойств потоковой и последовательной обработки в конкретном архитектурном воплощении. В частности архитектура, описанная А.Б. Барским и В.В. Шиловым в работе [21], представляет один из возможных ответов на него.
|
