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

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

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

Динамические потоковые вычислительные системы - системы, в которых каждый узел может иметь множество экземпляров. Для того, чтобы различать токены, адресованные в разные экземпляры одного узла, в структуру токена вводится дополнительное поле - контекст, называемый «цветом значения». По сравнению со статической архитектурой появляется возможность параллельного исполнения различных итераций цикла. Одной из первых реализаций динамической потоковой архитектуры была система Manchester Dataflow Machine, созданная в 1980 году.

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

Архитектура потоковых систем с помеченными токенами

Системы с помеченными токенами (tagged-token architecture) в известной мере свободны от основного недостатка статической модели. В них число токенов, одновременно присутствующих на дуге, не ограничивается. Это открывает возможность выполнения итераций в произвольной последовательности, но требует учета принадлежности токенов к одной и той же итерации. С этой целью токен должен содержать информацию о вычислительном контексте, в котором он используется, например о номере итерации цикла. Этот контекст называют «цветом значения», а токен соответственно называют «окрашенным», в силу чего метод имеет еще одно называние - метод окрашенных токенов.

В модели с помеченными токенами структура токена сложнее, чем в статической модели: <v, <f, n, c, i>, a>, где c определяет фрагмент кода или тело цикла в составе реализуемой функции f, а i (индекс) представляет цвет токена. Каждая дуга потокового графа может рассматриваться как вместилище, способное содержать произвольное число токенов с различными тегами. Правило активирования вершины в модели с помеченными токенами имеет вид: вершина активируется, когда на всех ее входных дугах присутствуют токены с идентичным цветом.

Для обнаружения одинаково окрашенных токенов (токенов с одинаковы¬ми тегами) в процессорный элемент введен согласующий блок. Этот блок получает очередной токен из очереди токенов и проверяет, нет ли в памяти согласования его партнера (токена с идентичным тегом). Если такой партнер не обнаружен, принятый токен заносится в память согласования. Если же токен-партнер уже хранится в памяти согласования, то согласующий блок удаляет его оттуда и направляет оба токена с совпавшими тегами в блок выборки. На основе общего тега блок выборки находит в памяти команд/данных соответствующую команду и формирует пакет операции, который затем направляет в функциональный блок. Функциональный блок выполняет операцию, создает токены результата и помещает их в очередь токенов.

Примеры динамических потоковых вычислительных систем с архитектурой окрашенных токенов: система Гурда и Ватсона, созданная в Манчестерском университете в 1980 году, системы SIGMA-1, NTT's Dataflow Processor Array System, DDDP Distributed Data Driven Processor, SDFA Stateless Data-Flow Architecture.

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

В последнее время все более популярной становится другая организация динамической потоковой ВС, позволяющая освободиться от ассоциативной памяти и известная как архитектура с явно адресуемыми токенами.

Архитектура потоковых систем с явно адресуемыми токенами

Значительным шагом в архитектуре потоковых ВС стало изобретение механизма явной адресации токенов (explicit token-store), имеющего и другое название - непосредственное согласование (direct matching). В основе этого механизма лежит наблюдение: все токены в одной и той же итерации цикла и в одном и том же вхождении в реентерабельную процедуру имеют идентичный тег (цвет). При инициализации очередной итерации цикла или очередном обращении к процедуре формируется так называемый кадр токенов, содержащий токены, относящиеся к данной итерации или данному обращению, то есть токены с одинаковыми тегами. Использование конкретных ячеек внутри кадра задается на этапе компиляции. Каждому кадру выделяется отдельная область в специальной памяти кадров (frame memory), причем раздача памяти под каждый кадр происходит уже на этапе выполнения программы.

В схеме с явной адресацией токенов любое вычисление полностью описывается указателем команды (IP, Instruction Pointer) и указателем кадра (FP, Frame Pointer). Токен выглядит следующим образом: <v, <FP,IP>>.

Команды, реализующие потоковый граф, хранятся в памяти команд и имеют формат: орс•i•dis. Здесь i (индекс в памяти кадров) определяет положение ячейки с нужным токеном внутри кадра, то есть какое число нужно добавить к FP, чтобы получить адрес интересующего токена. Поле dis указывает на местоположение команды, которой должен быть передан результат обработки данного токена. Адрес в этом поле также задан в виде смещения - числа, которое следует прибавить к текущему значению IP, чтобы получить исполнительный адрес команды назначенияв памяти команд. Если потребителей токена несколько, в поле dis заносится несколько значений смещения.

Каждому слову в памяти кадров придан бит наличия, единичное значение которого удостоверяет, что в ячейке находится токен, ждущий согласования, то есть что одно из искомых значений операндов уже имеется. Как и в архитектуре с окрашенными токенами, определено, что вершины могут иметь максимум две входных дуги. Когда на входную дугу вершины поступает токен <v1, <FP,IP>>, в ячейке памяти кадров с адресом FP+(IP.i) проверяется бит наличия (здесь IP.i означает содержимое поля i в команде, хранящейся по адресу, указанному в IP). Если бит наличия сброшен (ни один из пары токенов еще не поступал), поле значения пришедшего токена (v1) заносится в анализируемую ячейку памяти кадров, а бит наличия в этой ячейке устанавливается в единицу, фиксируя факт, что первый токен из пары уже доступен.
Если токен <v2,<FR,IP>> приходит в вершину, для которой уже хранится значение v1, команда, представляющая данную вершину, может быть активирована и выполнена с операндами v1 и v2. В этот момент значение v1 извлекается из памяти кадров, бит наличия сбрасывается, и на функциональный блок, предназначенный для выполнения операции, передается пакет команды <v1,v2, FP, IP, IP.opc, IP.dis>, содержащий операнды (v1 и v2), код операции (IP.opc) и адресат ее результата (IP. dis). Входящие в этот пакет значения FP и IP нужны, чтобы вместе с IP.dis вычислить исполнительный адрес адресата. После выполнения операции функциональный блок пересылает результат в блок формирования токенов.

Функция согласования токенов стала достаточно короткой операцией, что позволяет внедрить ее в виде нескольких ступеней процессорного конвейера.

Литература
• Gurd J.R. The Manchester dataflow machine // Future Generations Computer Systems 1, 1985. - P. 201-212.
• Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов / С.А. Орлов, Б.Я. Цилькер. - СПб.: Питер, 2011. - 688 с.

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

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

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

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

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

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