Анализ апериодических схем и асинхронных процессов тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Мамруков, Юрий Викторович

• Мамруков, Юрий Викторович
• кандидат технических наук
• 1984

Оглавление диссертации кандидат технических наук Мамруков, Юрий Викторович

Введение.

1. Обзор работ по анализу.апериодических схем.и. асинхронных процессов .ц

T.I. Анализ апериодических схем.ц

1.2. Анализ асинхронных процессов.

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

Краткие выводы к разделу I.

2. Анализ апериодических схем.

2.1. Основные понятия и определения

2.2. Полный анализ апериодических схем

2.3. Анализ рабочего множества схемы *.«»««««*««

2.4. Преобразование схем.

Краткие выводы к разделу 2 .jgj

3. Анализ асинхронных процессов .Юз

3.1. Основные понятия и определения.ЮЗ

3.2. Анализ сетей Петри .щ

3.3. Способ представления сетей Петри, .цд

Краткие выводы к разделу

41. Автоматизация анализа асинхронных схем и процессов

Ф'.Г, Архитектура системы автоматизации анализа. . асинхронных схем и процессов.

4».2. Организация информационных обменов в системе . 133 41.3. Организация формульных, и, табличных. преобразований булевых функций .;.

-.Краткие выводы.к,разделу.4, ,,,.,,,,.,,. jgj

Введение диссертации (часть автореферата) на тему «Анализ апериодических схем и асинхронных процессов»

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

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

-Преимущества подкласса асинхронных схем - апериодических схем [6] , основанных на идее индикации моментов окончания переходных процессов в схеме (самосинхронизации, работе в "запрос-ответном" режиме), по сравнению с традиционной схемотехникой выражаются в следующем:

- возможности реализации параллельно протекающих асинхронных процессов, в том числе конвейерных ;

- повышенное быстродействие за счет работы по реальным задержкам элементов ;

- возможность организации саморемонта л резервированных системах за счет локализации константных дефектов на уровне ТЭЗов (в силу самодиагностических свойств апериодических схем) ;

- блокировка распространения ошибочной информации за счет останова схемы при дефектах ;

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

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

- ослабление технологических требований при производстве БИС и СБИС (в частности, на разбросы задержек электронных компонент) ;

- упрощение процесса настройки ;

- существенно более простая контрольно-проверочная аппаратура [6, 15-18] .

Эти преимущества во многих случаях вполне компенсируют недостатки, присущие апериодической схемотехнике: полутора-двукратный расход оборудования (при использовании ИМС малой степени интеграции) ;

- более сложные процедуры синтеза и анализа.

Отметим также, что рост степени интеграции ИМС приводит к увеличению отношения величин задержек в связях к величинам задержек активных компонент [60, 68, 125, 126j . Это приводит к трудностям при синхронизации: фронты синхросигналов начинают "расползаться" за счет неодинаковых задержек активных компонент и различной длины связей. Фактически СБИС можно разделить на ряд эквипотенциальных (эквихронных) зон [96, 125, 12б] , в пределах которых можно в той или иной степени пренебрегать задержками распространения сигналов по проводам, а взаимодействие между этими зонами организовать по "запрос-ответному" интерфейсному принципу [7, 56, 57J .

К настоящему времени разработан теоретический аппарат для описания и изучения апериодических схем и асинхронных процессов [6, 25, 29, 34, 36, 39-42, 52, 53, 58, 62, 64, 71, 72, 82-87, 90-92, 93-95, 97, 106-109, III-II7, I2I-I24, 127, 128, 130J , решены некоторые проблемы их синтеза [5-7, 9, II, 16-19, 33, 54, 64, 66, 72, 74, 75, 77, 78, 81-87, 98, 99, 100, 102, ПО, 118, 120 J , и анализа [4, 33, 35, 64, 74, 80, 82-87, 101, 103-105, 119, 129 ] .

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

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

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

Достижение поставленной цели предусматривает решение следующих задач:

- исследование свойств полумодулярных асинхронных логических схем (апериодических схем) ;

- разработку методов анализа асинхронных схем на полумодулярность ;

- разработку методов анализа асинхронных процессов, представленных сетями Петри ;

- создание системы автоматизации анализа асинхронных схем и процессов.

Методы исследования базируются на общей теории автоматов и вычислительных алгоритмов [12, 13, 20-24, 26, 29-32, 37, 43, 44, 50, 58, 59, 61, 63, 66, 69, 70, 88, 89] и используют результаты теории полумодулярных схем [53, 114, 115, 117] , теории апериодических автоматов [6J , формальные модели поведения дискретных систем: асинхронный процесс, сети Петри, сигнальные графы, модель Маллера и др. [9 , 34 , 39 , 41, 42, ИЗ, 117, 121, 123 J , а также результаты и опыт, накопленные к настоящему времени в области создания систем автоматизации проектирования [ 1-3, 27, 51, 67] .

Научная новизна проведенных исследований состоит:

1) в теоретическом обосновании методов анализа асинхронных схем на принадлежность их различным подклассам схем, не зависящих от скорости ;

2) в теоретическом обосновании метода преобразования асинхронных с целью сокращения их размерности и сложности анализа ;

3) в создании методов анализа асинхронных процессов, представленных сетями Петри на достижимость, ограниченность, безопасность и устойчивость ; разработке языка описания сетей

Петри, допускающем их строчное представление ;

4) в создании системы автоматизации анализа асинхронных схем и процессов, допускающей как пакетную, так и диалоговую работу, обеспечивающей независмостъ прикладного программного обеспечения системы от состава и характеристик периферийного оборудования ЭВМ, легкую адаптацию к использованию системы совместно с другими САПР.

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

6) в создании высокоэффективных алгоритмов формульных преобразований булевых функций.

Практическая ценность. В настоящей работе описана созданная автором система автоматизации анализа асинхронных схем и процессов, в которой реализованы все предложенные алгоритмы. Эксплуатация системы полностью подтвердила правильность теоретических выводов работы. Система реализована на ЕС ЭВМ в ОС ЕС на языках ПК/1 (оптимизирующий транслятор) и Ассемблер. Достигнутые параметры таковы, что даже на младших моделях ЕС ЭВМ возможно эффективное решение практических задач проектирования апериодических схем и асинхронных процессов. Это позволяет повысить качество проектирования, снизить затраты на разработку и создание апериодических схем.

Внедрение результатов работы. Описанная в работе система автоматизации анализа асинхронных схем и процессов внедрена на промышленном предприятии, где применялась при создании отказоустойчивой специализированной ЦВМ, а также используется в работах, проводимых в ЛЭТИ им. В.И.Ульянова (Ленина) в соответствии с планом НИР.

Апробация работы. Основные положения работы докладывались и обсуждались на

1) Республиканском семинаре "Теория автоматов и ее приложения" в Институте кибернетики АН УССР, Киев, 1979 г. ;

