автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка микропрограммных методов синтеза структур параллельных вычислительных устройств

Введение. .••.«. .«.<

Глава I. Алгоритмы параллельных подстановок и их композиция.

§ I.I. Алгоритмы параллельных подстановок.

§ 1.2. Параллельные граф-схемы и сети Петри

§ 1.3. Асинхронная композиция алгоритмов параллельных подстановок.,.

§ 1.4. Асинхронная композиция алгоритмов параллельных подстановок с ограничениями на тип используемых конфигураций.

1.4.1.Асинхронная'композиция с использованием ограниченных конфигураций

1.4.2.Асинхронная композиция с использованием локальных конфигураций

1.4.3.Сложность канонических форм

§ 1.5. Построение сети автоматов, интерпретирующей параллельную микропрограмму

Выводы к первой главе.64'

Глава П. Структурное проектирование специализированных вычислителей

§ 2.1. Общая схема проектирования спецвычислителей

§ 2.2. Анализ алгоритма решения задачи

2.2.1.Построение ПГСА и выбор операторов

2.2.2.Построение графа информационных связей

§ 2.3. Составление полного микропрограммного описания. вычислителя.

2.3.1.Составление параллельных микропрограмм

2.3.2. Канонические представления параллельных. микропрограмм

§ 2.4. Построение структурной схемы спецвычислителя

Выводы ко второй главе

Глава Ш. Имитационное моделирование параллельных спецвычислителей.■.

§3.1. Назначение языка параллельного микропрограммирования

§ 3.2. Основные конструкции языка параллельного микропрограммирования

3.2.1. Общая характеристика яз-ыка.

3.2.2. Алфавит языка.ПО

3.2.3. Клеточный массив.ПО

3.2.4. Процедуры определения координат соседей

3.2.5. Композиция клеточных массивов .ИЗ

3.2.6. Микрокоманды

3.2.7. Микропрограмма.

3.2,.8. Микропрограммная модель сумматора многих двоичных чисел

§ 3.3., Реализация микропрограммных моделей на ЦВМ

Выводы к третьей главе

Глава 1У. Аппаратная интерпретация параллельных микропрограмм

§ 4.I., Реализация сетей автоматов, интерпретирующих параллельные микропрограммы

§ 4.2. Кодирование параллельных микропрограмм

§ 4.3. Варианты реализации элементарных автоматов

Выводы к четвертой главе

Развитие технологии обеспечило создание программируемых и перепрограммируемых ПЗУ,-ШШ, вентильных матриц и привело к интенсивным разработкам ассоциативных структур типа памяти с логикой

I, 2] ; вычислительных структур для обработки сигналов и изображений [3, 4J , сортировки [s] , быстрой арифметики [б, ?] ; микропроцессорных систем .[8, э] ; систолических матриц [l0, II] ; коммутационных структур [12] ; асинхронных устройств управления

13, 14, 15] и т.д. Все эти устройства состоят из множества одинаковых достаточно простых вычислителей, проблемно-ориентированы и эффективны при узкой специализации. Их называют однородными вы£ числительными структурами.

