Новосибирский государственный университет Факультет информационных технологий

Словарь терминов в коллекции "Вычислительные системы"

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

Статические потоковые вычислительные системы - системы, в которых каждый вычислительный узел представлен в единственном экземпляре, число узлов и число токенов, циркулирующих в системе заранее известно. Граф потока данных представляется здесь набором заранее подготовленных команд, содержащих код операции, поля для хранения поступающих операндов и поля адресов назначения, по которым должен быть отправлен вырабатываемый командой результат. Таким образом, каждая дуга графа может содержать одновременно не более одного токена. Примером реализации статической архитектуры является потоковый компьютер Денниса MIT Static Dataflow Machine, созданный в Массачусетском технологическом институте.

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

Токен в статической потоковой системе представляет собой триаду: <v, <f, n>, а>, где v - это данные, переносимые токеном, f - идентификатор функции, реализуемой текущим потоковым графом, n - номер целевой вершины, куда должен поступить данный токен, и, наконец, a - это номер дуги, по которой токен должен быть направлен к целевой вершине. Поле <f, n> называют тегом, оно определяет предназначение токена определенной вершине.

Для указания вершине о том, что ее выходной токен уже востребован последующей вершиной (вершинами) графа, в ВС обычно прибегают к механизму подтверждения с квитированием связи.

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

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

В качестве примеров статических потоковых ВС можно упомянуть: LAU System, TI's Distributed Data Processor, DDMI Utah Data Driven Machine, NEC Image Pipelined Processor, Hughes Dataflow Multiprocessor .

Литература
• Dennis J.B., Misunas D.P. A preliminary architecture for a basic data-flow processor // ISCA '75 Proceedings of the 2^nd Annual Symposium on Computer Architecture. - P. 126-132
• Dennis J.B. Dataflow Supercomputers // Computer. - 1980. - N 13. - P. 48-56.
• Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов / С.А. Орлов, Б.Я. Цилькер. - СПб.: Питер, 2011. - 688 с.

Ключевые термины, связанные с термином "статические потоковые вычислительные системы":

1. Динамические потоковые вычислительные системы
2. Потоковые вычислительные системы

Ключевые термины:  потоковые вычислительные системы;   управление от потока данных;

Контекстный поиск: Задайте образец для поиска:
    

Федотова Ольга

НГУ ФИТ НГУ ИВТ СО РАН