Построение синтаксически и семантически правильной Queue Network-модели в Triad.Net

Размещено на Allbest.ru

Рассматриваются вопросы автоматизации построения синтаксически и семантически правильной имитационной модели. В основании имитационной модели лежит математическая теория систем массового обслуживания. Такие модели в англоязычной литературе называют Queue Network. Для проверки синтаксической правильности модели в статье предлагается использовать графовую грамматику (поскольку для построения модели используют графический интерфейс и графовое представление лежит в основе Triad-моделей). Для проверки семантической правильности имитационной модели использован онтологический подход.

Ключевые слова: имитационная модель; графовая грамматика; онтологический подход.

Введение

правильная имитационная модель

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

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

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

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

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

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

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

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

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

Для того чтобы иметь представление о том, что такое система имитационного моделирования Triad. Net, рассмотрим структуру системы и место в ней графического редактора моделей.

1. Место графического редактора моделей в системе Triad. Net

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

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

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

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

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



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

Представление имитационной модели в системе Triad. Net.

Имитационную модель в системе Triad. Net можно определить как M = {STR, ROUT, MES}, где STR - слой структур, ROUT - слой рутин, MES - слой сообщений.

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

Каждая вершина обладает поведением, реализованным в виде наложенной на нее рутины из слоя ROUT.

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

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

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

2. Библиотека стандартных имитационных компонентов

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

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

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

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

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

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

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

Стандартные компоненты реализуются как специализации (расширения) стандартного класса «вершины» системы Triad. Net.

Список стандартных компонентов включает:

Генератор случайных чисел.

Очередь.

Устройство обслуживания.

Терминатор (завершение моделирования).

Внешний вид стандартных компонентов показан на рис. 2.



Рис. 2. Компоненты для моделирования систем массового обслуживания

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

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

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

рутина устройства обслуживания: закон распределения времени обслуживания, среднее время обслуживания заявки, количество каналов обслуживания.

Рутина терминатора настраиваемых параметров не имеет. Она лишь отмечает время ухода заявки из системы.

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

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

3. Проверка синтаксической правильности моделей

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

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

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

Резервной графовой грамматикой (RGG) будем называть четверку (A, P, Mt, Mn), где

A - начальный граф,

P - множество продукционных правил,

Mt - множество всех терминальных меток,

Mn - множество всех нетерминальных меток и p = (L, R) P:

R - это непустой граф,

L и R определены на одном множестве

меток l

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

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

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

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

Более подробно о графовых грамматиках и алгоритме парсинга графа с их помощью см. [3].

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

4. Резервная графовая грамматика для моделей систем массового обслуживания

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

Генератор требований не может быть напрямую присоединен к устройству обслуживания, так как большинство требований при этом, очевидно, будет теряться.

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

3. В очередь требований может входить любое количество дуг от любых вершин.

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

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

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

7. В терминатор требований может входить любое количество дуг от генераторов требований и устройств обслуживания.

8. В модели не должно быть ни к чему не присоединенных вершин.

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

SMO_RGG = {A, P, Mt, Mn},

где A = , Mt = {Генератор, Очередь, Устройство обслуживания, Терминатор, СМО}.

Здесь СМО - абстрактная вершина имитационной модели, играющая вспомогательную роль в процессе парсинга.

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

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

(а)
(б)
(в)
(г)
(д)
(е)

Рис. 3. Список продукций RGG для определения синтаксической правильности моделей систем массового обслуживания

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

На вход многоканальной системы обслуживания с n каналами поступает два потока заявок. Обслуживание заявки в устройстве занимает в среднем t.

Первый поток заявок - пуассоновский с интенсивностью h. Приоритет заявок первого потока - p1.

Во втором потоке интервалы поступления заявок распределены равномерно на отрезке [a; b]. Приоритет заявок второго потока - p2.

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

На рис. 4 изображен внешний вид графа модели данной системы массового обслуживания.

Рис. 4. Пример графа модели системы массового обслуживания

В результате последовательного применения продукций 3a, 3a, 3б, 3г, 3е получаем пустой граф.

На рис. 5 изображены все превращения графа в процессе применения продукций.

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

Автоматическое доопределение имитационных моделей

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

(а) После применения продукции 3а
(б) После применения продукции 3б
(в) После применения продукции 3г
(г) После применения продукции 3е

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

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

В терминологии системы Triad. Net не до конца описанная имитационная модель определяется следующим образом:

,

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

Здесь нам на помощь приходит понятие семантического типа. Семантический тип - это специальная абстракция, которая используется, чтобы сгруппировать ряд объектов системы по смысловому, структурному и поведенческому признакам [4].

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

условие специализации,

условие конфигурации,

условие декомпозиции.

Условие специализации выполняется, если просматриваемая рутина соответствует семантическому типу вершины, или более частному типу.

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

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

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

Иерархия семантических типов в онтологии представляется в виде иерархии классов рутин, верхним элементом которой является класс MpsRoutine, т. е. рутина системы массового обслуживания. При формировании иерархии семантических типов большую роль играет множественное наследование, например, семантический тип «Многоканальное устройство обслуживания с нормальным распределением времени обслуживания» является дочерним для семантических типов «Многоканальное устройство обслуживания» и «Устройство обслуживания с нормальным распределением времени обслуживания».

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

Список литературы

Миков А. И. Автоматизация синтеза микропроцессорных управляющих систем. Иркутск: Изд-во Иркут. ун-та, 1987.

Клейнрок Л. Теория массового обслуживания / под ред. В. И. Неймана. М. : Машиностроение, 1979.

Zhang D. -Q., Zhang K., Cao J. A context-sensitive graph grammar formalism for the specification of visual languages. // The Сompu-ter Journal. 2001. Vol. 44, №. 3. С. 186-200.

Миков А. И., Замятина Е. Б., Кубрак Е. Онтологический метод доопределения имитационной модели // XIVth International Conference «Knowledge-Dialogue-Solution», Var-na, Bulgaria, 2008. С. 133-140.

Размещено на Allbest.ru

...