У данного класса - две характерные грани. В рамках концепции вычислительных сред (СБИС однородной структуры, способной настраиваться тем или иным способом на реализацию любого алгоритма [16, 17J ) такие устройства можно определить как специализированные вычислительные среды. С другой стороны эти устройства можно рассматривать как модули нижнего уровня вычислительных систем, поскольку существует тенденция аппаратной реализации достаточно сложных функций в современных системах, а'также стремление снабдить мощные системы наборами специализированных устройств (спецпроцессоров) „строить системы в виде иерархической совокупности специализированных модулей [18, 19] .

Для однородных вычислительных структур частично или полностью характерны следующие черты.

1. Параллельность обработки, проникающая на самые низкие уровни выполнения операций„ вплоть до элементарных операций.

2. Децентрализация функций памяти, управления и преобразования информации: часто возможно только условное (но не пространственное) их разделение. Например, микропрограммное управление сочетаем в cede память и управлением ассоциативный процессор - память и преобразование.

3. Структурная и функциональная перестраиваемость, позволяющая получать разные специализированные конфигурации на основе одного е того же оборудования. Структурная перестройка представляет собой один из основополагающих принципов концепции вычислительных сред. Типичное проявление этого принципа на микроуровне -программируемые, перепрограммируемые f20, 213 и вентильные матрицы [22, 23J . Самый распространенный способ функциональной ' перестройки - микропрограммный. Микропрограммная настройка может выполняться как на этапе производства БИС, так и при их эксплуатации. Наиболее полно микропрограммирование проявляется как средство настройки и перестройки при проектировании микропроцессорных систем, в которых назначение стандартных вычислительных блоков определяется микропрограммами.

4. Широкий спектр сложностей элементов: от микропроцессора, который может выполнять достаточно сложные алгоритмы, до ячейки ассоциативного процессора, содержащего один бит памяти и несколько вентилей.

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

6. Увеличение роли микропрограммирования. Оно обеспечивает функциональную перестройку, увеличивает регулярность микроструктуры (за счет того, что основным блоком в устройстве управления делается память микропрограмм), служит инструментом проектирования и моделирования, использующим формальные методы близкие к программированию [24, 25, 26, 27] .

7. Асинхронное выполнение не только операторов алгоритма, но и элементарных операций. Это прежде всего справедливо при построении однородных структур управления [I3J .

Завершим перечисление свойств следующими замечаниями.

Не следует абсолютизировать необходимость построения полностью однородных вычислительных устройств. Действительно, даже при построении специализированного устройства реализуемый алгоритм может содержать "глобальные" операторы (операторы, использующие данные всего перерабатываемого массива). Как правило, это управляющие операторы. Реализация их в однородной структуре с локальными связями приводит к их итерационному выполнению, что уменьшает эффективность переработки информации,иногда весьма существенно. Например, вынесение за рамки однородной структуры нескольких процентов обработки информации может на порядок уменьшить общие временные затраты [283 .

Следует учитывать, что использование асинхронных принципов приводит к усложнению как устройства управления, так и управляемых элементов. Особенно сильно это проявляется при распределенном управлении, поскольку каждый элемент структуры должен быть способен сам определить свою готовность к выполнению операции и выдать сигнал о ее завершении [29, 30^ . Поэтому очень часто, при простых процессорных элементах, целесообразна синхронная реализация операторных блоков.

Учитывая эти замечания и все перечисленные свойства в комплексе, мы определим параллельную микропрограммную структуру как множество асинхронно взаимодействующих блоков, каждый из которых является однородной совокупностью синхронно действующих конечных автоматов (процессорных элементов). Блоки могут отличаться друг от друга числом процессорных элементов и их сложностью. Отдельный блок выполняет некоторый оператор, а совокупность блоков - асинхронную композицию операторов (алгоритм решения задачи).

Для такой достаточно общей трактовки специализированного вычислительного устройства параллельной обработки информации в течение ряда лет с участием автора проводятся исследования по методам синтеза, объединенные названием методы параллельного микропрограммирования DiJ .

Диссертация является частью научных исследований, выполненных в этой области.

Известны методы синтеза, разработанные для отдельных типов однородных вычислительных структур, например, параллельных арифметических блоков С бJ , цифровых интегрирующих структур [32] , ассоциативных процессоров [33] и др. В этих методах ключевым является распараллеливание .вычислений на процессорных элементах, вопросам распараллеливания управления внимание не уделяется, в следствие чего однородная структура рассматривается изолированно, вне рамок динамического взаимодействия с другими однородными автоматов, структурами. Методы не выходят за пределы классической теории^! их применение ограничено синтезом процессорного элемента.

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

Средства параллельного микропрограммирования базируются на расширенном понимании микропрограммирования. Необходимость расширения продиктована в первую очередь тем, что методы синтеза должны обеспечивать соответствие структуры устройства и функций процессорных элементов структуре информационных связей и операторов реализуемого алгоритма. Это соответствие понимается следующим образом: если операторы в алгоритме информационно независимы, то в структуре их микропрограммы выполняются параллельно. Расширение состоит в распространении идей асинхронного программирования [34, 35] на микропрограммирование. Каждый алгоритм представляется в виде некоторого неупорядоченного множества элементарных действий (микрокоманд), в котором на каждом шаге выполняются одновременно в.се действия, удовлетворяющие условиям готовности. Условия готовности определяются перерабатываемыми данными.

Методы параллельного микропрограммирования основываются на алгоритмической системе параллельного типа - алгоритмах параллельных подстановок [36, 37, 38J .

Эти алгоритмы базируются на понятиях клеточного автомата [39, 40J (параллельное и повсеместное применение локальных преобразований), нормального алгоритма [41] (операция подстановки, размеры слов в которой не фиксируются, а зависят от требуемого преобразования:)» алгоритма Колмогорова-Успенского C42J(преобразуемая информация необязательно представляется в виде линейно упорядоченного слова, а может иметь достаточно произвольную структуру).

Объектом преобразования служит клеточное множество W-конечная совокупность поименованных клеток, в которые вписаны символы из некоторого конечного алфавита состояний.

Элементарным преобразованием клеточного множества является j, операция подстановки, имеющая левую и правую части. В простейшем виде операция подстановки содержит в левой и правой части клетки с конкретными именами и состояниями. Если в клеточное множество входят все клетки левой части, то подстановка применима и часть клеток заменяется клетками из правой части. Совокупность клеток в левой части, не участвующих в замене, называется контекстом. Будем называть такую операцию подстановки элементарной операцией. В общем случае операция подстановки задает посредством конфигураций способ перечисления множества однотипных элементарных операций. Выполнение операции подстановки состоит в том, что с каждой клеткой из W связывается процедура Р , которая по имени клетки и записи конфигураций операции подстановки воспроизводит соответствующую элементарную операцию и выполняет ее, если она применима.

Совокупность операций подстановки, записанных в произвольном порядке, образует алгоритм параллельных подстановок.,

Применение алгоритма параллельных подстановок к клеточному множеству W производится следующим образом: для всех клеток из^и всех операций подстановки процедура? выполняется параллельно до тех пор, пока применима хотя вы одна элементарная операция.

Методы композиции алгоритмов параллельных подстановок целесообразно основывать на моделях асинхронных взаимодействий параллельных процессов. Известен целый ряд таких моделей £43 J . Наиболее приемлемым вариантом модели параллельных процессов является сеть Петри

44, 45.] , поскольку от сети Петри можно непосредственно переходить к ее микропрограммному описанию и условия, задаваемые маркированием сети Петри, могут быть интерпретированы контекстом в операци-ix подстановки, что обеспечивает возможность композиции алгоритмов.

Использование в качестве формальной основы параллельного микро-[рограммирования алгоритмов параллельных подстановок и аппарата се-■ей Петри позволило создать средства параллельного микропрограммирования, обладающие возможностями: а) описывать массовые преобразования информации в однородных структурах, протекающие повсеместно в пространстве и параллельно во времени; б) описывать как локальные так и глобальные преобразования информации; в) отображать произвольные структуры данных; г) записывать обычные (последовательные) микропрограммы; д) унифицировать средства для описания как управляющих действий, так и действий над данными.

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

1. Микропрограммное описание принимается первичным, и оно определяет основные параметры структуры (число блоков, объем блоков, сложность процессорных элементов, число входов и выходов процессорного элемента, тип управления и т.д.), можно говорить что получается "заказная" структура спецвычислителя.

2. Фиксируется универсальная структура (вычислительная среда, сеть из микропроцессоров и т.п.) и микропрограммное описание вычислительного процесса вкладывается в эту структуру ('Ьодгоняется" под структуру). В этом случае основная задача - представление некоторого алгоритма параллельной микропрограммой с заданными ограничениями на параметры микрокоманд.

Для решения этих задач необходимо разрабатывать методы построения, преобразования, проверки и аппаратной интерпретации параллельных микропрограмм. В этом направлении коллегами автора сделаны следующие шаги: исследованы вопросы построения непротиворечивых параллельных микропрограмм [Чб] , асинхронной интерпретации параллельных микропрограмм [47] , проверки ПГСА на корректность [48, 49 J , преобразования сетей Петри 150Л , интерпретации параллельных микропрограмм микропроцессорными системами [51] , синтеза микроструктуры микропрограммного управления [52] , структурного проектирования специализированных параллельных микропрограммных устройств [53 J . Автор диссертации занимался разработкой алгоритмической системы параллельного типа, способами асинхронной конпо-зиции параллельных микропрограмм, а также разработкой основ формальной методики проектирования микропрограммных вычислительных структур.

На защиту выносятся следующие результаты,полученные автором.

1. Алгоритмическая система - алгоритмы параллельных подстановок, как средство описания параллельных вычислительных процессов

31 стр. 16-23, 30-35; 36; 37; 38] .

2. Способы композиции алгоритмов параллельных подстановок как средство построения сложных микропрограмм с заданными свойствами из более простых микропрограмм [31 стр. 66-71; 38, 54J .

3. Методика структурного проектирования специализированных вычислительных устройств параллельной обработки информации, основанная на композиционном построении полных микропрограммных описаний

55] .

4. Язык параллельного микропрограммирования как средство описания структуры и функционирования параллельных спецвычислителей включая реализацию микропрограммных моделей спецвычислителей на ЭВМ [31 стр. II3-I44; 56 ] .

5. Аппаратная интерпретация параллельных микропрограмм в одном классе вычислительных сред [57, 58, 59] .

Весь материал диссертации распределен по четырем главам.

Первая глава посвящена вопросам композиции параллельных микропрограмм. Здесь дается развернутое определение алгоритмов параллельных подстановок, выделяется подкласс параллельных микропрограмм, проводится классификация конфигураций, из которых строятся микрокоманды. Конфигурации делятся на три типа: глобальные (в интерпретирующей микропрограмму сети автоматов существуют автоматы с числом соседей, зависящим от мощности клеточного множества), ограниченные (каждый автомат связан с числом соседей не большим заданного К-)» локальные (связи автомата с соседями не длиннее некоторого \г , Г- заданный линейный размер). Вводятся необходимые понятия и определения из теории сетей Петри и параллельных граф-схем алгоритмов (ЛГСА). Опшывается переход от любой параллельной микропрограммы к микропрограмме в канонической форме. Доказывается эквивалентность по результату исходной микропрограммы и микропрограммы в канонической форме. Доказывается возможность построения для набора микропрограмм операторов ,., и корректной ПГСА, описывающей их композицию, эквивалентный по результату параллельной микропрограммы, состоящей из управляющей микропрограммы и микропрограмм в канонической форме для операторов Показывается, что возможно построение канонических форм (а значит и композиций) с использованием в записи микрокоманд только ограниченных или только локальных конфигураций и оценивается сложность таких форм. И, наконец, излагается формальная процедура построения сети автоматов, интерпретирующей параллельную микропрограмму.

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

В третьей главе приводится описание языка параллельного -микропрограммирования. Он разработан на основе алгоритмов параллельных подстановок. Объектом преобразования в языке является клеточный массив - аналог клеточного множества. Основным элементарным преобразованием клеточных массивов является микрокоманда подстановки. Микрокоманда содержит управляющую и операционную части. Управляющая часть определяет условия применения операционной части микрокоманды. Язык предназначен для описания структуры и функционирования параллельных микропрограммных вычислителей. Описание образует микропрограммную модель проектируемого устройства.

В этой главе также излагается методика реализации микропрограммных моделей на ЭВМ. В качестве языка реализации микропрограммных моделей принят ПЛ-I. В основу методики положен принцип сборки ПЛ-ной реализации модели из стандартных заготовок по определенным правилам. Заготовки строятся на основе классификации микрокоманд подстановки по мерности клеточных массивов, типам описания топологии связей клеток и типам операционных частей.

Четвертая глава посвящена вопросам аппаратной интерпретации алгоритмов параллельных подстановок. От сети абстрактных автоматов, полученной по алгоритму параллельных подстановок, можно перейти к двум вариантам ее реализации: в виде сети из ми-кропрограммируемых автоматов, в этом случае каждый автомат содержит память микропрограмм, или в виде однородной машины, в этом случае память микропрограмм общая для всех автоматов, а сами автоматы содержат блок сравнения С37J . Реализация глубокого распараллеливания (вплоть до микрокоманд) достигается тем, что каждый элементарный автомат должен обладать способностью на каждом такте своей работы выбирать к выполнению микрокоманду из целого множества микрокоманд (обозначим его мощность буквой V ), поступающих на него одновременно или хранящихся в нем. Это приводит при использовании двоичной логики и традиционной схемотехники к М -кратному, при достаточно большом V , увеличению оборудования в каждом автомате по сравнению с тем, если бы на каждом такте работы на элементарный автомат поступала (или хранилась в нем) только одна микрокоманда. Это объясняется тем, что в V раз вырастает объем памяти микропрограмм или блока сравнения в каждом автомате. Так как мы имеем дело с построением микроструктуры, то такой рост приводит к пропорциональному росту объема оборудования всего вычислительного устройства. Поэтому весьма важно найти способы сокращения объема оборудования при сохранения параллелизма. В связи с этим предлагаются варианты вычислительных сред и кодирования микрокоманд в многозначном структурном алфавите, обеспечивающие логарифмический рост объема оборудования при линейном росте числа одновременно поступающих на элементарный автомат микрокоманд.

В заключении кратко излагаются основные результаты работы.

Основные результаты работы.

1. Заложена формальная основа перехода от алгоритма решения задачи к интерпретирующему его специализированному параллельному вычислительному устройству. Она базируется а) на алгоритмический системе параллельного типа - алгоритмах параллельных подстановок, обеспечивающих возможность построения микропрограммных описаний параллельных преобразований информации; б) методах и приемах асинхронной композиции параллельных микропрограмм; в) формальной процедуре, позволяющей по любой параллельной микропрограмме построить интерпретирующую ее сеть автоматов.

2. Предложены методы асинхронной композиции параллельных микропрограмм, опирающиеся на представление алгоритма параллельной граф-схемой. На основе сетей Петри разработана формальная процедура построения полного микропрограммного описания вычислительного процесса. Описание составляется из управляющей микропрограммы и канонических представлений микропрограмм функциональных операторов ПГСА. Доказана теорема об эквивалентности полного микропрограммного описания и исходного представления композиции.

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

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

Получены оценки сложности различных канонических форм параллельных микр опр ограмм.

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

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

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

8. Предложенная методика синтеза структур вычислительных устройств применялась на одном из предприятий г. Новосибирска и в Институте автоматики и электрометрии СО АН СССР.

Заключение.

1. Однородные микроэлектронные ассоциативные процессоры. /Под ред. И.В.Праягишвили. - М.: Сов.радио, 1973. - 280 с.

2. Фет Я.И. Массовая обработка информации в специализированных однородных процессорах. Новосибирск: Наука, 1976. - 200с.

3. Duff М.J.B., Watson D.M. The cellular logic array image processor. The Computer Journal, 1977, v.20,№1.

4. Смит Кевин. Матричный процессор, содержащий 96x96. ячеек для обработки изображений в реальном времени. Электроника,1980, т.53, № 10, с.14-15.

5. Chin P.Y., Рак К.S. Past sorting algorithms on uniform ladders (Multiple shift-register loops). IFFE Trans., 1980, v. 0-29, No.7, p.618-631.

6. Карцев M.A., Брик Б.А. Вычислительные системы и синхронная арифметика. М.: Радио и связь, 1981. - 359 с.

7. Смолов В.Б., Шумилов Л.А., Зайцев Л.А. Построение матричных вычислительных устройств для выполнения операций над многочленами и элементами конечных полей (2). Электронное моделирование, 1979, № 2, с. 63-67.

8. Aspinall D. Multi-micro systems. In: Future Systems. Pt.2. Infortech. International, 1977» p. 45-62.

9. Lipovski C.J. On a varistructured array of microprocessor. -IEEE Transaction on Computers, 1977, v. C-26, No.2, p. 125138.

10. Молдован Д.И. 0 разработке алгоритмов для систолических матриц СБИС. ТИИЭР, 1983, т.71, № I, с.140-149.

11. Kung Н.Т. The structure of parallel algorithms. In: Advances in Computers. New York: Academic Press, 1980, v. 19, p. 65-112.

12. Каляев А.В. Однородные коммутационные регистровые структуры.-М.: Сов.радио, 1978. 334 с.

13. Jump J.R. Asynchronous control arrays. IEEE Transactions on Computers, 1974, vol. C-23, No. 10, p. 1020-1029.

14. Patil Suhas S. An asynchronous logic array. MAG technical memorandum 62. MIT, 1975 May, 30 p.

15. Kinniment D.J. Regular programmable control structures. -In: VLSI-81 (ed. J.P.Gray), London, Acad.Press, 1981, p.193

16. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966, - 308 с.

17. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с настраиваемой структурой (однородные среды). -М.: Энергия, 1974. -240 с.

18. Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система (концепция). Часть I. Предпосылки и направления развития архитектуры вычислительных систем. Новосибирск, 1978, - 48с. - (Пре>принт/АН СССР, Сиб.отд-ние, ВЦ; 86).

19. Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система (концепция). Часть П. Основные принципы и особенности. Новосибирск, 1978, - 51с. - (Препринт/АН СССР, Сиб. отд-ние, ВЦ; 87).

20. Овсепян Г.И., Оганян Т.А., Гончаян В.Г., Щетинин Ю.И., Митина В.А., Грачян Г.Г. Программируемые логические матрицы в электронных электрических машинах. Управляющие системы и машины, 1976, № I, с.46-49.

21. Баранов С.И., Синев В.Н. Программируемые логические матрицы в цифровых системах. Зарубежная радиоэлектроника, 1979,1. I, с. 65-82.

22. Прайост, Рао, Б л ад. Функциональная матрица, упрощающая проектирование специализированных ЭСЛ БИС. Электроника, 1979, т.52, № 4, с.34-41.

23. Поса Дж. Вентильные матрицы: современное состояние техники и технологии. Электроника, 1980, т.53, № 21, с.54-73.

24. Глушеов В.М. Теория автоматов и формальные преобразования микропрограмм. Кибернетика, 1965, № 5, с. 1-10.

25. Чу Я. Организация ЭВМ и микропрограммирование. М.: Мир, 1975. - 592 с.

26. Баранов С.Й., Марин А.В. Языки микропрограммирования. -Зарубежная радиоэлектроника, 1977, J& 6, с. 85-102.

27. Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных. Под ред. М.Брейера. М.: Мир, 1979. - 463 с.

28. Денисов В.М., Матвеев Ю.Н., Очин Е.Ф. Принципы организации систем обработки изображений на базе клеточной логики. -Зарубежная радиоэлектроника, 1984, № I, с. 3-25.

29. Rosenstiehl P., Fiksel J.R., Holliger A. Intelligent Graphs: Networks of finite automata capable of solving graphs problems. In: Graph Theory and Gomput. Ed. R.C.Reed. Acad. Press, 1972, p. 219-265.

30. Lipton R.J., Miller R.E., Snyder L. Synchronization and computing capability of linear asynchronous structures. J. of Computer and System Sciences, 1977, v.14, p. 49-72.

31. Методы параллельного микропрограммирования / П.А.Аншпев, С.М.Ачасова, О.Л.Бандаган, С.В.Пискунов, С.Н.Сергеев; под ред. О.Л.Бандаан. Новосибирск: Наука, 1981. - 180 с.

32. Каляев А.В. Теория цифровых интегрирующих машин и структур. -М.: Сов.радио, 1970. 471 с.

33. Фет Я.И. Параллельные цроцессоры в управляющих системах. -М.: Энергоиздат, 1981. 160 с.

34. Элементы параллельного программирования / В.А.Вальковский, В.Е.Котов, А.Г.Марчук, Н.Н.Миренков; Под ред. В.Е.Котова.-М.: Радио я связь, 1983. 240 с.

35. Котов В.Е., Нариньяни А.С. Асинхронные вычислительные процессы над памятью. Кибернетика, 1966, Л 3, с.64-71.

36. Корнев Ю.Н., Пискунов С.В., Сергеев С.Н. Алгоритмы обобщенных подстановок и вопросы их интерпретации. Теоретическая кибернетика: Труды семинара, вып.4, Киев, 1970, с.3-20.

37. Корнев Ю.Н., Пискунов С.В., Сергеев С.Н. Алгоритмы обобщенных подстановок и их интерпретация сетями автоматов и однородными машинами. Изв.АН СССР. Техническая кибернетика, 1971, № 6, с.131-142.

38. Коренев Ю.Н., Пискунов С.В., Сергеев С.Н. Вопросы построения алгоритмов обобщенных подстановок с выделенным констектом. -Вычислительные системы, Новосибирск, 1971, вып.47, с.117-130.

39. Codd E.F. Cellular automata. New York-London: Academic Press, 1968. - 122 p.

40. Yamada H., Amoroso S.A. Tesselation automata. Information and Control, 1969, v. 14, No.3, p. 299-317.

41. Марков A.A. Теория алгоритмов. Труды Матем.ин-та им.Стек-лова АН СССР, 1954 г., т.42, 375с.

42. Колмогоров А.Н., Успенский В.А. К определению алгоритма. -Усп.мат.наук, 1958, т.13, вып.4/82, с.3-13.

43. Lipton R.J., Snyder L., Zalzstein Y. A comparative study of models of parallel computation. In: 15th Annual Symp. on Switching and Automata Theory, 1974, p. 145-155.

44. Peterson J.L. Petri net theory and the modeling of systems. -Englewood Cliffs (N.J.): Prentice-Hall, 1981. 290 p.

45. Котов В.Е. Сети Петри. М.: Наука. Главная редакция физико-математической литературы, 1984. - 160 с.

46. Сергеев С.Н. Распознавание непротиворечивости алгоритмов стационарных подстановок. В кн.: Архитектура вычислительных систем с программируемой структурой (Вычислительные системы, вып.82). Новосибирск, 1980, с.18-25.

47. Бандман О.Л. Асинхронная интерпретация параллельных микропрограмм. Кибернетика, 1984. № 2, с.14-20, 43.

48. Анишев П.А. Один способ анализа корректности граф-схем алгоритмов. Программирование, 1981, № I, с.20-28.

49. Анишев П.А. Редуцируемость сетей Петри. Программирование, 1982, & 4, с.36-43.

50. Бандман О.Л. Минимизация сетей Петри цри синтезе асинхронного параллельного управления. В кн.: Однородные вычислительные системы (Вычислительные системы, вып.90). Новосибирск, 1982, с.3-21.

51. Сергеев С.Н. Реализация алгоритмов параллельных подстановок в микропроцессорных системах. В кн.: Вопросы теории и построения вычислительных систем (Вычислительные системы, вып.73). Новосибирск, 1978, с.25-39.

52. Бандман О.Л. Синтез асинхронного микропрограммного управления параллельными процессами. Кибернетика, 1980, № I,с.42-47.

53. Сергеев С.Н. Структурное проектирование специализированных микропрограммных устройств. В кн.: Однородные вычислительные системы (Вычислительные системы, вып.90). Новосибирск, 1981, с.64-77.

54. Бандман 0.1., Пискунов С.В., Сергеев С.Н. Синтез параллельных микропрограммных структур. Кибернетика, 1981, 5,с.48-54.

55. Бандман О.Л., Пискунов С.В., Сергеев С.Н. Применение методов параллельного микропрограммирования для синтеза структуры специализированных вычислителей. Новосибирск, 1983.31 с. (Препринт/Институт математики СО АН СССР, JS 35 (0BC-I8) ).

56. Пискунов С.В. Язык мивропрограммного описания моделей однородных параллельных вычислительных устройств. В кн.: Архитектура вычислительных систем с программируемой структурой (Вычислительные системы, вып.82). Новосибирск, 1980,с.26-40.

57. А.С. I 664168 (СССР). Вычислительная однородная структура Д).Н.Корнев, С.В.Пискунов. Опубл.в Б.И., 1979, № 19.

