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

• Веселов, Алексей Аркадьевич
• доктор технических наук
• 2006

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

Введение

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

1.1. Цифровая электронная техника, ее особенности и тенденции развития

1.1.1. Цифровая аппаратура, состояние и тенденции развития.

1.1.2. Элементная база.

1.1.3. Особенности поведения объектов цифровой техники.

1.1.4. Технология конструирования

1.2. Средства моделирования объектов цифровой и вычислительной техники.

1.2.1. Роль и место моделирования в общем процессе конструирования.

1.2.2. Особенности моделирования дискретно-событийных систем.

1.2.3. Основные модели

1.2.3.1. Конечные автоматы

1.2.3.2. Язык конструирования и моделирования высокого уровня VHDL.

1.2.3.3. Сети Петри

1.2.3.4. Диаграммы состояний.

1.2.3.5. Процессы интерактивного взаимодействия.

1.2.3.6. Язык синхронизации Esterel.

1.2.3.7. Язык описания спецификаций SDL.

1.2.3.8. Синхронный информационный поток.

1.2.3.9. Модели потоков данных и управления.

1.2.3.10. Графы переходов.

1.2.3.11. Универсальные языки.

1.3. Методологии проектирования, ориентированные на использование моделей

1.3.1. Методики проектирования неоднородных систем.

1.3.2. Универсальные методики.

1.4. Сети Петри.

1.4.1. Формальное представление СП.

1.4.2. Свойства сетей Петри.

1.4.2.1. Поведенческие свойства.

1.4.2.2. Структурные свойства.

1.4.3. Учет времени в сетях Петри.

1.4.4. Типовые сети Петри.

1.4.5. Основные расширения сетей Петри для моделирования средств цифровой автоматики и вычислительной техники.

1.5. Проблема сложности и способы ослабления ее влияния.

1.5.1. Общие концепции пространства состояний.

1.5.2. Абстракции, связанные с понятием состояний и переходов.

1.5.3. Методические основы исследования пространства состояний.

1.5.4. Передовые методы борьбы с проблемой сложности.

1.5.4.1. Методы, основанные на предварительной обработке.

1.5.4.2. Методы, использующие упакованные пространства состояний.

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

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

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

Сети Петри (СП), предложенные для изучения поведения параллельных автоматов, очень хорошо подходят для моделирования дискретно-событийных систем. С момента своего появления они получили необычайно широкое распространение среди исследователей, определенное, главным образом, их простотой, наглядностью и хорошо развитым математическим аппаратом для формального представления, имитационного моделирования и анализа моделируемых дискретных систем. В настоящее время СП эффективно применяются при моделировании систем в самых различных областях человеческой деятельности, в том числе и для моделирования средств цифровой схемотехники. С этой целью используются как классические СП, так и специально разработанные расширения. В разработку и совершенствование теории СП и вопросам их практического применения для моделирования средств цифровой и вычислительной техники большой вклад виесли работы таких ученых как Hariel D., Cortadella, Esparza, McMillan, Milner, Ангер С., Варшавский В.И., Яковлев А.В., Кишиневский М.А., Закревский А.Д. и др. В результате было предложено множество новых средств, позволивших создать более эффективные и совершенные модели. Например, такие как ингибиторные, оценочные, схемные, операционные СП, графы операций и многие другие.

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

Существует и другая, не менее важная проблема, непосредственно связанная с использованием моделей при проведении аналитических исследований характеристик и свойств моделируемых объектов. Это проблема сложности. Суть этой проблемы заключается в том, что в основе преобладающего большинства методов, связанных с анализом поведения моделей, используется граф достижимых состояний или граф достижимости. Однако, при увеличении размера модели, количество достижимых ею состояний (то есть размер графа достижимости) возрастает еще более высокими темпами. Данное обстоятельство вынуждает использовать для этой цели только относительно простые модели. На эту тему было издано большое количество книг и монографий отечественных и зарубежных ученых, таких как (Valmari А., Мурата Т., Розенберг Г., Йенсел К., Яковлев А.В.и др.). В результате проведенных ими исследований были предложены достаточно эффективные способы, позволяющих в отдельных случаях обойти или ослабить влияние проблемы сложности. Однако, в целом важность этой проблемы не только сохраняется, но и становится все более злободневной. Такой результат, приводит к заключению о том, что многочисленные исследования, направленные на решение проблемы сложности и использующие классическую форму представления графа достижимости, по-видимому, исчерпали свои возможности. Необходим поиск новых, альтернативных средств и форм для более компактного представления пространства состояний, в которых могут оказаться моделируемые объекты.

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

