Файл: Мультипроцессоры (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МУЛЬТИ ПРОФЕССОРОВ И ИХ ИСПОЛЬЗОВАНИЯ).pdf

Селектор вылавливает в потоке самоопределяемых данных операнды с совпадающими значениями теговых кодов и формирует из них пару. Пара операндов поступает в канал обработки, где над информационными полями выполняются арифметические операции, а теговые коды проходят через дискретный функциональный преобразователь. На выходе канала обработки формируется новый операнд с новым значением тега. На выходе канала обработки изображён коммутатор, в котором определяется выбор направления передачи операнда. Дешифрирующая схема коммутатора анализирует определённые разряды тега и принимает решение о перемещении операнда, либо в выходной блок для формирования выходных данных, либо в одно из трёх направлений продолжения обработки. Таким образом, приведенная схема иллюстрирует, как именно самоопределяемый операнд прокладывает путь своих перемещений в аппаратной среде.

Далее новые поколения операндов вновь вылавливаются селекторами и передаются в каналы обработки, где теговые коды вновь проходят через функциональный преобразователь. Путь превращений теговых кодов выделен на схеме дугообразной стрелкой, замыкающей вход и выход функционального преобразователя. Динамика развития вычислительного процесса осуществляется следующим образом. В секции преобразования теговых кодов всех каналов обработки загружается определённая функция F. В вычислительное устройство вводится набор исходных операндов, с заданными значениями тегов. В силу принятых принципов построения аппаратуры из исходного набора операндов селекторами отбирается множество пар, которые загружаются в каналы обработки для выполнения бинарных арифметических операций. Таким образом осуществляется первый шаг обработки, который полностью определяется состояниями теговых кодов, присвоенных исходному набору операндов. В результате выполнения первого шага на выходе каналов обработки формируется второе поколение операндов с новыми значениями тегов. Далее поведение вновь образованных операндов полностью определяется значениями новых теговых кодов и таким образом осуществляется следующий шаг. Динамическим ядром процесса обработки является рекуррентный генератор кодовых последовательностей, изображённый в правой части Рис. 10. Рекуррентный генератор работает в режиме самообращения и на каждом шаге преобразования передаёт выходной код на входной регистр в качестве нового аргумента.

В классической машине динамика вычислений формируется в результате последовательного считывания программы, которая представляет собой статическую запись опережающей разметки трассы процесса. В самоопределяемых данных процесс разворачивается динамически шаг за шагом и задаётся в аналитической форме в виде функции преобразования теговых кодов F. При этом важно отметить, что в данном случае аналитическое представление динамики процесса не является функцией от времени, а является функцией от предыдущего состояния. В архитектуре самоопределяемых данных роль программы как детерминанта процесса выполняет функция преобразования тегов F и начальные состояния теговых кодов в исходном наборе операндов.

Можно ли в описанной логике взаимодействия самоопределяемых операндов сконструировать осмысленный вычислительный процесс? Рассмотрим конкретный пример на базе введенного ранее упрощённого представления самоопределяемых операндов с одним теговым полем, совмещающим кодирование селекции пар и арифметических операций. Для простоты и наглядности примера будем считать, что тег имеет минимальную разрядность три бита, а функция дискретного кодового преобразователя F есть простая операция сдвига битового набора вправо на один разряд. Трёхразрядный битовый код имеет всего восемь возможных состояний и заданное отображение F можно представить в виде таблицы. Отображение F также можно представить в виде графа, в котором кодовые состояния это вершины графа, а рёбра определяются как пары x; F(x). Назовёт такой граф графом кодовых переходов. Таблица отображения F и граф кодовых переходов приведены на Рис. 11. На графе кодовых переходов для удобства чтения вершины обозначены как целые десятичные числа. Необходимо также назначить кодовым значениям тега арифметические операции и зафиксировать соответствие в виде таблицы, по которой арифметический блок будет интерпретировать теговые коды. Таблица кодирования арифметических операций также приведена на рис. 26. Поскольку кодовых состояний 8, а арифметических операций только 4, целесообразно привязать лишние коды к имеющимся операциям повторно. В данном случае соответствие не должно быть обязательно взаимно однозначным. Код «0» присваивается операции завершения процедуры и интерпретируется аппаратурой как останов.

Рис. 26 Таблица отображения F и граф кодовых переходов

Итак, мы сделали все необходимые определения и можем проследить как будет развиваться вычислительный процесс. Графическое изображение процесса в виде графовой диаграммы приведено на рис. 27. Прямоугольниками на диаграмме обозначены операнды, состоящие из двух полей – тега и информационного поля. Пирамидками обозначены процессы, включающие операции селекции пар, арифметические операции и операции преобразования тегов.

Рис. 27 Диаграмма вычислительного процесса.

Перед началом работы во все каналы обработки вычислительного устройства загружаются преобразователи тегов F и таблицы интерпретации теговых кодов, приведенные на рис. 26. Далее вводится исходный набор операндов. Исходные операнды заполняют нижний слой диаграммы на рис. 27. Теговые коды исходных операндов позволяют отселектирвать пары и направить их в каналы обработки, что отображено во втором слое диаграммы. Третий слой диаграммы заполнен результатами выполнения первого шага обработки, представляющими второе поколение операндов. Формирование содержания полей операндов второго поколения можно проследить по графу кодовых переходов и по таблице интерпретации тегов, которые для наглядности приведены на рис. 27. Преобразования тегов прослеживаются на графе кодовых переходов, а выполняемые арифметические операции определяются таблицей кодирования операций. В информационные поля операндов записывается операция вычисления нового операнда. Во втором поколении операндов в полном соответствии с графом кодовых переходов образуются пары с одинаковыми тегами, которые на следующем шаге обработки вновь отлавливаются селекторами и передаются в каналы обработки. И таким образом события разворачиваются до появления тега со значением «0», что интерпретируется аппаратурой как операция останова и вывода результата в выходной блок.

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