58. A.C.J& 805301 (СССР). Вычислительная однородная среда/ С.В.Пискунов. Опубл.в Б.И., 1981, Ш 6.

59. Пискунов С.В. Однородная вычислительная структура из многозначных ячеек,реализующая алгоритмы параллельных подстановок. В кн.: Однородные вычислительные системы (Вычислительные системы, вып.90). Новосибирск, 1982, с.119-131.

60. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия, 1974. - 216с.

61. Rumbaugh J. A data flow multiprocessor. IEEE Transactions on Computers, 1977, v. C-21, No.2, p. 138-147.

62. Бандман О.Л., Пискунов С.В., Сергеев С.Н. Задачи параллельного микропрограммирования. В кн.: Вопросы теории и построения вычислительных систем (Вычислительные системы, вып.73). Новосибирск, 1978, с.3-24.

63. Howard. B.V. Parallel computation schemata and their hardware implementation. Digital Processes, 1975, v.1, No.3, p. 183-192.

64. Landweber L.H., Robertson E.L. Properties of conflictfree and persistent Petri nets. Journal of Association for Computing Machinery, 1978, v. 25, No.3, p. 352-364.

65. Hack M. Analysis of production schemata by Petri nets. MAC TR-94. Cambridge (Mass.): M.I.T. Project MAC, 1972.- 119 p.

