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

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

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

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

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

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

Дата добавления: 2014-01-04