|
|
| |
РАЗРАБОТКА ПРОГРАММНО -АЛГОРИТМИЧЕСКИХ СРЕДСТВ МОДЕЛИРОВАНИЯ СЛОЖНЫХ ДИСКРЕТНЫХ СИСТЕМА.А. Суконщиков, А.Н. Швецов Возрастающая роль моделирования сложных дискретных систем объясняется тем, что аналитические и инженерные методы анализа поведения таких систем, принятые для традиционных подходов, оказываются не применимыми или слишком приблизительными для современных информационных систем, вычислительных сетей, автоматизированных производств и им подобных объектов. Исследование функционирования сложных систем требует использования математического аппарата, учитывающего параллельный и асинхронный характер взаимодействия процессов в системе. Традиционным математическим средством являются математические модели, системы массового обслуживания (СМО) и различные языки имитационного моделирования ( Simula, GPSS, SMPL, Modula и т.д.)Смо не всегда позволяет отразить в моделе особенности аппаратной и программной архитектуры моделируемых сложных объектов, не отражают иерархичность моделируемых систем, не обладают достаточными свойствами модульности и расширяемости. Модели построенные с помощью языков имитационного моделирования, особенно сложных систем с большим количеством связей и параметров, не отвечают требованиям корректности к логической противоречивости. Возможности применения аналитических моделей ограничиваются тем, что существует ряд сложных дискретных систем, поведение которых трудно или вообще не возможно описать традиционными алгоритмическими средствами. К таким системам могут быть отнесены сложные технологические процессы, экономические системы со столкновением интересов участников взаимодействия, социальные системы, в которых поведение объектов социума зависит от множества трудноформализуемых факторов.Авторы в данной работе предлагают на основе авторских публикаций рассматривать моделирование как целостный процесс, включающий в себя не только построение модели и реализацию ее теми или иными средствами имитационного моделирования, но и формализацию, верификацию, проверку корректности и логической непротиворечивости в статике и в динамике на всех стадиях моделирования: -формализация сложных объектов [1]; – верификация моделей [2]; - оптимизация структуры моделей [3]; - моделирование сложных дискретных объектов [4]В настоящее время существует несколько подходов к формализации сложных дискретных систем: автоматные модели, языки спецификаций и комбинированные методы. Первая группа базируется на использовании моделей с состояниями и переходами. Данные методы просты и наглядны, однако при детальном описании сложной системы их применение приводит к чрезмерно большому числу состояний (диаграммы состояний, конечные автоматы, одинарные сети Петри ).[5]Методы второй группы позволяют формально представить сложный объект через алгоритмы его функционирования ( SDL, система ПРАНАС, ESTELLE и др.)[5] Преимущество этих методов заключается в уменьшении размерности описания объектов, недостатки же состоят в том что теряется наглядность формального описания и отсутствует возможность выделения важнейших свойств объекта.Комбинированные методы представляют собой сочетание средств первой и второй группы и позволяют использовать преимущество каждого из подходов. Предлагаемый авторами подход представлен на рис. 1 Существенным отличием от классического подхода к процессу моделирования может служить автоматизированный выбор аппарата формализации в процессе диалогового взаимодействия с создаваемой для этого программной системой.Для формализации моделируемого объекта предлагается использовать аппарат сетей Петри (СП ), обладающих множеством различных классов. Наиболее мощный класс СП – это прдикатно-временные сети (ПВС), которые позволяют строить более адекватные модели объектов. Однако непосредственный переход от вербального представления объекта к формализованному описанию является весьма сложным. Это связано с тем/, что при указанном переходе должна быть обеспечена строгая однозначность и непротиворечивость вербальных структур и их формальных спецификаций. Для исключения возможных ошибок на этапе перехода необходима последовательная детализация формализованного описания.В связи с этим предлагается следующая методика построения описания формализованного объекта: - первый этап – построение структурной схемы объекта с указанием всех взаимосвязей; - второй этап – построение модели объекта на основе диаграмм состояний, определение состояний объекта, условий и вероятностей перехода из олного состояния в другое; - третий этап – более детальную формализацию объекта обеспечивает аппарат сетей Петри, модель на основе ПВС является базой для верификации объекта.По мнению авторов значительный интерес для решения задач формализации и верификации моделей сложных систем в условиях вероятностного поведения представляют такие математические средства как аппарат канонических исчислений Э.Поста, квазиканонические исчисления Н.А.Шанина, атрибутные и W- грамматики [6]. При использовании таких формализмов появляется возможность описания поведения сложной системы правилами вывода или системами продукций, определяющими взаимодействие объектов сложной системы без знания точных алгоритмов их поведения в любой момент времени.Теория дедуктивных систем представляет мощный и естественный аппарат для моделирования недетерминированных процессов. При этом требуется введение вероятностных мер на множествах выводов, способы построения таких вероятностных исчислений были определены в работах С.Ю.Маслова.Авторами статьи аппарат канонических вычислений использовался для формализованного описания языковых средств и процессов трансляции в системе программирования [3].Применение для верификации свойств модели ПВС с матричным анализом ведет к существенному сокращению времени исследования, позволяет решить задачу корректности логической модели объекта. [2]Для анализа модели объекта ПВС используется матричный метод, который основан на получении систем L и I инвариантов (по предикатам и переходам модели), при этом используется модификация алгоритма Фаркаса [2].Модель полученная в результате верификации, является основой для имитационного моделирования с целью оптимизации и определения выжнейших свойств сложного объекта с вероятностным поведением. Результатами такого моделирования могут служить стратегия управления объектом, критерии и области корректного поведения объекта, свойства реализуемости и выводимости [7].Как видно из вышеизложенного, основными проблемами при решении исходной задачи являются: определение критериев выбора аппарата формализации, разработка способов построения формальных моделей, разработка критериев оптимизации моделей, построение программных средств, обеспечивающих соответствующие этапы моделирования. Для этих целей разработана программа верификации формализованной модели на основе ПВС, осуществлен переход от формальной модели на базе ПВС к модели на языках имитационного моделирования GPSS и SMPL. Разработанные программы были использованы при исследовании протоколов для сетей ЭВМ, моделировании робототехничеких комплексов и проектировании вычислительных устройств.ЛИТЕРАТУРА
|
|
|