66. Ачасова G.M. Анализ асинхронной интерцретации параллельных микропрограмм. В кн.: Однородные вычислительные системы из микро-ЭВМ (Вычислительные системы, вып.97). Новосибирск, 1983, с.28-52.

67. Однородные структуры. Анализ. Синтез. Поведение /Варшавский В.й., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. -М.: Энергия, 1973. 150 с.

68. Horowitz, Zorat A. The binary tree as an interconnection network. Applications to multiprocessor systems and VLSI.- IEEE Transaction on Computers, 1981, vol. C-30, No.4, p. 247-253.

69. Gordon D., Koren I., Silberman G.M. Embedding tree structures in VLSI hexagonal arrays. IEEE Transaction on Computers, 1984, vol. C-33, No.1, p. 104-107.

70. Grasselli A. Synchronization of cellular array: the firing squard problem in two dimensions. Information and Control, 1975, 28, p. 113-124.

71. Фаддеева B.H., Фадцеев Д. К. Параллельные вычисления в линейной алгебре. Кибернетика, 1977, И 6, с.28-40.

72. Nishitani У., Honda N. The firing squard synchronization problem for graphs. Theor. Сотр. Sci., 1981, v. 14, No.1, p. 39-61.

73. Ckott P., Сондак H. Ш/I для программистов. M.: Статистика 1977. - 223 с.

