Новосибирский государственный университетФакультет информационных технологий |
А.М.Федотов |
Динамические потоковые вычислительные системы - системы, в которых каждый узел может иметь множество экземпляров. Для того, чтобы различать токены, адресованные в разные экземпляры одного узла, в структуру токена вводится дополнительное поле - контекст, называемый «цветом значения». По сравнению со статической архитектурой появляется возможность параллельного исполнения различных итераций цикла. Одной из первых реализаций динамической потоковой архитектуры была система 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 вычислить
исполнительный адрес адресата. После
выполнения операции функциональный блок
пересылает результат в блок формирования
токенов.
Функция согласования
токенов стала достаточно короткой
операцией, что позволяет внедрить ее в
виде нескольких ступеней процессорного
конвейера.
Основная:
Ключевые термины (головные): Потоковые вычислительные системы; Статические потоковые вычислительные системы; Управление от потока данных;
Федотов Анатолий Михайлович |
НГУ ФИТ НГУ ИВТ СО РАН |