В настоящее время имеется большое количество работ, в которых в разной (той или иной степени) мере отражены отдельные попытки, направленные на решение проблемы несоответствия между моделью и средствами цифровой техники. К наиболее значимым из них следует отнести работы под руководством В.И.Варшавского и А.В.Яковлева. В работах В.И.Варшавского основное внимание уделяется вопросам поиска новых схемотехнических и архитектурных решений в области вычислительной техники и дискретной автоматики и разработке теории самосихронизирующихся устройств, поведение которых не зависит от задержек ее компонентов [1]. В процессе выполнения этих работ было разработано "схемное" расширение СП, в состав которого впервые были введены и использованы соединительные дуги разрешающего типа. Предложенные Варшавским и его группой идеи получили свое последующее развитие в работах А.В.Яковлева, J.Cortadella, E.Pastor, М.А.Кишиневского, А.Р.Таубина, ЛЛ.Розенблюма и многих других [2-4]. В используемых ими новых сетевых расширениях находят уже применение не только разрешающие, но и запрещающие (ингибиторные) дуги. В результате, появились такие инструментальные средства как, например, "Petrify", позволяющее осуществлять синтез асинхронных цифровых устройств управления. По мере появления новых расширений СП, постепенно сформировался класс высокоуровневых СП. В качестве одного примеров систем, использующих этот класс СП для моделирования устройств цифровой техники можно привести систему моделирования асинхронными высокоуровневыми СП "ALPiNe" [5]. В настоящее время, среди всех известных инструментальных средств, наибольшее распространение получил программный пакет "Design/CPN" [6], на основе раскрашенных СП [7], разработанных К.Йенсеном.

Однако, в процессе выполнения этих работ, проблеме несоответствия между моделью и объектом не уделялось достаточно должного внимания. Ее решение сводилось к преимущественно количественным изменениям состава атрибутов сетевых моделей, направленных в основном на расширение их функциональных возможностей, моделирующей мощности и улучшение выразительных возможностей. Тем не менее, были получены и некоторые положительные результаты, среди которых необходимо отметить работы А.Д.Закревского и К.Йенсена. А.Д.Закревский одним из первых увидел полезность выделения из множества всех позиций в СП ее особых позиций - полюсов, соответствующих входным сигналам объекта, с помощью которых внешняя среда воздействует на объект. На основе такого подхода им была предложена операционная СП и сформулированы такие важные положения как распознаваемость множества входных воздействий и реализация распознаваемых отношений. В работах К.Йенсена впервые ощущается необходимость в преодолении уже наметившегося разрыва между большим количеством инструментальных средств моделирования и малым количеством этих же средств, нашедших свое применение в составе систем автоматизированного конструирования реальных объектов. В его системе "Design/CPN" наиболее удачно решена задача иерархического конструирования моделей. Причем особое внимание уделяется интерфейсу, ориентированному на более широкий круг пользователей, а не только на специалистов по моделированию. Подход, используемый в этом инструменте, позволил выделить особую важность процессов, характеризующих внутреннюю работу объекта, скрытую от непосредственного наблюдения, и его внешнее поведение. А использование многоуровневого представления объектов указывает на его потенциальную возможность значительно ослабить влияние проблемы сложности.

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

Проблема сложности и масштабы ее влияния были осознаны значительно раньше, чем представленная выше проблема несоответствия. Разработке мер для ее устранения или хотя бы частичного ее ослабления посвящено большое количество работ [8-28], среди которых следует выделить работы таких известных ученых как K.McMillan, J.Esparza, A.Valmari, R.E.Bryant, W.Reisig, L.M.Kristensen, E.M. Clarke. В процессе проведенных исследований постепенно были сформированы основные подходы и методы, позволяющие обойти данную проблему. В результате были разработаны достаточно эффективные средства, среди которых наибольшее распространение получили: метод исключения внутренних, ненаблюдаемых последовательностей событий ("Stuttering") [24], метод упорядоченных (устойчивых) последовательностей ("Stubborn") [25], "Unfolding", метод диаграмм бинарных решений (BDD) [26], метод вложенных графов [27], методы, основанные на композиции [28] графов. В отдельных случаях предложенные подходы, позволяют существенно облегчить процессы анализа, верификации и валидации систем значительно больших, чем при использовании классических графов достижимости [21,29-32].

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

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

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

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

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

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

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

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

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

6. Разработать и исследовать новые, более эффективные и выразительные способы представления пространства достижимых состояний моделируемых объектов, методов их построения, реализации и использования.

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

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

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

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

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

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

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

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

К наиболее существенным научным результатам относятся:

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

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

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

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

5. Методология и основные принципы построения распределенных DPN-моделей.

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

Основные положения, выносимые на защиту:

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

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

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

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

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

