Содержание к диссертации
Введение
Глава 1 Аналитический обзор средств, предназначенных для функционально-логического проектирования и моделирования устройств цифровой техники 1 б
1.1.. Цифровая электронная техника, ее особенности и тенденции развития 16
1.1.1, Цифровая аппаратура, состояние и тенденции развития. 16
1.L2. Элементная база, 18
1.1.3, Особенности поведения объектов цифровой техники. 20
1.1.4. Технология конструирования 21
1.2. Средства моделирования объектов цифровой и вычислительной техники- 26
1.2.1. Роль и место моделирования в общем процессе конструирования. 29
1.2.2. Особенности моделирования дискретно-событийных систем, 31
1.2.3. Основные модели 34 1,23.1, Конечные автоматы 34
1.2.3.2. Язык конструирования и моделирования высокого уровня VHDL. 37
1.2.3.3. Сети Петри . 38
1.2.3.4. Диаграммы состояний. 40
1.2.3.5. Процессы интерактивного взаимодействия. 41
1.2.3.6. Язык синхронизации Esterel, 41
1.2.3.7. Язык описания спецификаций SDL, 42
1.2.3.8. Синхронный информационный поток. 43
1.2.3.9. Модели потоков данных и управления, 43
1.23.10. Графы переходов. 44
1.23.11. Универсальные языки, 44
1.3. Методологии проектирования, ориентированные на использование моделей 46
13.1. Методики проектирования неоднородных систем, 46
1,3.2, Универсальные методики. 49
1.4. Сети Петри. 52
1.4Л. Формальное представление СП. 54
1.4.2. Свойства сетей Петри. 58
1.4.2.1, Поведенческие свойства. 58
1.4.2.2. Структурные свойства. 60
1.4.3. Учет времени в сетях Петри, 61
1.4.4. Типовые сети Петри, 62
1.4.5. Основные расширения сетей Петри для моделирования средств цифровой автоматики и вычислительной техники . 63
1.5. Проблема сложности и способы ослабления ее влияния. 69
1.5.1. Общие концепции пространства состояний. 70
1.5.2, Абстракции, связанные с понятием состояний и переходов. 72
1.5.3, Методические основы исследования пространства состояний, 73
1.5.4. Передовые методы борьбы с проблемой сложности, 75
1.5.4.1, Методы, основанные на предварительной обработке. 76
1.5.4.2. Методы, использующие упакованные пространства состояний. 76
1.6. Основные выводы по разделу. 83
Глава 2. Разработка сетевого расширения для моделирования средств цифровой автоматики и вычислительной техники . 84
2.1, D-расширение сетей Петри. 86
2.1.1* Концепция построения. 86
2.1.2, Формальное определение. 88
2.1.3. . Правила выполнения. 89
2.2, Типовые структурные образования в D-сетях и их особенности» 91
2.3, Композиция D-сетей, 94
2.4, Редуцирующие возможности. 97
2.4.1. Замещение переходов. 98
2.4.2. Замещение позиций. 101
2.4.3. Влияние временных задержек в переходах на редуцирусмость DPN. 106
2,4.4, Пример композиции и редукции D-сетей. 111
2А5. D-сетсвые модели типовых функциональных компонентов цифровых устройств. 120
2,5, Выводы по разделу. 123
Глава 3, Разработка новых форм представления пространства достижимых состояний . 124
3.1- Граф достижимости с переменной структурой (ГДПС), 125
3.2. Неуправляемые часта ГДПС. 132
3.3. Управляемые части ГДПС 135
3.4. Значение и роль управляемых и неуправляемых частей ГДПС. 136
3.5. Структурные преобразования в ГДПС, 137
3.6. Граф достижимости устойчивых состояний. 141
3.7. Методика построения ГДПС. 151
3.8. Выводы по разделу, 154
Глава 4. Перспективные направления применения DPN-модели . 155
4.1, Разработка распределенной DPN-модели, 155
4,1.1- Существующие подходы к организации распределенных моделей. 156
4Л,2. Понятия о воздействии и взаимодействии. 158
4Л.З, Взаимодействующие объекты и их представление. 160
4.1.4. Концепция построения распределенной модели. 161
4.1.5. Структура и алгоритм функционирования распределенной модели, 163
4.2, Моделирование микропрограммируемой аппаратуры. 167
4.2.1. Особенности моделирования цифровых устройств памяти сетями
Петри. 167
4.2.2. Микропрограммные устройства управления. 170
4.3, Выводы по разделу. 172
Глава 5. Практическая реализация, Разработка систем автоматизированного моделирования и анализа поведения проектируемых цифровых устройств» 173
5.1, Система конструирования и исследования D-сетевых моделей "DPN-tool". 174
5.1.1.Структура системы.
5.1.2* Функциональные возможности.
5.1.3. Реализация DPN-модели.
5.2. Система моделирования средств цифровой электронной техники schematics",
5.2Л. Режим конструирования и редактирования схем, 5.2.2. Проведение имитационного эксперимента.
5.3. Выводы по разделу.
Заключение
Литература
- Цифровая электронная техника, ее особенности и тенденции развития
- Основные расширения сетей Петри для моделирования средств цифровой автоматики и вычислительной техники
- Типовые структурные образования в D-сетях и их особенности»
- Граф достижимости с переменной структурой (ГДПС),
Введение к работе
Актуальность проблемы. Глобальная информатизация, охватившая современное общество, обусловлена бурным развитием современных средств цифровой автоматики и вычислительной техники. Ее интенсивное распространение во все сферы человеческой деятельности настоятельно требует создания постоянно растущего количества новой, все более совершенной и самой разнообразной аппаратуры. При этом наблюдается явная тенденция к непрерывному увеличению ассортимента и сложности цифровой электронной техники при одновременном сокращении сроков разработки и ужесточении требований к качеству ее функционирования. Кроме того, становится все более заметным возрастающий интерес специалистов, занимающихся разработкой цифровой аппаратуры, к использованию в своей практической работе средств и методов имитационного моделирования, анализа характеристик и особенностей поведения объектов, которые были бы одинаково понимаемы и доступны, как специалистам по моделированию, так и специалистам по цифровой электронной технике. Быстрое и качественное проектирование и разработка цифровой аппаратуры становятся уже невозможными без использования высокоэффективных инструментальных средств, предназначенных как для проведения имитационного эксперимента, так и анализа качества функционирования сложных цифровых устройств и систем,
Благодаря особенностям функционирования, характеризующих поведение объектов цифровой техники, их принято рассматривать как дискретно-событийные системы. Для изучения систем было предложено множество моделей, наиболее известными из которых, являются: модели алгебры логики, конечные автоматы, сети Петри, диаграммы состояний, системы массового обслуживания, цепи Маркова, нейронные сети и другие.
Сети Петри (СП), предложенные для изучения поведения параллельных автоматов, очень хорошо подходят для моделирования дискретно-событийных систем. С момента своего появления они получили необычайно широкое распространение среди исследователей, определенное, главным образом, их простотой, наглядностью и хорошо развитым математическим аппаратом для формального представления, имитационного моделирования и анализа моделируемых дискретных систем, В настоящее время СП эффективно применяются при моделировании систем в самых различных областях человеческой деятельности, в том числе и для моделирования средств цифровой схемотехники. С этой целью используются как классические СП, так и специально разработанные расширения. В разработку и совершенствование теории СП и вопросам их практического применения для моделирования средств цифровой и вычислительной техники большой вклад внесли работы таких ученых как Hariel D., Cortadella, Esparza, McMillan, Milner, Ангер С, Варшавский В.И., Яковлев А.В., Кишиневский М.А., Закревский АД. и др. В результате было предложено множество новых средств, позволивших создать более зффеїспівньїе и совершенные модели. Например, такие как ингибиторные, оценочные, схемные, операционные СП, графы операций и многие другие.
Однако, несмотря на успехи, достигнутые в процессе развития СП, их практическое применение связано с рядом проблем, возникающими, в основном, при использовании этих моделей в существующих инструментальных средствах для разработки цифровой техники. Одна из них заключается в наличии слабой формальной и однозначной связи между языками, на которых осуществляется описание модели и объекта. Объясняется это тем, что совершенствование моделей происходит преимущественно в направлении расширения их моделирующих возможностей и игнорируются вопросы, связанные с их последующим использованием разработчиками реальной аппаратуры, слабо ориентирующихся в технике моделирования. Совершенно очевидно, что для представления или описания моделей, как правило, используются атрибуты и понятия необходимые только для описания наиболее общих свойств объектов. При этом многие из атрибутов, при помощи которых происходит описание реальных объектов, например, на схемном уровне, в моделях могут отсутствовать. Подобная ситуация вынуждает использовать соответствующую интерпретацию результатов моделирования с последующим их переносом на реальный объект и наоборот. Однако, часто такая интерпретация оказывается достаточно сложной или вообще невозможной операцией и, как правило, плохо поддается формализации. Другими словами, несмотря на усилия многих исследователей, проблема несоответствия между понятием модели как формального объекта и понятием дискретного устройства, впервые рассмотренная Д.Е. Маллером в рамках теории "схем", сохранилась. Это приводит к искусственному и нежелательному разделению процесса исследования моделируемого объекта на два отдельных процесса: собственно моделирования и последующей его интерпретации и переноса полученных результатов на моделируемый объект. Такая ситуация диктует необходимость либо дополнительного привлечения специалиста по имитационному моделированию, либо наличия более квалифицированного разработчика цифровых устройств, одинаково хорошо ориентирующегося как в своей предметной области, так и в области моделирования. Как показывает опыт работы многих ученых, устранить несоответствие между моделью и объектом только за счет рационального подбора атрибутов -модели не приводит к желаемому результату. Становится очевидным, что для решения этой проблемы следует учитывать не только влияние не только атрибутов, но и правил функционирования и основных положений концепций, положенных в основу построения сетевых моделей.
Существует и другая, не менее важная проблема, непосредственно связанная с использованием моделей при проведении аналитических исследований характеристик и свойств моделируемых объектов. Это проблема сложности. Суть этой проблемы заключается в том, что в основе преобладающего большинства методов, связанных с анализом поведения моделей, используется граф достижимых состояний или граф достижимости. Однако, при увеличении размера модели, количество достижимых ею состояний (то есть размер графа достижимости) возрастает еще более высокими темпами. Данное обстоятельство вынуждает использовать для этой цели только относительно простые модели. На эту тему было издано большое количество книг и монографий отечественных и зарубежных ученых, таких как (Valmari А., Мурата Т., Розенберг Г., Йенсен К., Яковлев А.В.и др.). В результате проведенных ими исследований были предложены достаточно зффеїсгивньїе способы, позволяющих в отдельных случаях обойти или ослабить влияние проблемы сложности. Однако, в целом важность этой проблемы не только сохраняется, но и становится все более злободневной. Такой результат, приводит к заключению о том, что многочисленные исследования, направленные на решение проблемы сложности и использующие классическую форму представления графа достижимости, по-видимому, исчерпали свои возможности. Необходим поиск новых, альтернативных средств и форм для более компактного представления пространства состояний, в которых могут оказаться моделируемые объекты.
В результате, слабая формальная связь между языками описания модели и объекта и проблема сложности становятся в настоящее время особенно важным фактором, который существенно ограничивает применение моделей и использование аналитических возможностей их моделирующих аппаратов. Именно поэтому решение перечисленных проблем или, хотя бы, частичное ослабление их влияния приобретает в настоящее время особо актуальное значение,
В настоящее время имеется большое количество работ, в которых в разной (той или иной степени) мерс отражены отдельные попытки, направленные на решение проблемы несоответствия между моделью и средствами цифровой техники. К наиболее значимым из них следует отнести работы под руководством В.И.Варшавского и А.В.Яковлева. В работах В.И.Варшавского основное внимание уделяется вопросам поиска новых схемотехнических и --архитектурных решений в области вычислительной техники и дискретной автоматики и разработке теории самосихронизирующихся устройств, поведение которых не зависит от задержек ее компонентов [1]. В процессе выполнения этих работ было разработано "схемное" расширение СП, в состав которого впервые были введены и использованы соединительные дуги разрешающего типа. Предложенные Варшавским и его группой идеи получили свое последующее развитие в работах А.В.Яковлева, J.Cortadella, E.Pastor, MA.Кишиневского, А.РЛаубина, ЛЛ.Розенблюма и многих других [2-4]. В используемых ими новых сетевых расширениях находят уже применение не только разрешающие, но и запрещающие (ингибиторные) дуги, В результате, появились такие инструментальные средства как, например, "Petrify", позволяющее осуществлять синтез асинхронных цифровых устройств управления. По мере появления новых расширений СП, постепенно сформировался класс высокоуровневых СП. В качестве одного примеров систем, использующих этот класс СП для моделирования устройств цифровой техники можно привести систему моделирования асинхронными высокоуровневыми СП "ALPiNe" [5]. В настоящее время, среди всех известных инструментальных средств, наибольшее распространение получил программный пакет "Design/CPN" [6], на основе раскрашенных СП [7], разработанных К.Йенсеном,
Однако, в процессе выполнения этих работ, проблеме несоответствия между моделью и объектом не уделялось достаточно должного внимания. Ее решение сводилось к преимущественно количественным изменениям состава атрибутов сетевых моделей, направленных в основном на расширение их функциональных возможностей, моделирующей мощности и улучшение выразительных возможностей. Тем не менее, были получены и некоторые положительные результаты, среди которых необходимо отметить работы А.ДЗакревского и К.Йенсена. АДЗакревский одним из первых увидел полезность выделения из множества всех позиций в СП ее особых позиций - полюсов, соответствующих входным сигналам объекта, с помощью которых внешняя среда воздействует на объект. На основе такого подхода им была предложена операционная СП и сформулированы такие важные положения как распознаваемость множества входных воздействий и реализация распознаваемых отношений. В работах К.Йенсена впервые ощущается необходимость в преодолении уже наметившегося разрыва между большим количеством инструментальных средств моделирования и малым количеством этих же средств, нашедших свое применение в составе систем автоматизированного конструирования реальных объектов. В его системе "Design/CPN" наиболее удачно решена задача иерархического конструирования моделей. Причем особое - внимаиие уделяется интерфейсу, ориентированному на более широкий круг пользователей, а не только на специалистов по моделированию. Подход, используемый в этом инструменте, позволил выделить особую важность процессов, характеризующих внутреннюю работу объекта, скрытую от непосредственного наблюдения, и его внешнее поведение. А использование многоуровневого представления объектов указывает на его потенциальную возможность значительно ослабить влияние проблемы сложности.
Явный разрыв между наличием многочисленных средств моделирования и их слабым использованием в практике конструирования реальной цифровой аппаратура становится все более ощутимым и выдвигает задачу решения проблемы несоответствия между моделью и объектом в качестве одной из первоочередных задач. В особенности это проявляется в несоответствии между состоянием физических сигналов, определяющих общее состояние объекта и маркировкой позиций в их сетевых моделях. Становится очевидным, что в каждом отдельном случае, при выборе модели для конкретной предметной области, эту задачи следует решать комплексно, путем рационального подбора не только атрибутов модели, но и ограничений на правила ее функционирования и общие концепции ее построения.
Проблема сложности и масштабы ее влияния были осознаны значительно раньше, чем представленная выше проблема несоответствия. Разработке мер для ее устранения или хотя бы частичного ее ослабления посвящено большое количество работ [8-28], среди которых следует выделить работы таких известных ученых как K.McMillan, J.Esparza, A.Valmari, R,E,Bryant, W.Reisig, LAl.Kristensen, E.M Clarke. В процессе проведенных исследований постепенно были сформированы основные подходы и методы, позволяющие обойти данную проблему. В результате были разработаны достаточно эффективные средства, среди которых наибольшее распространение получили: метод исключения внутренних, ненаблюдаемых последовательностей событий ("Stuttering") [24], метод упорядоченных (устойчивых) последовательностей ("Stubborn") [25], "Unfolding", метод диаграмм бинарных решений (BDD) [26], метод вложенных графов [27], методы, основанные ка композиции [28] графов. В отдельных случаях предложенные подходы, позволяют существенно облегчить процессы анализа, верификации и валидации систем значительно больших, чем при использовании классических графов достижимости [21,29-32], По мере появления новых результатов становится все более очевидным, что внешние сигналы объекта не характеризуют его состояния, а определяют лишь условия их смены. Такое понимание позволяет вывести внешние воздействия из состава узлов графа достижимости, --сохранив их присутствие только в описателях дуг. Кроме того, становится ясно, что внешнее поведение объекта проявляется только его реакцией на внешние воздействия в виде выходных сигналов, доступных для непосредственного наблюдения, В процессе реагирования на внешние воздействия в объекте могут происходить некоторые внутренние, переходные процессы, происходящие вне зависимости от состояния внешнего окружения и недоступные для непосредственного наблюдения. Такие переходные процессы не оказывают существенного влияния на наблюдаемое поведение объекта и характеризуют собой только особенности его конкретной реализации. Эти и другие полезные наблюдения предполагается использовать для построения новых, более компактных и выразительных форм представления пространства достижимости, использование которых позволило бы существенно расширить границы использования существующих моделей.
Таким образом, актуальность темы диссертационной работы заключается в необходимости расширения функциональных возможностей САПР за счет дальнейшего совершенствования теоретического аппарата СП и его расширений применительно к моделированию средств цифровой автоматики и вычислительной техники, а также поиска и разработки новых, более эффективных способов и форм представления пространства достижимых состояний и методов их реализации, позволяющих расширить область применения моделей и методов их анализа в САПР.
Целью диссертационной работы является расширении функциональных возможностей систем автоматизированного функционально-логического проектирования электронных устройств цифровой и вычислительной техники путем разработки, теоретического обобщения и совершенствования моделей на основе сетей Петри и методов их анализа.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Исследовать особенности технических средств цифровой электропики как объектов функционально-логического проектирования, включая используемые модели, методы анализа и тенденции их развития,
2. Разработать модель, позволяющую наиболее полно отобразить характерные особенности поведения реальных объектов цифровой и вычислительной техники и установить взаимное и однозначное соответствие между физическими сигналами, характеризующими состояние реальных цифровых устройств, и атрибутами, характеризующими состояние их моделей.
3. Разработать методы синтеза и редукции новой модели и способы их интеграции в системы функционально-логического проектирования цифровых устройств.
4. Исследовать возможности применения новой модели для описания поведения программно-управляемой аппаратуры и ее использования при построении распределенных моделей сложных иерархических цифровых систем и объектов,
5. Провести анализ методов построения и использования пространства состояний, достижимых моделируемыми объектами, путей и способов преодоления проблемы сложности и оценить перспективы их развития,
6. Разработать и исследовать новые, более эффективные и выразительные способы представления пространства достижимых состояний моделируемых объектов, методов их построения, реализации и использования.
7. Разработать методические основы построения программного обеспечения, предназначенные для реализации предложенных подходов моделирования сетями Петри в системах автоматизированного функционально-логического проектирования устройств цифровой и вычислительной техники.
8. Разработать инструментальные программные средства, предназначенные для проведения имитационного моделирования и анализа проектных решений и реализующих предложенные подходы.
Важность решения поставленных задач состоит в создании теоретической и технической базы для моделирования средств вычислительной техники и цифровой автоматики в системах их автоматизированного функционально-логического проектирования, обладающих высокими качественными и эксплуатационными характеристиками, обеспечивающими ускорение научно-технического прогресса и имеющих важное народно-хозяйственное значение.
Методы исследований. При выполнении данной работы использована методология общей теории сетей Петри, математической логики, теории автоматов, методы теории графов, теории алгоритмов, теории множеств, матриц, теории систем, информатики, автоматизации проектирования, машинной графики и теории программирования.
Исследования, результаты которых представлены в диссертационной работе, включают теоретический анализ и экспериментальное исследование особенностей поведения элементов и устройств вычислительной техники и систем управления, разработку принципиально новых подходов и методов анализа с целью улучшения их технико-экономических и эксплуатационных характеристик.
Все полученные в работе результаты были реализованы и проверены с помощью разработанной автором экспериментальной системы автоматизироваїшого моделирования и исследования качества функционирования электронных средств цифровой техники "DPNool" и "DPN-Schematic", при сопоставлении их с аналогичными результатами» полученными другими исследователями.
Научная новизна. В работе предложен и теоретически обоснован новый подход к моделированию средств цифровой автоматики и вычислительной техники сетями Петри, обеспечивающий возможность установить взаимное и однозначное соответствие между позициями модели и физическими сигналами объекта. Данный подход основан на использовании модели, представленной в виде подкласса элементарных СП, расширяющий возможности моделирования средств цифровой автоматики и вычислительной техники. Показано, что предложенная модель позволяет формальным образом различать в ней входные и выходные полюса (позиции), соответствующие входным и выходным сигналам и внутренним состояниям моделируемых объектов. Эта особенность позволяет наиболее полно использовать в ней все преимущества автоматного подхода при моделировании сложных дискретных систем.
Для изучения поведения дискретных систем предлагаются и теоретически обосновываются новые формы представления графов достижимости, определяются их основные свойства и особенности. Показано, что новая разновидность графов достижимости, представляющая собой результат дальнейшего развития понятия операционных графов, обладает значительно большей компактностью и выразительностью, чем ее классические предшественники. Для изучения поведения моделируемых объектов з установившихся режимах впервые предложено и теоретически обосновано использование графа достижимости устойчивых (статических) состояний,
К наиболее существенным научным результатам относятся:
1. Новая модель» получившая условное наименование DPN-расширения сетей Петри. Структурные и поведенческие особенности данной модели позволяют наиболее полно реализовать преимущества автоматного подхода при моделировании дискретных систем и объектов сетями Петри,
2. Теоретико-методологические основы построения, композиции, структурных преобразований, редукции и использования DPN-моделей. Методы и принципы их программной реализации.
3. - Новая форма представления графов достижимых состояний с переменной структурой и ее разновидности, позволяющие значительно расширить область применения аналитических методов для исследования поведения объектов. Основные принципы построения графов с переменной структурой и методы их использования.
4. Новая форма для отображения пространства достижимых состояний в виде графа достижимости устойчивых состояний объектов, позволяющая исследовать поведение моделируемых объектов в статических режимах их работы.
5. Методология и основные принципы построения распределенных DPN-моделей. Научная значимость работы. Совокупность полученных результатов можно рассматривать как теоретическое обобщение и решение крупной научной проблемы построения имитационных моделей для описания поведения средств цифровой и вычислительной техники, обладающих, как высокой моделирующей способностью, так и широкими аналитическими возможностями.
Основные положения, выносимые на защиту:
1. Модель, представленная в виде оригинального подкласса элементарных сетей Петри, наиболее полно учитывающая особенности поведения реальных средств цифровой автоматики и вычислительной техники и позволяющая установить взаимное и однозначное соответствие между атрибутами модели и моделируемого объекта. Структура модели, ее свойства и особенности,
2. Основные принципы и методы построения, синтеза и структурных преобразований предложенной модели,
3. Концепция, принципы и методы построения распределенных моделей на основе нового подкласса сетей Петри Структура компонентов модели и способы организации их взаимодействия.
4. Методологические основы совместного моделирования технического и программного обеспечения микропрограммных устройств управления.
5. Методика и технология встраивания и применения моделей нового подкласса СП в системах автоматизированного функционального гическо го проектирования цифровой аппаратуры,
6. Граф достижимости с переменной струюурой. Структура графа, его разновидности, свойства и особенности.
7. - Теоретико-методологические основы построения, анализа и использования графа достижимости с переменной структурой для исследования поведения моделируемых устройств, как в статических, так и динамических режимах их функционирования.
8. Методика, алгоритмы и технология программной реализации преложенной модели и аналитических средств на основе с использованием графов достижимости с переменной структурой, в системах автоматизированного функционально-логического проектирования цифровой электронной аппаратуры.
Практическая ценность работы. Разработана новая модель для представления дискретных устройств, позволяющая более адекватно описывать поведение средств цифровой и вычислительной техники и установить взаимное и однозначное соответствие между ее атрибутами и атрибутами моделируемого объекта. Это позволяет использовать схемное изображение средств цифровой и вычислительной техники в качестве контекстно-чувствительной формы для непосредственного отображения состояния модели и оказания на нее возмущающих воздействий. Простота теоретического аппарата DPN модели, ее свойства и особенности делают данное расширение сетей Петри, максимально приспособленным для его органичного встраивания в технологические процессы и системы, предназначенные для автоматизированного проектирования средств цифровой и вычислительной техники.
Разработанные новые формы деревьев достижимости с переменной структурой представляют собой очень компактные, наглядные и интуитивно понятные, мощные инструментальные средства, позволяющие значительно расширить область практического применения аналитических методов исследования дискретных систем. Их применение позволит значительно расширить арсенал инструментальных средств, предназначенных для проведения аналитические исследования поведения дискретных систем еще одним эффективным инструментом.
Результаты данной диссертационной работы могут быть использованы при создании программного обеспечения интегрированных систем автоматизированного проектирования, имитационного моделирования и аналитических исследований качества функционирования сложных дискретных систем и объектов средств цифровой автоматики и вычислительной техники, систем визуального синтеза и анализа графических образов моделей и пространства достижимых ими состояний, методологий и технологий при разработке, моделировании и анализе систем и объектов данного класса в качестве методических материалов при подготовке инженеров по специальности САПР, автоматизированных систем научных исследований, -вычислительной технике и средств цифровой автоматики, системное и прикладное программирование на факультетах информатики, технической кибернетики, автоматизированных систем управления и т\п„ Разработанные в диссертации конкретные алгоритмы синтеза и анализа моделей, способы представления пространства достижимых ими состояний могут непосредственно применяться при реализации пакетов программ, предназначенных для моделирования дискретно-событийных систем и машинной графики.
Основная часть диссертации состоит из 5 глав, В первой главе проводится аналитический обзор состояния развития средств цифровой автоматики и вычислительной техники, современных технологий и средств, предназначенных для конструирования, имитационного моделирования и проведения аналитических исследований их поведения. Основное внимание уделяется изучению особенностей расширений сетей Петри, наиболее часто используемых для моделирования цифровой электронной техники. Результаты анализа используются для определения основных причин и факторов, препятствующих установлению соответствия между моделью и объектом, формирования требований к новой модели и новым формам представления пространства достижимых состояний. Вторая глава включает выбор и обоснование концепции DPN-модели, которая обеспечивающая соответствие между ее позициями и физическими сигналами, характеризующими общее состояние объекта. Приводится формальное определение DPN-модсли, особенности функционирования, ее структурные и поведенческие особенности. Рассматриваются возможности композиции, структурных преобразований и редукции предложенной модели. Третья глава посвящена проблеме сложности и способам ее ослабления. Предлагается несколько новых форм для отображения пространства достижимых состояний в виде графа достижимости с переменной структурой (ГДПС). Рассматриваются возможные разновидности ГДПС, приводятся результаты исследования их особенностей, возможности композиции, демонстрируются их достоинства и недостатки. Показана уникальная особенность ГДПС, заключающаяся в предоставлении возможности исследовать поведение моделируемых объектов, как в динамических, так и статических режимах их функционирования, В четвертой главе приводятся результаты исследований, связанных с применением DPN-моделей для распределенного моделирования и моделирования микропрограммных устройств управления, В последней, пятой главе приводится описание двух систем, разработанных на основе применения DPN-моделей, рассматриваются их возможности и области возможного применения.
Цифровая электронная техника, ее особенности и тенденции развития
Современные средства цифровой автоматики и вычислительной техники (ЦА и ВТ) характеризуются постоянным увеличением объемов ее производства, номенклатуры и сложности, при одновременном повышении конкуренции на рынке сбыта и сокращении времени морального старения. По данным, приведенным в [1,2], в развитии современных средств ЦА и ВТ можно выделить следующие основные тенденции: время создания новых образцов новых изделий от зарождения идеи до серийного производства сокращается в два раза каждые 25 лет; число вновь разрабатываемых изделий удваивается каждые 15 лет; количество повторно используемых деталей, узлов и агрегатов удваивается через каждые 10 лет; обьем научно-технической информации, необходимой при создании новых образцов техники удваивается через каждые 8 лет.
История современной цифровой элеюронной техники (ЦЭТ) показывает, что она прошла большой и сложный путь развития. Особое влияние на нее оказывали и продолжают оказывать процессы, связанные с совершенствованием используемой элементной базы и технологий ее изготовления. Соответствующие изменения элементной базы позволили не только улучшить рабочие хараюеристики, но и значительно расширить функциональные возможности ЦЭТ» Последуют цеє развитие и совершенствование технологий изготовления элементной базы привело вначале к вытеснению электронных ламп на элементы с ТТЛ логикой, а затем и к появлению интегральных микросхем: МИС (малой), СИС (средней), БИС (большой) и СБИС (сверхбольшой) степени интеграции, В результате такого развития элементной базы, ЦЭТ становится все более компактной и быстродействующей, менее энергоемкой, но и значительно более сложной. На одном кристалле такой микросхемы теперь можно было разместить не только несколько простых логических блоков (МИС), но и достаточно мощный процессор или специализированный компьютер (СБИС контроллера), предназначенный для выполнения сложных функций обработки и управления объектами самого различного назначения, В результате их последующего развития появились новые их разновидности, такие как: программируемые логические матрицы (ПЛМ) и программируемые логические интегральные схемы (ПЛИС), получившие заметное распространение в цифровой аппаратуре [1-4].
Основное назначение цифровой техники связано, как правило, с выполнением некоторого набора логических функций, преобразованием и манипулированием сигналами, имеющими всего два логических уровня, соответствующих условным значениям нуля и единицы. То есть, функционирование цифровых электронных устройств (ЦУ) осуществляется в соответствии с бинарной логикой. Простота реализации и почти неограниченный спектр функциональных возможностей, которыми обладают цифровые методы обработки и управления информацией, нашли самое широкое применение ЦЭТ практически во всех областях человеческой деятельности. Особенно широкое применение цифровая аппаратура нашла в современных информационных технологиях, в которых цифровые устройства составляют основу для построения самых разнообразных средств ЦА и ВТ,
Классической и широко используемой формой для представления и описания цифровых устройств является их условное изображение в виде их функциональных, принципиальных схем или блок-схем. Именно в терминах схемного решения конструктор обдумывает, обсуждает с другими участниками проекта и принимает те или иные технические решения, связанные с разрабатываемым цифровым устройством или системой. Схема устройства представляет собой наиболее удобный, эффективный и испытанный временем инструмент на всех стадиях жизненного цикла изделия. Начиная с его разработки и заканчивая его обслуживанием, ремонтом или модификацией. Общее состояние схемы или отдельных ее компонентов оценивают по совокупности состояний сигналов на выводах ее функциональных компонентов. В качестве другой вспомогательной формы, часто используемой для отображения и исследования поведения схемного решения устройства, являются временные диаграммы. Временные диаграммы являются удобной формой для отображения процессов, происходящих внутри цифрового объекта, и позволяют изучать особенности его поведения во времени путем исследования причинно-следственных зависимостей между соответствующими событиями и изменяемыми состояниями.
В зависимости от способа построения все дискретные цифровые устройства условно делятся на три большие группы: устройства с жесткой (ЖЛ), гибкой (ГЛ) и универсальной (УЛ) логикой функционирования. Наиболее простыми из них являются устройства с ЖЛ, алгоритм функционирования которых жестко определяется его схемой (структурой). Начальный этап развития ЦЭТ характеризуется развитием устройств именно такого типа. Характерный недостаток такого способа построения заключается в том, что каждый раз, при изменении (даже очень незначительном) алгоритма функционирования устройства приходится изменять (корректировать) или заново разрабатывать новый вариант его схемного решения. Уникальность такой реализации сильно ограничивает возможности ее использования при массовом производстве таких изделий и, следовательно, препятствует снижению их себестоимости.
Появление надежных и емких запоминающих устройств создало необходимые предпосылки для создания более эффективного способа реализации ЦЭТ. Его идея заключается в построении устройства в виде логического автомата, логика функционирования которого (в виде последовательности управляющих кодов) размещается о блоке памяти. Такой подход позволяет унифицировать структуру функциональных устройств и использовать одно и то же схемное решение для реализации уже не одного, а целого семейства алгоритмов. Подобные устройства стали называть микропрограммными устройствами управления (МПУ).
Последней и наиболее совершенной и универсальной формой реализации цифровых систем и блоков является компьютер. По сравнению с МПУ, компьютер имеет значительно более высокий уровень организации своей внутренней работы. Микропрограммная и в особенности компьютерная форма реализации цифровой электронной аппаратуры указывают на устойчивую тенденцию органичного слияния непосредственно цифровой техники (hardware) и программного обеспечения (software) в единую взаимодействующую систему. Наличие издержек, связанных с организацией своей внутренней работы, заметно снижает быстродействие цифровых систем, реализованных на компьютерах, по сравнению с аналогичными системами, реализованными в виде устройств с жесткой (схемной) логикой функционирования. По быстродействию МПУ занимают промежуточное положение между устройствами с жесткой и универсальной логикой функционирования,
Основные расширения сетей Петри для моделирования средств цифровой автоматики и вычислительной техники
СП очень хорошо адаптируются к особенностям каждой конкретной области применения. Среди множества возможных расширений СП можно выделить такие из них, которые получили наибольшее распространение при моделировании средств цифровой автоматики и вычислительной техники. К ним относятся автоматные СП, граф сигнальных переходов, маркированные графы, схемные СП, граф операций и цветные СП.
Автоматные СП, Автоматные СП представляют собой наиболее простое средство для моделирования цифровой техники. Они могут моделировать конфликты посредством условий с несколькими выходами, но, из-за отсутствия возможности синхронизировать входные условия событий, они не могут моделировать параллельные процессы.
Маркированные графы. В силу установившейся традиции маркированные графы изображаются не в виде СП, а в виде обычного ориентированного графа, дуги которого маркируются точками. Наличие этих точек на всех дугах, входящих в вершину маркированного графа, означает его возбуждение. Через конечный отрезок времени после возбуждения возбужденная вершина срабатывает. Все вершины, в которые входит более одной дуги, называются синхронизаторами, а вершины, из которых выходит более одной дуги называются бифуркаторами. Функциональные возможности маркированных графов ниже, чем у обычных СП. Маркированные графы двойственны автоматным СП. В отличие от автоматных СП, маркированные графы могут моделировать параллелизм, но, из-за отсутствия вершин с альтернативными выходами, они не могут моделировать конфликтных ситуаций. В маркированном графе существует три типа вершин, представленных на Рис.6. При возбуждении этих вершин (наличие точек-маркеров на всех ее входных дугах) инициализируется переход "Sj-Sj" (Рис.ба). При достижении Sj, точки-маркера со всех выходных дуг снимаются и устанавливаются точки-маркера на все выходные дуги. Любая промежуточная ситуация условий перехода не вызывает изменения маркировки. При возбуждении вершины, тип которой изображен на Рис.66 и Рис.бв, осуществляется изменение значения только некоторой компоненты ситуации из 0 в 1 (или из 1 в 0), При завершении перехода маркировка изменяются описанным выше способом.
Граф сигнальных переходов. Как правило, под графом сигнальных переходов понимают предметную интерпретацию маркированного, что его вершины помечены (нагружены) обозначениями переходов видов: Sj-Sj, ak+, at-, а смена маркировок подчиняется правилам выполнения маркированных графов. Таким образом, граф сигнальных переходов позволяет сократить общее описание моделируемых объектов, путем замены полного описания перехода на описание единственного перехода от инициализатора к результанту.
Схемные СП. В основе данного подхода используется идея представления элемента схемы некоторой подсетью СП [62]. Для этого вводятся понятия петли и цикла элемента. Схемные СП однозначно соответствуют модели Маллера [107], наглядно отображают динамику функционирования цифровых схем и свободны от ряда недостатков рассмотренных выше расширений. Они обладают структурными особенностями, которые заключаются в том, что каждое событие входит в какой-либо цикл элемента и при этом все условия, инцидентные этому событию и не входящие в цикл элемента, образуют с ним петлю. Более детальное описание этого расширения можно найти в [62].
Операционные сети (граф операций). Операционная сеть представляется в виде безопасной СП, ориентированной, прежде всего, на моделирование дискретных и управляющих вычислительных систем [108]. Основная особенность операционных сетей предложенных А.Д.Закревским заключается в том, что среди всех ее позиций предлагается в явном виде выделять входные и выходные полюса (позиции). Такой подход предоставляет возможность использования некоторых новых аналитические возможностей аппарата СП. В частности, вводится такие понятия, как распознаваемость наборов входных сигналов и реализуемости преобразования множества входных сигналов моделируемой системы в множество ее выходных сигналов.
СА.Юдицкий предложил использовать граф операций в качестве модели для описания алгоритмов управления, В графе операций позиции помечены значениями выходных переменных, а переходы - значениями входных переменных. Для описания иерархически построенных алгоритмов применяются системы вложенных графов операций. Поскольку в безопасных СП в позициях не может быть более одного маркера, а в живых СП имеется возможность срабатывания любого перехода, то для целей управления С.А.Юдицким было предложено применять в графах операций только безопасные и живые СП. Достоинство графов операций состоит в возможности описания в наглядной графической форме сложных алгоритмов управления, обладающих параллелизмом [109].
Оценочные сети (вычислительные СП или Е-сети) [ПО]. Также как и классические СП, Е-сеть является графом, содержащем вершины двух типов - позиции и переходы. Однако, в отличие от них, в Е-сети среди множества ее позиций выделяют некоторое подмножество, которое соответствует так называемым разрешающим позициям, которые обозначают буквой "г". Каждая позиция Е-сети может содержать метку. Причем, метки могут быть простыми, определяющими свободность или занятость данной позиции, или сложными. Сложная метка является вектором, характеризующих множество некоторых параметров. Метки перемещаются по Е-сети вдоль направленных дуг, при этом содержание метки может меняться по мере ее прохождения по сети. Каждая позиция Е-сети может иметь только одну входящую и одну исходящую дугу. Переходы Е-сети являются вершинами, в которых происходит преобразование потока меток.
Типовые структурные образования в D-сетях и их особенности»
Дальнейшее рассмотрение D-сстевого расширения и его особенностей, представляется полезным рассматривать с учетом постоянного переноса соответствующих понятий, используемых в сетевых моделях, в аналогичные понятия, используемые в области цифровой схемотехники, Такой акцент позволит увидеть в новом расширении не просто еще одну оригинальную форму СП, а расширение, позволяющее использовать набор взаимно и однозначно интерпретируемых атрибутов и правил для выполнения формальных преобразований понятий и категорий, которые можно успешно использовать при анализе поведения объектов цифровой электроники и адекватного их отображения в сетевых моделях.
Именно эта особенность нового расширения предоставляет разработчику средство, которое, обладая высокими моделирующими возможностями, одновременно представляло бы собой и хорошо формализуемое и однозначно интерпретируемое отображение схемного решения, позволяющее осуществлять адекватные формальные преобразования понятийных аппаратов между моделью и объектом в обоих направлениях. Располагая таким инструментальным средством, разработчик смог бы на любой стадии процесса разработки цифрового устройства, и в любое время проводить исследования его поведения. Причем, делать это путем непосредственного воздействия на графический образ создаваемого схемного решения и тут же наблюдать соответствующую реакцию модели, отображаемую па той же схеме в наиболее понятной и удобной для него форме. Подобный инструмент позволил бы спрятать от разработчика саму модель, функционирующую как бы на заднем плане за рабочим полем чертежа, и тем самым позволить ему максимально сконцентрироваться на решении самой схемно-технической задачи, без необходимости привлечения понятийного аппарата подыгрывающей модели. Другими словами, разработчику можно было бы предоставить возможность конструировать не "мертвые" изображения схем цифровых устройств, а "живые", на которые можно было бы воздействовать как на реальные устройства и наблюдать ответную реакцию на оказанные воздействия. Именно поэтому в данной работе само D-расширение и его свойства и особенности рассматриваются с учетом их постоянного переноса на традиционные формы представления объектов той предметной области, для которой они предназначаются.
Из теории автоматов известно, что, в самом общем виде, цифровые устройства можно представить в виде "черного ящика" с множеством входов, состояний и выходов. Более конкретные и детализированные формы такого представления, понятные большинству разработчиков, имеют вид соответствующих схемных решений или просто схем. Поэтому в дальнейшем, говоря о моделируемых объектах, будем иметь в виду их представления в виде того или иного схемного решения.
Так же, как и в классических СП, в D-сетях возможно образование так называемых изолированных позиций и переходов. То есть узлов сети, между которыми не существует никаких связей. Подобные элементарные структурные образования не представляют особого интереса. Поэтому, перейдем к рассмотрению несколько более сложных структур связей, которые могут образовываться в D-сетях вокруг переходов и позиций.
В соответствии с ограничением (2), наложенным на D-сеть, кроме изолированных переходов, в ней возможно образование и таких переходов, среди сопряженных позиций которых нет ни одной активной позиции, а одни только условные (Рис.Юв). Срабатывание таких переходов носит чисто формальный характер и не изменяет маркировки ни одной из сопряженных с ними позиций. Будем называть такие переходы условно изолированными. Поскольку наличие таких переходов в сети не оказывает на ее поведение никакого влияния, то их можно исключать из ее состава.
Более пристального внимания, по-видимому, заслуживают такие структуры, которые образуются переходами с общими позициями (Рис.11).
Первые две структуры образованы переходами с общей активной позицией (Рис.Па,б). Если оба перехода, например ТІ и Т2 (Рис.11а), возбуждены и срабатывают одновременно, то, в соответствии с определением D-сети, сделать это они могут независимо друг от друга, то есть в произвольном порядке. Но срабатывание любого из них, сразу же нарушает условия возбуждения другого. В результате переход, потерявший активность, сработать уже не сможет. В этой ситуации нет ничего, что противоречило бы реальному поведению дискретных систем. Потому что, независимо от того, какое событие выполняется, маркер в любом случае попадает в позицию Р1. Такие же рассуждения можно привести и относительно другой аналогичной структуры (Рисі 16). Таким естественным образом снимается проблема, связанная с приоритетами.
На Рис.11в и Рис.11г представлены структуры, в которых общая позиция для одного из переходов является активной, а для другого условной. Анализ функционирования этих структур показывает, что если переходы возбуждены и одновременно срабатывают, то переход с активной связью будет срабатывать всегда, а срабатывание перехода с условной связью может и не быть. Объясняется это все той же независимостью выполнения событий, принятой для дискретных систем. Что же касается двух других возможных структур (Рис.11д,с), с общей для нескольких переходов позицией, то в таких структурах вообще невозможно создать условия для одновременного возбуждения переходов. Потому что, если маркер в позиции для одного из переходов является разрешающим, то одновременно для другого из них- запрещающим.
Аналогично условно изолированным переходам, в D-сетях возможно образование структурных фрагментов, содержащих позицию, которая, для всех сопряженных с нею переходов, является либо только условной (Рис.12а), либо только активной (Рис.126). Позицию, которая для всех сопряженных с ней переходов, является условной, будем называть управляющей позицией. А позицию, которая для всех сопряженных с ней переходов является активной, будем называть управляемой позицией или позицией-индикатором.
Граф достижимости с переменной структурой (ГДПС),
В предыдущей главе было показано, что преобладающее большинство известных аналитических методов, предназначенных дія проведения исследований поведения моделируемых дискретных систем сетями Петри (СП), ориентированы на использование пространства достижимых состояний. Его наглядное отображение представляется в виде графа достижимости (ГД), включающего в себя множество узлов, интерпретируемых как отдельные состояния моделируемого объекта, и связей между ними, характеризующих переходы из одного состояния в другое» Однако, практическое использование ГД сильно ограничено и применимо только к очень простым моделям. Причина заключается в возникновении проблемы сложности, которая проявляется в том, что, при увеличении размера модели, размерность соответствующего ГД резко увеличивается.
Тип модели, для которой строятся ГД, также может оказывать существенное влияние на их основные свойства и особенности. Используемая в данной работе имитационная модель в виде D-расширения СП (DPN) отличается от существующих расширений СП, прежде всего, тем, что обеспечивает взаимное и однозначное соответствие между позициями модели и реальными сигналами, характеризующими состояние моделируемых цифровых устройств. Кроме того, в -отличии от других моделей, она позволяет формальным образом различать в ней позиции, соответствующие входным сигналам и внутренним состояниям моделируемых объектов, что позволяет использовать все преимущества автоматного подхода при изучении поведения моделируемых объектов,
С учетом сказанного, последующие исследования новых форм для отображения пространства состояний и их возможностей будут проводиться с использованием DPN-моделей,
Пространство состояний, в которых может оказаться моделируемая система или объект, в процессе своего функционирования, обычно представляют в виде графа, который часто называют графом достижимых состояний или просто графом достижимости. В общем виде, граф достижимости (ГД) можно представить в виде следующего набора: ГД=(Я, Tf Ц So), где: S - { рь р2 ." , рп } множество состояний, каждое из которых представлено в виде уникального сочетания состояний элементов алфавита позиций (п=Р, р,сР для каждого О І п). Т - множество структурных переходов, L - { (SJ, tic, Sj) } - множество семантических переходов или соединительных дуг между узлами (0 i S, 0 j S, 0 k ;L[s LcS T S). So - множество начальных состояний (Sorf).
Если каждое состояние моделируемого объекта рассматривать как уникальную маркировку позиций в СП, то множество всех се позиций можно рассматривать как алфавит состояний. Тогда каждое состояние сетевой модели удобно представлять в виде уникального сочетания состояний всех элементов этого алфавит.
Аналогично, множество всех переходов можно рассматривать как алфавит переходов. Подобные структуры часто называют системами помеченных переходов (LTS-Labeled Transition Systems)[117], Как правило, пространство состояний или LTS изображаются в виде графа достижимых состояний, состоящего из множества узлов, представляющих собой различные состояния объекта, и соединительных дуг. Наличие дуги (семантического перехода) между двумя узлами графа обозначает событие, в результате которого осуществляется переход из одного состояния в другое. Каждой такой семантической дуге в ГД можно поставить в
несоответствие свой структурный переход в модели. В общем случае, несколько семантических переходов могут ссылаться на один и тот же структурный переход- Формально семантический переход можно представить как тройку (s,t,s ), включающую начальное состояние s S, структурный переход teT и конечное состояние s eS. Иногда семантический переход обозначают и как: M[t)M\
Если не учитывать вычислительную сложность, то размер пространства состояний для безопасных СП (когда в каждой позиции может быть не более одного маркера) можно определить с помощью выражения S]+L]. При этом, общее количество узлов в графе зависит только от размера алфавита состояний Р сетевой модели, для которого строится этот граф.
Для удобства дальнейших рассуждений введем дополнительно следующие множества, характеризующие некоторые важные особенности DPN моделей: Pin, Pout, Pinter - соответственно непересекающиеся множества позиций, имитирующих поведение входных, выходных сигналов моделируемого объекта и его внутренних состояний. P=PinuPoutuPinter. Эти множества можно рассматривать как алфавиты входов, выходов и внутренних состояний модели, Pv, Pu - соответственно, множество позиций доступных (видимых) и не доступных для непосредственного наблюдения (невидимых) сигналов. P=PvuPu (PvnPu-0). Будем называть их алфавитами наблюдаемых и ненаблюдаемых состояний. Тс, Ти - соответственно множество переходов (действий), условия возбуждения которых зависят или не зависят от входного алфавита. T=TcuTu (TcnTu=0). Будем называть их алфавитами управляемых и внутренних (независимых) переходов.
Следует отметить, что DPN модель сама не способна изменить маркировку ни одной из ее позиций pePin, представляющих алфавит его входов. Маркировку этих позиций может изменить только внешняя среда, в окружении которой функционирует модель. Таким образом, если исключить входные позиции из алфавита достижимых состояний, то это позволило бы уменьшить как размер каждого из его узлов, так и размер пространства достижимых состояний в целом. При этом их влияние продолжает учитываться в семантических переходах ГД, которые ссылаются на структурные переходы в модели. В свою очередь, структурные переходы учитывают входной алфавите качестве условий, необходимых для их возбуждения.
