Новосибирский государственный университетФакультет информационных технологий |
А.М.Федотов |
Механизм управления вычислениями, где выполнение операции инициируется приходом необходимых для ее исполнения данных, известен, как управляемый данными (Data Driven) или потоковый (Dataflow).
Идеология вычислений, управляемых потоком данных (потоковой обработки), была разработана в 60-х годах Карпом и Миллером. В начале 70-х годов Деннис, а позже и другие начали разрабатывать компьютерные архитектуры, основанные на вычислительной модели с управлением от потока данных.
В потоковой вычислительной модели (Data Driven) команда выполняется, когда становятся доступными ее операнды.
В отличие от Control Flow в Dataflow архитектурах отсутствует понятие «последовательность инструкций», нет счетчика команд, отсутствует даже адресуемая память в привычном смысле. Программа в потоковой системе - это не набор команд, а ориентированный граф, иногда называемый графом потоков данных (dataflow graph). Этот граф состоит из вершин (узлов), отображающих операции, и ребер или дуг, показывающих потоки данных между теми вершинами графа, которые они соединяют.
Операция в вершине выполняется лишь когда по дугам в нее поступила вся необходимая информация. Обычно такая операция требует одного или двух операндов, а для условных операций необходимо наличие входного логического значения. Операция формирует один, два или один из двух возможных результатов. Таким образом, у каждой вершины может быть от одной до трех входящих дуг и одна или две выходящих. После активации вершины и выполнения операции результат передается по дуге к ожидающей вершине. Процесс повторяется, пока не будут активированы все вершины и получен окончательный результат. Одновременно могут быть активированы несколько вершин, при этом параллелизм в вычислительной модели выявляется автоматически.
Направление вычислений - сверху вниз.
Данные (операнды/результаты), перемещаемые вдоль дуг, содержатся в опознавательных информационных кадрах, маркерах специального формата - токенах (иначе фишках или маркерах доступа).
Практические вычисления требуют некоторых дополнительных возможностей, например, при выполнении команд условного перехода. По этой причине в потоковых графах предусмотрены вершины-примитивы нескольких типов:
Основная:
Ключевые термины (головные): Архитектура вычислительной машины; Потоковые вычислительные системы; Control Flow;
Федотов Анатолий Михайлович |
НГУ ФИТ НГУ ИВТ СО РАН |