6. Граф достижимости с переменной структурой. Структура графа, его разновидности, свойства и особенности.

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

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

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

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

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

Основная часть диссертации состоит из 5 глав. В первой главе проводится аналитический обзор состояния развития средств цифровой автоматики и вычислительной техники, современных технологий и средств, предназначенных для конструирования, имитационного моделирования и проведения аналитических исследований их поведения. Основное внимание уделяется изучению особенностей расширений сетей Петри, наиболее часто используемых для моделирования цифровой электронной техники. Результаты анализа используются для определения основных причин и факторов, препятствующих установлению соответствия между моделью и объектом, формирования требований к новой модели и новым формам представления пространства достижимых состояний. Вторая глава включает выбор и обоснование концепции DPN-модели, которая обеспечивающая соответствие между ее позициями и физическими сигналами, характеризующими общее состояние объекта. Приводится формальное определение DPN-модели, особенности функционирования, ее структурные и поведенческие особенности. Рассматриваются возможности композиции, структурных преобразований и редукции предложенной модели. Третья глава посвящена проблеме сложности и способам ее ослабления. Предлагается несколько новых форм для отображения пространства достижимых состояний в виде графа достижимости с переменной структурой (ГДПС). Рассматриваются возможные разновидности ГДПС, приводятся результаты исследования их особенностей, возможности композиции, демонстрируются их достоинства и недостатки. Показана уникальная особенность ГДПС, заключающаяся в предоставлении возможности исследовать поведение моделируемых объектов, как в динамических, так и статических режимах их функционирования. В четвертой главе приводятся результаты исследований, связанных с применением DPN-моделей для распределенного моделирования и моделирования микропрограммных устройств управления. В последней, пятой главе приводится описание двух систем, разработанных на основе применения DPN-моделей, рассматриваются их возможности и области возможного применения.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Веселов, Алексей Аркадьевич

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

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

В диссертации получены следующие основные результаты.

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

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

1.2. Исследованы свойства нового расширения СП и сформулированы основные правила для выполнения структурных преобразований и редукции нового расширения сетей Петри.

1.3. Разработана методика использования DPN-расширения СП для совместного моделирования аппаратных и программных средств цифровой электронной техники

1.4. Разработаны методика построения и алгоритм функционирования распределенной DPN-модели.

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

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

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

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

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

Заключение.

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

Список литературы диссертационного исследования доктор технических наук Веселов, Алексей Аркадьевич, 2006 год

1. Казеннов Г.Г., Соколов А.Г. Принципы и методология построения САПР БИС. Автоматизация проектирования БИС. Книга 1. / Под ред. Г.Г.Казеннова. - М.: Высшая школа, 1990,- 140с.

2. Армстронг Дж. Моделирование цифровых систем на языке VHDL. Концепция моделирования на уровне ИС. Перевод с англ. Л.А.Теплицкой. / Под ред. Ю.А.Татарникова. М.: Мир. 1992.- 174с.

3. Савельев П.В., Конякин В.В. Функционально-логическое проектирование БИС. Книга 2. Автоматизация проектирования БИС./ Под ред. Г.Г.Казеннова. М.: Высшая школа, 1990. -155с.

4. Вычужанин В.В. Устройство частотомера/счетчика на ПЛИС. Приборы и системы. Управление, контроль, диагностика. 2004, №9. с.38-43.

5. Daniel D.Gajski, Frank Vahid. Specification and Design of Embedded Software/Hardware Systems. 1994.

6. S. Edwards, L. Lavagno, E. A. Lee, and A. Sangiovanni-Vincentelli. Design of Embedded Systems: Formal Models, Validation, and Synthesis. Published in: Proceedings of the IEEE, Vol. 85, No. 3, March 1997.

7. Kundig A.T., A Note on the Meaning of Embedded Systems, In Embedded Systems: New Approaches to Their Formal Description. Springer-Verlag, 1986.

8. Бадулин B.H., Барнаулов Ю.М., Бердышев B.A. и др. Автоматизированное проектирование цифровых устройств. /Под ред. Бадулина С.С. М.: Радио и связь, 1981. - 240с.

9. Голдеуорт Б. Проектирование цифровых логических устройств: Пер. с англ./ Под ред. Ю.И. Тютчева. М.: Машиностроение, 1985. - 288с.

10. Угрюмов Е.П. Проектирование элементов и узлов ЭВМ. -М.: Высшая школа, 1987. -318с.

11. Савельев А.Я. Прикладная теория цифровых автоматов. -М.: Высшая школа, 1987. -272с.

12. Автоматизированное проектирование цифровых устройств. / Под ред. С.С.Бадулина. -М.: Радио и связь. 1981.

