автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Метод Р-сетей для моделирования мультипроцессорных вычислительных систем

ол

2 о т,! ' Государственный университет

аэрокосмического приборостроения

на правах рукописи

Гордеев Александр Владимирович

Метод Р-сетей для моделирования мультипроцессорных вычислительных систем

специальность 05.13.11 "Математическое и программное обеспечение вычислигельных машин, комплексов, систем и сетей"

Автореферат диссертации на соискание ученой степени доктора технических наук

Санкт-Петербург 1998

Работа выполнена в Государственном университете аэрокосмического приборостроения

Официальные оппоненты:

докт. техн. наук, профессор Колесников Дмитрий Николаевич докт. техн. наук, профессор Советов Борис Яковлевич докт. техн. наук, профессор Юдицкий Семен Абрамович

Ведущая организация : Холдинговая компания "Ленинец"

Защита диссертации состоится " уме- 1998 г. в_часов на заседании

диссертационного совета Д 063.21.02 .

С диссертацией можно ознакомиться в библиотеке

Автореферат разослан "_"_ 1998 г.

Ученый секретарь совета

докт. техн. наук, профессор Фильчаков Владимир Васильевич

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

2. Анализ различных модификаций сетей Петри с целью определен)::: возможности и целесообразности использования и\ наиболее важных особенностей дня моделирования МВС (с учетом особенностей выполнения параллельных вычислений на низком уровне представления) и использования в новой предлагаемой модификации сетей Петри.

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

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

5. Разработка моделей (примитивов) основных компонентов МВС и некоторых других сложных систем, методики и средств автоматизированного построения F-сетевых моделей.

6. Разработка концепции, архитектуры и макета программно-инструментальных средств для ПЭВМ типа IBM PC для моделиро-

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

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

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

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

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

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

4. Предложен алгоритм построения дерева достижимых маркирований Р-сетевых моделей для анализа систем, представляемых сетями.

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

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

1. Создано несколько программных макетов и законченных программных средств для моделирования и анализа систем, представленных И-сетями Петри:

* "Подсистема имитационного моделирования бортовых цифровых вычислительных систем на основе модифицированных сетей Петри", 1990 г. - по заказу НИИ АО;

* Электронный учебник '"Сети Пегри: Моделирование и анализ", 1992 т. - по заказу Рос! 1ИИИС;

* ''Интегрированная система моделирования и анализа на основе сетей Пегри", 1994 г. - по заказу С.-Г16. РФИТР;

* "Сети Петри для Windows" (версии 1.0, 1995г. и 2.2, 1996г.) по заказу РосНИИИС.

2. В процессе проведения ряда НИР промоделировано несколько вычислительных систем. в юм числе микропроцессорная система диспетчерского контроля и управления устройствами электроснабжения железных дорог (по заказу ВНИИЖТ, совместно с ПИИТ), варианты бортовых цифровых вычислительных систем ЦВМ 80-400 и СБ3541, перспективной многомашинной распределенной бортовой вычислительной системы (работы проводились в рамках НИР-781, утвержденной приказом МинВУЗа РСФСР N 00147 от 12.11.87г.) и др., что позволило оценить и подтвердить правильность и эффективность проектных решений.

