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

Статическая потоковая архитектура, известная также под названием «единственный-токен-на-дугу» (single-token-per-arc dataflow), была предложена Деннисом в 1975 году. В ней допускается присутствие на ребре графа не бо- лее чем одного токена. Это выражается в правиле активации узла: вершина активируется, когда на всех ее входных дугах присутствует по токену и ни на одном из ее выходов токенов нет. Для указания вершине о том, что ее выход- ной токен уже востребован последующим узлом графа, используется механизм подтверждения с квитированием связи (рис. 14.8). Его суть состоит в посылке процессорами в ответ на инициирование узлов графа специальных контроль- ных токенов.

Рис. 14.8. Механизм подтверждения с квитированием

Типовая статическая потоковая архитектура представлена на рис. 14.9.

Рис. 14.9. Структура процессорного элемента типовой статической потоковой системы

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

§ код операции;

§ операнд 1;

§ …

§ операнд N;

§ вершина/дуга 1;

§ …

§ вершина/дуга K.

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

Основное преимущество статической модели потоковых вычислений за-ключается в упрощенном механизме обнаружения активированных узлов.

Недостатки статической модели:

§ не допускает параллельного выполнения независимых итераций цикла;

§ колебания трафика токенов;

§ отсутствие в современных языках программирования поддержки описан-ного режима обработки данных.

Архитектуру первой системы, строго соответствующей модели потоковых вычислений типа «единственный-токен-на-дугу», предложил Деннис (рис. 14.10).

Рис. 14.10. Статическая потоковая архитектура по Деннису

Система представляет собой кольцо из процессорных элементов и эле-ментов памяти, в котором информация передается в форме пакетов. Процес-сорные элементы получают пакеты действий (activity templates) в виде: Код операции • Операнды • Адресат, где точка обозначает операцию составления целого слова из его частей. «Код операции» определяет подлежащую выполне-нию операцию, «Операнды» – используемые в операции числа, а «Адресат» – указывает место, куда должен быть направлен результат операции. При этом в полях операндов задаются не адреса ячеек памяти, а непосредственно числа, которые должны участвовать в операции. Преимущество такого подхода состо- ит в том, что в каждый момент времени операнды могут быть использованы только одной выбранной вершиной, а недостаток – невозможность включения в команду в качестве операндов сложных структур данных, даже простых векторов и массивов.

Пакет результата имеет вид: Значение • Адресат, где в поле «Значение» содержится значение результата, полученное после выполнения операции. Эти пакеты передаются по маршрутизирующей сети в ячейки команды блока па- мяти, указанные в их поле «Адресат». Когда получены все входные пакеты (токены), ячейка команды порождает пакет операции. Обычно для генерации пакета операции ячейке команды нужны два входных пакета с операндами. За- тем пакет операции маршрутизируется к одному из процессорных элементов (ПЭ). Если все процессорные элементы идентичны (гомогенная система), то может быть выбран любой свободный ПЭ. В негомогенных системах со спе-циализированными ПЭ, способными выполнять только определенные функции, выбор нужного ПЭ производится по коду операции, заключенном в пакете операции.

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