13. D.Coelho "HELIX, A Tool for Multi-Level Simulation of VLSI Systems"/ International Semi-Custom 1С Conference, November, 1983.

14. Fichtner W., Design of VLSI Systems, In Embedded Systems: New Approaches to Their Formal Description and Desigh. Kundig A., Buhrer R.E., Dahler J.(Eds) LNCS 284, Springer-Verlag, 1986.

15. Benders L.P.M, Analysis of Real-Time Embedded Systems for Co-Design, Sixth IEEE International Workshop on Rapid System Prototyping, ISBN 0-8186-7100-9, 1995.

16. Berry J., Courone P., Gonthier G., The Synchronous Approach to Reactive and Real-Time Systems. IEEE Proceedings, 79, September, 1991.

17. Robert Esser.An Object Oriented Petri Net Approach to Embedded System Design, A dissertation Swiss Federal Institute of Technology, Zurich. 1996.

18. IEEE Inc., N.Y., IEEE Standard VHDL Language Reference Manual. 1988.

19. D.Tomas, P.Moorby, The Verilog Hardware Description Language. Kluwer Academic Publishers, 1991.

20. F.Boussinot, R.De Simine, "The ESTEREL language," Proc. Of the IEEE, vol.79, no. 9, 1991.

21. D.Harel, "Statcharts: A visual formalism for complex systems," Sci. Comput. Program. Vol. 8, pp 231-274,1987.

22. S.Narayan, F.Vahid and D.Gajski, "System specification with the SpecCharts language," in IEEE Design & Test of Computers, Dec. 1992.

23. CCITT Recommendation Z.100: Specification and Description Language SDL (Blue Book), General Secretariat Place des Nations, CHI 211 Geneva 20,1988.

24. P.Hilinger and J.Rabey, Anatomy of a Silicon Compiler. Kluwer Academic Publisher, 1992.

25. C-T.Hwang, J-H Lee, and Y-C Hsu, "A Formal Approach to the Scheduling Problem in High Level Synthesis", Vol.10, No.4, pp.464-475, April, 1991.

26. D.Hariel, H.Lachover, A.Naamad, A.Pnueli, M.Politi, R.Sherman, A.Shtull-Trauring, and M.Trakhtenbrot. "Statemate: A working environment for the development of complex reactive systems," IEEE Trans, on Software Engeneering, vol.16, no.4, Apr. 1990.

27. D.Drusinski and D.Hariel. "On the power of bounded concurrency. 1. Finite automata.," Journal of the Association for Computing Machinery, vol.41, no.3, pp.517-539, May 1994.

28. M.Chiodo, P.Giusto, H.Hsich, A.Jurecska, J.Lavagno. and A.Sangiovanni-Vincentelli, "A formal methodology for hardware/software codesign of embedded systems," IEEE Micro, Aug. 1994.

29. J.T.Back, S.Ha, E.a.Lee, and D.G.Messerchmitt, "Ptolemy: A framework for simulating and prototyping heterogeneous systems," Int.Journal of Computer Simulation, vol.4, no.155, pp.155-182, Apr. 1994, Special issue on simulation software development.

30. W.-T.Chang, A.Kalavade, and E.A.Lee, "Effective heterogeneous design and cosimulation," in NATO Advanced Study Institute Workshop on Hardware/Software Codesign, Lake Como, Italy, June 1995.

31. Jr C.N.Coelho and G.De Micheli, "Analysis and synthesis of concurrent digital circuits using control-flow expressions," IEEE Trans, on CAD, vol.15, no.8, pp.854-876, Aug. 1996.

32. A.Benveniste and G.Berry, "The synchronous approach to reactive and real time systems," Proc. ofthe IEEE, vol.79, n0.9, pp.1270-1282, 1991.

33. G.Berry, "A hardware implementation of pure Esterel," in Proc. Ofthe Int. Workshop on Formal Methods in VLSI Design, Jan 1991.

34. F.Rocheteau and N.Halbwaches, "Implementing reactive programs on circuits: A hardware implementation of LUSTRE," in Real-Time, Theory in Practice, Rex Workshop Proceedings, Mook, Netherland, June 1992, vol.600 of LNCS, pp. 195-208, Springer-Verlag.

35. C.A.R.Hoar, "Communicating sequential processes," Comm.of the ACM, vol.21, no.8, 1978.

36. R.Milner, Communication and Concurrency, Prentice Hall, Englewood Cliffs, NJ, 1989.

37. Питтерсон Дж., Теория сетей Петри и моделирование систем. Пер. с англ. -М.: Мир 1984. сс. 264.

38. W.Reizig, Petri Nets: An Introduction, Springer-Verlag, 1985.

39. Трахтеиброт Б.А., Барзинь Я.М. Конечные автоматы. Поведение и синтез. М.: Наука, 1970.

