Разработка и анализ каркаса имитационной системы на основе логической сети действия Цукровски Яцек

Введение к работе

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

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

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

В данной диссертации разработка этого направления проводится в соответствии с координационным планом.НИР АН СССР и ГКНТ СССР на 1986 - 1990 г.г. по заданш пп 1.13.5.1 "Разработка методов манившого моделирования для решения задач управления развитием систем различного назначения. Разработка специализированных имитационных систем моделирования ...", по.которым Московский энергетический институт записан исполнителем.

Целью диссертационной работы является разработка

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

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

( Logic rfctivitt/ foih/erA -LA/J),

разработки принципов формализации объектов в имитацион- них моделях ВСС на базе LAN ,

определения эквивалентных преобразований структур моделей, описанных в терминах LAN,

программной реализации базовой имитационной системы (каркаса имитационной системы), обеспечивающей проведение машинных экспериментов в среде DOS IBM/PC, в которой реализованы также алгоритмы преобразований структур сетевых моделей,

разработки компонентов проблемно-ориентированной моделирующей системы с использованием языка TURBO PASCAL IBM/PC,

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

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

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

'5 -

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

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

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

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

диалоговые срецотва общения пользователя с системой,

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

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

О с н о їв не научные результаты:

разработаны принципы формирования каркаса имитационной системы,

разработан метод формализации объектов в терминах логических сетей действий,

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

разработаны методы эквивалентных преобразований сетевых моделей,

разработаны алгоритмы функционирования каркаса имитационной системы,

создана программная реализация каркаса имитационной системы на языке Паскаль для ПЭВМ типа ІБМ/РС,

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

Реализация резу ль татов работы.

С использованием созданной автором моделирующей системы была разработана и внедрена в эксплуатацию имитационная модель информационно-вычислительной системы, работающей под управлением пакета прикладных программ "Щ'А" в НПО "ПОИСК". На основе разработанного программного комплекса создан и внедрен в учебный процесс цикл лабораторных работ, предназначенный для обучения основам имитационного моделирования технических систем.

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

Международной научной конференции по теме: "Средства обучения и их научное использование для реализации новых программ обучения" в Педагогическом институте им. Н.К. Крупской города Халле (ГДР) (2 доклада),

Научной конференции, посвященной вопросам телекоммуникации, в городе Быдгои (ШР),

Публикации. По теме работы опубликовано шесть научных статей.

Структура, и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, описка литературы и приложений. Основной текст - 143 страницы. Список литературы включает 119 названий. В работе имеется 9 табтщ я 58 рисунков.

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

дедей с целью более рационального использования ресурсов ПЭВМ.

Во второй главе разработаны принципы формирования каркаса имитационной системы. На основе анализа структурных особенностей существующих сетевых моделей с позиций имитационного моделирования, выделен набор компонентов формализованного описания событий, действий и процессов. По аналогии с известныш сетями представленная схема названа логической сетью действий ( Logic bctil/ity NetWOrK -LA/V).

Формально LAN определяются выражением:

< V, П,ф,М, fo, R > , где

И - множество ПОЗИЦИЙ П =QUSUL , Q - макропозиции (очереди), S - простые позиции, L - разрешающие позиции, У - множество переходов V = Т иР , Т - элементарные переходы, Р - макропереходы, Ф - отношение инцидентности ^ = Лк V v Vxfl , М - множество меток М = [ті | ті*(ві,і, &;,г,—, &;,#)} где Oi,j - J -тый атрибут і -той метки {<-=77л , где п - количество меток; ]'!7к , где к - количество атрибутов метки), и₀ - отношение разметки в начальный момент,

/о-pi,mj,n,)\z_le- ausi/P, rn^M, />*t/} , где

Zi - идентификатор узла сети, mj - метка,

n, - порядковый номер метки в узле ( /V - множество натуральных чисед).

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

Состояние модели, описанной в терминах LAЛ/, определяется виражением: W = ( R ,//'), где^и - отношение разметки.

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

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

Простые позиции ( S ) выражают условия. Пустая позиция означает, что условие не выполняется. Позиция, содержащая метку, означает выполнение условия. Очереди (Q ) накапливают метки в соответствии с дисциплиной FIFO . разрешающие позиции ( L ) модифицируют функции активизации переходов. Позиция L выражает связь между инцидентными с ней переходами и другими компонента-ля сети и реализует функцию: IV» Г — (0,1), где IV - множество состояний системы, Т - модельное время.

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

-io-

где П;( Vj ) - множество входных позиций перехода V_t-(^^e7~vP )

n₀{Vi) - множество выходных позиций перехода Vity-^TuP )

П_а№)= ( Пх/ П_к <* П *Vi ФПк }
и(Пі) - состояние ПОЗИЦИЙ Л/(/е {},К } )

О, если f?j eSuQ и позиция пустая или u)(f7_t) = fl_t*-L и не выполнено разрешающее условие, *0 , в противном случае, .

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

Срабатывание перехода вызывает изменение состояния модели. (отношения разметки и содержимого регистров сети): VJ* Т — W .

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

-ii -

лементарных переходов, образующих макропереход.

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