2) постоянно действующем семинаре "Теория автоматов" секции вычислительной техники НТО РЗС им. А.Попова, Ленинград,

1982 г. ;

3) Межреспубликанском совещении по децентрализованным вычислительным системам, Таллин, 1979 - 1984 гг. ;

4) УП Всесоюзной школе-семинаре по вычислительным сетям, Ереван, 1983 г. ;

5) У школе-семинаре "Интерактивные системы", Кутаиси,

1983 г. ;

6) постоянно действующем семинаре "Автоматизация проектирования электронных цепей" секции вычислительной техники НТО "Приборпром", Ленинград, 1983 г. ;

7) 1У Всесоюзном семинаре "Моделирование дискретных управляющих и вычислительных систем", Свердловск, 1984 г. ;

8) научно-технических конференциях профессорско-преподавательского состава ЛЭТИ им. В.И.Ульянова (Ленина), Ленинград, 1981 - 1984 гг.

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

I. ОБЗОР РАБОТ ПО АНАЛИЗУ АПЕРИОДИЧЕСКИХ СХЕМ И АСИНХРОННЫХ ПРОЦЕССОВ

I.I. Анализ апериодических схем

Основы теории апериодических схем были заложены Д.Маллером, который в работе [II7J ввел понятие класса асинхронных схем, не зависящих от скорости, и его подклассов: полумодулярных, дистрибутивных и последовательных схем. Этими названиями схемы обязаны структурно-алгеброическим свойствам своих кумулятивных диаграмм. Асинхронная схема в этой теории задается на множестве двоичных переменных Z* Iв виде системы булевых уравнений вида Zi in),

При этом предполагается, что переменная представляет выход /-го элемента схемы, а /< (Z) - функцию, реализуемую этим элементом. Изменения состояния выхода элемента инициируются сменой состояний его входов, являющихся выходами других элементов. В течение переходного процесса, т.е. в течение того времени, когда изменение входных сигналов, приводящее к изменению выхода, уже произошло, а значение сигнала на выходе элемента еще не изменилось, элемент считается находящимся в возбужденном состоянии, и возбужденное значение его выхода помечают "звездочкой" Я? , di в{0,1} . Таким образом, элемент в каждый момент времени может находится в одном из четырех состояний {0,0*г4г1*]л Вектор значений всех выходов элементов схемы для каждого момента времени называется состоянием схемы. .

Возможности, предоставляемые моделью асинхронной схемы, существенно зависят от принятых гипотез относительно характера паразитивных задержек схемы [5, 53, 87, 95] . Эти гипотезы различаются по трем признакам. Во-первых, по месту расположения паразитных задержек - в элементах или проводах. Во-вторых, по типу задержек - инерциальные, инерциалъные идеальные, чистые. В-третьих, по ограниченности их величин - ограниченные или неограниченные.

Однако вне зависимости от гипотез о задержках, для всех моделей асинхронных схем характерно следующее предположение о вход-выходной дисциплине: входные наборы не изменяются до тех пор, пока выходы схемы или вся схема не перейдет в устойчивое состояние, т.е. пока не выработан результат предыдущего такта работы [6, 53, 90, 130] . Очевидно, возможно лишь два способа реализации этого требования. Первый, применимый лишь в предположении ограниченности паразитных задержек схемы, заключается в том, что внешняя среда, изменив входной набор схемы, блокирует свои входы, воспринимающие значения выходов схемы, на время, равное максимальной длительности переходных процессов в схеме. Этот способ естественно назвать временным, так как его реализация связана с тактированием внешней среды с помощью тактовых генераторов или встроенных элементов задержки и существенно использует информацию о величинах паразитных задержек схемных элементов.

Второй способ, который естественно назвать логическим, заключается в том, что схема сама вырабатывает сигналы о завершении переходных процессов и, следовательно, сама может . блокировать воспринятие внешней средой неустановившихся значений своих выходов. Такой механизм будет работать при любых величинах задержек элементов и не требует учета их конкретных значений. Именно такой способ связи схемы с внешней средой был положен в основу концепции апериодических автоматов [6] .

Иными словами, совместное функционирование апериодических схем с внешней средой организовано по принципу "запрос-ответ".