40. Малышев Н.Г. Структурно-автоматные модели технических систем. М.: Радио и связь. 1986.-168с.

41. Ангер С. Асинхронные последователыюстные схемы. Перев. с англ., серия "Теоретические основы технической кибернетики". -М.: Наука, Гл. ред. Физ.-мат. лит., 1977.400 стр.

42. S. Edwards, L. Lavagno, Е. A. Lee, and A. Sangiovanni-Vincentelli. Design of Embedded Systems: Formal Models, Validation, and Synthesis. Published in: Proceedings of the IEEE, Vol. 85, No. 3, March 1997.

43. J.T.Back, S.Ha, E.A.Lee and D.G.Messershmidtt. "Ptolemy: A framework for simulating and prototyping heterogeneous systems". Int. Journal of Computer Simulation, vol.4, no. 155, pp.155-182.

44. W.-T.Chang, A.Kalavade and E.A.Lee, "Effective heterogeneous design and cosimilation", in NATO Advance Study Institute Workshop on Hardware/Software Codesign, Lake Como, Italy, June 1995. http://ptolemy.eecs.berkeley.edu/papers/eflfective.

45. D.Harel, H.Lachover, A.Naamad, A.Pnueli, M.Politi, R.Sherman, A.Shtull-Trauring and M.Trakhtenbrot. "Statemate: A working environment for the development of complex reactive systems," IEEE Trans. On Software Engineering, vol. 16, no.4, Apr. 1990.

46. IEEE, IEEE Standard VHDL language Reference Manual, Institute of Electrical and Electronic Engineers, 1988.

47. Douglas L. Perry, McGraw Hill. "VHDL", Second Edition, 1994, ISBN 0-07-049434-7

48. Лиза Мадиньяк. Моделирование систем. Высокоуровневое моделирование возможности, проблемы и перспективы. "Электроника", № 17(890), 1993. Стр.11-18.

49. Армстронг Дж. Моделирование цифровых систем на языке VHDL. Концепция моделирования на уровне ИС. Перевод с англ. Л.А.Теплицкой. / Под ред. Ю.А.Татарпикова. М.: Мир. 1992.-174с.

50. R.Esser. An Object Oriented Petri Net Approach to Embedded System Design. PhD dissertation submitted to the Swiss Federal Institute of Technology Zurich. October 1996.

51. Котов B.E. Сети Петри. -M.: Наука, 1984.

52. Tadao Murata. Petri nets: Properties, Analysis and Application. Proceeding of the IEEE, vol. 77, no. 4, April 1989. pp. 541-580.

53. Grzegorz Rozenberg, Joost Engelfriet. Elementary Net System. Lectures on Petri Nets I: Basic Models. Advanced in Petri Nets/Volfgang Reisig; Grzegorz Rozenberg(ed.). -Springer-Verlag Berlin Heidelberg New York. 1998.

54. Никонов B.B., Подгурский Ю.Е. Применение Сетей Петри. Зарубежная радиоэлектроника, №11, 1986г. (Москва "Радио и связь"), с. 17-37.

55. Варшавский В.И., М.А.Кишиневский и др. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах/ Под ред. В.И.Варшавского. -М.: Гл. ред. Физ.-мат. лит., 1986.-400 стр.

56. Лазарев В.Г., Пийль Е.И., Турута Е.Н, Построение программируемых управляющих устройств. -М.: Энергоатомиздат, 1984. 192с.

57. Бойченко Е.В. Методы схеомтехнического проектирования распределенных информационно-вычислительных микропроцессорных систем/ Под ред. В.Г.Домрачева. -М.: Энергоатомиздат, 1988. -128 с. ISBN 5-283-01487-8.

58. Слепцов А.И., Юрасов А.А. Автоматизация проектирования управляющих систем гибких автоматизированных производств/Под ред. Б.Н.Малиновского. -К.: Техника, 1986. 110 с.

59. Управление ГПС: Модели и алгоритмы/ Под общ. ред. Академика АН СССР С.В.Емельянова. М.: Машиностроение, 1987, 365 с.

60. Harel D., StateCharts: A Visual Formalism for Complex systems, Science of Computer Programming 8 (1987) 231-274 North-Holand, 1987 194 An Object Oriented Petri Nets Approach to Embedded System Design.

61. Battiston E., de Cindio F., Mauri G, OBJSA Nets: A Class of High-level Nets having Objects as Domains, in LNCS 340, Advances in Petri nets 1988, Spinger Verlag 1988.

62. Карабегов A.B., Тер-Микаэлян T.M. Введение в язык SDL. М.: Радио и связь, 1993.

