Tuillet

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К настоящему времени разработан теоретический аппарат для описания и изучения апериодических схем и асинхронных процессов [6, 25, 29, 34, 36, , 52, 53, 58, 62, 64, 71, 72, , , , 97, , III-II7, I2I-I24, , , J , решены некоторые проблемы их синтеза [, 9, II, , 33, 54, 64, 66, 72, 74, 75, 77, 78, , 98, 99, , , ПО, , J , и анализа [4, 33, 35, 64, 74, 80, , , , , ] .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

г. ;

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

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

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

г. ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Параллельно с указанными работами сотрудниками группы вычислительных структур Массачусетского технологического института - seafoodplus.infoером, seafoodplus.info, seafoodplus.infoом, seafoodplus.infoм и др. [, ] , сотрудниками отдела автоматики Центра авиационных и космических исследований в Тулузе - seafoodplus.infoом, seafoodplus.info, seafoodplus.info, seafoodplus.infoром, seafoodplus.infoо, seafoodplus.infoм [91, 97, ] и сотрудниками группы seafoodplus.infoского [6, 33, 72, 79] развивались методы аппаратной реализации в классе апериодических схем параллельных асинхронных процессов, заданных различными языками: сетями Петри, сигнальными графами, параллельными граф-схемами алгоритмов.

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

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

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

Zi 2c s \

Ri St

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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