В простейшем случае в таких схемах помимо информационных входов и выходов имеется пара шин управляющих сигналов - запроса & и ответа & . Инициатором перехода схемы в новое состояние является изменение сигнала Л . Этот переход завершается изменением сигнала & , после чего допускается новое изменение сигнала & , в общем случае, однако, не обязательно выделять специальные сигналы для организации такой работы. Достаточно, чтобы для каждого внутреннего состояния схемы, наборы входных и выходных сигналов разделялись на два непересекающихся класса [5, 6, 18, 33, 54, 56, 573 .

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

Явным преимуществом схем, работающих по принципу "запрос-ответ", является сохранение работоспособности при любых соотношениях быстродействия схемы и среды.

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

Модель логического элемента, отвечающего таким требованиям, изображена на рис. I.I. Она представляет собой последовательное соединение безынерционного логического преобразователя

Рис. I.I. Модель логического элемента асинхронной схемы и инерциальноы задержки Dl произвольной, но конечной величины.

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

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

Построение сложных дискретных вычислительных устройств . осуществляется, так правило, путем декомпозиции на управляющий и операционный автоматы [2, 6, 23, 43, 63] , которые в свою очередь разбиваются на достаточно мелкие блоки (модули). При этом, посредством задания упорядочения срабатывания этих блоков, описывается управляющий процесс координации их действия. Можно построить базисную логическую схему, срабатывание элементов которой соответствует томе же упорядочению, что и блоков устройства [79] (для апериодического устройства и эта схема будет апериодической).

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

Широкий класс асинхронных процессов управления удовлетворяет условию независимости от скорости [53] , и реализующие их базисные апериодические схемы должны обладать свойством полумодулярности (более подробно об этом говорится в разделе 2).

Описанная концепция апериодических автоматов, основу которой заложил Д.Маллер, в течение нескольких лет разрабатывалась самим Д.Маллером совместно с У.Бартки [117] , Р.Миллером [53, 114, 115] , а также рядом других исследователей [118, 119] . Ключевую роль в этих работах играли вопросы построения полумодулярных схем. Самим Маллером была предпринята первая попытка предложить метод синтеза полумодулярных схем, на основе "С-эле-ментов", поведение которых описывается функцией где X*,Xz - входные, а £ выходная переменная С-элемента (в отечественной литературе [6] этот элемент, благодаря своей вход-выходной характеристике, получил название гистерезисного триггера, или коротко Г-триггера ; этого, названия мы и будем придерживаться в дальнейшем изложении). Затем Г.Цеманеком £78] был описан набор блоков, в основном однотипных блокам Маллера.

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

Дальнейший прогресс в области синтеза апериодических схем был достигнут в рамках структурной модели апериодических автоматов. В [102] Д.Б.Армстронгом, А.Д.Фридменом и П.Меноном в рамках концепции традиционного асинхронного автомата была предложена модель, которая, как оказалось впоследствии, удовлетворяет определению апериодического автомата. В этой работе не был реализован механизм согласования поведения автомата и внешней среды. Кроме того, высокая сложность технической реализации предлагаемых решений практически неприемлема. В работе [130] В.И.Варшавским была предложена структурная модель апериодического автомата на основе использования в качестве элемента памяти апериодических D-триггеров. В качестве составной части эта модель содержит схему индикации, служащую для сигнализации о завершении переходных процессов в автомате. Практическая реализация этой модели не сложнее, чем реализация синхронного автомата. В работах Г72, 77 J даны не только методы синтеза всех типовых узлов автомата: элементов памяти, комбинационных схем и ицдикаторов, но и приведены схемы этих узлов на элементах промышленных серий ТТЛ ИМС. В дальнейшем в [6] была предложена другая модель апериодического автомата на базе Т-триггеров.

В работе [54] В.И.Варшавским, В.Б.Мараховским, В.А.Песчан-ским и Л.Я.Розенблюмом была разработана модель апериодического автомата с прямыми переходами. В дальнейшем эти результаты были обобщены и доказана возможность построения апериодических автоматов, работающих в кодах в изменениях [7] . Кроме того, теш же авторами был развит подход к построению апериодических интерфейсов, инвариантных к "перекосу задержек", на основе самосинхронизируюпдах кодов [56, 57] и многозначной логики.

Параллельно с указанными работами сотрудниками группы вычислительных структур Массачусетского технологического института - Ф.Коммонером, А.У.Холтом, Дж.Б.Деннисом, С.С.Патилом и др. [100, 120] , сотрудниками отдела автоматики Центра авиационных и космических исследований в Тулузе - Ж.Маршаном, Г.Гиде, Г.Тюилье, М.Бланшаром, Ж.К.Каварро, Ж.Жийоном [91, 97, 127] и сотрудниками группы В.И.Варшавского [6, 33, 72, 79] развивались методы аппаратной реализации в классе апериодических схем параллельных асинхронных процессов, заданных различными языками: сетями Петри, сигнальными графами, параллельными граф-схемами алгоритмов.

В работе [79] Б.С.Цирлиным была впервые решена задача синтеза произвольной полумодулярной схемы в практически используемом базисе - элементах И-ШИ-НЕ. Щея предложенной парафаз-ной реализации заключается в том, что каждой переменной схемы 1с ставится в соответствие триггер на элементах И-ЖИ-НЕ, с одного плеча которого снимается значение самой переменной, а с другого ее инверсии (рис. 1.2). Функции возбуждения Si и Rt подаются на .триггер в виде сокращенных д.н.ф. и таковы, что It - Si v ZiRi и Si Ri = О # при этом в транзитном состоянии.(0,0) выходы триггера не влияют на работу других триггеров.

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

В дальнейшем в работах [19, 81] была показана возможность

Zi 2c s---- \---1

Ri St

Рис. 1.2. Триггер переменной схемы при парафазной реализации парафазной реализации подкласса полумодулярных схем - дистрибутивных схем на элементах И-НЕ. Н.А.Стародубцевым [72] развиты методы реализации последовательных схем, т.е. схем, в которых в любой момент времени возбужден не более чем один элемент, на элементах И-ШИ-НЕ.