63. Бардзинь Я.М., Калниньш А.А., Стродс Ю.Ф., Сыцко В.А. Язык спецификаций SDL /PLUS/ и методика его использования. Рига: ЛГУ, 1986.

64. Fisher J, Dimitrov Е. Verification of SDL'92 specifications using extended Petri nets. // Proc. IFIP 15th Intern. Conf. on Protocol Specification, Testing and Verification. Warsaw, Poland, 1995. pp. 455-458.

65. Чурина Т.Г. Способ построения раскрашенных сетей Петри, моделирующих SDL системы. СО РАН, Институт систем информатики им. Ершова. Препринт 56, Новосибирск 1998.

66. Dennis J.B., Data Flow Supercomputers, Computer, vol. 13, no. 11, November 1980.

67. Lee E.A., Consistency in Dataflow Graphs, IEEE Transactions on Parallel and Distributed Systems, vol. 2, no. 2. April 1991.

68. Кузнецов О.П. Графы логических автоматов и их преобразования // Автоматика и телемеханика. 1975, №9.

69. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.

70. Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления // Известия академии наук. Теория и системы управления, №6. 2000.

71. Ernst R., Henkel J., Benner Th., TU Braunschweig, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design and Test of Computers, 1993.

72. Edwards M.D., Hardware/Software Codesign: Experiences with Languages and Architectures, Codesign Computer-Aided Software/Hardware Engineering, Eds Rozenblit J., Buchenrieder K., IEEE Press ISBN 0-7803-1049-7, 1994.

73. Benner J., Schaub H.-C., A Prototyping System for Verification and Evaluation in Hardware/Software Cosynthesis, Sixth IEEE International Workshop on Rapid System Prototyping, ISBN 0-8186-7100-9, 1995.

74. De Micheli G., Ku D., Mailhot F., Truong Т. Stanford University, The Olympus Synthesis System, IEEE Design and Test of Computers, 1990.

75. Yourdon E., Constantine L.L., Structured Design: Fundamentals of a Discipline of Computer Program and systems Design, Prentice Hall Inc., Englewood Cliffs, 1979.

76. Booch G., Object-Oriented Analysis and Design with Applications, The Benjamin/Cummings Publishing Company Inc. Redwood City, Calif. 1994.

77. Selic, GuIIekson, Ward, Real-Time Object-Oriented modeling. Wiley ISBN 0-471-59917, 1994.

78. Rumbaugh J.Blaha M., PremerlaniW., Eddy F., Lorensen W., Object-Oriented Modeling and Design, Prentice Hall, 1991.

79. Jacobson I., Object-Oriented Software Engineering. A Use Case Driven Approach, Addison-Wesley, 1992.

80. G.Rozenberg, P.S.Thiagarajan; Petri nets: Basic notions, structure, behavior, in Current Trends in Concurrency (J.W.de Bakker, W.-P.de Roever, G.Rozenberg, eds.), Lecture Notes in Computer Science 224, Springer-Verlag, Berlin, 1986, pp. 585-668.

81. P.S.Tthagarajan; Elementary net systems, // W.Brauer, W.Reisig, G.Rozenberg, eds.; Petri nets: Central Models and their Properties, Lecture Notes in Computer Science 254, Springer-Verlag, Berlin, 1987, pp. 26-59.

82. G.Rozenberg; Behavior of elementary net systems// W.Brauer, W.Reisig, G.Rozenberg, eds.; Petri nets: Central Models and their Properties, Lecture Notes in Computer Science 254, Springer-Verlag, Berlin, 1987, pp. 60-94.

83. W.Reisig; Petri Nets, EATCS Monographs on Theoretical Computer Science, vol. 4, Springer-Verlag, Berlin, 1982.

84. HJ.Genrich; Predicate/Transition nets,// W.Brauer, W.Reisig, G.Rozenberg, eds.; Petri nets: Central Models and their Properties, Lecture Notes in Computer Science 254, Springer-Verlag, Berlin, 1987, pp. 207-247.

85. K.Lautmbach, "Liveness in Petri nets," St.Augustin, Cessellschaft fur Mathematic und Datenverarbeitung Bonn, Interner Bericht 1SF-75-02.1, 1975.

86. B.Dennis and S.S.Patil, "Speed independent asynchronous circuits," in Proc. 4th Hawaii Int. Conf. Sys. Sci., 1971, pp.55-58.

87. D.P.Misunas, "Petri nets and speed independent design," Comm. ACM 16, No. 8, 1973, pp.474481.

88. C.A.Petri, "Interpretation of net theory," St.Augustin: Gesellschaft fur Mathematic und Datenverarbeitung Bonn, Interner Bericht ISF-75-07, Second Edition, 1976.