74. А.С. № 436350 (СССР). Двоичный сумматор / Ю.Н.Корнев, С.В.Писвунов, С.Н.Сергеев. Опубл.в Б.И., 1974, № 26.

75. Дцрег.-гор-заучный руководитель /НЕЙ измерительных приборов ■ -' кандидат те^з^тескЕХ наук• : ч, • •1. А 1С Т'о внедрении результатов диссертационной • работы ШСКУЯОВА СеВ^

76. По характеру репаекых задач и условия?.! эксплуатации епецвнчЕС-лег ель долкен обеспечивать обработку с интенсивностью 10* 20 мега-ба:гг/сек?: Требуемая производительность вычислителя в наиболее слоеном pe5.is.ie отработки составляет 250 * 10 опер/сек

77. Работа прово дптся в соответствии с приказом-распоранением СО АН СССР II Министерства от 7.12,79г. и 21.12.79г. .©47/15000-952.

78. Начальник отдела-кандидат технических наукk.b.LiTaiDK

79. СПРАВКА об использовании результатов диссертационной работы С.З.Пиекунова при выполнении хоздоговорной работы по теме "Процессор-1".

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

81. Зав.лабораторией 1-2 ИАиЭ СО АН СССР д.ф. м.н.1. Старший научный сотрудникк. 11'.- м.н.1. В.К.Малиновский1. Э.Г.Косцов