В работе Т.Накамуры и К.Утсаномия [118] предложена процедура синтеза полумодулярных схем на мажоритарных элементах, элементах И и ШИ-НЕ. К сожалению, получаемые по этой процедуре схемы не являются полумодулярными.

В.И.Варшавским, М.А.Кишиневским и Б.С.Цирлиным изучались вопросы реализации апериодических схем в "ограниченных базисах", т.е. таких, в которых накладываются ограничения на число входов элементов и на их нагрузочную способность. В работе [36] приведена конструкция, позволяющая реализовать дистрибутивные схемы на двухвходовых элементах И-НЕ (ШИ-НЕ) с нагрузочной способностью, равной двум. Таким образом, впервые для подкласса полумодулярных схем решена задача синтеза в базисе элементов с минимально возможными параметрами по входу и выходу.

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

Использование интуитивных методов в данном случае оставляет далеко позади результаты, полученные формальным путем, но одновременно требует проверки корректности реализации. Процедуру такой проверки можно назвать анализом апериодических схем. В самом деле, под задачей анализа синхронной схемы обычно понимают выявление ее семантики: вычисление функций, реализуемых схемой, нахождение реакции схемы на заданное входное воздействие, поиск входного воздействия, вызывающего заданную реакцию и др. [53, 61, 88J . Естественно, выяснение, того, что "делает" устройство, остается важной задачей анализа и для схем других типов. Однако к ней добавляется необходимость проверки ряда структурных ограничений, присущих тому или иному типу схем.

Для обычных асинхронных схем таким ограничением является отсутствие критических состояний или риска [6, 53, 85, 96] . Если отказаться от присущей обычным асинхронным схемам гипотезы о том, что переходные процессы в схеме завершаются спустя некоторое фиксированное время после установки входного набора, и считать, что схема должна быть работоспособной при любых конечных задержках элементов схемы, то условие отсутствия состязаний становится недостаточно для обеспечения корректного функционирования схем. Как уже говорилось, Д.Маллером [53, 117] было показано, что схемы, не зависящие от скорости, работоспособны при произвольных конечных задержках элементов. В таких схемах отсутствуют критические состязания. Таким образом, анализ апериодических схем должен включать в себя определение их принадлежности к классу схем, не зависящих от скорости, и его подклассам: полумодулярных, дистрибутивных и последовательных схем.

Функционирование схемы, заданной моделью Маллера, заключается в смене одного состояния другим. Этот процесс можно отразить на ориентированном графе, вершинам которого поставлены в соответствие состояния схемы, а дуга связывает две вершины CL и в , если из состояния d схема может, посредством переключения возбужденных в состоянии & переменных перейти непосредственно в состояние ^ . Такой графический способ задания схемы, предложенный Д.Маллером, получил название диаграмм переходов.

Хотя в работах Маллера анализ схем специально не рассматривался, в них были найдены формальные признаки принадлежности схем к классу схем, не зависящих от скорости, и его подклассам. Первые попытки такого анализа были сделаны в [101] . Алгоритм анализа заключался в последовательном просмотре всех путей в диаграмме переходов с одновременной проверкой сохранения возбуждения непереключившихся элементов. Однако использование не очень удачной формы представления исходных данных и сложный алгоритм делают эту процедуру малопригодной для практического использования.

Работа А.Н.Чеботарева [85] посвящена вопросам анализа асинхронных схем, а именно: построению автоматов, реализуемого схемой, в процессе чего проводится анализ риска переходов. Решаемая в этой работе задача весьма сложна, ибо включает в себя выявление всех классов эквивалентности состояний схемы (определение класса эквивалентности дается в разделе 2.1). В процессе такого анализа необходимо решать задачу прямой и обратной достижимости состояний, заключающуюся в определении состояний, в которые можно попасть из заданного. Для решения последней задачи в работе предлагается, не прибегая к непосредственному построению диаграммы переходов, оперировать с функциональной формой представления множеств состояний схемы. Если некоторое множество состояний А задано характеристической функцией ip(fi)9 то для получения характеристической функции множест-множества всех состояний, из которых непосредственно достижимы состояния множества £\ , можно в д.н.ф. заменить каждое прямое вхождение переменной 7i на ^ A (Z) , а каждое инверсное 1с - на Н7 vfilZ) . Полученное множество состояний содержит также и множество /) . (В работе [85] операция подстановки определена только для д.н.ф. однако, как легко видеть, она справедлива для любой скобочной формы, в которой операция инверсии применяется только к переменным) .

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

Б работах [74, 101] для анализа схем на полумодулярность используется частный случай общей задачи прямой достижимости - достижимость по соседям, т.е. когда два следующих друг за другом состояния отличаются значением только одной переменной, даны условия, при которых такой способ эквивалентен методу общей прямой достижимости при анализе асинхронных схем. Такая процедура в ряде слз^чаев существенно упрощает сложность решения задачи анализа асинхронных схем. Для определения соответственно предшественников и последователей множества А по соседям в [74] предложены формулы

У L2i®klz))-I(%(Z)t?c)t 1-1 п у I«ii<8fi(Z))-%(Z),H), где J- - символ двуместной операции, заключающейся.в инвертировании аргумента, представленного вторым операндом, в функции, представленной первым операндом.

Для определения множества так называемых конфликтных состояний схемы, в которых непосредственно нарушается свойство полумодулярности, там же предложена формула