89. E.Best, "Structural theory of Petri nets: The free choice hiatus," in Lecture Notes in Computer Science. New-York: Springer-Verlag, vol.254, 1987, pp. 168-206.

90. P.S.Triagarajan, K.Voss, "A fresh look at free choice nets," Inform. Contr., vol. 61, no. 2, 1984, pp.85-113.

91. Muller D.E. Asynchronous logics and application to information processing. -In: Proc. Symp. On Application of Switching Theory in Space Technology. Stanford, 1962, pp. 289-297.

92. Закревский А.Д. Анализ операционных сетей Петри. Минск, 1967. -24с. (Препринт/Ин-т техн. Кибернетики АН БССР, № 44).

93. Юдицкий С.А., Магергут В.З. Логическое управление дискретными процессами. М.: Машиностроение, 1987.

94. Noe Jerre D., Nutt Gary J. Macro E-Nets for Representation of Parallel Systems. IEEE Trans, on Сотр., 1973, vol. C-22, № 8, pp. 718-727.

95. А.Гультяев. Визуальное моделирование в среде MATHLAB: учебный курс. Спб: Питер, 2000. - 432 с.

96. Лазарев В.Г. и др. Построение программируемых управляющих устройств/ В.Г.Лазарев, Е.И.Пийль, Е.Н.Турута. -М.: Энергоатомиздат, 1984. 192 с.

97. Desel J., Esparza J.: Free-Choice Petri Nets. Cambridge Tracts in theoretical Computer Science 40, Cambridge University Press, 1995,244 p.

98. Reisig W.: Petri Nets, An Introduction. EATCS Monographs on Theoretical Computer Science, vol.4, Springer-Verlag, 1985, 161 p.

99. Valmari A.: "The State Explosion Problem", Lectures on Petri Nets I: Basic Models, Lectures Notes in Computer Science 1491, Spinger-Verlag 1998, pp. 459-528.

100. Б.Страуструп. Язык прграммирования С++, спец. Изд./Пер. с англ. -М.: СПб.: "Издательство БИНОМ" "Невский Диалект", 2001. - 1099 с.

101. Milner R.: Communication and Concurrency. Prentice-Hall, 1989,260 p.

102. Brookes S.D., Hoare C.A.R., Roscore A.W.: "A theory of Communicating Sequential Processes". Journal ofthe ACM, 31 (3), 1984, pp. 560-599.

103. Hoare C.A.R.: Communicating Sequential Processes. Prentice-Hall, 1985,256 p.

104. Roscore A.W.: "The Theory and Practice of Concurrency. Prentice-Hall, 1998,565 p.

105. Holzmann G.J.: Design and Validation of Computer Protocols. Prentice-Hall, 1991, 500 p.

106. S.Haddad.: "A Reduction Theory for Color Nets". Advances in Petri Nets 1989, Lecture Notes in Computer Science 424, Springer-Verlag 1991, pp.399-425.

107. S.M.Shatz, S.Tu, T.Murata, S.Duri.: "Application of Petri Nets Reduction for Ada Tasking Deadlock Analysis". IEEE Transactions on Parallel and Distributed Systems 7 (12) 1996, pp. 13071322.

108. KJensen.: Coloured Petri Nets. Vol. 2, Analysis Methods. Monographs in Theoretical Computer Science, Springer-Verlag, 1995,174 p.

109. E.A.Emerson, A.P.Silva.: "Utilizing Symmetry when Model-Checking under Fairness Assumption: An Automata-Theoretical Approach". ACM Transaction and Programming Languages and Systems, 19 (4), 1997, pp. 617-638.

110. Gyrus V., Sistla P.: "On-the-Fly Model Checking Under Fairness That Exploits Symmetry". Proc. Computer Aided Verification (CAV) '97, Lecture Notes in Computer Science 1254, Springer-Verlag 1997, pp 232-243.

111. Pastor E., Roig 0., Cortadella J., Badia R.: "Petri Net Analysis Using Boolean Manipulation." Proc. Application and Theory Petri Nets 1994, Lecture Notes in Computer Science 815, Springer-Verlag, 1994, pp. 416-435.

112. Burch J.R., Clarce E.M., McMillan K.L., Dill D.L., Hwang L.J.: Symbolic Model Checking: Ю20 State and Beyond". Information and Computation 98 (2) 1992, pp. 142-170.

113. Meinel C., Theobald.T.: "Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits". Bulletin of the European Association for Theoretical Computer Science.

