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

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

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

Команды, реализующие потоковый граф, хранятся в памяти команд и имеют формат: Код операции • Индекс в памяти кадров • Адресат.

Поле «Индекс в памяти кадров» определяет положение ячейки с нужным токеном внутри кадра, т.е. какое число нужно добавить к FP, чтобы получить адрес этого токена. Поле «Адресат» указывает на местоположение команды, ко-торой должен быть передан результат обработки данного токена. Адрес в этом поле также задан в виде смещения, т.е. числа, которое следует прибавить к текущему значению IP, чтобы получить исполнительный адрес команды наз-начения в памяти команд. Если потребителей токена несколько, то в поле «Адресат» заносится несколько значений смещения. На рис. 14.13 показан прос-той пример кодирования потокового графа и токенов на его дугах.

Рис. 14.13. Кодирование в архитектуре с явной адресацией токенов: а – активизация вершины вычитания; б – активизация вершин умножения и сложения; в – кодирование потокового графа

Каждому слову в памяти кадров придан бит наличия, единичное значе- ние которого удостоверяет, что в ячейке находится токен, ждущий согласова- ния, т.е. что одно из искомых значений операндов уже имеется. Как и в архи-тектуре с окрашенными токенами, определено, что вершины могут иметь мак- симум две входные дуги. Когда на входную дугу вершины поступает токен <v1, < FP, I P >>, в ячейке памяти кадров с адресом FP + (I P. I) проверяется бит наличия. Здесь I P. I означает содержимое поля I в команде, хранящейся по ад- ресу, указанному в I P. Если бит наличия сброшен (ни один из пары токенов еще не поступал), то поле значения пришедшего токена (v1) заносится в ана-лизируемую ячейку памяти кадров, а бит наличия в этой ячейке устанавлива- ется в единицу, фиксируя тот факт, что первый токен из пары уже доступен:

(FP + (I P. I)).значение:= v1

(FP + (I P. I)).наличие:= 1

Этот случай отражен на рис. 14.13, а, когда на вершину SUB по левой входной дуге поступил токен <35, < FP, I P >>.

Если токен <v2, < FP, I P >> приходит на узел, для которого уже хранится значение v1, то команда, представляющая данную вершину, может быть акти-вирована и выполнена с операндами v1 и v2. В этот момент значение v1 из-влекается из памяти кадров, бит наличия сбрасывается, и на функциональный блок, предназначенный для выполнения операции, передается пакет команды <v1, v2, FP, I P, I P. 0P, I P. D >, содержащий операнды (v1 и v2), код операции (I P. 0P) и адресат ее результата (I P. D). Входящие в этот пакет значения FP и I P нужны, чтобы вместе с I P. D вычислить исполнительный адрес адресата. После

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

выполнения операции функциональный блок пересылает результат в блок фор-мирования токенов. Рис. 14.13, б демонстрирует ситуацию, когда токен уже пришел и на второй вход вершины SUB. Операция становится активируемой и после ее выполнения результат передается на вершины ADD и MUL, кото- рые ожидают входных токенов в ячейках FP +3 и FP +4 соответственно.

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

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