V Иъ ©/. (г)) ( I jti (*i ®/j<№(h&/.■ (2), Zj»).

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

В то же время в [74] для случая, когда необходимо проанализировать поведение схемы только относительно одного начального состояния, разработана процедура анализа схемы "по слоям". Эта процедура заключается в применении формулы прямой достижимости по соседям и проверки конфликтности получаемых состояний. При этом показано, что для определения.завершения процедуры анализа достаточно хранить не все множество достижимых состояний, а только так называемый "полный слой", некоторые формальные признаки которого указаны в [74] . К сожалению, отсутствие приемлемой практической реализации этого алгоритма не дает возможности оценить, насколько его преимущества компенсируют сильное возрастание сложности из-за больших накладных расходов по формированию полного слоя. Кроме того, для некоторых типов диаграмм возможно зацикливание этого алгоритма.

В [74] рассматривались также методы анализа апериодических схем, построенных в соответствии со структурными моделями апериодических автоматов. Эти методы основаны на структурных особенностях указанных схем, которые характеризуются понятием индицируемости, и заключаются в анализе ицдицируемости в комбинационных и последовательностных апериодических схемах. Однако высокая сложность и недостаточная разработанность не позволяет использовать эти методы на практике.

В [36] помимо методов анализа схем на полумодулярность рассмотрены методы анализа на дистрибутивность. Получена формула для определения состояний, в которых нарушается дистрибутивность схемы, аналогичная формуле выявления конфликтный состояний. Введены также новые подклассы схем, не зависящих от скорости: параллельно-последовательные, бесповторные и беспетлевые. Для некоторых из этих классов схем предложены более простые процедуры анализа и синтеза. Кроме того, в этой работе рассматрены вопросы анализа схем, имеющих задержки в проводах и методы определения чувствительности схем к этим задержкам. Показано, что только маломощный, не имеющий большой практической ценности класс асинхронных схем, не зависящих от скорости, является нечувствительным к задержкам в проводах после разветвлений.

Поведение любой асинхронной схемы может характеризоваться асинхронным процессом изменения состояний элементов [9, III, 112]. Следовательно, процесс ее функционирования может задаваться не только моделью Маллера, но и любой моделью параллельных процессов. В качестве таковой наибольшее распространение получила модель для описания потоков событий К.А.Петри.

В [35, ЮЗ] предложены метода анализа схем описываемых специальным подклассом сетей Петри - переключательными сетями Петри (схемными сетями Петри). Отметим однако, что такого рода представлениям схем свойственна большая сложности затрудняющая их использование на практике.

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

Оценка результатов

1. В работах [36,53,117] найдены формальные признаки принадлежности схем к классу полумодулярных, дистрибутивных, последовательных и тем самым заложены теоретические основы анализа асинхронных схем. На этой основе в [74, 101-] реализованы алгоритмы анализа схем на полумодулярность. Однако высокая сложность этих алгоритмов делает их не пригодными для решения практических задач большой размерности.

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

- 3. В работах [36, 53] показана важность исследования закономерностей зависимости работы апериодической схемы от задержек в проводах и от разброса параметров элементов. В [36]предложены методы решения этой задачи на основе некоторого преобразования схем, позволяющего учитывать лишь часть задержек, что дает сокращение размерности анализируемой схемы. Однако способ преобразования схем, сокращающий размерность ее в общем случае, не разработан.

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

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Мамруков, Юрий Викторович

163 ЗАКЛЮЧЕНИЕ

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

Эти преимущества достигаются за счет некоторой, становящейся несущественной по мере роста степени интеграции серийных ИМС,' избыточности оборудования.

Достоинства этих схем предопределяют расширение области их использования, в связи с чем возникает необходимость в совершенствовании методики их проектирования.

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

Вместе с тем к настоящему времени отсутствуют приемлемые алгоритмы анализа, пригодные для решения задач анализа широкого класса практических задач.

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

Таким образом, задачи анализа асинхронных схем и процессов взаимосвязаны, и желательно их комплексное решение.

Основные научные результаты работы состоят в следующем.

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

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

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

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

5. Предложен способ представления сетей Петри, обладающий хорошей наглядностью, компактностью и удобством использования.

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

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

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

Основные практические результаты работы состоят в следующем:

1. Создана система автоматизации анализа асинхронных схем и процессов, работающей в среде ОС ЕС ЭВМ. Основой для создания этой.системы послужили теоретические результаты, полученные в работе.

2. Создана инженерная методика логического проектирования апериодических схем, не зависящих от скорости, основанная на предложенных алгоритмах анализа апериодических схем и асинхронных процессов.и возможностях, предоставляемых системой автоматизации анализа.

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

Результаты диссертации нашли отражение в работах [38, 33, 45-49, 64J и широко использовались в практике проектирования апериодических схем, в том числе и при создании новых технических решений апериодической схемотехники,-защищенных соответствующими авторскими свидетельствами [8, 10, 28, 76 J .

Список литературы диссертационного исследования кандидат технических наук Мамруков, Юрий Викторович, 1984 год

1. Ангер С. Асинхронные последовательные схемы. М.: Наука,. 1977. - 400 с.

2. Апериодические автоматы / под ред. В.И.Варшавского.- М.: Наука, 1976. 424 с.

3. Асинхронный.регистр сдвига / В.И.Варшавекий, М.А.Кишиневский, Ю.В.Мамруков, В.Б.Мараховский и др.: Положительное решение Г.К. по делам изобретений и открытий по заявке В 35II24I/I8-24 от 16.11.82.

4. Астановский.А.Г. Апериодические вычислительные устройства. Дис. . канд.техн.наук. -.Л., 1975. - 215 с.

5. Ахо А., Хопкрофт Д}К., Ульман, да. Построение и анализ вычислительных алгоритмов. М.: 1979. - 536 с.

6. Баранов С.Н. Синтез микропрограммных автоматов, (графехемы и автоматы). 2-е изд., перераб. и доп. -JI.: Энергия, Ленингр. отд-ние, 1979. - 232 с.14'. Биркгоф Г. Теория структур. М.: Ж, 1952. - 408 с.

7. Варшавский В.И., Кишиневский М.А. Проблема арбитража в асинхронных параллельных системах.- В кн.: Методы.синтеза и планирования развития сложных систем, ч.,П: Тез докл. П Всесоюзного семинара. Ташкент,.1981, с. 122-123.

8. Варшавский В.И., Розенблюм Л.Я., Методы, устранения состязаний в.асинхронных схемах : Учеб.пособие. Л.: ЛЭТИ, 1978. -.73 с.

9. Варшавский В.И., Розенблюм Л.Я., Таубин А.Р. Полностью само.проверяемые. асинхронные комбинационные .схемы и свойство индицируемости. Автоматика и телемеханика, 1982, № 5, е., 138-146.

10. Гаврилов М.А. Теория релейно-контактных. схем. Анализ и синтез структуры релейно-контактных схем. М.-Л.: Издат. АН СССР, 1950. - 303 с.

11. Гаврилов М.А. Современные проблемы развития теории дискретных устройств. М., 1980, е.3-30.

12. Гаврилов М.А., Девятков В.В., Пупырев Е.Н. Логическое, проектирование дискретных автоматов (языки, методы, алгоритмы).- М.: Наука, 1977.,-.352 с. .

13. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. -.476 с.

14. Глушков В.М., Капитонова Ю.В., Летичевский А.А. Автоматизация.проектирования.вычислительных машин. Киев: Наукова.думка, 1975. - 321 с.

15. Головкин Б.А. Параллельные вычислительные системы.- М.: Наука, 1980. 520 с.

16. Горбатов В.А. Теория частично упорядоченных систем.- М.: Советское.радио, 1976. 336 с.

17. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. -.344 с.

18. Г-триггер / В.И.Варшавский, О.В.Маевский, Ю.В.Мамруков и др.: Положительное решение Г.К. по делам изобретений и открытий по заявке № 1429084/18-21 от 28.12.82.

19. Дийкстра Э. Взаимодействие последовательных процессов.- В кн.: Языки программирования. М.: Мир, 1972, с. 9-86.

20. Дискретная математика.и,математические.вопросы кибернетики. т.1./ Под. общей ред. С.В.Яблонского и О.БЛупанова.- М.: Наука, 1974. 321 с.

21. Закревский А.Д. Алгоритмы синтеза дискретных автоматов.- М.: Наука, 1971. 512 с.у

22. Захаров В.Н. Автоматы с распределенной памятью.- М.: Энергия, 1975. 136 с.

23. Карп P.M., Миллер Р.Е. Параллельные схемы программ.- В кн.: Кибернетический сборник. Новая серия. М., 1976, т.13, с. 6-61.

24. Кишиневский М.А., Таубин А.Р., Цирлин B.C. Сети Петри и анализ переключательных схем. Кибернетика, 1982, № 4,с. II4-II7.

25. Кишиневский М.А. Реализация и анализ апериодических схем. Дис. . канд.техн.наук. - Л., 1982. - 264 с.

26. Кнут Д. Искусство программирования для ЭВМ. т. 3. Сортировка и поиск. М.: Мир, 1978. - 844 с.

27. Котов В.Е. Теория параллельного программирования. Прикладные аспекты. Кибернетика, 1974, 16 I, с. I—16; № 2, с. I-I8.

28. Котов В.Е. 0 параллельных языках. Кибернетика, 1980, 1&.3, с. I-I2; В 4, с. 1-10.

29. Котов В.Е. Алгебра.регулярных сетей Петри.- Кибернетика, 1980, К» 5, с, 10-18.

30. Котов В.Е. Формальные модели параллельных вычислений.- В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. М.: Наука, 1982,с. 104-135.

31. Лазарев В.Г., Пийлъ Е.И. Синтез управляющих автоматов.- 2-е изд., перераб. и доп. М.: Энергия, 1978. - 408 с.

32. Логика, автоматы, алгоритмы / М.А.Айзерман, Л.А.Гусев, Л.И.Розоноэр и др. М.: Физматгиз, 1963. - 556 с.

33. Маевский О.В., Мамруков Ю.В. Некоторые вопросы построения апериодических автоматов. В кн.: Научное и космическое приборостроение. - М.: Наука, 1981, с. II9-I24.

34. Мамруков Ю.В., Розенблюм Л.Я. Система верификации протоколов диалога. В кн.: Интерактивные системы: Тез.Докл. Пятой школы-семинара, Кутаиси, 1983, с. 186-188.

35. Мамруков Ю.В., Розенблюм Л.Я. Моделирование и анализ асинхронных процессов. В кн.: Моделирование дискретных управляющих и вычислительных систем: Тез.докл. 1У Всесоюзного семинара, Свердловск, 1984, с. 64-65.

36. Мамруков Ю.В., Розенблюм Л.Я. Система автоматизации верификации протоколов обмена. Тез. докл. УП Всесоюзной школы-семинара по вычислительным сетям. ч.Ш, М. Ереван: 1983, с. 6973.

37. Мамруков Ю.В., Цирлин Б.С. Система автоматизации анализа асинхронных схем: Информационный листок № 790-82. Л., ЛенЦНТИ, 1982. 2 с.

38. Мейер Б., Бодуэн К. Методы программирования: В 2-х томах, т.1, М.: Мир, 1982. - 368 с.

39. Методология и средства проектирования СБИС / К.Ниссен. ТИИЭР, 1983, т. 71, № I, с. 81-94.

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

41. Миллер Р. Теория переключательных схем. т. 2. М.: Наука, 1971. - 304 с.

42. Модель асинхронного автомата с прямыми переходами /

43. В.И.Варшавский, В.Б.Мараховский, В.А.Песчанский, Л.Я.Розенблюм.- Автоматика и телемеханика, 1980, № II, с. II7-I23.

44. Николаенко В.Н. Реализация автомата асинхронной логической схемой. Кибернетика, 1979, JS 5, с. 21-27.56. 0 возможности реализации асинхронного интерфейса, использующего самосинхронизирующийся код с идентификатором

45. Параллельные вычислительные системы с общим управлением / И.В.Прангишвили, С.Я.Виленкин, И.Л.Медведев. М.: Энергоатомиздат, 1983. - 312 с.

46. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики (оптимизация алгоритмов диагностирования, аппаратурные средства). М.: Энергия, 1981. - 320 с.

47. Планы ВМС по разработке отказоустойчивых СБИС. -Электроника, 1979, т. 52, № 22, с. 12-13.

48. Поспелов Д.А. Логические методы анализа и синтеза схем.- 3-е изд., перераб. и доп. М.: Энергия, 1974. - 368 с.

49. Прангишвили И.В., Стецюра Г.Г. Микропроцессорные системы. М.: Наука, 1980. - 326 с.

50. Проектирование цифровых вычислительных машин:.Учеб. пособие для студентов вузов / С.А.Майоров, Г.И.Новиков, О.Ф.Немолочков и др. М.: Высш. школа, 1972. - 344 с.

51. Разработка теоретических принципов построения вычислительных и управляющих устройств и систем управления параллельными асинхронными процессами: M0-I2. Промежуточный отчет / ЛЭТИ.им. В.И.Ульянова .(Ленина) ; научный руководитель

52. Д.т.н., проф. Варшавский В.И. ; JB Г.Р.8Ю72301, Л., 1981. 163 с.

53. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.:.Мир, 1980. - 476 с.

54. Розенблюм.Л.Я., Цирлин Б.С. 0 реализации асинхронных согласованных схем. В кн.: Вопросы теории проектирования ЭЦВМ и систем обработки информации. Киев, 1976. с. 52-59.

55. Системы автоматизированного проектирования СБИС в Японии / Ц.Судо, Т.Оцуки, С.Гото. ТИИЭР, 1983, т. 71, № I, с. 159-178.

56. Скарлет Дж. Транзисторно-транзисторноые логические . интегральные схемы и их приложение. .-.М.: Мир, 1974. 288 с.

57. Стародубцев Н.А. Вопросы организации управления в, апериодических.вычислительных устройствах. Дис. . канд. тенх.наук. - Л., 1975. .-.208 с.

58. Стародубцев Н.А.Автономные антитонные последователь-ные.схемы. Изв„ АН.СССР. Техническая.кибернетика, 1981,1.4, с. I55-I6I 5, с. 87-93 6, с. 82-86.

59. Схемотехнический анализ, логическое моделирование и верификация СБИС / А.Э.Рюли, Г.С.Дитлоу. ТИИЭР, 1983, т. 71, В I, е.42-60. . .

60. Таубин А.Р. Анализ апериодических схем. Дис. . канд.техн.наук. Л., 1981. - 211 с.

61. Финкелыитейн Р.Л. Схемотехнические аспекты построения апериодических вычислительных и.управляющих устройств. Дис. . канд.техн.наук. - Уфа, 1975. - 197 с.

62. Цеманек Г. Последовательная асинхронная, логика., В кн. : Теория конечных и.вероятностных автоматов: Труды международного симпозиума ИФАК. М., 1965, с. 232-245. . .

63. Цирлин Б.С. Вопросы.синтеза апериодических схем. -Дис. ,v. кацд.техн.наук. Л., 1976. - 220 с.

64. Цирлин Б.С. Алгебра и анализ асинхронных логических., схем. Л;., 1981. - 40. (Препринт / Институт социально-экономических проблем АН.СССР).

65. Цирлин Б.С. Базисы реализации схем, не зависящих от скорости.- Известия АН СССР. Техническая кибернетика, 1981, №.3, с. I2I-I26.

66. Чеботарев А.Н. Риск в. асинхронных логических схемам. Кибернетика, 1976, Jf 4, с. 8-II.

67. Чеботарев. А.Н. Схемы и.автоматы. Кибернетика, 1976, 1Й.5, с. 5-9 ;15.5, с. 9-14.

68. Чеботарев А.Н. Декомпозиция асинхронных логических схем. -. Кибернетика,. 1978, 15 2, с. 1-9 ; JS 4, с. 6-9.

69. Чеботарев А.Н. Анализ асинхронных логических схем. -Кибернетика, 1980, 15.6. с. 14-23.

70. Чеботарев А.Н., Николаенко В.Н. Простые декомбинации асинхронных схем. Кибернетика, 1979, 15 6, с. 51-55.

71. Чеботарев А.Н. Модели асинхронных схем и задержки. -Кибернетика, 1983,.№.4, с. 32-37, 70.

72. Шоломов Л.Я. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. - 400 с.

73. Якубайтис Э.А. Синтез.асинхронных конечных автоматов. Рига: Зинатне, 1970. - 326 с.

74. Armstrong D.B., Friedman A.D., Menon P.R. Design of asynchronous circuits assuming unbounded gate delay. IEEE Trans. Comput., 1969, vol. 0-18, No. 12, p. 1110-1120.

75. Automatismes a sequences / M.Blanchard, J.C.Cavarroc, J.Gillon et al. Rapport final du contract DGRST H.7.2912/DERA. Tuillet, 1973. - 420 p.

76. Catt I. Time loss through gating of asynchronous logic signal pulses. IEEE Trans. Electr. Comput., 1966, vol. EC-15, No. 1, p. 108-111.

77. Cavarroc J.C., Blancbard M., Gillon J. An approach to the modular design of industrial switching system. Ins Proc. of Intern. Symp. on Discrete Systems, 1974, vol. 3 . Riga,1974, p. 93-102.

78. Corsini P. Self-synchronising asynchronous arbiter. -Digital Processes, 1975, vol. 1, No. 1, p. 67-73.

79. Clark B.J. Speed independent arbiter switch for digital communication networks. US Pat. No. 4251879. Offic. Gazette of the US Pat. and Trademark Office, 1981, vol. 1003, No. 3, p. 1314.

80. Dennis J.В» Modular asynchronous control structures for a high performance computer. In: Rec. of the Project MAC Cong, on Concurrent Systems and Parallel Computation. ACM. N.Y., 1970, p. 55-80.

81. Grabowski J. On the analysis of switching circuits by means of Petri nets. Elektronische Informationsverarbeitung und Kybernetik, 1978, Bd. 14, S. 611-617.

82. Hack M. Analysis of production schemata by Petri nets. Computer Structure Group, TR-94. Project MAC/M.I.T., Cambridge, 1972. - 119 P.

83. Hack M. Decidability question for Petri nets. Computer Structure Group, TR-161. Project ЩС/M.I.T., Cambridge, 1976. 197 P.

84. Holt A.W. , Commoner F. Events and Conditions. In: Record of Project MA.C Conf. Concurrent Systems and Parallel Computation, N.Y., 1970, p. 3-52.

85. Irani K.B., Zervos C.R. Modelling of conflicts, priority hierarchies and reentrancy in concurrent synchronization structures. In: Proc. Int. Conf. Parallel Proc., Tampa Fla. N.Y., 1979» Р- 169-204.

86. Jones N.D., Landweber L.H., Lion Y.E. Complexity of some problems on Petri nets. Theoretical Computer Sci., 1977» vol. 4, No. 3, P. 277-299.

87. Jump J.R., Thiagarajan P.S. On the interconnection of asynchronous control structures. J. of ACM, 1975» vol. 22, No. p. 596-612.

88. Kasai Т., Miller R.E. Homomorphisms between models of parallel computation. J. Computer and Systems Sci., 1982, vol. 25, No. J, p. 285-331.

89. Keller R.M. Toward a theory on universal speed independent modules. IEEE Trans. Comput., 1974, vol. C-23, No. 1, p. 21-23.

90. Keller R.M. A fundamental theorem of asynchronous parallel computation. Lecture Notes in Computer Science, 1975, vol. 24, p. 102-112.

91. Marked directed graphs / F.Commoner, A.Holt,S.Even, A.Pnueli. J. of Computer and Systems Sci., 1971, vol. 5, No. 5, P. 511-523.

92. Miller R.E., Yap C.K. On formulating simultaneity for studying parallelism and synchronization. In: Conf. Rec.lOth Annual ACM Symp. Theory Comput , San Diego, 1978; N.Y., 1978, p. 105-113.

93. Miller R.E. An introduction to speed independent circuit theory, н In: Proc. of the Second Annual AIEE Symp. on Switching Circuit Theory and Logical Design, Detroit, 1961; N.Y., 1961, p. 87-93.

94. Misunas D. Petri speed independed design. Comm. ACM, 1973, vol. 16, No. 8, p. 474-481.

95. Muller D.E., Bartky W.S. A theory of asynchronous circuits. Annual of Computation Lab. of Harvard Univ., 1959, vol. 29, p. 204-243.

96. Nakumura Т., Utsunomiya K. On a universal design procedure to realise the semimodular state transition graph.

97. Digital Processes, 1977, vol. 3, No. 3, p. 237-257.

98. Nozaki A. Hazard analysis of asynchronous circuits in Muller-Bartky*s sense. J. of Computer and Systems Sci., 1976, vol. 13, No. 2, p. 161-171.

99. Patil S.S. Circuit implementation of Petri nets. -Сотр. Structure Group, Memo-73. Project MAC/M.I.T., Cambridge, 1972. 14 p.

100. Peterson J.L. Petri nets. Computing Surveys, 1977, vol. 9, N0. 3, p. 223-252.

101. Peterson J.L. A note on colored Petri nets. Inform. Process. Lett., 1980, vol. 11, No. 1, p. 40-43.

102. Petri C.A. Kommunication mit Automaten. Schriften des Rhinich-Westfalischen ftir Instrumentalle Matbematikan der Univ. Bonn. - Bonn, 1962.

103. Petri C.A. Concepts of net theory. In: Mathematical foundations of computer science: Proc. of Symp. and Summer School. High Tatras, 1973, P« 137-146.

104. Seitz C.L. Self-timed VLSI Systems. In: Proc. of the Caltech Conference on Very Large Scale Integration, Pasadena,1979, p. 345-355.

105. Stucki M.J., Cox J.R. Synchronization strategies. -In: Proc. of the Caltech Conference Very Large Scale Integration, Pasadena, 1979, p. 375-393.

106. Valette R. Analysis of Petri nets by stepwise re-feinements. J. of Computer and Systems Sci., 1979, vol.18,1. No.l, p. 35-46.

107. Varsbavsky V.I., Rosenblum L.Ya. Dead-beat automata and asynchronous parallel processes control. In: Preprints of the 1st IFAC-IFIP Symp., SOCOCO-76, Tallinn, 1976, p. 161-164.