Рассмотренный пример показывает, что при заданной логике взаимодействия операндов и некоторых произвольно выбранных начальных условиях в системе развивается детерминированный процесс, соответствующий вычислению определённого арифметического выражения. Параллелизм извлекается аппаратурой из текущего состояния данных и не требует специальных мер синхронизации, привязки данных к каналам обработки и других мер программирования и обслуживания параллелизма. При условии, что во все каналы обработки загружена одна функция преобразования тегов и одна таблица интерпретации тегов, любой операнд может обрабатываться в любом канале. Где операнд оказался в текущий момент, там он и обрабатывается. При этом привязка операнда к определённой позиции на графе процесса обработки содержится в его теговом сопровождении и неотделима от него. Таким образом архитектура самоопределяемых данных ликвидирует накладные потери в виде многочисленных паразитных пересылок данных из мест хранения к местам обработки и обратно.

Для наглядности и простоты примера мы выбрали малое значение разрядности тега, равное трём. Но даже в этом простейшем случае вычисляемое арифметическое выражение оказалось относительно протяжённым и не тривиальным. Достаточно увеличить теговый код на один разряд и число вершин в графе кодовых переходов удвоится, соответственно удвоится и сложность вычислительной процедуры. При 8-разрядном теге граф кодовых переходов с топологией бинарного дерева будет состоять из 256 вершин и 8 этажей, что позволит поддерживать достаточно сложные и многоэлементные вычислительные процедуры. При этом затраты на программирование и поддержку программы (вернее того, что является аналогом программы) останутся незначительными. В классической архитектуре сложность программирования и сложность алгоритма связаны очень просто. Для простой процедуры надо написать десять строк программы, а для сложной тысячу строк. А в самоопределяемых данных для усложнения программируемой процедуры на порядок достаточно только увеличить разрядность тегового кода примерно на три – четыре разряда.

В предыдущем разделе при оценке эффективности разных форм организации вычислений рассматривались механизмы, поддерживающие многократное использование стереотипных фрагментов программы или так называемых стандартных процедур. Было показано, что как в классической архитектуре, так и в архитектуре Data Flow обеспечение перемещаемости процедуры и привязка тела программы процедуры к разным данным является источником огромных издержек и в программном и в аппаратном обеспечении. Посмотрим как эта проблема решается в архитектуре самоопределяемых данных. Рассмотрим тот же пример с обработкой табличных данных, в котором строка таблицы содержит десяток атрибутов, а таблица в целом состоит из нескольких сотен строк. Создаётся процедура обработки строки, для неё формируется функция преобразования тегов F и набор теговых кодов, присваиваемых исходным операндам из строки таблицы. Для тиражирования процедуры и привязки её к разным строкам таблицы достаточно ввести в теговое сопровождение операндов дополнительное поле индексной метки строк таблицы. (В первичных определениях констатировалось, что набор теговых полей открыт для пополнения и введение новых полей не нарушает основы архитектуры и не требует перестраивать конструкцию машины). Тогда все операнды, принадлежащие одной строке таблицы, будут иметь одно значение в индексном поле, а разные строки будут иметь разные индексные метки. Поле индексной метки будет участвовать в операции селекции, но не будет участвовать в преобразовании теговых кодов. Далее можно загружать таблицу в вычислительную среду в произвольном темпе и в произвольном порядке. Операнды, принадлежащие одной строке всегда отселектируются в один процесс обработки строки, а атрибуты разных строк никогда не пересекутся на всех стадиях выполнении процедуры. Любая процедура в архитектуре самоопределяемых данных может быть тиражирована с заданной кратностью путём расширения тегового сопровождения. Дополнительные разряды тега это необходимая плата за обеспечение требуемого свойства. Можно предполагать, что в данном случае издержки окажутся ощутимо меньше чем в классической архитектуре.

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

Рассмотрим возможности расширения разнообразия вычислительных процедур в самоопределяемых данных. Поскольку в машинной обработке приняты двухместные базовые операции, базовые процессы имеют топологию бинарного дерева. Но можно усложнить топологию реального процесса путём склеивания бинарных деревьев в определённых вершинах. Это потребует механизма многократного вхождения некоторых операндов в граф вычислений либо обмена операндами между разными поддеревьями. Создать набор непересекающихся бинарных деревьев можно при условии, что теговый код имеет достаточно большую разрядность и порождает большое дерево. Тогда при одной порождающей функции в графе кодовых переходов можно выделить набор непересекающихся поддеревьев. Локализация поддеревьев определяется выбором листовых кодов. Для привязки групп исходных операндов к своим фрагментам процесса необходимо присвоить им в качестве тегов листовые коды выбранных поддеревьев. Многократное вхождение определённых операндов в граф вычислений можно обеспечить созданием в исходном наборе операндов ряда копий операнда с разными тегами, поскольку именно тег позиционирует место операнда на графе.

Широкие возможности многократного вхождения операндов в граф процесса обеспечивает некоторое усложнение операции селекции путём маскирования части разрядов теговых полей, в частности полей индексных меток. В этом случае возможен множественный отклик при селекции и организация векторной обработки.

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