3. Разработанные методы, модели, алгоритмы и пренраммные средства были использованы при выполнении НИР-524 (шифр - ЭК'-i М!;Н-ЛПЛП) "Разработка методов и среда и iimiii;iiiiiohhi4 о чо лирования. формального анализа и экспертных моделей для оценивания вариантов СВГС", коюрая была дополнением к доюворх N 2511 "Экзамен -РВО" с в/ч 25970 от 29.07.91 и соскшной частью темы "Поисковые исследования и разрабо1ка математических методов многокритериального оценивания вариантов управленческих и организационных решений по проектированию и созданию СВ ГС с целью повышения их эффективности и качества в условиях неполной информации", а также при выполнения НИР "Разработка методов и алгоритмов моделирования и анализа для исследования компонентов и подсистем автоматизированной системы обработки информации в комплексах сигнально-информационных средств с целью повышения их тактико-технических характеристик" (шифр

.л

4. Комплекс программ "Сети Петри для Windows", который имеет все необходимые встроенные средства обучения, используется при подготовке магистров по направлению 552800 в рамках специализации "Высокопроизводительные вычислительные системы". Названный комплекс программ используется в Санкт-Петербургском государственном техническом университете на кафедре автоматики и вычислительной техники при подготовке студентов по специальности 22.01 и в Санкт-Петербургском государственном электро-

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

Основные результаты диссертационной работы наиболее полно реализованы в программном комплексе моделирования и анализа "Сети Петри для Windows". Программный комплекс предназначен для построения F-сетевых моделей различных систем, содержащих параллельно протекающие асинхронные процессы, имитационного моделирования со сбором статистики, анализа построенных моделей, а также для обучения методам имитационного моделирования. Программный комплекс функционирует на персональной ЭВМ типа IBM PC/AT при наличии не менее 4 Мб ОЗУ и 1800 Кб свободного пространства на жестком диске иод управлением MS DOS в графической среде MS Windows 3.x или в Windovvs-95 и позволяет решать следующие задачи: ввод и редактирование моделей на основе F-сетей в графическом режиме; хранение построенных сетевых моделей в виде файлов на диске; создание из сетевых моделей библиотек примитивов с приложением описаний и подсказок в формате Windows; автоматизированное построение модели системы из заранее созданных моделей подсистем и примитивов; моделирование функционирования F-сетей со сбором статистических данных в автоматическом режиме и в режиме пошагового прогона модели с целью ее отладки; анализ модели на основе классических сетей Петри; построение дерева достижимости для моделей на основе F-сетей. Основные положения, выносимые на защиту:

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

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

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

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

Внедрение. Результаты диссертационной работы использованы в с л еду ю щ и х о р га н и за ци я х:

НИИВМПУ , в/ч 25970 (НИР-524, шифр темы Экзамен-РВО);

п/я IO-9539 (Н! ÍP-7SI, шифр темы Нева);

СПбПЭТУ (НИР-429, НИР-483, НИР-648, шифр темы Жердь-РВО); в учебном процессе в СПбГТУ, СПбГЭТУ, СПбГУАП при подготовке студентов по специальности 22.01 и 22.02.

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

1. Общеинститутская научно-техническая конференция ЛИАП "НТК-37", Ленинград, 1987г.;

2. Совещание-семинар по учебно-исследовательским САПР, Ленинград, 1988:

3. ! {аучно-ирак i ический семинар "1 cxhu.ioi ия проектирования программных и аппаратных среде ib вычислительных ciicicv" ЛДНТП. Ленинград. 1989. 1990 н .

4. X Симпозиум по проблеме избыточности в информационных системах. Ленинград, 1989.

5. Ш Всесоюзная конференция "Качество программных средств"'. Дагомыс, 1991.

6. Всероссийская научно-техническая конференция с международным участием "Информационно-управляющие и вычислительные комплексы на основе .новых технологий. Conference Inter Aero Spacc Systems"'. Санкт-Петербург. 1992.

7. Научно-техническая конференция "Техническое диагностирование-93". Санкт-Петербург, 1993.

8. Научное совещание по проблемам безопасности программного обеспечения, в/ч 30895, 1993.

9. Научно-техническая конференция "Диагностика, информатика и метрология -94". Санкт-Петербург, 1994.

10.Вторая международная школа-семинар "Новые информационные технологии". Гурзуф, 1994.

11.Научно-техническая конференция "Диагностика, информатика и метрология -95". Санкт-Петербург, 1995.

12.Научная военно-техническая конференция "Автоматизация процессов управления соединениями и частями ПВО, информационные технологии." Санкт-Петербург, 1996.

13.Международный симпозиум по проблемам модульных информационных компьютерных систем и сетей. Санкт-Петербург, 1997. Публикации. По теме диссертационной работы опубликовано 16

статей и тезисов докладов, 1 учебное пособие, 3 электронных монографии - 1 электронный учебник и 2 интегрированных системы со встроенными средствами обучения. Основные положения диссертационной работы отражены в 12 отчетах по НИР, выполненных в ГААП, СЗРЦНИТ, СПбИИТ, СПбГУ в 1986-95 гг.

Структура и объем диссертации. Работа состоит из введения, четырех разделов, заключения, списка литературы (197 наименований) и приложений. Объем основной части (без приложений) - 200 страниц машинописного текста, в том числе 56 рисунков, 3 таблицы.

Краткое содержание работы

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

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

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

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

■Завершается первый раздел обзором и анализом iex известных модификаций и расширений ceieii lleipn. и с\шествующих комплексов программ (в Приложении 1 приведены данные об основных характерна i и к. ; ч 73 ирофаммных комплексов), которые обладают механизмами, воики-шими в F-сеги. В результате проведенною обзора и анализа отмечены следующие основные момен ты:

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

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

3) подавляющее большинство коммерческих пакетов ориентировано на мощные вычислительные средства тина рабочих станций НР-9000 Appolo-series, Sun SparcStation, DEC micro VAX, IBM RS/6000 и других, что позволяет быстро получать статистические результаты и решать серьезные задачи большой размерности. Что касается разработок, ориентированных на персональные компьютеры, то

они используются скорее для целей обучения или как макетный образец и, как правило, свободно доступны;

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

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

6) в основном сетевое представление исследуемого объекта компилируется в программу на языке C/C++ (есть примеры использования языков ADA, Smaltalk, языков близких к Pascal), однако есть и примеры использования системы GPSS;

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

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

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

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

• введение дискретного модельного времени;

• синхронизация срабатывания переходов (выполняется естественным образом благодаря введению механизма учета времени);

• введение механизма учета приоритетов в срабатывании конкурирующих (конфликтующих) переходов;

• введение атрибутов маркеров (атрибуты являются носителями информации);

• ассоциирование с переходами сложных функций для обработки данных, отображаемых с помощью атрибутов маркеров;

• введение множества правил срабатывания переходов (типизация переходов и позиций, введение специальных переходов дня моделирования основных компонентов МВС - процессор, контроллер, па-мят ь);

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

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

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

Приведено формальное описания предлагаемой модели, согласно которому Р-сети можно представить в следующем виде:

1^ = (8,4'1,4'2,9г,мв|,0о|) ,

где Я - структура Р-сети:

Ч',/!', функции определения (ппрамефпзапии) переходом и

полшип сети, соогвекл вепно: Уг - функция приори 1С1 ноет и: Мц - начальная маркировка сети;

©о _ начальное состояние переходов. Структура Р-сети как и в обычных сетях Петри представляется двудольным ориентированным мультиграфом 8 =< V, V >. где V - вершины зюго графа, а V - его дуги. Поскольку граф является двудольным, то по традиции будем обозначать через Т конечное множество его переходов, Т = {^} ,1 = 1,п, а через Р - конечное множество позиций,

п <"—1 ' 1 Т1 1м % г т/М» О!

= »и г = >, =

Конечное множество V дут ориентированного биграфа в задается отношениями В и Е: У е(Р* Т)и(Т* Р) :

