Принцип потоковой обработки

Граф потока данных. Программа представляется направленным графом потока данных (см. рис. 20.2), при этом:

  • вершины графа соответствуют командам (инструкциям, операциям);
  • дуги графа указывают на связь между командами.

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

На рис. 20.2 показан граф потока данных, управляющих решением квадратного уравнения. Прирешение уравнения имеет следующий вид:.

В исходном состоянии готовы все входные данные: а, b, с, 2. Вершины графа активизируются в произвольном порядке по мере готов-

Граф потока данных

Рис. 20.2. Граф потока данных

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

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

 
< Пред   СОДЕРЖАНИЕ     След >