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

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

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

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

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

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

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

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

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

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

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

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

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

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