В:(Р*'Г) {-те,...,-2,-1, 0, 1, - отношение предшество-

вания, которое задает отображение из позиций в комплекты переходов и позволяет определить для каждого перехода ^ комплект его входных по-

зиций 1(1;) = |р4|в(р},е^> I, j = l,mî; I(t,)eP; i = l,n.

E:(T* P)-> {0,1,2..., w} - отношение следования, которое задает отображение из переходов в комплекты позиций и позволяет определить для каждого перехода t; комплект его выходных позиций

O(tj) - {Pj|E(t,, Pj) > 1, j = M»}; 0(t;)eP; i=l,n.

Здесь w - мультичисло графа S, a P - пространство комплектов, заданное на множестве Р отношениями В и Е;

(pj,tj) - дуга, выходящая из позиции pj и входящая в переход tj; (tj ,pj) - дуга, выходящая из перехода t; и входящая в позицию Pj. Отрицательный вес дуги (Pj,tj) означает, что эта дуга является сдерживающей (часто ее называют ингибиторной).

Пусть In(îj) обозначает одномерную матрицу размером 1х п, где п - количество позиций, связанных с переходом t;, у которой элемент с номером i равен числу дуг, выходящих из позиции Pj и входящих в переход (¡; i = l,n. Соответственно, пусть Out(tj) означает подобную матрицу, но с ненулевыми значениями для выходных позиций перехода tj и с нулевыми для входных. Можно сказать, что In(t;) представляет

собой i-ый столбец в матрице В, a Out(t;) - i-ую строку в матрице Е.

Таким образом, с учетом введенных обозначений структуру F-сеги мы будем представлять, как и в других модификациях сетей Петри, через четверку, т.е. S = (Т, Р, В, Е).

Функции Т, и Т2 определяют отображения переходов и позиций сети на соответствующие классы (типы) этих объектов. Ч^ : Т-> {Fj} , i= 1,L - функция определения переходов, задающая отображение множества переходов сети на множества типов процедур функционирования. Другими словами, на множестве Т задано отношение эквивалентности, которое разбивает его на так называемые типы, характеризующие основные закономерности как в определении комплектов I(t,) и 0(t,), так и процедур функционирования Fj. Здесь Fj - процедура срабатывания перехода i-ro типа. В общем случае

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

Fj = (Ai,Qi,B„0i,Ai,3l) .где л, - входной алфавит; В; - выходной алфавит; Q; - множество внутренних состояний автомата; 0j - функция переходов автомата из одного состояния в другое; А; - функция выходов автомата: 3; - функция времени. Рассмотрим эти компоненты подробнее.

Входной алфавит Л; = {а0,ац ,a-l2,...,aim| всегда содержит по крайней мере один элемент - символ а0. Поскольку, с одной стороны, маркер можег и не иметь атрибутов, а с другой стороны, мощность этого множества зависит от числа атрибутов и количест ва значений для каждого атрибута, у каждого типа перехода будет свой входной алфавит. Всего в сети может быть I. таких алфавитов.

Выходной алфавит В| |[50. [Î;,, Р ;,,. .,1^,,,}- ana.ioi нчно. bcci ы содержит по крайней мерс один элемент символ ()„.

Множество внутренних состояний Q-, -- (<|ц,(|п, Ч î 2 ' - - - ; к} |аКАС имеет ,тдя каждого типа (класса эквивалентности) свою мощность. Состояние q0 является начальным состоянием автомата. В частом вырожденном случае множество Q, состоит из одного единственного элемента : Qî эта ситуация может быть отнесена к обычному нетипишро-

ванному переходу традиционной модели сетей Петри. Что касается уже упомянутых четырех состояний перехода (пассивное, возбужденное, блокированное и активное), то множество Q-, - ,qi2,...,qik| относится ко всем этим состояниям: т.е. для каждого состояния автомата q^

можно говорить о пассивном, возбужденном и других состояниях собственно перехода.

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

©i : Q, х Ai -> Q|.

Функция выходов Aj : Q; х Aj -> Bs определяет значения выходных символов автомата.

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

Поэтому функция времени 3j определяется следующим образом:

3, : f(05,S)-> {5i}. Это означает, что длительность активного состояния перехода (задержка в перемещении маркера из входной позиции в выходную, которая имитирует выполнение некоторого действия в течение заданного времени) может зависеть как от состояния qä автомата и значения входного символа Gtj, так и от текущего времени S.

Функция : Р-* {PfhoJ'ufo} определяет дисциплину обслуживания для каждой позиции р-, еР, т.е. очередность обработки маркеров, находящихся в позиции Pj. Дисциплина FIFO (Firsl-In-Firsi-Out) определяет обслуживание в порядке очереди (первый пришел - первым обслужен), дисциплина LIFO (Last-In-First-Out) - обслуживание в обратном порядке (последним пришел - обслужен первым).

Функция приоритетности (порядка) переходов 5R : Т -> N + сопоставляет каждому переходу t j б Т приоритет активизации pt eN+ ;

N+ - множество натуральных чисел. Чем больше значение pj , тем выше приоритет активизации.

Если обозначить через Ttv множество возбужденных переходов в момент модельного времени т (если время не учитывается, то можно говорить о том, что система в состоянии Mt), т. е. справедливо

TTv={t,| Vtj eT,v : Vpjel(t;) => m(Pj)>#(Pj,I(t;))} ,

то срабатывает переход

tjelV : p(t,)>p(tj) , Vtj ет; , i#j.

Для того, чтобы срсдп tj с I? (если T,v * 0) всегда имелся переход

t| : p(t;)= maxp(tj), т '

функция SJ1 должна быть инъективной. В противном случае опять возможны конфликты. В качестве такой функции при реализации комплекса программ дня моделирования F-сетей можег быть взято следующее отображение: p(t;) = (m - i) + 1 , где m = |'l1 — мощность множества Т.

Начальная маркировка сеж М0 однозначно определяет начальное состояние модели, поскольку все автоматы переходов F-сети при этом находятся в состоянии q0, а сами переходы изначально считаются пассивными. Таким образом, с помощью маркировки М0 мы определяем только расположение маркеров и значения атрибутов в позициях сети. Вследствие того, что некоторые маркеры могут иметь атрибуты и для каждого атрибута можег быть определено свое множество возможных значений, в общем случае маркировку М(( можно представить в виде одномерной матрицы размером m - . ».темешами ко юрой ячлчкче: множества векторов необязательно одинакового размера. I акая структура напоминае! одномерную матрицу из так называемых сгрукчурных чисел, которые можно представить в виде следующей системы элементов:

Здесь п - это количество маркеров в некоторой позиции; пи - количество атрибутов при ¡-ом маркере; - это значение ¡-го атрибута для {-го

маркера.

При использовании введенного понятия маркировка М для Р-сети может быть представлена в следующем виде:

где К(р|) - структурное число, которое определяет маркеры и значения

К =

Xll X12

X 21 X 22

X tu

X 2d

М = (К(р1),К(р2),...,К(ри))1

атрибутов при них, которые находятся в позиции Pj. Если обозначить через p(pi) количество маркеров в позиции р;, то ц(р;) будет равно и количеству столбцов в структурном числе К(р;).

Таким образом, начальная маркировка М0 может быть задана в виде вектора из структурных чисел:

М0=(Ко(Р|),Ко(Р2).-.-.Ко(Р»))-

Однако, поскольку переходы могут иметь более одного состояния и фаза активности перехода протекает во времени, т.е. имеет некоторую длительность, то состояние всей сети в некоторый момент времени 5 должно в себя включать помимо маркировки Мй и информацию о состояниях переходов. Эту информацию несет вектор ©й, состоящий из тех значений функций ©j, которые справедливы для каждого перехода tj в

некоторый момент времени 8. Другими словами, элементами вектора ©5 являются текущие состояния переходов с указанием информации о маркерах, по которым он сработал.

В формальном описании F-сети вектор 0О помещен в прямоугольные скобки, поскольку для начального состояния сети мы по определению считаем его состоящим из элементов q0 и поэтому он может быть опущен. Однако при рассмотрении любого текущего состояния сети вектор ©6 необходим.

Введено понятие локальной маркировки, т.е. маркировки в позициях, непосредственно связанных с данным переходом. Обозначим через p(l(tj)) локальную маркировку во водных позициях перехода tj , а через p(0(tj)) - локальную маркировку в выходных позициях перехода tj. Можно сказать, что локальные маркировки n(l(tj)) и n(0(tj)) тоже представляют собой векторы из структурных чисел. Однако нас будут интересовать не все такие возможные векторы, а "минимальные" векторы, т.е. наборы структурных чисел, содержащие минимально возможное количество компонентов х_ , при которых переходы могут сработать.

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

ствин (если не будут в течение активное! и перехода поглощены каким-нибудь другим переходом tj, который имеет не нулевое пересечение своего входного комплекта 1(1)) с комплектом Цц) ).

Таким образом, можно сказать, что множество входных символов Л| перехода (•, определяется множеством тех значений минимальной локальной маркировки {р-щт(НЧ))} (можно установить взаимно-однозначное соответствие между элементами указанных множеств), при которых переход ^ может перейти из пассивного состояния в состояние возбуждения. Эти минимальные локальные маркировки, в свою очередь, определяются семантикой моделей, которыми мы представляем реальные объекты. Аналогично определяются и множества выходных символов автомата, ассоциированного с переходом ^.

Принципиальное отличие новой модели от сетей автоматов заключается в том, что в Р-сетях мы имеем дело не только с автоматами Г|, ассоциированными с переходами, но и с самой сетью, структура графа Б которой двудольна. Для явного указания фактов появления некоторых входных сигналов, как и для отображения фактов появления выходных символов автомаюв. используется понятие позиций, в которых ночи."-ются маркеры. То есть связь автомаюв. ассоциированных с переходам*-Г-сетн. осуществляется через позиции сети посредством прохождения через них маркеров с атрибутами, с помощью которых эти автоматы и обмениваются информацией. Причем появление одного из входных сигналов может являться всего лишь необходимым, но не достаточным условием для срабатывания автомата и перевода его в новое состояние. Другими словами, этот формализм имеет явный механизм для синхронизации событии, происходящих в параллельно или последовательно функционирующих автоматах, а также механизмы для построения сети сложным образом взаимодействующих между собой автоматов, позволяющих учитывать модельное время. Г-сети естественным образом позволяют отобразить параллельный асинхронньп') характер в функционировании своих примитивов. В то же время Р-сети позволяют отобразить преобразование информации.

Рассмотрены моделирующие возможности Р-сетей и доказаны следующие утверждения: 1. И-сетями может быть представлена любая ординарная сеть Петри:

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

3. F-сетями может быть представлена любая раскрашенная сеть Петри;

4. F-сетями может быть представлена любая временная сеть Петри;

5. F-сетями можно представить любой автомат;

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

Из формального описания F-сетей следует, что в общем случае для каждой F-сетевой модели с п переходами ( |Т| = п ) мы можем иметь п различных типов переходов. В этом случае пользователь должен будег определять множества A^Q^B-, и функции 0 j, Л,,3; для каждого перехода построенной им сети, что, безусловно, трудоемко. С другой стороны, обычными сетями Петри (например, ординарными сетями, у которых все переходы одинаковы и в терминах F-сетей можно было бы говорить о единственной процедуре функционирования) можно представлять самые разнообразные объекты, для которых наиболее важными моментами прежде всего является необходимость отобразить их параллельный характер функционирования. Поэтому представляется целесообразным говорить о некотором наборе базовых примитивов (типов или процедур функционирования), с помощью которых можно строить F-сегевые модели в некоторой заданной предметной области для решения определенного класса задач. В работе приведено вербальное и формальное описания предлагаемого набора примитивов.

Как известно, автомат можно описать либо в виде графа, либо в виде автоматной таблицы, либо в виде системы продукций. Важно только чтобы система продукций была непротиворечивой. Однако, поскольку входной алфавит Л; автомата Fs определяется минимальной входной маркировкой, продукции для описания процедуры функционирования перехода tj могут быть представлены в виде

if n(l(t; ),qj) then (qk,p(0(ti))) .

Таким образом, в общем случае процедуру функционирования F некоторого перехода t; еТ, где через Т обозначается множество переходов сети (Т= {{¡¡,i = 1,п), и каждый переход fc определяется своим типом и правилами срабатывания, временной задержкой б (характеризующей

длительность протекания процесса, который представлен переходом ¡¡), мы будем представлять следующим образом: Р : [л, -> Г2;...;тсь -> .

Здесь ^ - функция изменения локальной маркировки М(0 и атрибутов маркеров (под локал1>ной будем понимать маркировку на множестве входных и выходных позиций перехода Г) в случае, если некоторый предикат г.-, принимает значение "истина", а предикаты я,,тс2,...т>.) , принимают значение "ложь". Таким образом, функционирование перехода I. будет определять та функция Г, которая соответствует первому истинному высказыванию л, в порядке следования предикатов. Естественно

предположить, что никаких особых ограничений на отображение П -» {Г;} , где П = {к1,л2,...п-1_х} , не задается и при составлении сетевой

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

считается неопределенным и обозначается через ноль.

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

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

II = {к1} ; к1 = иле ¡Г Ур,- е1(Те)=> т(Р|)>#(Р!,1(Те)) .

Здесь запись вида #(рр1(Те)) означает число появлений позиций во входном комплекте перехода Те. Это число равно количеству дуг, входя-

щих в переход Тс из позиции р,, если граф S - ориентированный мульти-граф, либо весу дуги (р,-,Те), если граф S взвешенный орграф *.

Предикату тс соответствует следующая функция изменения локальной маркировки: М й (Те) = М 0(Те) - 1п(Тс) + Out(Te).

Здесь М0(Те) - маркировка позиций возбужденного перехода Те; М s (Те) - маркировка позиций перехода Те после его срабатывания (через время 5 после возбуждения перехода). Задержка в общем случае может быть величиной случайной и закон распределения этой величины (ввиду специфики цифровой вычислительной техники) в программной реализации определяется дискретной функцией распределения, хотя можно реализовать вычисление и непрерывной величины 5. Во время активности перехода Те его маркировка Ма(Те) равна:

Мя(Те) = М0(Те)-1п(Те).

У перехода типа "переключатель" (обозначается Тх) имеется одна входная (р„) и несколько выходных () позиций. Для определения истинного предиката тсг вычисляется значение случайной величины X. Эта величина попадает в один из к интервалов области допустимых значений величины X, где к - число выходных позиций перехода Тх. Разбиение области допустимых значений величины X на к интервалов как и само значение к задается на этапе составления F-сетевой модели для каждого перехода типа Тх .

Номер г предиката тсг еIIх = {itj, те 71 k! определяет соответствующую функцию fr изменения локальной маркировки перехода Тх.

Ма(Тх) = М0(Тх)-1п(Тх);

ms (Рот) = т» (Рои, )+# (Pout, О(Тх));

rns (Pout) = ma (Pout). i = l.k,

Ms (Тх) = (ma ( pin), ms (p'ut),..., ms ( pL,),..., nig ( p0kut)).

Для перехода типа "приоритетная выборка" ( "код" Ту) имеется к входных позиций Ру, и одна выходная позиция Р00( , соответственно задаются к предикатов 7tj еПу

я, = true if m5(p|D)>#(p|D,I(Ty)) & r=j,

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

М.(Ту) = (ш,(р'ь),...,т.(р;„),...,т.(р'),т.(р„„));

тЖ)=>Ч,(р;.)-#(р;.,1(Ту));

т,(р;,)=т(,(р;.), V] = I,к,

М,(Ту) = М.(Ту) + 0|й(Ту).

Для перехода типа "критический ресурс" ("код" Т<1) имеется по к пар входных р;п и выходных рои( позиций. Предикат тс | еП,) и функция

^\ с ■> ] - к имеют вид:

¡Г т(р|п)>#(р|,1,1(Т(1));

ш3{р1) = п,()(р|п)-#(р|п,1(Т(1)); т,(р,)=«пв(рД V?,. е{0(Тс1)и1(Та)\{р|пИ; тй(рЦ) = та(р!„,)+#(р^,0(Т(1)); тя(р,Ьта(РЛ еП(Тс!)110(Т(1)\!р:„1,П.

Каждая пара (р,„,р,!„„) представляет собой коикурирмошчй ирои.чч-¡а право использован, представляемый переходом критический рес\.. Нел и в переходе уже находится маркер (переход в актином состятнп. то маркеры в остальных входных позициях будут ожидать окончания активной фазы. Выбор входной позиции, из которой будет извлекаться маркер, зависит от приоритета этой позиции. На основе этого перехода строится и процедура функционирования перехода типа память (Тш).

Для перехода "прерывание" (код Т() имеем (3*к-2) предикатов, которые сгруппированы по три для ] ~ 2, к — 1 и образуют следующую последовательность:

7г]=1гие ¡С ш(р|в) >#(р{„, 1(Т1)) & переход "П активен от

срабатывания по предикату с номером г > 3* ] ; 71?=1гие ¡Г ш(р^)>#(р[1,1('П)) & значение приоритета

(статуса) маркера на вершине стека позиции Р0 больше номера (8(р0)>|);

7г? = егие ¡Г ш(р|в)>#(р|п,1(Т|*)) & переход Т1 пассивен. Для ] -1 задаются два предиката : тс} подобен тс-, а тс* - я?

Для j - к - тоже два предиката: первый подобен я?, а второй - я]\

Таким образом, любой из предикатов относится к одному из трех классов. Каждому предикату соответствует своя функция изменения маркировки.

Функция fji определяется следующими выражениями:

ma(Pu)= т«(Ро)+* ? в стек позиции р<> засылается запись из двух полей - статуса маркера S(p0), равного j, и времени 5(р0), равного 5-z, где г - момент времени прерывания предыдущей активности перехода;

ma(pL) = n,0(pL)-#(pLJ(Ti));

ma(pv)=m0(pT), Vp, е{O(Ti)UI(Ti)\{p|„, PoH > ma(Poui) = ma(pLi)+#(pLi»0(Ti));

ш6(р,) = т,(Рт), Vp, e{I(Ti)(JO(Ti)\{ pLt П;

Для функции fp справедливы выражения :

ma(Po) = rn0(p0)-I; с вершины стека позиции снимается запись {S(p0),(8-z)}, где S(p0) - статус (приоритет) прерванного ранее процесса, а 5 - г - оставшееся время его активности: ma(pv)=m0(pi), Vpv e{O(Ti)(JI(Ti)\{p0}};

m5z(Pout) = та(Р:«.)+#(Р^,О(Т0);

m5,(Pl)=ma(pv), VPv e {I(Ti)UO(Ti) V {p®ttt}}. Наконец, для функции 1}з имеем следующие выражения:

•n.(p,h) = «ne(pL)-#(pL.I(TI));

«n,(Pv)=m„(pT), Vpv 6{0(Ti)UKTi)\{p|n}};

ms(pL) = ma(pLt)+#(pL„0(Ti));

m6(Pi) = ma(Pv), Vpv е{1(Т!)иОСП)\{р^}}.

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

1) ф! - выборка из памяти и загрузка в регистр команд новой команды по адресу, указанному в счетчике команд;

2) tp2 - дешифрация кода операции:

3) фз - определение адреса операнда н, если он находится в одном из рабочих регистров процессора, - его перепись в соответствующий регистр-аккумулятор арифмегико-логичского устройства (АЛУ) и переход к фазе cps;

4) ф4 - извлечение операнда из памяти:

5) ф5 - собс!венно выполнение указанной операции над операндами;

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

7) ф7 - определение адреса следующей команды посредством соответствующего изменения значения в счетчике команд.

Реально моделируемый процессорный элемент может и не иметь все эти семь фаз. а иметь, например, только фазы ф1 . фг . фз . ф* . ф? . что справедливо для одноадресной команды. Информация о возможных фазах для данною процессор;) и граф-схема переходов и; фа я,; в фа .•. должна оьпь отображена в параметрах перехода, представ ¡ямше:о соо:-веювуюший процессор. В начальный момент времени при ипиииади ;а-ции перехода Тр он находится в фазе ф1. а дальше, в еоошетствин с процедурой эмуляции, он последовательно переходит в другие фазы. Маркировка при этом будет изменяться в соответствии с предикатами 7t[ и л2, которые вычисляются следующим образом:

Til = <pi v ф4 v фй ; ti i-->fi ;

Til = ф2 V фЗ V ф5 V ф7 ; К2->Í2.

Для предиката т имеем следующие правила изменения маркировки, составляющие функцию fj:

m-(p;<.) ~ т«(р») - 1 : т-(р„) ~ т,(р,.,) - 1 :

ms(po«t ¡) = 0 , V i * k ; гт(р»«1 0 = 1 , k=I v2v3 .

То есть, если переход находится в фазе ф| v ф< v ф6 , то маркер изымается из входной позиции pin и переходит в одну из выходных позиций,

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

А для предиката к2 маркировка изменяется следующим образом:

ma(Pin)=mo(Pin)~1 J m5 С Pin ) — mo(Pin) ;

mfi(Pout) = ma(Pout )=m«(PD -

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

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

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

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

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

Завершастся раше! описанием предложенною алгоритма построения дерева достижимых маркирований К-сстсвыч моделей. Вершины »того дерева показываю! с какой всрожнистыо и. черс» какое время •'!.! можем попасть в то или иное состояние.

Третий раздел диссертации "Принципы создания комплекса программ для имитационного моделирования мультипроцессорных вычислительных систем на основе использования Я-сетей" начинается с

изложения основных принципов его создания, к которым отнесены следующие:

• использование "моделирующей машины" для имитации функционирования сети;

• использование возможностей современного графического интерфейса для ввода и редактирования моделей, наблюдения и управления процессом имитации;

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

мени выполнения программ и определения ожиданий;

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

• использование объектно-ориентированных методов программирования не только как современной технологии создания программных средств, но и как средства для обеспечения идеи типизации переходов и открытости к введению новых типов;

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

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

Схема алгоритма моделирования функционирования Р-сети приведена на рис. 1. Алгоритм построен на использовании нескольких динамических списков:

1. список переходов, входящих в состав Р-сетевой модели, который и представляет собой структуру 8 сети N. Элемент этого списка -сложная структура данных (запись), поля которой отображают тип и параметры перехода, его идентификатор (порядковый номер и имя), входные и выходные комплекты перехода и другие данные;

2. список завершения - список активных переходов, упорядоченный по временам завершения активной фазы перехода;

3. очередь блокированных переходов - неупорядоченный список блокированных переходов.

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

Рис. 1. Схема алгоритма имитационного моделирования Р-сети.

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

Возможность систематически проверить каждую комбинацию значений так, чтобы быть уверенным, что не пропущено ни одного правила, является большим преимуществом таблиц решений. Если принимаем в учет N условий и значения комбинаций условий представляют собой только 0 (нет, ложь - false) или 1 (да, истина - true), то количество правил

будет равно 2N. Возникает задача определения правила, соответствующего конкретной ситуации. Очевидно, что последовательное вычисление

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

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

n

Rj = £cu-cij . Каждая возможная комбинация ответов должна давать

¡=1

свою единственную, отличную от других, сумму весов (код правила). Очевидно, что таким весом может быть соответствующая степень двойки. Определив код правила, можно с помощью оператора вычисляемого перехода типа GOTO(Li,L2,...lLif...Lk))Rj передать управление на ту часть программы, которая исполнит соответствующие действия.

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

В общем случае для определения времени выполнения машинных циклов и направления транзактов МВС описание модели процессорного элемента должно состоять из:

• возможных фаз (циклов) и длительности каждого цикла в машинных i актах;

• системы команд, включающей форматы команд и набор операций;

• peí истровой структуры процессора;

• способов адресации команд и данных;

• форматов данных.

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

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

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

Редактор настроечных таблиц осуществляет ввод и редактирование элементов таблицы форматов и таблицы кодов операций. Микропро-

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

Рис. 2. Структура и функциональные связи подсистемы эмуляции

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

В.чстнертом разделе диссертационной работы "Примеры использования Р-сетей для моделирования вычислительных систем" рассмотрены: бортовая многомашинная вычислительная система с высоконадежной кольцевой магистралью и маркерным методом доступа, бортовая вычислительная система ЦВМ 80-400 и работа процессора с кэшпамятью.

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

Второй пример иллюстрирует подход к моделированию МВС на уровне исполнения двоичного кода. Для двухпроцессорной ЦВМ 80-400, структурная схема которой изображена на рис. 3, построена Р-сеть, представленная на рис. 4.

! Пи'ШСЛНТСАЬНЫН

клитур НС. 1

Процессор

мп т в

Э ЗЧ-ЧЯКЧб

МП -1/ и

ЭЧ'| ЧГ.К'16

МП «Д I О.Ш 1К-11, | 1ИЧЗ/Г.ЧН ]

гин 16КЧЕ ОЗУ

пзи 1СК-1Е ОЗУ 2КЧ6

ОЗИДП 2К-1Е

М(1 <11

) ■;!! и." и.

~г

МВ 40

Процессор

Л

ОЗУДП

гкчв

ль

£

Оичнсактельиый КОНГ/р П'К 2

МП 4 7 А

оза-4к*1С

ПЗУ 32КЧ6 ЭЗН-16К*!

ип 1<П

03Я-1КЧ6

I 1 • - ■ ! ■ Т—1__г

П^Т"

И<1 >1 I

" I

03У-1КЧ6 I

Рис. 3. Структурная схема ЦВМ 80-400

Бортовая вычислительная система ЦВМ 80-400 состоит из двух вычислительных контуров ВК1 и ВК2. Каждый контур комплексируется на

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

Рис. 4. F-сетевая модель ЦВМ 80-400

На оба вычислительных контура ЦВМ 80-400 возлагается несколько задач вычислительной системы управления полетом (ВСУГ1). При моделировании необходимо учесть, что обмен информацией - программно управляемый (процессор при обмене занят), канал занят на все время обмена. Архитектура процессора МВ40 задана, двоичные коды исполняемых программ и карты распределения памяти для этих программ имеются. Функциональные программы решения задач ВСУГ1 разработаны на языке Pascal и подготовлены для ЦВМ 80-400 с помощью соответствую-

inert кросс-сисгемы. Микропрограммы, описывающие систему команд процессора МВ40 на изложенном в подразд. 2.3. языке, приведены в Прил. 2. Результаты вычислений, выполняемых в МВ40 В К1 каждые 0.1с, используются ВК2, и наоборот. Некоторые исходные данные и вычисленные параметры выбираются и записываются в модули МД40 и МД41.

В модели, представленной на рис. 4, каждый из вычислительных контуров представлен своей подсетью (подсхемой) обработки транзитов. Подсеть содержит в качестве обрабатывающих устройств процессор и устройства памяти - ОЗУ, ПЗУ, ОЗУДП, МП и МД. Процессоры представлены переходами ti и tz. Переходы h и in представ ляют ОЗУ из модулей МП47А каждого вычислительного контура. ПЗУ и энергонезависимое запоминающее устройство (ЭЗУ) в работе не участвуют; ПЗУ этих модулей хранят программы, которые загружаются в ОЗУ при включения ЦВМ. Переходы ti и tn представляют модули МД40, предназначенные для связи ЦВМ 80-400 с остальным оборудованием. Из них читаются некоторые переменные и в них записываются вычисленные управляющие воздействия. Переходы t? и tin, U и ti, Ь и tx представляют ПЗУ, ОЗУ и ОЗУДП первого и второго вычислительных конт\ров соответственно.

Подсети пересекаются: каждый из процессоров может обртигыъ к ОЗУДП другою ВК. что моделируется использованием переходов b е ь которые в качестве базово! о т ипа имеюt тип I'd.

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

В результате проведенных на этой модели исследований были сделаны выводы о гарантированном выполнения программ ВСУП на ЦВМ 80-400 в масштабе реального времени при тех параметрах быстродействия МВ40, которые предлагалось реализовать разработчика мл (программы выполнялись за 27340 тактов при резерве в 100000 тактов), и что можно не делать внешней синхронизации вычислителей для уменьшения потерь времени на ожидание результатов.

Завершается последний раздел кратким изложением методики составления F-сетевых моделей.

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

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

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

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

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

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

Разработанные мегоды, модели, алгоритмы и программные средства использовались при проведении ряда НИР, в том числе и для исследования и разработки концепции бортовых вычислительных систем и сетей 1990-х годов, что позволило промоделировать основные варианты создаваемых БЦВС, сократить сроки проектных работ и гарантировать работу систем в режиме реального времени.

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

Windows", который находится в фонде Российского ПИИ информационных систем при министерстве высшей школы и технической политики

Российской Фсдерации.

Публикации

По материалам диссертации опубликованы следующие работы:

1. Гордеев A.B. Расширение модели Г-сетей для представления процессов обработки прерываний. Н Распределенные вычисления и системы на СБИС: Сб. науч. тр. / ЛИАП, JL, 1988. С. 51-56.

2. Гордеев A.B., Филиппов С.Г. Автоматизация системотехнического этапа проектирования систем управления дискретными процессами. // Ав томатизация проектирования приборов и систем управления. Меж-вуз.сб науч.тр., ЛИАП, Л., 1989. С. 39-43.

3. Гордеев A.B., Доманский В.Т., Молчанов АЛО. Использование сетевых моделей для имитационного моделирования системы диспетчерского контроля и управления устройствами электроснабжения железных дорог // Вестник ВШ111ЖТ. 1994. X 1. С.38-48.

4. Гордеев A.B.. Доманский В.Т.. Молчанов А.К). Применение слевы-. имитационных моделей для опенки надежное!и функнионирован!:-, системы лиспе!черского контроля и управления. II В сб. наем. тр. СПбИИТ, 1994. С. 71-76.

5. Гордеев A.B. Моделирование дискретных параллельных eueres! с использованием Г-сетей Петри II Материалы Международного симпозиума по проблемам модульных информационных компьютерных систем и сетей. С.-Пб.. 1997.

6. Гордеев A.B., Кириллов П.П., Молчанов А.10. Система имитационного моделирования процессов функционирования сложных систем как компонентов систем поддержки принятия решений. // Материалы ДСП секции прикладных проблем при АН СССР. 1992. С. 34-40.

7. Гордеев A.B., Молчанов А.Ю. Применение сетей Петри для анализа вычислительных процессов и проектирования вычислительных систем: Учеб. пособие. / Санкт-Петербург : ГААП, 1993. 75 с.

8. Гордеев A.B., Молчанов АЛО. Проектирование вычислительных комплексов с использованием средств имитационного моделирования на основе F-сетей. // Информа-ционно упраляющие и вычислительны комплексы на основе новых технологий. Тез.докл. Всероссийской НТК. Санкт-Петербург, 1992, С. 61.

9. Гордеев A.B., Молчанов А.Ю., Платонов Н.Э. Диагностирование мультипроцессорных вычислительных систем реального времени. // Техническое диагностирование - 93: Тез. докл. науч.-техн. конф. (г. Санкт-Петербург, 8-10 июня 1993 г.) - с.13-14.

Ю.Гордеев A.B., Платонов Н.Э. Применение новых методов для повышения качества программного обеспечения вычислительных комплексов и систем. // Всероссийская научно-техническая конференция с международным участием "Информационно-управляющие и вычислительные комплексы на основе новых технологий. Наука и маркетинг": тез. докл. / СПИАП. СПб., 1992. С. 66-67.

11.Гордеев A.B., Платонов И.Э. Технология эмуляции базового системного программного обеспечения мультипроцессорных вычислительных систем. // Качество программных средств. Материалы Ш Всесоюзной конференции. Дагомыс. 1991, С. I07-111.

12.Гордеев A.B., Платонов И.Э., Молчанов А.Ю. Средства эмуляции мультимикропроцессорных вычислительных систем. // Новые информационные технологии. Тез. докл. 2-й международной студенческой школы-семинара. Гурзуф, 1994. С.97-98.

1 З.Гордеев A.B., Филиппов С.Г. Введение избыточности в Е-сети для редуцирования имитационных моделей. //' X Всесоюзный симпозиум по проблеме избыточности в информационных системах : Тез. докл. / АН СССР, Д., 1989. ч.З, С.22-25.

Н.Гордеев A.B., Филиппов С.Г. Инструментальные средства моделирования и анализа архитектуры вычислительных систем. // Технология проектирования программных и аппаратных средств вычислительных систем. Материалы НТК 15-16февр., Л., ЛДНТП, 1989, С.75

15.Гордеев A.B., Филиппов С.Г. Синтез имитационных моделей с эмуляцией программ для виртуальных вычислительных систем. // Технология проектирования программных и аппаратных средств вычислительных систем. Л. ЛДНТП. 1990. С.17-20.

^.Программирование на Фортране 4Х: Метод, указания к выполнению лабораторных работ. / В.Н. Арсентьев, A.B. Гордеев и др. - ЛИАП, Л., 1988. С. 22-31.

17.Программный комплекс моделирования и анализа на основе сетей Пегри / С.И. Волков, A.B. Гордеев, М.Г. Зеленский и др. II Каталог отраслевого фонда алгоритмов и программ. Вып.7 - М.: НИИВО Госкомитета СССР по народному образованию, 1991, С. 30-31.

18.Программный комплекс моделирования и формального анализа систем на основе сетей Петри / A.B. Гордеев, М.Г. Зеленский, А.Ю. Молчанов, A.B. Никитин и др. // В кн. CASE-технологии - М.: Центральный Российский дом знаний, 1992. С. 71-76.

19.Гордеев Л.В. F-Сетн Петри для моделирования дискретных параллельных систем. Деи. в ВИНИТИ, per. номер 2638-В98. 1998. 2! с.

20.Gordejev A.V. Simulation of discrete parallel systems by modificated F-net's mctiiod. // ICS-Net'97: International Symposium on Problems of Modular Information Computer Systems and Networks. Abstracts. Moscow-Sl.-Peterburg, 1997, P. 13.

21.Электронный учебник "Сети Петри: Моделирование и анализ", ¡992 г. - по заказу РосНИИИС;

22,"Интегрированная система моделирования и анализа на основе сетей Петри", 1994 г. - по заказу С.-Пб. РФНТР;

23. "Сети Петри для Windows" (версия 2.2, 1996г.) по заказу РосПШШС.

.цензик ЛР № 020341 or 07.05.97 i. )рмат 60x84 1/16. Печать офсетная, .-изд. л. 2,25

Подписано к печати 20.10.3Sr Бумага тип Усл.-псч л 2

Заказ № 246 Тираж 100 экз.

Отдел оперативной полиграфии СПбГУАП 190000, Санкт-Петербург, ул. Б. Морская, 67