В зависимости от требований описания объекта (степени дета-шзации модели), определяемая Р-переходом задержка метки, а такие другие действия над моделируема/ объектом задаются с помощью:

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

сети, характеризующей внутреннюю структуру моделируемого переходом объекта.

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

Сложный переход может содержать произвольное число меток.

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

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

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

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

,/77 - КОЛИЧеСТ-

ВО подмоделей сетевой модели А/ ) ,

определен набор прообразorгний Н: Я-{hi | hi (М) --ЛІ' ({й(*Гі > (f_t(tf'S * (Г, (A/J > /, (tf'J) и (f_r ('/// z.(f_r (Vj л (f_e сл/> > f_ecf/')>) л * А (ли'Яш';}

( і ^f»" ), где /_г - временная сигнализирующая функция (указывает количество тактов работы машины Тюринга, являющейся математической моделью ЭВМ), fa - емкостная сигнализирующая функция (указывает количество используемых ячеек памяти, необходимых для получения реакции модели)./? (Jfj , R(M'J - реакции программных моделей: М - заданной набором сетей /И и М - заданной набором сетей Л/ .

-ІЗ -

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

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

сохранение функции продвижения молельного времени,

сохранение функции переходов,

сохранение выходной функции модели.

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

В модели, описанной в терминах АМ , выделяются следую-цие группы элементов (вершин графа):

1. Элементы структуры сети: л/=/1и/ ,

2. Сетевые регистры: R .

При этом множество элементов «одели ( D ) определяется суммой множеств:

В = Пи Vuk

Взаимодействие элементов модели может быть отражено направленным графом:

н>,

где J? - множество вершин (множество элементов модели),

H - множество направленных связей

tfc:J>* В,

Связь ( d; , cfj ) между элементами, di и <т существует тс да и только тогда, если состояние элемента ctj влияет на состояние элемента Оу

Тают образом, в имитационной модели, описанной в термина LAЛ/ , выделены следующие типы связей:

1. Сетевые связи:

(задаются конфигурацией сети).

2. Связи кежду-элементами структуры сети и сетевыми регж

рами:

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

3. Связи между регистрами сети и элементами ее структуры
#'* ihj CJ.-.JjJ] Є 4 ьЛ; л (c/j<&luV) J ,

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

4. Связи между регистрами сети:

(устанавливается в случае, если значение регистра fj определ , ся с учетом значеная регистра /} ).

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

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

t

S а C_f*t * Z h *j

где: с і - сложность элемента типа і ,

к і - количество элементов типа і ,

lj - сложность связи типа J ,

dj - количество связей типа J . Элементы и связи в приведенной формуле соответствуют вершинам и дугам графа модели. С использованием операций на' сетях разработаны основные методы преобразования имитационных моделей, описанных в терминах ІААҐ, На основе сформулированных требований, обеспечивающих эквивалентность преобразований имитационных моделей и соотношений оценки сложности моделей показано, что разработанные метода преобразования структур моделей, описанных в терминах LAH, сохраняют реакцию входа-выхода исходной модели й упрощают ее структуру.

В четвертой главе на основе анализа структуры каркаса имитационной системы., показана возможность алгоритмического описания взаимодействия его основных компонент и разработаны алгоритмы генерации процедур, описывающих функции базовых элементов модели. Показано, что возможности, предоставляемые системой программирования TUR50 PASCAL 4.0., предназначенной для ПЭВМ типа IBM/PC, такие как: динамическое управление памятью, организация библиотек скомпилированных процедур и функций, возможность присоединения и использования функций и процедур разработанных на других алгоритмических языках, таких как АССЕМБЛЕР, ЗОРТРАН, С,

-.16 -

ПРОІОГ, широкий набор математических и графических процедур и т, д., позволяют заложить этот язык в основу разрабатываемой имитационной системы. На основе анализа особенностей программных и сетевых структур имитационных моделей,, описанных в терминах LAN , показана возможность программной реализации эквивалентны) преобразований сетевых моделей и разработаны их алгоритмы. Разработана программная реализация каркаса имитационной системы, состоящая из:

управляющей програти имитационной системы,

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

библиотеки, содержащей моделирующие и отладочные процедуры каркаса имитационной системы,

компилятора языка TUR60PASCAL 4.0,

работающая под управлением SOS в среде ПЭВМ типа ІВЇЦ/РС. Показано, что разработанная имитационная система, обеспечивающая, возможность определения и присоединения наборов скомпилированных процедур и функций, является основой для разработки проблемно-ориентированных моделирующих систем. Показано, что реализованный в разработанной имитационной системе принцип формирования имитационных моделей из набора ранее созданных сетевых модулей обеспечивает возможность создания на ее основе проблемно-ориентированной системы моделирования в виде множества параметрических моделей типовых компонент объектов,принадлежащих данной предметной области.

В пятой главе рассмотрены особенности применения имитационной системы. Описана разработанная имитационная модель информационно-вычислительной системы (вычислительного центра с або-

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

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

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

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

автоматическую генерацию моделирующей программы на осно-! сетевой модели,

возможность просмотра и'анализа работы сетевых моделей . экранах мониторов,

возможность отладки и тестирования создаваемых моделей графическом режиме,

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

е разработанного программного комплекса в учебном процессе.

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

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