Содержание к диссертации
Введение
Главе. I. Алгоритмы параллельных подстановок и их композиция , 16
I.I. Алгоритмы параллельных подстановок 16
1.2. Параллельные граф-схемы и сети Петри 24
1.3. Асинхронная композиция алгоритмов параллельных подстановок 28
1.4. Асинхронная композиция алгоритмов параллельных подстановок с ограничениями на тип используемых конфигураций 43
І.4.1.Асинхронная композиция с использованием ограниченных конфигурации 45
1.4.2.Асинхронная композиция с использованием локальных конфигураций 50
1.4.3.Сложность канонических форм 59
1.5. Построение сети автоматов, интерпретирующей параллельную микропрограмму . 59
Выводы к первой главе 64
Глава II. Структурное проектирование специализированных вычислителей 67
2.1. Общая схема проектирования спецвычислителей
2.2. Анализ алгоритма решения задачи 70
2.2.1.Построение ПТСА и выбор операторов 70
2.2.2.Построение графа информационных связей 75
2.3. Составление полного микропрограммного описания вычислителя 77
2.3.1.Составление параллельных микропрограмм 77
2.3.2. Канонические представления параллельных микропрограмм 88
2.4. Построение структурной схемы спецвычислителя , 97
Выводы ко второй главе 107
Глава III. Имитационное моделирование параллельных спецвычислителей 108
3.1. Назначение языка параллельного микропрограммирования 108
3.2. Основные конструкции языка параллельного микро программирования IU9
3.2.1. Общая характеристика языка 109
3.2.2. Алфавит языка
3.2.3. Клеточный массив
3.2.4. Процедуры определения координат соседей ІЇ2
3.2.5. Композиция клеточных массивов ИЗ
3.2.6. ьіикрокомандьі П4
3.2.7. Микропрограмма Ц9
3.2..8. Микропрограммная модель сумматора многих двоичных чисел 121
3.3., Реализация микропрограммных моделей на ЦВМ 123
Выводы к третьей главе 139
Глава IV. Аппаратная интерпретация параллельных микро программ 140
4.1. Реализация сетей автоматов, интерпретирующих параллельные микропрограммы 140
4.2. Кодирование параллельных микропрограмм 143
4.3. Варианты реализации элементарных автоматов . 162
Выводы к четвертой главе 165
Заключение 166
Литература
- Алгоритмы параллельных подстановок
- Общая схема проектирования спецвычислителей
- Назначение языка параллельного микропрограммирования
- Реализация сетей автоматов, интерпретирующих параллельные микропрограммы
Введение к работе
Развитие технологии обеспечило создание программируемых и перепрограммируемых ПЗУ, ПЛМ, вентильных матриц и привело к интенсивным разработкам ассоциативных структур типа памяти с логикой
[I, 2J ; вычислительных структур для обработки сигналов и изображений [3, Ч] , сортировки [5J , быстрой арифметики [в, ?] ; микропроцессорных систем [8, э] ; систолических матриц [Ю, її] ; коммутационных структур [12] ; асинхронных устройств управления
[13, 14, I5J и т.д. Все эти устройства состоят из множества одинаковых достаточно простых вычислителей, проблемно-ориентированы и эффективны при узкой специализации. Их называют однородными вы* числительными структурами.
У данного класса - две характерные грани. В рамках концепции вычислительных сред (СБИС однородной структуры, способной настраиваться тем или иным способом на реализацию любого алгоритма [16, I?J ) такие устройства можно определить как специализированные вычислительные среды. С другой стороны эти устройства можно рассматривать как модули нижнего уровня вычислительных систем, поскольку существует тенденция аппаратной реализации достаточно сложных функций в современных системах, а1также стремление снабдить мощные системы наборами специализированных устройств (спецпроцессоров) „строить системы в виде иерархической совокупности специализированных модулей [18, 19] .
Длг однородных вычислительных структур частично или полностью характерны следующие черты.
Параллельность обработки, проникающая на самые низкие уровни выполнения операций, вплоть до элементарных операций.
Децентрализация функций памяти, управления и преобразования информации: часто возможно только условное (но не пространен-
венное) их разделение. Например, микропрограммное управление сочетаем в себе память и управление^ ассоциативный процессор - память и преобразование.
3. Структурная и функциональная перестраиваемость, позволяющая получать разные специализированные конфигурации на основе одного к того же оборудования. Структурная перестроила представляет собой один из основополагающих принципов концепции вычислительных сред. Типичное проявление этого принципа на микроуровне -программируемые, перепрограммируемые C2U, 21 ] и вентильные матрицы [22, 23J . Самый распространенный способ функциональной ' перестройки - микропрограммный. Микропрограммная настройка может выполняться как на этапе производства ЕЙС, так и при их эксплуатации. Наиболее полно микропрограммирование проявляется как средство настройки и перестройки при проектировании микропроцессорных систем, в которых назначение стандартных вычислительных блокозопределяется микропрограммами.
4. Широкий спектр сложностей элементов: от микропроцессора, который может выполнять достаточно сложные алгоритмы, до ячейки ассоциативного процессора, содержащего один бит памяти и несколько вентилей.
Однородность структуры и локальность связей элементов структуры. Как правило, задачи, решаемые на таких структурах, содержат параллельную обработку массивов данных, и однородность и локальность фактически являются следствием этой особенности решаемых задач. Кроме того, построение однородных структур с локальными связями целесообразно с точки зрения технологии.
Увеличение роли микропрограммирования. Оно обеспечивает функциональную перестройку, увеличивает регулярность микроструктуры (за счет того, что основным блоком в устройстве управления де-
лается память микропрограмм), служит инструментом проектирования и моделирования, использующим формальные методы близкие к программированию [24, 25, 26, 27] .
7, Асинхронное выполнение не только операторов алгоритма, но и элементарных операций. Это аренде всего справедливо при построении однородных структур управления [із] .
Завершим перечисление свойств следующими замечаниями.
Не следует абсолютизировать необходимость построения полностью однородных вычислительных устройств. Действительно, даже при построении специализированного устройства реализуемый алгоритм может содержать "глобальные" операторы (операторы, использующие данные всего перерабатываемого массива). Как правило, это управляющие операторы. Реализация их в однородной структуре с локальными связями приводит к их итерационному выполнению, что уменьшает эффективность переработки информации,иногда весьма существенно. Например, вынесение за рамки однородной структуры нескольких процентов обработки информации может на порядок уменьшить общие временные затраты [28^ .
Следует учитывать, что использование асинхронных принципов приводит к усложнению как устройства управления, так и управляемых элементов. Особенно сильно это проявляется при распределенном управлении, поскольку каждый элемент структуры должен быть способен сам определить свою готовность к выполнению операции и выдать сигнал о ее завершении [29, 3CQ . Поэтому очень часто, при простых процессорных элементах, целесообразна синхронная реализация операторных блоков.
Учитывая эти замечания и все перечисленные свойства в комплексе, мы определим параллельную микропрограммную структуру как множество асинхронно взаимодействующих блоков, каждый из которых
8 '
является однородной совокупностью синхронно действующих конечных автоматов (процессорных элементов). Блоки могут отличаться друг от друга числом процессорных элементов и их сложностью. Отдельный блок выполняет некоторый оператор, а совокупность блоков - асинхронную композицию операторов (алгоритм решения задачи).
Для такой достаточно общей трактовки специализированного вычислительного устройства параллельной обработки информации в течение ряда лет с участием автора проводятся исследования по методам синтеза, объединенные названием методы параллельного микропрограммирования DlJ .
Диссертация является частью научных исследований, выполненных в этой области.
Известны методы синтеза, разработанные для отдельных типов однородных вычислительных структур, например, параллельных арифметических блоков СбЛ * цифровых интегрирующих структур [32J , ассоциативных процессоров [33] и др. Б этих методах ключевым является распараллеливание .вычислений на процессорных элементах, вопросам распараллеливания управления внимание не уделяется, в следствие чего однородная структура рассматривается изолированно,
вне рамок динамического взаимодействия с другими однородными
автоматов, структурами. Методы не выходят за пределы классической теорийки
их применение ограничено синтезом процессорного элемента.
В отличие от них методы параллельного микропрограммирования нацелены на комплексное решение вопросов организации параллельных вычислений с учетом как распараллеливания собственно вычислений , так и управления вычислениями, на разработку формальных методов синтеза структуры спецвычислителя, моделирование спецвычислителя и отображение его структуры в некоторую реальную физическую струну РУ.
Средства параллельного микропрограммирования базируются на расширенном понимании микропрограммирования. Необходимость расширения продиктована в первую очередь тем, что методы синтеза должны обеспечивать соответствие структуры устройства и функций процессорных элементов структуре информационных связей и операторов реализуемого алгоритма. Это соответствие понимается следующим образом; если операторы в алгоритме информационно независимы, то в структуре их микропрограммы выполняются параллельно. Расширение состоит в распространении идей асинхронного программирования [34, 353 на микропрограммирование. Каждый алгоритм представляется в виде некоторого неупорядоченного множества элементарных действий (микрокоманд), в котором на каждом шаге выполняются одновременно все действия, удовлетворяющие условиям готовности. Условия готовности определяются перерабатываемыми данными.
Методы параллельного микропрограммирования основываются на алгоритмической системе параллельного типа - алгоритмах параллельных подстановок [36, 37, 38] .
Эти алгоритмы базируются на понятиях клеточного автомата [39, 40 J (параллельное и повсеместное применение локальных преобразований), нормального алгоритма [41] (операция подстановки, размеры слов в которой не фиксируются, а зависят от требуемого преобразования:) , алгоритма Колмогорова-Успенского С42](преобразуемая информация необязательно представляется в виде линейно упорядоченного слова, а может иметь достаточно произвольную структуру).
Объектом преобразования служит клеточное множество V-конечная совокупность поименованных клеток, в которые вписаны символы из некоторого конечного алфавита состояний.
Элементарным преобразованием клеточного множества является операция подстановки, имеющая левую и правую части. В простейшем
виде операция подстановки содержит в левой и правой части клетки с конкретными именами и состояниями. Ясли в клеточное множество входят все клетки левой части, то подстановка применима и часть клеток заменяется клетками из правой части. Совокупность клеток в левой части, не участвующих в замене, называется контекстом. Будем называть такую операцию подстановки элементарной операцией. В общем случае операция подстановки задает посредством конфигураций способ перечисления множества однотипных элементарных операций. Выполнение операции подстановки состоит в том, что с каждой клеткой из W связывается процедура Р , которая по имени клетки и записи конфигураций операции подстановки воспроизводит соответствующую элементарную операцию и выполняет ее, если она применима.
Совокупность операций подстановки, записанных в произвольном порядке, образует алгоритм параллельных подстановок.,
Применение алгоритма параллельных подстановок к клеточному множеству W производится следующим образом: для всех клеток из W и всех операций подстановки процедура? выполняется параллельно до тех пор, пока, применима хотя бы одна элементарная операция.
Методы композиции алгоритмов параллельных подстановок целесообразно основывать на моделях асинхронных взаимодействий параллельных процессов. Известен целый ряд таких моделей [43J . Наиболее лрием-іемьш вариантом модели параллельных процессов является сеть Петри
[44, 45.] , поскольку от сети Петри можно непосредственно перехопіть к ее микропрограммному описанию и условия, задаваемые маркированием сети Петри, могут быть интерпретированы контекстом в операци-IX подстановки, что обеспечивает возможность композиции алгоритмов.
Использование в качестве формальной основы параллельного микро-[рограммирования алгоритмов параллельных подстановок и аппарата се-'ей Петри позволило создать средства параллельного микропрограммиро-
вания, обладающие возможностями:
а) описывать массовые преобразования информации в однородных
структурах, протекающие повсеместно в пространстве и параллельно во
времени;
б) описывать как локальные так и глобальные преобразования
информации;
в) отображать произвольные структуры данных;
г) записывать обычные (последовательные) микропрограммы;
д) унифицировать средства для описания как управляющих дейст
вий, так и действий над данными.
Микропрограммный способ описания параллельных преобразований информации обеспечивает формальный переход к микроструктуре спецвычислителя и здесь возможны два пути.
Микропрограммное описание принимается первичным, и оно определяет основные параметры структуры (число блоков, объем блоков, сложность процессорных элементов, число входов и выходов процессорного элемента, тип управления и т.д.), монно говорить что получается "заказная" структура спецвычислителя.
Фиксируется универсальная структура (вычислительная среда, сеть из микропроцессоров и т.п.) и микропрограммное описание вычислительного процесса вкладывается в эту структуру ('подгоняется" под структуру). В этом случае основная задача - представление некоторого алгоритма параллельной микропрограммой с заданными ограничениями на параметры микрокоманд.
Для решения этих задач необходимо разрабатывать методы построения, преобразования, проверки и аппаратной интерпретации параллельных микропрограмм. В этом направлении коллегами автора сделаны следующие шаги: исследованы вопросы построения непротиворечивых параллельных микропрограмм [Чб] , асинхронной интерпретации пара-
ллельных микропрограмм [47] , проверки ПГСА на корректность [48, 49] , преобразования сетей Петри [50] , интерпретации параллельных микропрограмм" микропроцессорными системами [5l] , синтеза микроструктуры микропрограммного управления [52] , структурного проектирования специализированных параллельных микропрограммных устройств [53 J . Автор диссертации занимался разработкой алгоритмической системы параллельного типа, способами асинхронной коыпо-зиции параллельных микропрограмм, а также разработкой основ формальной методики проектирования микропрограммных вычислительных структур.
На защиту выносятся следующие результаты»полученные автором.
1. Алгоритмическая система - алгоритмы параллельных подстано
вок, как средство описания параллельных вычислительных процессов
[31 стр. 16-23, 30-35; 36; 37; 38] ,
2. Способы композиции алгоритмов параллельных подстановок
как средство построения сложных микропрограмм с заданными свойствами из более простых микропрограмм [31 стр. 66-71; 38, 54-J .
3. Методика структурного проектирования специализированных
вычислительных устройств параллельной обработки информации, основа
нная на композиционном построении полных микропрограммных описаний
[55] .
Язык параллельного микропрограммирования как средство описания структуры и функционирования параллельных спецвычислителей включая реализацию микропрограммных моделей спецвычислителей на ЭВМ [31 стр. II3-I44; 56] .
Аппаратная интерпретация параллельных микропрограмм в одном классе .вычислительных сред [57, 58, 59] .
Весь материал диссертации распределен по четырем главам.
П з р в а я глава посвящена вопросам композиции параллельных
микропрограмм. Здесь дается развернутое определение алгоритмов параллельных подстановок, выделяется подкласс параллельных микропрограмм, проводится классификация конфигураций, из которых строятся микрокоманды. Конфигурации делятся на три типа; глобальные (в интерпретирующей микропрограмму сети автоматов существуют автоматы с числом соседей, зависящим от мощности клеточного множества), ограниченные (каждый автомат связан с числом соседей не большим заданного К ), локальные (связи автомата с соседями не длиннее некоторого г , Г- заданный линейный размер). Вводятся необходимые понятия и определения из теории сетей Петри и параллельных граф-схем алгоритмов (ПГСА). Опжывается переход от любой параллельной микропрограммы к микропрограмме в канонической форме. Доказывается эквивалентность по результату исходной микропрограммы и микропрограммы в канонической форме. Доказывается возможность построения для набора микропрограмм операторов «, ,..., Фя, и корректной ПГСА, описывающей их композицию, эквивалентный по результату параллельной микропрограммы, состоящей из управляющей микропрограммы и микропрограмм в канонической форме для операторов 4j ,..., 4. Показывается, что возможно построение канонических форы (а значит и композиций) с использованием в записи микрокоманд только ограниченных или только локальных конфигураций и оценивается сложность таких форм. И, наконец, излагается формальная процедура построения сети автоматов, интерпретирующей параллельную микропрограмму.
Материал второй главы опирается на теоретические результаты первой главы. Вторая глава посвящена разработке методики и практических приемов перехода от параллельного алгоритма решения заданного класса задач к структурной схеме устройства, реализующего этот алгоритм. Методика содержит три этапа. На первом этапе проводится анализ класса решаемых задач, разрабатывается алгоритм реше-
ния, производится выбор операторов и составляется ПГСА. Бторой этап содержит составление полного микропрограммного описания, которое с одной стороны представляет алгоритм решаемой задачи, а с другой -характеризует структуру проектируемого устройства. Составление микропрограммных описаний спецвычислителей демонстрируется на примерах,, при этом существенное внимание уделяется построению сети Петри, выбору алфавита, структуры имен клеток, особенностям построения композиционных расширений, продиктованным практикой,- выбору типа управления. На третьем этапе осуществляется построение структурных схем спецпроцессоров, при этом сперва строятся структурные схемы операторов, а затем объединяются в общую структурную схему.
В третьей главе приводится описание языка параллельного микропрограммирования. Он разработан на основе алгоритмов параллельных подстановок. Объектом преобразования в языке является клеточный массив - аналог клеточного множества. Основным элементарным преобразованием клеточных массивов является микрокоманда подстановки. Микрокоманда содернит управляющую и операционную части. Управляющая часть определяет условия применения операционной части микрокоманды. Язык предназначен для описания структуры и функционирования паранлельных микропрограммных вычислителей. Описание образует микропрограммную модель проектируемого устройства.
В этой главе также излагается методика реализации микропрограммных моделей на ЭВМ. В качестве языка реализации микропрограммных моделей принят ШКЕ. В основу методики положен принцип сборки ПЛ-ной реализации модели из стандартных заготовок по определенным правилам. Заготовки строятся на основе классификации микрокоманд подстановки по мерности клеточных массивов, типам описания топологии связей клеток и типам операционных частей.
Четвертая глава посвящена вопросам аппаратной интер-
претации алгоритмов параллельных подстановок. От сети абстрактных автоматов, полученной по алгоритму параллельных подстановок, можно перейти к двум вариантам ее реализации: в виде оети из ыи-нролрограммируемых автоматов, в этом случае каждый автомат содержит падшть микропрограмм, или в виде однородной машины, в этом случае память микропрограмм общая.для всех автоматов, а сами автоматы содержат блок сравнения Г 373 , Реализация глубокого распараллеливания (вплоть до микрокоманд) достигается тем, что каждый элементарный автомат должен обладать способностью на каждом такте своей работы выбирать к выполнению микрокоманду из целого множества микрокоманд (обозначим его мощность буквой V ), поступающих на него одновременно или хранящихся в нем. Это приводит при использовании двоичной логики и традиционной схемотехники к ^ -кратному, при достаточно большом V , увеличению оборудования в каждом автомате по сравнению с тем, если бы на каждом такте работы на элементарный автомат поступала (или хранилась в нем) только одна микрокоманда. Это объясняется тем, что в V раз вырастает объем памяти микропрограмм или блока сравнения в каждом автомате. Так как мы имеем дело с построением микроструктуры, то такой рост приводит к пропорциональному росту объема оборудования всего вычислительного устройства. Поэтому весьма важно найти способы сокращения объема аборудования при сохранения параллелизма. В связи с этим предлагаются варианты вычислительных сред и кодирования микрокоманд в многозначном структурном алфавите, обеспечивающие логарифмический рост объема оборудования при линейном росте числа одновременно поступающих на элементарный автомат микрокоманд.
В заключении кратко излагаются основные результаты работы.
Алгоритмы параллельных подстановок
Микропрограмма, именующие функции и клеточное множество фактически образуют формальную модель проектируемого устройства, причем микропрограмма описывает функционирование устройства, а именующие функпии и клеточное множество задают структуру устройства. Кажется вполне естественным еще до реального построения специализированного устройства и дане до детальной проработки его логической схемы исследовать эту модель, хотя бы для того, чтобы убедиться в отсутствии ошибок в микропрограмме. Это исследование может быть проведено о помощью имитационного моделирования на ЦВМ. Для LSEODO на основе алгоритмов параллельных подстановок мы разработали язык параллельного микропрограммирования -С56, 31 стр. II3-I23J . Б этом языке конкретизированы основные понятия алгоритмов параллельных подстановок с учетом его реализации на машине, расширено понятие крнтекста, введены средства, сокращающие запись микропрограммы, учтены особенности моделирования параллельных вычислений на последовательной машине.
В качестве модели параллельного вычислительного устройства в языке используется совокупность взаимодействующих блоков. Отдельный блок - это массив однотипных ячеек. На каждую ячейку одновременно поступают все микрокоманды микропрограммы, выполняемой блоком. Отдельная ячейка в зависимости от собственного состояния и состояния некоторых ячеек, называемых соседними (окрестность ячейки), осуществляет выбор и выполнение той или иной микрокоманды микропрограммы. Это отличает предлагаемый язык от языков регистровых передач, в которых основной структурной единицей является регистр и все преобразования информации осуществляются в совокупности регистров.
Будем называть микропрограмм и ой моделью запись формальной модели устройства на языке параллельного микропрограммирования.
В качестве языка реализации микропрограммных моделей выбран язык \1A-1 . ПЛ-ная программа собирается из ПЛ -ных заготовок, сопоставленных конструкциям языка параллельного ыикро-пр огвашшр ов ания.
Средства языка обеспечивают как описание структуры моделируемого устройства, так и алгоритмов его функционирования. К характеристикам структуры устройства на макроуровне относятся: 1) размерность блока, 2) размеры блока, 3) число блоков в устройстве, 4-) взаимосвязи блоков в устройстве; на микроуровне: 1) алфавит ячейки, 2) число входов ячейки, 3) число выходов ячейки, 4) топология связей ячейки по входам и выходам. К характеристикам алгоритма функционирования относятся: 1) функциональное преобразование, реализуемое ячейкой,
2) параллельное и повсеместное выполнение функциональных преобразований во всех ячейках устройства.
Алфавит языка. Б качестве имен состояний ячеек устройства в языке используются символы (возможно с индексами) шестиде-оятисиывольного алфавита, кроме символов # , # , і й) , машин серии НС. Эти символы образуют группу основных символов языка. Символы могут быть разбиты ка классы. Имя класса образует пара символов, первым в паре является знак рг, вторым - буквенный символ, возможно с индексом. Имена классов образуют группу переменных символов языка. Переменный символ, обозначающий любой символ языка,-это X . Переменные символы используются только в записи микрокоманд. Основные символы могут быть представлены в виде символьных кодов в некотором1 базовом алфавите, в качестве, которого применяются различные подмножества шестидесятисимвольного алфавита, чаще всего jo,lj . Для представления переменных символов используются коды в расширении базового алфавита. Расширение получается при пополнении алфавита символом #- , обозначающим любой символ базового алфавита.
Клеточный массив. Блоку устройства сопоставляется клеточный массив - аналог клеточного множества. Элементами массива служат символьные коды, представляющие состояния соответствующих ячеек блока. Положение ячейки в блоке отражает набор координат соответствующего элемента клеточного массива. Для всех массивов, сопоставленных устройству, принята единая система координат. Клеточный массив обозначается служебным словом TS с положительным целым индексом. Например, устройство, изображенное на рис. 3.1, состоит из двух блоков.
Общая схема проектирования спецвычислителей
Пренде чем перейти к рассмотрению построения вспомогательных процедур, отметим следующее. То,насколько удачно каждому типу микрокоманды сопоставлен соответствующий ПЛ-ный текст, определяет эффективность ПЛ-ных моделей. Так как микрокоманды управления аналогичны соответствующим операторам ЗЛ-І, то основное внимание сосредоточено на микрокомандах подстановки.
Реальные структурные схемы содержат сотни и тысячи ячеек. В этих структурах применение микрокоманд, как правило, идет параллельно во времени и повсеместно в пространстве. Это означает, что при моделировании таких структур на обычных ЭВМ на каждом шаге вычислений для каждой микрокоманды подстановки необходимо op- . ганизовать процедуру последовательного просмотра всех ячеек всех клеточных массивов, указанных в микрокоманде, и изменять состояния ячеек в зависимости от применимости микрокоманд. То, насколько рационально этот цикл организован для каждого типа микрокоманды, а основном, определяет время работы модели.
Микрокоманды подстановки отличаются друг от друга числом зон и типом зон. Проведем классификацию типов зон. Контекстные и базовые, зоны делятся на 1) зоны с одномерным клеточным массивом, 2) зоны с двумерным клеточным массивом, 3) зоны с трехмерным клеточным массивом. "Это свойство отражает характеристика М, принимающая значение 1,2,3. Каждая из зон I), 2), 3) может быть: . а) с процедурой определения соседей первого типа {PAT ), б) с процедурой определения соседей второго типа ( FUSf ). Это свойство отражает характеристика Ы , принимающая значение О для случая а) и значение FU i для случая б), если в записи зоны использована процедура FUMi В свою очередь каждый из этих шести типов зон может быть: а) с переменными ( УХ ) , б) без переменных.
Это свойство отражает характеристика П , принимающая значение О для случая а) и значение I для случая б). Зоны отличаются одна от другой числом элементов Б перечне пар. Кроме того, каждая зона монет быть либо просто с перечислением пар, содержащих символ алфавита и номер элемента, либо с перечислением пар, содержащих состояние отдельного разряда (группы разрядов) символа алфавита и не только номер элемента, но и номер (номера) разряда (разрядов).
Операционные зоны микрокоманд могут быть 1) с одномерным клеточным массивом, 2) с двумерным клеточным массивом, 3) с трехмерным клеточным массивом. Каждая из операционных зон I), 2), 3) монет быть а) с процедурой определения соседей первого типа, б) с процедурой определения соседей второго типа. В свою очередь каждый из этих шести типов может быть а) с функциональным преобразованием (MAP ), б) без функционального преобразования. Это свойство отражает характеристика , принимающая значение МАРі для случая а), осли в записи зоны использовано преобразование МАРІ , и значение О для случая б).
Кроме того, и в этом случае справедливо замечание о возможности указания состояний и номеров отдельных разрядов. Отметим также, что операционная зона микрокоманды может быть либо снабжена списком признаков, либо нет.
При создании ПЛ-ной записи микропрограммы можно пойти по пути создания одной процедуры, пригодной для реализации всех типов микрокоманд. Анализ такой возможности был проведен и показал, что из-за накладных расходов, вызванных необходимостью вводить подстройку под тот или иной тип микрокоманды, существенно возрастает время моделирования. Можно выбрать диаметрально прошивополож-ный вариант: создавать для каждого типа зоны свой вариант ПЛ-ной заготовки и собирать из этих заготовок специализированную процедуру для каждой микрокоманды. Но у этого пути также есть недостаток: возрастает объем ffll-ноіі записи модели. Нами выбран компромиссный вариант: строится набор специализированных процедур, пригодных каждая для своего класса микрокоманд подстановки. Но при этом правила построения процедур и блоки заготовок, из которых лни .строятся, унифицируются. Достигается это при помощи построения вспомогательных массивов, используемых ПЛ-ной моделью структурной схемы. Это: 1) массив подшаблоиов SP \ 2) двумерный массив кодов символов зон С ; 3) двумерный массив Pv/, задающий начала и концы каждого подшаблона в массиве SP .
Введение вспомогательных массивов позволяет относить к одному классу зоны с переменными и указанием состояния разряда (группы разрядов), а также зоны с различным, числом элементов в перечне пар при условии, что у них совпали характеристики М , М , /7 или М , н л.
На основе классификации зон можно провести разделение микрокоманд на классы. Микрокоманды, отличающиеся перестановкой зон с совпадающими характеристиками, относятся к одному классу.
Ванными параметрами микрокоманды подстановки, о которых пока не упоминалось, являются имена индексов пробега I , J ,к по клеточным массивам. Эти имена используются в качестве фактических параметров в операторах САН , сопоставляемых конкретным" микрокомандам в главной процедуре.
Назначение языка параллельного микропрограммирования
Для получения логической структуры элементарного автомата сети ыонно использовать любые известные методы синтеза. Но, так как элементарный автомат в сети, интерпретирующей параллельные микропрограммы с большим числом подстановок получается неприемлемо сложным, весьма вакен поиск способов упрощения сетей и процедур их синтеза. Процедуру синтеза можно упростить, если сделать каждый элементарный автомат минр программируемым (содержащим память, хранящую микропрограмму Фп , построенную по исходной микропрограмме Ф ).
Существует несколько вариантов исходного представления Фм , мы ограничимся следующим. Микропрограмма Фм содержит V строк. г-ая строка представляет микрокоманду ЗІ из г и состоит из двух частей .У/и Л. Часть-J/содернит р+1 символ, часть П - $+ У символ. Первый символ части JI совладает с первым символом пары (ЯІ1} (т)) из записи Sin остальные Р символов совпадают с первыми р символами входного состояния ei . Часть Л совпадает с выходным состоянием W . Здесь и далее используются обозначения из первой главы.
грамму 4м- Блок 2 - внутренняя память автомата. М - первые р входов совокупности И . Мг - остальные S входов совокупности М . Реализация такой схемы возможна в виде специальной БИС либо в виде соединения из стандартных ЯЗУ или Шій и регистровых БИС.
Значительное упрощение"сети может быть достигнуто, осли память микропрограмм, повторяющуюся в каждом автомате, вынести за пределы сети в отдельный блок (рис. 4.2). Оставшаяся сеть называется памятью данных. Элементарные автоматы в ней содержат ячейку внутренней памяти, блок сравнения и коммутатор Г 37 J . Кандый элементарный автомат наряду с входами и выходами , определяемыми связями элементарных автоматов друг с другом, имеет группу входов, связывающих его с выходами памяти микропрограмм. Эти входы называются программными (рис.4.3), Назовем оловом-состоянием элементарного автомата слово, образованное состоянием его внутренней памяти и состояниями соседей по входам из Пі данного автомата. Автомат памяти данных работает следующим образом. Б блоке сравнения осуществляется сравнение слова - состояние автомата с частями Л строк микропрограммы Ум, хранящейся в памяти микропрограмм. При совпадении слова-состояния с частью А некоторой строки первый символ части Л этой строки записывается во внутреннюю память, остальные символы по выходам М поступают на входы записи Да соседних автоматов. Так осуществляется применение микрокоманды. Полученное устройство называется параллельной машиной.
В [зі, стр. 40-41j проведен анализ связи производительное- -ти параллельной машины со сложностью ее элементарного автомата. Микропрограммы могут выполняться в памяти данных с разной степенью параллельности и по этому признаку параллельные машины ыокно разделить на четыре типа: 1) с параллельным сравнением символов и параллельным применением микрокоманд, 2) с последовательным сравнением символов и параллельным применением микрокоманд, 3) с параллельным сравнением символов и последовательным применением микрокоманд, 4) с последовательным сравнением символов и последовательным применением микрокоманд.
Каждый тип машины характеризуется двумя параметрами: степенью замедления HG сравнению с предельно-параллельным случаем (тип I) и слонностыо автомата памяти данных, выраженной в количестве программных входов автомата (табл.4.1).
Таблица 4.1 получена в предположении, что по любому программному входу в одном такте поступает один А -пчный символ. Анализ таблицы показывает, что если бы удалось построить элементар-ныи автомат, в котором по каждому програшшому г одном и том ке такте поступали несколько Д -ичных символов (обозначим их чис-ло буквой с/ ), то нокао было бы уменьшить в d раз сложность элементарного автомата без увеличения замедления для машин первого и второго типа, либо сохранив сложность элементарного автомата в сі раз уменьшить замедление для машин третьего и четвертого типов.
Далее мы предлагаем способы кодирования микропрограмм, обеспечивающие построение такого элементарного автомата для машин первого и третьего типов. Основное внимание уделяется кодированию для машин первого типа, кодирование основано на введении нескольких специальных операций.
Реализация сетей автоматов, интерпретирующих параллельные микропрограммы
Выбор частотного диапазона представления символов микрокоманд. Переход в оптический диапазон частот позволяет заменить каждый столбец фильтров в матрице одним фильтром, а блок детектирования выполнить содержащим одну конструктивную единицу - фоторезистор [ 57J . Сложность элементарного автомата получается пропорциональной длине левой части микрокоманды и как функция, зависящая от числа микрокоманд в микропрограмме, имеет логарифмический характер, т.к. мощность всего множества возможных микрокоманд равна р , а длина левой части - ( Р-М) . 2) Реализация, наряду с общими для всех элементарных автоматов, индивидуальных для каждого автомата параллельных микропрограмм. Для достижения этой цели в блок-схеме (рис.4.5) между блоками фильтрации и детектирования включается дополнительный блок памяти для хранения индивидуальной микропрограммы. Детальное описание такого варианта блок-схемы и ее реализации в оптическом диапазоне частот приведено в [58j . Отметим, что и в этом случае логарифмический характер зависимости сложности автомата от объема как общей дак и индивидуальной микропрограммы сохраняется.
Реализация в элементарном автомате функциональных подстановок. При разработке блок-схемы (рис.4.5) основное внимание было уделено реализации выборки микрокоманды из совокупности микрокоманд. Выполнение микрокоманды было традиционным: коды символов правой части микрокоманды записывались в собственную память элементарного автомата и память соседей. Для обеспечения возможности выполнения функциональных подстановок предлагается следующая модификация базовой блок-схемы: между блоком детектирования и коммутатором включается арифметико-логическое устройство (АЛУ) (рис. 4.7). После выборки микрокоманды код ее правой части анализируется в АЛУ. Если в нем есть функциональный символ, в АЛУ осуществляется соответствующее преобразование над состояниями соседей по входам: получается новый код правой части. Он поступает в коммутатор и далее, как и ранее, составляющие этот код символы записываются в памяти соседей по выходам. Ясли в коде правой части нет функционального символа, символы кода сразу поступают в коммутатор. 1. Предложено несколько вариантов многозначного кодирования микрокоманд. Показано, что при определенных правилах выполнения микрокоманд возможна одновременная передача по одним и тем же информационным каналам кодов многих микрокоманд. При этом выборка и выполнение любой из них осуществляется на одном и том же оборудовании.
2. Предложено несколько вариантов блок-схем элементарных автоматов, обеспечивающих логарифмический рост объема оборудо-. вания спецвычислителей при линейном росте числа выполняемых ими микрокоманд. Заключение. Основные результаты работы. 1. Заложена формальная основа перехода от алгоритма решения задачи к интерпретирующему его специализированному параллельному вычислительному устройству. Она базируется а) на алгоритмический системе параллельного типа - алгорит мах параллельных подстановок, обеспечивающих возможность постро ения микропрограммных описаний параллельных преобразований ин формации; б) методах и приемах асинхронной композиции параллельных микропрограмм; в) формальной процедуре, позволяющей по любой параллельной микропрограмме построить интерпретирующую ее сеть автоматов.
2. Предложены методы асинхронной композиции параллельных микропрограмм, опирающиеся на представление алгоритма параллельной граф-схемой. На основе сетей Петри разработана формальная процедура построения полного микропрограммного описания вычислительного процесса. Описание составляется из управляющей микропрограммы и канонических представлений микропрограмм функциональных операторов DTCA. Доказана теорема об эквивалентности полного микропрограммного описания и исходного представления композиции,
3. Найдены варианты канонических форм параллельных микропрограмм, обеспечивающие их включение в асинхронную композицию.
Канонические формы строятся при самых общих предположениях о механизмах пуска-останова параллельной микропрограммы и таковы, что обеспечивают любую степень локальности взаимодействий в сети автоматов, интерпретирующей микропрограмму.
4. Получены оценки сложности различных канонических форм параллельных-микропрограмм.
5. Разработана методика проектирования олецвычислителей. Она основана на приемах асинхронной композиции и интерпретации параллельных микропрограмм сетями автоматов. В ней даны рекомендации по выбору основных параметров микропрограммных описаний операторов, детально проработаны приемы композиции, учитывающие конкретные особенности операторов. Предложена двухэтал-ная процедура построения структурной схемы слецвычислителя, как с распределенным так и с сосредоточенным управлением.
6. На базе алгоритмов параллельных подстановок разработан язык параллельного микропрограммирования, обеспечивающий построение микропрограммных моделей проектируемых спецв.ычислителей. Разработана методика реализации микропрограммных моделей на ЭВМ, В ее основу положена библиотека унифицированных заготовок, записанных на языке Ш1-І. Машинная реализация микропрограммной модели собирается из заготовок по определенным правилам. Эта методика применялась для моделирования процессов вычислений в нескольких типичных однородных структурах.
7. Предложены варианты кодирования параллельных микропрограмм и соответствующие варианты реализации процессорного элемента спецвычислителя, обеспечивающие одновременную передачу по одним и тем не шинам на каждый процессорный элемент кодов многих микрокоманд. Это позволяет при сохранении быстродействия спецвычислителя существенно сократить объем его оборудования.
8. Предложенная методика синтеза структур вычислительных устройств применялась на одном из предприятий г. Новосибирска и в Институте автоматики и электрометрии СО АН СССР.