114. Madelaine E., Vergamini D.: "AUTO: A Verification Tool for Distributed Systems Using Reduction of Finite Automata Networks", Proc. Formal Description Techniques II (FORTE '89), North-Holland, 1990, pp.61-66.

115. A.Valmari. "Compositional Analysis with Place-Bordered Subnets". Proc. Application and Theory of Petri Nets, 1994, Lecture Notes in Computer Science 815, Springer-Verlag 1994, pp. 531-547.

116. Valmari A.: "Failure-based Equivalences Are Faster Than Many Believe". Proc Structures in Concurrency Theory, 1995, pp. 326-340.

117. Valmari A.: "Compositionality in State Space Verification Methods". Proc. Application and Theory of Petri Nets, 1996, Lecture Notes in Computer Science 1091, Springer-Verlag 1990, pp. 29-56.

118. Godefroid P.: "Partial-Order Methods for Verification of Concurrent Systems, An Approach to the Stste Explosion Problem. Lecture Notes in Computer Science 1032, Springer-Verlag 1996, 143 p.

119. Godefroid P.: "Using Partial Orders to Improve Automatic Verification Methods". Proc. Computer-Aided Verification 90, AMS-ACM DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 3,1991, pp. 321-340.

120. Paled D.: "All from One, One for All: On Model Checking Using Representatives". Proc. Computer-Aided Verification (CAV) '93, Lecture Notes in Computer Science 697, Springer-Verlag, 1993, pp. 409-423.

121. Rauhamaa M.: A Comparative Study of Methods for Efficient Reachability Analysis. Lie. Tech. Thesis, Helsinki University of Technology, Digital Systems Laboratory, Research Report, A-14, Espoo, Finland, 1990,61 p.

122. Varpaaniemi K.: On Stubborn Set Method in Reduce State Space Generation. Ph.D. Thesis, Helsinki University of Technology, Digital Systems Laboratory, Research Report, A-51, Espoo, Finland, 1998,105 p.

123. Веселов A.A. Расширение сетей Петри для моделирования цифровой и вычислительной техники. Материалы всероссийской конференции "Перспективы развития Волжского региона ". Тверь, ТГТУ(Тверской государственный технический университет), 1999. стр. 131-134.

124. Merlin P., D.J. Faber.: Recoverability of communication protocols. IEEE Transactions on Communications, COM 24(9), 1976.

125. Kurt Jensen. Colored Petri nets. Basic concepts, analysis methods and practical use/Vol.l, Second ed. Springer-Verlag Berlin Heidelberg New York. 1997.

126. A.A.Veselov, Chirag Pathak, Edmund Kazmierczak. A new approach to the modeling and analysis of complex discrete systems. Proceedings of International conference ESMC 2003. 27-29 October 2003 in Naples.

127. Веселов A.A. Анализ поведения электронных цифровых устройств на основе графа достижимости с переменной структурой. Приборы и Системы: Управление, Контроль, Диагностика, №9,2004. СС. 19-25.

128. Веселов А.А. Расширение сетей Петри для моделирования средств цифровой и вычислительной техники.// Сборник материалов Всероссийской конференции молодых учёных Волжского региона "Перспективы развития Волжского региона". ТГТУ, 1999. с. 131-134.

129. Philip Merlin, Gregor V.Bochman. On the construction of submodule specifications and communication protocols. ACM Transactions on programming languages and systems, Vol.5, No.l, January 1983, Pages 1-25.

130. Tat Y.Choi and Raymond Miller. A decomposition method for the analysis and design of finite state protocols. ACM 0-89791-113-X/83/0010/0167, 1983.

131. С. Ангер. Асинхронные последовательностные схемы. Перев. с англ., серия "Теоретические основы технической кибернентики", Гл. редакция физ.-мат. Литературы изд-ва "Наука", М., 1977,400 с.

132. Rishinevsky M., Kondratyev A., Taubin A., Varshavsky V.: Concurrent Hardware: The Theory and Practice of Self-Timed Design. Series in Parallel Computing. John Wiley & Son, 1994.

133. Lavagno L., Sangiovanni-Vincentelli. Algoritm for Synthesis and Testing of Asynchronous Circuits. Kluwer Academic Publishers, 1993.

134. CJ.Myers, Teresa H.-Y. Meng.: Synthesis og Timed Asynchronous Circuits. IEEE Transactions on VLSI Systems, 1(2): 106-119, June 1993.

135. Nowick S.M., Coates В.: Automated design of high-performance asynchronous state machines. In Proc. International Conf. Conputer Design (ICCD). IEEE Computer Society Press, October 1994.

136. Pastor E., Cortadella J., Kondratyev A., Roig 0.: Structural Methods for the synthesis of speed-independent circuits. IEEE Transaction on Computer-Aided Design, 17(11): 1108-1129, November 1998.

137. Веселов А.А. Устройство микропрограммного управления. Авт.св. №1322281. СССР. 1987.