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

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

Олзоева Сэсэг Ивановна

МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ В ЗАДАЧАХ РАЗРАБОТКИ РАСПРЕДЕЛЕННЫХ АСУ

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

процессами и производствами (промышленность)

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

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

Работа выполнена в Санкт-Петербургском Государственном электротехническом университете «ЛЭТИ» им. В.И. Ульянова (Ленина)

Научный консультант -

доктор технических наук, профессор Кутузов О.И.

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

доктор технических наук, профессор Сольницев Р.И.

доктор технических наук, профессор Водяхо А.И.

доктор технических наук, старший научный сотрудник Песиков Э.Б.

Ведущая организация — ОАО Научно-производственная фирма "Меридиан"

Защита диссертации состоится «-^<7 » 1Л1Си2006 г. в 7 У час, на заседании диссертационного совета Д 212.238.07 Санкт-Петербургского Государственного электротехнического университета «ЛЭТИ» им. В.И.Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

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

Автореферат разослан

2006 г.

Ученый секретарь диссертационного совета

Яшин А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

Современные методы имитационного моделирования систем берут начало в работах таких российских и зарубежных ученых, как Бусленко Н.П, Глушков В.М., Моисеев ПН, Марчук Г.И., Нейлор, Шеннон Р., Гнеденко Б.В, Емельянов.С.В, Калашников C.B., Бусленко В.Н., Коваленко И.Н., Марьянович Т.П., Литвинов В.В., Гусев В.В, Вавилов A.A., Советов Б.Я., Яковлев Ç.A., Фомин Б.Ф., Аврамчук Е.Ф. В трудах этих и других ученых выполнен большой объем исследований по развитию методологии, методов и технологий системного моделирования. Разработаны средства и системы моделирования на базе универсальных алгоритмических языков, специализированные пакеты моделирования, проблемно-ориентированные системы моделирования.

Основные ограничения известных методов и технологий имитационного моделирования, используемых в настоящее время, обусловлены недостаточной эффективностью решения в них проблем производительности, настройки и адаптации к новой вычислительной платформе — многопроцессорным системам и сетям. Эти ограничения могут быть устранены на основе проведения исследований и разработки методов имитационного моделирования систем на распределенной вычислительной платформе, что должно обеспечить ускорение процесса моделирования без потери точности и упрощения модели. Исследованию и практическому применению методов и технологий распределенного имитационного моделирования посвящены работы Смелянского Р. Л., Бигдана В Ja., Марьяновича Т.П., Сахнюка М.А., Окольнишникова В.В., Вознесенской Т.В., Кутузова О.И., Замятиной Е.Б. и др.

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

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

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

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

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

1. Исследование и разработка методов, нацеленных на повышение эффективности применения имитационного моделирования в автоматизированных системах проектирования распределенных информационных систем АСУ:

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

- аналитико-статистических методов моделирования, ускоряющих сходимость метода Монте-Карло.

2. Исследование и разработка принципов построения автоматизированных средств организации распределенного имитационного моделирования РИСУ (АСОРИМ), ориентированных на специфику предметной области и предназначенных для комплексного решения задачи организации распределенного вычислительного процесса.

3. Исследование и разработка методов и алгоритмов решения задач, соответствующих технологическим этапам функционирования АСОРИМ и

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

4. Разработка распределенных имитационных моделей РИСУ и методик исследования характеристик функционирования РИСУ с использованием распределенного имитационного моделирования.

5. Исследование на практике эффективности применения созданных методов, алгоритмов и программных средств.

Объект и предмет исследования. Объектом исследования является распределенная информационная система управления, формально описываемая стохастической сетевой моделью. Предметом исследования является процесс имитационного моделирования РИСУ.

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

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

Конкретные новые научные результаты:

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

• - Предложен способ формализации и классификации множества путей транспортировки трагоактов, позволяющий с помощью построенной метрики и введенного критерия оптимальности разбиения выделить классы путей, близких по условиям транспортировки транзакгов. Предложенный подход к декомпозиции РИСУ сохраняет взаимообусловленность параметров и процессов всей РИСУ при имитационном моделировании конкретного пути, что позволяет организовать распределенное моделирование по модели параллельных вычислений БРМО.

■ Методы распределенного имитационного моделирования РИСУ с использованием моделей параллельных вычислений МРМО и БРМО, отличаю-

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

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

Научные положения и результаты, выносимые на защиту:

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

2. Комплекс методов распределенного имитационного моделирования РИСУ, включающий:

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

- метод распределенного имитационного моделирования по модели параллельных вычислений БРМО, отличающийся сочетанием принципов модели БРМО с аналитико-статистическим методом ускорения имитационного исследования РИСУ.

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

4. Принципы построения, методы и алгоритмы автоматизированного средства организации распределенного имитационного моделирования (АСОРИМ), обеспечивающего реализацию распределенного моделирования по критерию минимизации общего времени выполнения имитации и предназначенного для отделения аспектов создания программного обеспечения имитационной модели от вопросов организации распределенного вычислительного процесса.

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

- программный инстументарий АСОРИМ, автоматизирующий процесс организации распределенного имитационного моделирования;

, - распределенную имитационную модель РИСУ; . - имитационную модель виртуального канала.

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

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

Реализация и внедрение результатов работы. Теоретический базис разработанных методов повышения эффективности имитационного моделирования РИСУ основан на исследованиях, результаты которых обобщены в монографии, учебных пособиях, научных статьях и в докладах на национальных и международных конференциях. Часть разработанного программного обеспечения зарегистрирована в Роспатенте (имеется 2 авторских свидетельства об официальной регистрации программ для ЭВМ) 1 программа зарегистрирована в ФАП НИВЦ МГУ.

Тематика научных исследований, выполненных в диссертации, связана с планами кафедры «Автоматизированных систем обработки информации и управления» Санкт-Петербургского государственного электротехнического университета и кафедры «Электронно-вычислительных систем» ВосточноСибирского государственного технологического университета. Тема диссертационной работы тесно связана с выполнявшимися в СПбГЭТУ "ЛЭТИ" в 2002 - 2003 гг.. научно-исследовательскими работами: "Анализ и синтез моделей предметных областей на основе объектно — ориентированной технологии". (шифр НИР ГБ-2/ АСОИУ - 46, ГР - 01990003464), "Анализ и синтез моделей адаптивного автоматизированного управления производством" (шифр НИР ГБ-2. АСОИУ-58 к, ГР 01200405732).

, Теоретические и практические результаты работы использовались в научно-исследовательских работах, проводимых по планам госбюджетной НИР «Разработка и проектирование элементов и средств вычислительной

техники, информатики и радиотехники» ( Гос. per. № 012005738), «Теория и моделирование сверхбыстрых вычислителей на ОИС СВЧ и КВЧ диапазонах» (раздел «Проектирование телекоммуникационных систем, локальных и глобальных сетей») (Гос. per. № 01970005062), выполнявшихся на кафедре ЭВС ВСГТУ в 1997-2002 гг.. Основные результаты диссертационной работы нашли свое применение в виде инженерных рекомендаций и методик, пакетов прикладных программ и инструментальных средств при разработке корпоративной сети ВСГТУ и телекоммуникационного центра в качестве базы регионального телепорта.

Материалы, изложенные в диссертации, и полученные в ней результаты использовались при разработке информационно-вычислительной сети для Автоматизированной информационной системы «Информационный расчет-но-платежный комплекс» (АИС «ИРПК») по договору о научно-техническом сотрудничестве между кафедрой ЭВС ВСГТУ и ООО «ИПК «Биллинговый Центр», выполнявшемся в 2003 - 2005 годах. Комплекс программных средств, обеспечивающий методику исследования и моделирования ИВС с учетом конструктивных и эксплуатационных характеристик Автоматизированной информационной системы «ИРПК» внедрен в ООО «Информационно - процессинговая компания «Биллинговый Центр» г. Улан-Удэ.

Результаты диссертационной работы, связанные с аналитико — статистическим методом ускоренной имитации сетей АСУ, использовались при разработке сети обмена информацией в рамках хоздоговорной НИР, выполненной кафедрой АСОИУ СПбГЭТУ, по теме "Разработка методов и средств построения сетей обмена информацией с учетом необходимости их развития " (договор № 3138/ИС-8 от 2 декабря 1983 г.), а также при разработке сети обмена информацией Гидрометслужбы, выполнявшейся по НИР на тему "Разработка методов и средств построения системы сбора, передачи и распространения гидрометеоинформации" (договор № 2932/АСОИУ-3 от 29 ноября 1982 г.).

Результаты диссертационной работы используются в учебном процессе при чтении лекций, курсовом и дипломном проектировании, проведении студенческих НИР и в лабораторных работах на кафедре "Электронно-вычислительные системы" Восточно-Сибирского государственного технологического университета, кафедре «Автоматизированных систем обработки информации и управления» Санкт-Петербургского государственного электротехнического университета. Издано 2 учебных пособия, в том числе с рекомендацией УМЦ объединения ВУЗов политехнического профиля при МГТУ им. Баумана, и ряд методических указаний.

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих международных, всероссийских, региональных конференциях и семинарах: Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2003, МГУ им. Ломоносова); II и V Международных научно-практических Семинарах "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, 2002, 2005); I и П Международных конференциях "Математика, ее приложения и математическое образование", (Улан-Удэ, 2002, 2005); V, VI, VII и VIII Международных конференциях по мягким вычислениям и измерениям (Санкт-Петербург, 2002, 2003, 2004, 2005); I и II Межрегиональной школе - семинаре "Распределенные и кластерные вычисления" (Красноярск, 2001, 2002); Всероссийской конференции «Высокопроизводительные вычисления и технологии» (Ижевск, 2003); I, II и IV Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2000,2001, 2003); IV Международной электронной научно-технической конференции «Технологическая системотехника» (Тула, 2005); Международной научно-технической конференции «Информатизация процессов формирования открытых систем на основе СУБД, САЛР, АСНИ и систем искусственного интеллекта» (Вологда, 2001); Международной научно-технической конференции «Моделирование, оптимизация и интенсификация производственных процессов и систем» (Вологда, 2001); Международной научно-технической конференции «Автоматизированная подготовка машиностроительного производства, технология и надежность машин, приборов и оборудования» (Вологда, 2005); Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (Новосибирск, 2000); межвузовской научно-технической конференции «Управляющие вычислительные системы» (Вологда, 2000); Региональной межвузовской научно- практической конференции «Новые информационные технологии» (Владивосток, 2000); Региональной научно-практической конференции «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, 2005); Всесоюзной научно-технической конференции «Методы и средства решения задач в интегрированных АСУ» (Ташкент, 1984); Всесоюзной научно-технической конференции «Системы и средства передачи данных» (Черкассы, 1985); Всероссийской научно-технической конференции «Повышение эффективности и помехоустойчивости систем связи» (Севастополь, 1984); 15-ой научно-технической конференции «Проблемы создания новых и совершенствования старых существующих систем, средств связи и АСУ» (Киев, 1984); научно-технических конференциях ЛЭТИ им. В.И. Ульянова (Ленина) в 1983-1985 гг.; научно-технических конференциях ВосточноСибирского государственного технологического университета (Улан-Удэ, 1986-2005).

Публикации. По теме диссертации опубликована 41 научная работа, из них: 1 монография, 12 статей (6 статей - в изданиях, рекомендованных ВАК Минобразования и науки РФ), 2 свидетельства об официальной регистрации программ для ЭВМ в Российском агентстве по патентам и товарным знакам.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

-применение современных средств вычислительной техники - многопроцессорных систем и сетей для организации распределенного имитационного моделирования РИСУ;

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

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

Таблица 1.

№ Причина Проблема Способ разрешения

1. Размерность РИСУ Требует значительного вычислительного ресурса: памяти и быстродействия ЭВМ Разработка методов распределенного имитационного моделирования на многопроцессорных системах

2. Медленная сходимость метода Монте-Карло Требует значительного ресурса времени, для получения убедительных статистических выводов Разработка аналитико-статистических методов ускорения статистического моделирования

3. Выбор оптимального варианта проекта РИСУ Требует многократных прогонов модели с различными исходными данными и параметрами РИСУ Разработка методов повышения эффективности имитационного моделирования РИСУ, включающие методы п.1 и п.2 данной таблицы

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

В теории параллельных вычислений определены основные парадигмы (модели) распараллеливания: MPMD (Multiple Program — Multiple Data) и SPMD (Single Program - Multiple Data). Первой парадигме соответствует разбиение алгоритма программы на параллельно исполняемые фрагменты, второй - распараллеливание данных, обрабатываемых программой. Распараллеливание в обоих случаях производится по критерию минимизации интенсивности обмена данными по среде передачи между процессорами распределенной вычислительной платформы.

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

Использование MPMD — модели требует разработки метода распараллеливания, отвечающего специфике построения моделирующего алгоритма, заключающейся в сильной связности программного кода ИМ. Связность по данным и управлению обусловлена централизацией базы данных моделирования и управляющей программы (УП) ИМ, отслеживающей выполнение взаимодействующих процессов моделируемой системы в едином модельном времени. Следовательно, организация распределенного моделирования по модели параллельных вычислений MPMD требует разработки: метода распараллеливания ПО ИМ по определенному выше критерию; принципов построения децентрализованной УП; принципов построения децентрализованной базы данных модели.

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

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

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

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

Вторая глава посвящена разработке общей концепции распределенного имитационного моделирования РИСУ.

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

Таблица 2

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

Цель: Ускорение выпол-ненияпрограмм с использованием большего числа Ьроцессоров Обеспечение совместной работы программных компонент, размещенных на разных компьютерах Ускорение выполнения программ с использованием большего числа процессоров

Вычислительная платформа МРР-системы локальные сети локальные сети

БМР-системы глобальные сети

кластерные системы кластерные системы

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

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

Критерий распараллеливания минимизация межпроцессорных взаимодействий минимизация межпроцессорных взаимодействий ми нимизация межпроцессорных взаимодействий

Размещение задач по процессорам Оптимальное отображение на топологию многопроцессорной системы ПО^ЙТЩР^'МИч Химизации време-^ ни выполнения программы Планирование вычислительного процесса по различным критериям, в том числе и Йинймвдацш времени выполнения прйграммы Распределение по процессорам по критерию минимизации времени выполнения всей задачи

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

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

- В теории параллельных вычислений существующие методы ориентированы на детерминированные алгоритмы программ и распараллеливание производится на уровне операторов.

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

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

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

Концепция распределенного имитационного моделирования РИСУ состоит в реализации всех этапов организации параллельного исполнения программ, принятых в ТПВ и ТРВ и совпадающих по содержательному смыслу:

1. Анализ задач и выявление потенциального параллелизма.

2. Декомпозиция задачи на параллельные процессы.

3. Оптимальное размещение параллельных процессов по процессорам вычислительной системы.

4. Анализ производительности, оценка прогнозируемого ускорения.

5. Организация параллельного (распределенного) вычислительного процесса.

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

В третьей главе рассматриваются вопросы разработки метода распределенного имитационного моделирования РИСУ, основанного на парадигме параллельных вычислений МР№), принципов построения распределенной имитационной модели РИСУ, методов организации распределенного вычислительного процесса моделирования.

В рамках разработки метода решена задача распараллеливания ПО ИМ РИСУ по критерию минимизации межпроцессорных обменов данными.

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

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

Для выделения объектов, подлежащих классификации, произведено формализованное описание имитационной модели РИСУ с использованием РДО - метода, в результате которого определены подмножества однотипных действий, имеющих одинаковую логику изменения состояний релевантных ресурсов. Виртуальное (возможное) действие V = (е„, е„) описывается через события начала и окончания действия, Е= \е]в2,...еп\ - множество всех возможных событий моделируемой системы. Ресурсы, состояния которых изменяются при наступлении некоторого события е, называются релевантными событию е. Ресурсы, релевантные действию V, есть объедине-

ние множеств ресурсов, релевантных событиям начала и конца действия: 1С =иг-тч.

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

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

В?2 =Кв2 У Яез, где Л*2 ={иомера входящих каналов в УС},

={номера исходящих каналов из УС}. Пересечение множеств релевантных виртуальных действий отражает структурную связность моделируемой системы. Чтобы отразить динамические характеристики системы разработан алгоритм, использующий входные данные модели: интенсивности информационных потоков, матрицу маршрутизации потоков. В итоге работы алгоритма формируется матрица X (п — число узлов РИСУ, р — число каналов)

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

Задача распараллеливания (декомпозиции) ПО ИМ РИСУ ставится следующим образом.

Задано конечное множество объектов Г = (у/,у2,...,у„), в котором каждый объект V/ имеет набор признаков Х{ = (хц,Х12,—,Хф). Необходимо произвести разбиение множества V на классы наиболее связанных объектов по критерию минимизации связей между классами.

Для решения задачи вводится метрика количественной характеристики различия объектов:

хп х12 ... х1р

Х =

Х21 х22 ••

Хп1 хп2 — хпр

2

(1)

к=1

Выбор метрики вида (1) произведен, исходя из предложенного способа задания количественных признаков объектов. Признаки, заданные в матрице X, являются однородными и равноценными, имеют одинаковый вес с точки зрения влияния на формирование кластеров.

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

W : ditk = min {dik},(k*i)

k—l,m

где i и к - номера кластеров, т - количество кластеров.

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

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

... М

Vi ={v'j,v'2.....v^) - i- кластер, состоящий из щ действий., п = Y.ni •

Число полученных кластеров определяет количество блоков декомпозированной ИМ РИСУ. Виртуальные действия, входящие в один кластер, формируют единый блок имитационной модели. Номерам объектов (виртуальных действий) кластера соответствуют номера узлов сети; множества релевантных ресурсов данных действий определяют конкретные каналы связи и информационные потоки; событиям, определяющим действие v;-, соответствуют конкретные обрабатывающие модули имитационной модели.

По результатам произведенной классификации виртуальных действий формируются: матрица сопряжения полученных блоков ИМ; матрица ин-тенсивностей взаимодействий между блоками; распределенная база данных моделирования.

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

Входными данными алгоритма вычисления прогнозируемого ускорения являются: Tj, (j=l, М) - средняя продолжительность выполнения программы у'-го блока; Xj, (j—1, М) частота взаимодействия j-го блока с другими

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

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

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

Разработаны принципы построения децентрализованной управляющей программы распределенной имитационной модели. УП РИМ состоит из управляющих программ блоков, взаимодействующих между собой через прием и посылку сообщений. Управляющие программы блоков осуществляют только операцию чтения из буфера линий связи. Прием сообщений осуществляется в фоновом режиме без остановки алгоритма имитации. Операция передачи сообщений другим блокам ИМ осуществляется обрабатывающим модулем - ОМ4 «начало передачи по каналу связи».

УП блоков ИМ выполняют действия, которые делятся на две основные группы:

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

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

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

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

к1 Тс

цессами {а,- } и приращения локальных часов процессов {Щ}.

В работе исследованы вопросы определения указанных параметров для распределенной имитационной модели РИСУ, которые получают, используя результаты декомпозиции ПО ИМ РИСУ.

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

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

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

Имеется п процессоров вычислительной системы и т про-

граммных модулей РИМ , при чем т < п. Задана матрица эффек-

тивности С=|| Су ||, (}=1,...,т,]=1,...,п), элементы которой СуХ) определяют меру эффектиЕности программного модуля на процессоре Pj, т.е. Су

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

распределение программных модуль по процессорам описано подстановкой:

( 1 2 ... к ... т

\

Л ... п. ... 1П

а =

\Ч ¡2 - 'к

Требуется найти такое распределение а0 модулей и'1>...,-н,т по процессорам ру..,рп, чтобы величина минимальной производительности Су была

максимальной по всем подстановкам ст,-, i =1,...,L. Оптимизационным параметром является величина S(cr) = minC,;Cr., где а,- некоторая подстановка,

isL

и ставится вопрос о нахождении оптимального параметра Sg — тах^'(<т).

Решение поставленной задачи сводится к нахождению наибольшего паросочетания в двудольном графе, в котором подмножество вершин А] = \w} twm} - есть множество программных модулей декомпозированной имитационной модели, а подмножество вершин = {pi, -,pn} - есть множество процессоров вычислительной системы. Алгоритм выбора наибольшего паросочетания в двудольном графе позволит найти распределение егг В процессе работы алгоритма оптимального распределения программных модулей по процессорам выделяется последовательность наборов распределений а-,-, г =1, ...,L , с каждым шагом приближающих к максимальной эффективности S0 = max S(a).

Постановка задачи оптимального размещения модулей ИМ по процессорам в таком виде позволяет свести задачу к сравнительно простой и получить решение в удобном для практического использования виде. Алгоритм при 10¿»г<50 сходится очень быстро, за малое число шагов, тогда как полный перебор всех возможностей распределения программных модулей по процессорам потребовал бы для расчета ml вариантов.

Исследованы и разработаны принципы построения программного инструментария АСОРИМ, автоматизирующего процесс организации распределенного моделирования РИСУ. Определены основные функции в виде технологических этапов и их алгоритмическое наполнение.

Технологическими этапами функционирования АСОРИМ являются:

1. Декомпозиция ПО ИМ РИСУ.

2. Оценка качества вариантов проектов декомпозиции РИСУ. Определение прогнозируемого ускорения.

3. Выбор алгоритма синхронизации распределенных процессов.

4. Формирование децентрализованной управляющей программы РИМ и распределенной базы данных моделирования.

5. Оптимальное распределение программных блоков ИМ по процессорам вычислительной системы.

Алгоритмическим наполнением технологических этапов являются:

- метод декомпозиции имитационной модели РИСУ, основанный на иерархическом агломеративном алгоритме автоматической классификации. По результатам декомпозиции формируется состав блоков РИМ и распределенная база данных модели.

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

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

которого производится построение децентрализованной управляющей программы РИМ.

- способ оптимального распределения программных блоков РИМ по процессорам вычислительной системы.

Автономность функционирования АСОРИМ вкупе с пользовательским интерфейсом делают его удобным средством для решения задачи распараллеливания ИМ РИСУ и перенесения имитационной программы на имеющийся в распоряжении пользователя парк компьютеров: локальную или кластерную сеть.

На основе проведенных исследований и разработки АСОРИМ предложена комплексная методика организации распределенного имитационного моделирования РИСУ по модели параллельных вычислений MPMD.

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

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

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

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

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

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

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

®= I Ph®h, (2)

h = 1

где phопределяется, как доля объектов совокупности, входящих в к- ый класс; ©й- средние оценки по классам.

Моделью ПТТ и объектом имитации служит виртуальный канал (ВК), представляющий собой некоторый маршрут в РИСУ, состоящий из последовательности узлов коммутации-обработки транзактов и каналов связи-передачи транзактов между узлами. Одна и та же модель ВК для представления разных классов отличается только параметрами.

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

В рамках построения генератора фоновых потоков решены следующие задачи:

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

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

/

Л = Хд + ^ kjXj j=l

где Xq- интенсивность внешнего потока, Xj - интенсивности потоков из смежных узлов, I - число смежных узлов, kj =1 — pj - коэффициент пропускания входного потока, a pj - вероятность потери сообщений на смежном узле из-за переполнения буферного накопителя.

Разработаны способ расчета вероятностей потери сообщений на узлах коммутации-обработки и алгоритм учета задержки сообщений фоновых потоков на УС после обработки по причине переполненности буферного накопителя следующего узла. В результате работы алгоритма в ИМ ВК сообщения транзитных потоков с некоторой вероятностью Р„)р покидают узел Xj

выделенного пути, либо остаются на узле с вероятностью 1-РЩр. Получена формула вероятностей перехода сообщения с i-ro узла на j-ый узел:

j-l,...,l.\ p^ - вероятность адресации сообщений j-му смежному с xt узлу; pj — вероятность переполнения буферного накопителя j-ro узла.

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

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

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

N N vik

t=n=i г

где N - число узлов; гд - средняя задержка сообщений, возникающих в узле j и предназначенных для узла к; у- полный входящий трафик сети, уд-трафик пути я jk. Величина представляет собой сумму средних задержек в различных системах (УС и КС), составляющих путь гд = £7}» где

icnjk

Т/ - среднее время, проведенное сообщением в системе, где под системой понимается УС или КС (обслуживающий прибор) и очередь сообщений, стоящих перед узлом или каналом.

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

Предложена комплексная методика проведения распределенных имитационных экспериментов в соответствии с моделью БРМБ, все этапы которой автоматизированы.

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

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

На первом этапе выполняются декомпозиция РИСУ на классы путей транспортировки транзактов. Выходом данного этапа является число моделируемых ПТТ, определяющее необходимое количество процессоров для организации распределенного имитационного моделирования РИСУ.

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

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

Отличительными особенностями разработанного метода распределенного моделирования, основанного на парадигме параллельных вычислений БРМЕ), являются: возможность получения как интегральных, так и дифференциальных характеристик моделируемой системы; возможность использования существующих последовательных программ имитации РИСУ без внесения существенных изменений для параллельного исполнения на многопроцессорной системе; практически линейное ускорение вычислительного процесса имитации в зависимости от числа используемых процессоров.

Пятая глава посвящена теоретическому обоснованию и разработке аналитико-статистического метода моделирования РИСУ.

Предлагаемая концепция метода исходит из основных причин вычис-

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

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

- декомпозиции исследуемого объекта, с целью понижения размерности объекта моделирования.

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

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

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

Ранжирование элементов проводится следующим образом. Каждый элемент (УС, КС) вносит свое влияние на исследуемую характеристику объекта. Эту "долю влияния" будем называть составляющей результативного признака (СРП).

Пусть 7} = <р{р1) выражает зависимость СРП от фактора р, (нагрузка элемента г). Тогда, задав число в, как допустимое различие значений СРП в процентах, элементам / и ] присваивается одинаковый ранг при выполнении условия:

Таким образом, имеем конечное множество объектов, каждый из которых характеризуется фиксированным набором признаков г={гт.....2(2"+1)}.

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

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

\1-Т<1Т,\йв

' }

где Б% =

к=1

Выбор меры близости такого вида продиктован тем фактом, что компоненты вектора признаков однородны по своему физическому смыслу и все одинаково важны с точки зрения решения вопроса об отнесении объекта к тому или иному классу.

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

/(а,Л)=| I (%-я) (4)

к=\ 1,]сЯк

Оптимальным будет то разбиение, которое максимизирует (4) при заданном а по всем возможным разбиениям данного множества объектов. Критерий (4) позволяет проводить разбиение на априорно незаданное число классов.

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

(с - е(ш, +1) + тгс!)) ф

в(т,(с? +1) + тгс1 - 2(1 -1)

где ¿1 -число транзитных участков путей подмножества, внутри которого производится разбиение; /я; - число рангов для УС; тз — число рангов для КС.

Заданием е, как желательной степени однородности объектов внутри классов, однозначно определяется порог существенности связей а. В работе приведены рекомендации по выбору параметров в и е. Построенное разбиение множества ПТТ дает возможность оценить искомые характеристики РИСУ по классам и построить оценку вида (2).

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

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

ритмов, методик и программных средств имитационного моделирования РИСУ.

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

Подсистема подготовки РИМ РИСУ выполняет преобразование программы последовательной имитационной модели в параллельную конструкцию в соответствии с алгоритмами технологических этапов АСОРИМ.

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

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

В соответствии со структурой системы распределенного моделирования РИСУ программное обеспечение разработанного комплекса программных средств делится на слои:

- ПО организации вычислительного процесса РИМ, включающее программы алгоритмов технологических этапов АСОРИМ;

- ПО межпроцессорных взаимодействий, включающее стандартную библиотеку Winsock 2.0, библиотеки функций обмена сообщениями протоколов IPX или TCP/IP. Использование того или иного вида программных средств обмена сообщениями зависит от того, какие транспортные протоколы использует вычислительная система, на которой реализуется моделирование.

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

- ПО последовательной имитационной модели, представляющей собой проблемно-ориентированную дискретно - событийную имитационную модель РИСУ.

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

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

Представлены результаты практического применения разработанных методов к моделированию распределенной АСУ "Система-Город", внедряемой в г.Улан-Удэ.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

Основные результаты работы заключаются в следующем.

1. Развитие теории распределенного имитационного моделирования. В этом направлении:

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

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

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

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

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

- метод распределенного имитационного моделирования РИСУ, заключающийся в сочетании разработанного аналитико-статистического метода с

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

- аналитйко-статистический метод ускоренной имитации, заключающийся в преобразовании статистического метода расслоенного отбора к имитационному моделированию РИСУ;

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

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

3. Разработаны комплексные методики организации распределенного имитационного моделирования РИСУ с использованием модели параллельных вычислений SPMD и модели параллельных вычислений MPMD на многопроцессорной вычислительной системе, все этапы которых автоматизированы.

4. Разработан программный комплекс, реализующий распределенное моделирование РИСУ на многопроцессорной платформе, включающий:

а) программный инструментарий АСОРИМ, автоматизирующий процесс организации вычислительного процесса распределенного моделирования РИСУ. Разработаны алгоритмы технологических этапов АСОРИМ:

- распараллеливания программного обеспечения ИМ РИСУ;

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

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

- оптимального размещения блоков РИМ по процессорам вычислительной системы;

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

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

- *

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Олзоева С.И. Распределенное моделирование в задачах разработки АСУ. // Монография: - Улан-Удэ, изд-во ВСГТУ, 2005 - 219 с.

2. Олзоева С.И. Общая концепция повышения эффективности моделирования распределенных автоматизированных систем. II «Вестник Бурятского университета», серия 8 « Теория и методика обучения естественно-математическим дисциплинам», выпуск 2, Улан-Удэ, 2005, стр. 1926.

3. Олзоева С.И. Алгоритмы инструментального средства для организации имитационных экспериментов на кластерах.//«Вестник Бурятского университета», серия 13 «Математика и информатика», выпуск 1, Улан-Удэ, 2004, стр. 228-238.

4. Олзоева С.И. Метод оптимального распределения программных модулей по процессорам вычислительной системы. // «Вестник Бурятского университета», серия 13 «Математика и информатика», выпуск 2, Улан-Удэ, 2005, стр. 257-261.

5. Кутузов О.И, Олзоева С.И, Улзутуев Б.И. Методы повышения эффективности моделирования распределенных автоматизированных систем. П Известия Тульского государственного университета, 2005, стр. 63 - 70

6. Олзоева С.И. Способ составления расписания для имитационного моделирования на многопроцессорных системах. // Известия Тульского государственного университета, 2005, стр. 111-115

7. Олзоева С.И., Улзутуев Б.И. Имитационная модель виртуального канала. // Свидетельство об официальной регистрации программы для ЭВМ № 2005611078, от 04.05.2005, Реестр программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным зна кам.

8. Олзоева С.И., Кирюшин А.И. Телеконференция в локальной сети типа «Novell». П Свидетельство об официальной регистрации программы для ЭВМ в Рос.АПО № 97472 0т 26.09.97

9. Кутузов О.И., Олзоева С.И. Алгоритмический анализ стохастических сетевых моделей на многопроцессорных системах. // Методы и средства обработки информации: Сб.трудов Всероссийской научн. конф., МГУ им. Ломоносова, Москва, 2003, стр. 228 - 233.

10. Кутузов О.И., Улзутуева С.И. Методика ускоренной оценки характеристик функционирования сети обмена информацией // Рукопись деп. в ВИНИТИ 24.07.85, №5343

11. Головин Ю.А., Кутузов О.И., Матвеева В.А., Улзутуева С.И. Разработка модельного обеспечения для автоматизации процесса проектирования микропроцессорных устройств управления узлов сетей обмена информацией. // Известия ЛЭТИ, выпуск 358, Ленинград, 1985, с. 48-51.

12. Кутузов О.И., Олзоева С.И. Концепции и подходы к построению программного инструментария для организации распределенного имитационного моделирования систем. // Сб. докладов VII Международной конференции по мягким вычислениям и измерениям, Санкт - Петербург, 2004 г., том 1, стр. 224 - 227.

13. Олзоева С.И. К решению задач имитационного моделирования слож-

ных систем на кластерах. // Высокопроизводительные параллельные вычисления на кластерных системах: Сб. материалов II Международного научно-практического Семинара, Нижний Новгород, 2002, стр. 231 -239.

14. Олзоева С.И., Тюменцев Д.В., Костенко А.В. Моделирование распределенной автоматизированной системы на кластере рабочих станций. // Высокопроизводительные параллельные вычисления на кластерных системах: Сб. материалов V Международного научно-практического Семинара, Нижний Новгород, 2005.

15. Олзоева С.И., Тюменцев Д.В., Костенко А.В. Имитационное моделирование РАС «Система-город» // Автоматизированная подготовка машиностроительного производства, технология и надежность машин, приборов и оборудования: Сб. материалов Международной научно-технической конференции, Вологда, 2005, стр. 133-136.

16. Олзоева С.И. Способ оценки потенциального параллелизма для распределенного имитационного моделирования систем. // Математика, ее приложения и математическое образование: Сб. трудов Международной конференции, Улан -Удэ, 2002, часть 2, стр. 27 - 32.

17. Кутузов О.И., Олзоева С.И. Организация вычислительного процесса для распределенного имитационного моделирования дискретно-событийных систем. // Сб. докладов V Международной конференции по мягким вычислениям и измерениям, Санкт-Петербург, 2002, том 1, стр. 101-105.

18. Kutuzov O.I., Olzoeva S.I. Some questions of the simulation of complex systems onto message-passing parallel architectures. // In Proceedings of VI International Conference on Soft Computing and Measurements' 2003, St. Petersburg, Russia, vol. 1, (2003), p. 187-190. (Вопросы имитационного моделирования сложных систем на параллельных системах с распределенной памятью.// Сб. материалов VI Международной конф. По мягким вычислениям и измерениям, 2003, том 1, стр. 187 -190.)

19. Кутузов О.И., Олзоева С.И. Методы ускорения имитационного моделирования распределенных автоматизированных систем. // Сборник докладов VIII Международной конференции по мягким вычислениям и измерениям, Санкт - Петербург, 2005, том 1., стр. 145-148.

20. Олзоева С.И., Машеева Е.П. Система обеспечения технологии дистанционного обучения. // Новые информационные технологии в университетском образовании: Сб. трудов Международной научно-методической конф., Новосибирск, 2000 г., стр. 171-173.

21. Олзоева С.И. Распределенная обработка в имитационном моделировании систем. // Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта: Сб. материалов Международной научно-технической конф., Вологда, 2001, стр. 71 - 74.

22. Олзоева С.И. Построение имитационных систем моделирования на базе

локальных вычислительных сетей. // Моделирование, оптимизация и интенсификация производственных процессов: Сб. материалов Международной научно-технической конф., Вологда, 2001, стр. 197 - 199.

23. Олзоева С.И., Улзутуев Б.И. Модель вычислений SPMD в имитационном моделировании систем. // Теоретические и прикладные вопросы современных информационных технологий: Сб. материалов IV Всероссийской научно-технической конференции, Улан-Удэ, 2003, часть 1. стр.81-85.

24. Олзоева С.И., Улзутуев Б.И. Автоматизированное средство организации вычислительного процесса для распределенного имитационного моделирования систем. // Распределенные и кластерные вычисления: Сб. избранных трудов 2-й Межрегиональной школы - семинара, Красноярск, 2002, стр. 157- 172.

25. Олзоева С.И. Способ моделирования сетей массового обслуживания на многопроцессорных системах. // Высокопроизводительные вычисления и технологии: Сб. материалов Всероссийской конф., Ижевск, 2003, стр. 159-165.

26. Ябжанова С.Б., Олзоева С.И. Моделирование стохастических сетей на многопроцессорных системах. // Математика, ее приложения и математическое образование: Сб. трудов Всероссийской конференции с международным участием, Улан-Удэ, 2005, стр. 295-298.

27. Машеева Е.П., Ябжанова С.Б., Олзоева С.И. Особенности программной реализации модели виртуального канала. // Математика, ее приложения и математическое образование: Сб. трудов Всероссийской конференции с международным участием, Улан-Удэ, 2005, стр. 163-166.

28. Олзоева С.И. Задачи построения имитационных систем моделирования с распределенным вычислительным процессом. // Теоретические и прикладные вопросы современных информационных технологий: Сб. материалов Всероссийской научно-технической конф., Улан-Удэ, 2001, стр. 64 - 67.

29. Олзоева С.И., Лоскутов Р.В. Сетевая имитационная модель системы управления распределенными базами данных. // Теоретические и прикладные вопросы современных информационных технологий: Сб. материалов Всероссийской научно-технической конференции, Улан-Удэ, 2000, стр. 111-112.

30. Олзоева С.И. Задачи построения имитационных систем моделирования на базе кластерных вычислительных систем. // Распределенные и кластерные вычисления: Сб. избранных трудов 1-й Межрегиональной школы - семинара, Красноярск, 2001, стр. 147 - 156.

31. Кутузов О.И., Олзоева С.И. О подходе к моделированию в задачах проектирования сетей обмена информацией. // Теоретические и прикладные вопросы современных информационных технологий: Сб. материалов Всероссийской научно-технической конф., Улан-Удэ, 2000 г., стр. 62 - 64.

32. Олзоева С.И., Ябжанова С.Б. Методы автоматизации распределения вычислительного процесса имитационного моделирования систем. // Информационные технологии в профессиональной деятельности и научной работе: Сб. материалов региональной научно-практической конф., Йошкар-Ола, 2005., стр. 158 -161.

33. Кутузов О.И., Задорожный В.Н., Олзоева С.И. Имитационное моделирование сетей массового обслуживания. // Улан-Удэ: ВСГТУ, 2001, 228 с.

34. Олзоева С.И., Кутузов О.И. Сетевая имитационная система моделирования информационно-вычислительных сетей. // Новые информационные технологии: Сб. материалов региональной межвузовской научно-практической конференции "", Владивосток, 2000, стр. 120 -121.

35. Машеева Е.П., Олзоева С.И. Новые информационные технологии в инженерном образовании. // Сборник научных трудов ВСГТУ, серия "Технические науки", вып. 7, том 2, Улан-Удэ, 1999 г., стр. 224 - 227.

36. Олзоева С.И., Машеева Е.П. Система дистанционного обучения. // Сборник научных статей ВСГТУ, вып. 7, Улан-Удэ, 2001 г., стр. 202 -208.

37. Олзоева С.И., Мохосоева С.Т. Способ построения имитационной модели коммутатора ЛВС. // Сборник научных трудов ВСГТУ, серия " Технические науки", вып. 7, том 2, Улан-Удэ, 1999, стр. 234 - 239.

38. Улзутуева С.И. Планирование эксперимента с целью уменьшения числа испытаний в имитационном моделировании СОИ. // Рукопись деп. в ВИНИТИ 06.04.84, № 2068-84

39. Кутузов О.И., Улзутуева С.И. Метод эквивалентного генератора транзитных потоков в имитационном моделировании сетей обмена информацией АСУ. // Методы и средства решения задач в интегрированных АСУ: Сб. материалов. Всесоюзн. конф., Ташкент, 1984, с 40 - 41.

40. Луговая Н.В., Смирнов М.И., Улзутуева С.И. Программа вычисления деревьев кратчайших путей взвешенного графа. М.: ФАП НИВЦ МГУ, Рег.№ 5085.0000491, Бюллетень №1,1986 г.

41. Олзоева СЛ. Проект автоматизированной системы моделирования информационно- вычислительных сетей. // Сборник научных статей. Серия: технические науки. Выпуск 1, Улан-Удэ, 1994 г., с. 31-33

Подписано в печать 19.04.2006. Формат 60x84/16 Отпечатано с готового оригинал-макета в типографии ЗАО «КопиСервис». Печать ризографическая. Заказ № 1/1904. П. л. 2.0. Уч.-иад. л. 2.0. Т^раж 100 экз.

ЗАО «КопиСервис» Адрес юр.: 194017, Санкт-Петербург, Скобелевский пр., д. 16. Адрес факт.: 197376, Санкт-Петербург, ул. Проф. Попова, д. 3. тел.: (812) 327 5098

Введение.

1. Обзор и анализ методов моделирования распределенных информационных систем АСУ. Постановка задачи исследования.

1.1. Распределенные информационные системы управления.

1.2. Анализ задач проектирования РИСУ.

1.3. Методы моделирования РИСУ.

1.3.1. Технологическая схема имитационного моделирования систем.

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

1.4.1. Анализ проблем имитационного моделирования систем.

1.4.2. Методы ускорения имитационного моделирования систем.

1.5. Формулировка задач исследования.

Выводы к главе 1.

2. Разработка концепции распределенного имитационного моделирования РИСУ.

2.1. Современные высокопроизводительные вычислительные системы.

2.2. Организация параллельных вычислений в имитационном моделировании РИСУ.

2.2.1. Типовые вычислительные схемы имитации РИСУ.

2.2.2. Методы теории параллельных вычислений.

2.2.2.1. Основные парадигмы параллельных вычислений.

2.2.2.2. Программное обеспечение параллельных вычислений.

2.2.2.3. Методы распараллеливания программ.

2.2.3. Методы теории распределенных вычислений.

2.2.3.1. Сегментация программ для параллельного исполнения.

2.2.3.2. Распределение программных сегментов для одновременного исполнения.

2.2.3.3. Вопросы использовании Grid-систем для задач имитационного моделирования.

2.2.4. Концепция распределенного имитационного моделирования РИСУ.

Выводы к главе

3. Разработка метода распределенного имитационного моделирования РИСУ, основанного на модели вычислений MPMD.

3.1. Принципы организации распределенного имитационного моделирования

РИСУ по модели вычислений MPMD.

3.2. Метод декомпозиции ПО ИМ РИСУ.

3.2.1. Формализованное представление ИМ РИСУ.

3.2.2. Разработка метода декомпозиции модели РИСУ.

3.2.3. Дендрограммы.

3.2.4. Алгоритм кластеризации множества виртуальных действий ИМ.

3.2.5. Результаты декомпозиции ПО ИМ РИСУ.

3.3. Оценка качества вариантов проектов распределенной имитационной модели.

3.3.1. Способ определения возможных временных факторов.

3.4. Выбор оптимального алгоритма синхронизации для проекта РИМ.

3.4.1. Математическая модель функционирования пары «АС, ИМ».

3.4.2. Метод сравнения эффективности различных АС.

3.5. Принципы построения управляющей программы РИМ.

3.5.1. Организация управляющей программы РИМ при консервативном алгоритме синхронизации.

3.5.2. Организация управляющей программы РИМ при оптимистическом алгоритме синхронизации.

3.6. Оптимальное распределение программных блоков ИМ по процессорам вычислительной системы.

3.6.1. Алгоритм выбора наибольшего паросочетания в двудольном графе

3.6.2. Пример оптимального распределения блоков РИМ.

3.7. Автоматизированное средство организации распределенного имитационного моделирования РИСУ.

3.8. Методика организации вычислительного процесса распределенного имитационного моделирования РИСУ.

Выводы к главе 3.

4. Разработка метода распределенного имитационного моделирования РИСУ, основанного на модели вычислений SPMD.

4.1. Общая концепция распределенного имитационного моделирования РИСУ по модели вычислений SPMD.

4.2. Принципы построения имитационной модели виртуального канала.

4.3. Разработка имитационной модели виртуального канала

4.3.1. Путь транспортировки транзактов как объект моделирования.

4.3.2. Построение генератора фоновых потоков.

4.3.2.1. Способ определения вероятности потери сообщений на УС

4.3.2.2. Алгоритм формирования интенсивностей фоновых потоков.

4.3.2.3. Распределение входящего потока на УС.

4.4. Исследование влияния распределения входных потоков на характеристики функционирования ПТТ.

4.5. Вопросы адекватности модели виртуального канала.

4.6. Методика организации вычислительного процесса распределенного моделирования РИСУ по SPMD - модели

Выводы к главе 4.

5. Разработка аналитико-статистического метода моделирования РИСУ.

5.1. Общая концепция ускорения имитационного моделирования РИСУ.

5.2. Разработка метода декомпозиции РИСУ с применением процедуры кластерного анализа.

5.2.1. Критерий и свойства оптимального разбиения.

5.2.2. Назначение рангов УС и КС сети.

5.2.3. Выбор порога существенности связей.

5.3. Алгоритм двухступенчатой декомпозиции сети.

5.4. Точность оценки исследуемых характеристик.

5.5. Методика ускоренного анализа РИС АСУ.

5.6. О применимости метода ускоренного машинного анализа РИСУ.

Выводы к главе 5.

6. Результаты применения предлагаемых методов ускорения статистического моделирования РИСУ.

6.1. Структура системы распределенного моделирования РИСУ.

6.2. Коммуникационное программное обеспечение.

6.3. Описание имитационной модели РИСУ и имитационной модели виртуального канала.

6.3.1. Алгоритмы обслуживания моделирования.

6.3.2. Алгоритмы обрабатывающих модулей.

6.4. Экспериментальная оценка характеристик функционирования РИСУ с использованием аналитико-статистического метода.

6.4.1 Сравнение затрат машинных ресурсов при моделировании РИСУ двумя способами.

6.5. Оценка характеристик функционирования РИСУ с использованием методов распределенного имитационного моделирования.

6.5.1. Описание распределенной автоматизированной системы

Система «Город»».

6.5.2. Оценка характеристик функционирования РИСУ с использованием 8РМО - моделирования.

6.5.3. Оценка характеристик функционирования РИСУ с использованием МРМО - моделирования.

Выводы к главе 6.

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

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

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

Адекватное проектирование РИСУ во многом определяет эффективность функционирования создаваемой РАС в целом. Отсюда следует актуальность разработки эффективного модельного обеспечения методов проектирования распределенных информационных систем АСУ.

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

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

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

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

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

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

Под эффективностью имитационного моделирования понимается:

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

- уменьшение затрачиваемого времени на получение результатов моделирования без упрощения модели.

Современные методы имитационного моделирования систем берут начало в работах таких российских и зарубежных ученых, как Бусленко Н.П, Глушков В.М., Моисеев Н.Н, Марчук Г.И., Нейлор, Шеннон Р., Гнеденко Б.В, Емельянов С.В, Калашников С.В., Бусленко В.Н., Коваленко И.Н., Марьянович Т.П., Литвинов В.В., Гусев В.В, Вавилов A.A., Советов Б.Я., Яковлев С.А., Фомин Б.Ф., Аврамчук Е.Ф. В трудах этих и других ученых выполнен большой объем исследований по развитию методологии, методов и технологий системного моделирования. Разработаны средства и системы моделирования на базе универсальных алгоритмических языков, специализированные пакеты моделирования, проблемно-ориентированные системы моделирования.

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

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

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

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

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

1. Исследование и разработка методов, нацеленных на повышение эффективности применения имитационного моделирования в автоматизированных системах проектирования распределенных информационных систем АСУ:

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

- аналитико-статистических методов моделирования, ускоряющих сходимость метода Монте-Карло.

2. Исследование и разработка принципов построения автоматизированных средств организации распределенного имитационного моделирования РИСУ (АСОРИМ), ориентированных на специфику предметной области и предназначенных для комплексного решения задачи организации распределенного вычислительного процесса.

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

4. Разработка распределенных имитационных моделей РИСУ и методик исследования характеристик функционирования РИСУ с использованием распределенного имитационного моделирования.

5. Исследование на практике эффективности применения созданных методов, алгоритмов и программных средств.

Объектом исследования является распределенная информационная система АСУ, формально описываемая стохастической сетевой моделью.

Предметом исследования является процесс имитационного моделирования РИСУ.

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

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

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

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

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

В результате проведенного анализа методов и средств современной теории параллельных вычислений и теории распределенных вычислений выделены основные парадигмы параллельных вычислений: MPMD (Multiple Program - Multiple Data) и SPMD (Single Program - Multiple Data), а также основные задачи и методы планирования и организации распределенных вычислений. Выявлены причины невозможности прямого применения существующих методов к имитационному моделированию РИСУ. Разработана концепция распределенного имитационного моделирования РИСУ, состоящая в модификации рассмотренных методов с учетом специфики построения моделирующих алгоритмов.

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

В третьей главе рассматриваются вопросы разработки метода распределенного имитационного моделирования РИСУ, основанного на парадигме параллельных вычислений MPMD (Multiple Program - Multiple Data), принципов построения распределенной имитационной модели РИСУ, методов организации распределенного вычислительного процесса моделирования.

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

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

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

На основе проведенных исследований и разработки АСОРИМ предлагается комплексная методика организации распределенного имитационного моделирования РИСУ на многопроцессорной вычислительной платформе.

Четвертая глава посвящена вопросам применения в имитационном моделировании стохастических сетей модели параллельных вычислений SPMD (Single Program - Multiple Data) в сочетании с аналитико-статистическим методом моделирования для ускоренного анализа характеристик стохастической сети. Описывается метод распределенного имитационного моделирования РИСУ, основанный на модели параллельных вычислений SPMD.

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

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

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

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

Предложена комплексная методика проведения распределенных имитационных экспериментов в соответствии с моделью ЯРМБ, все этапы которой автоматизированы.

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

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

В главе приводится описание формализованного метода декомпозиции РИСУ с использованием процедуры кластерного анализа, позволяющим выделить классы путей транспортировки транзактов (ПТТ) на основе введенной метрики, определяющей близость процессов функционирования ПТТ, и критерия оптимальности разбиения.

Далее приводится общая методика ускоренного исследования сети на основе машинной имитации. Дано подробное изложение этапов предлагаемой методики. Показана возможность построения интервальной оценки искомых характеристик при исследовании РИСУ по предлагаемой методике. Такой подход дает возможность исследования РИСУ большой размерности за приемлемые затраты машинных ресурсов.

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

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

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

Основными результатами проведенных исследований являются:

1. Развитие теории распределенного имитационного моделирования. В этом направлении:

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

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

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

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

- метод распределенного имитационного моделирования РИСУ с использованием модели параллельных вычислений МР1УГО, заключающийся в оптимальном разбиении программного обеспечения ИМ РИСУ на программные блоки по критерию минимизации обмена данными между блоками и оптимальном распределении блоков по процессорам ВС по критерию минимизации общего времени выполнения имитации;

- метод распределенного имитационного моделирования РИСУ, заключающийся в сочетании разработанного аналитико-статистического метода с моделью параллельных вычислений 8РМЭ, отличающийся подходом к распараллеливанию данных, обрабатываемых единой программой на процессорах распределенной вычислительной системы;

- аналитико-статистический метод ускоренной имитации, заключающийся в преобразовании статистического метода расслоенного отбора к имитационному моделированию РИСУ;

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

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

3. Разработаны комплексные методики организации распределенного имитационного моделирования РИСУ с использованием модели параллельных вычислений 8РЖ) и модели параллельных вычислений МРМГО на многопроцессорной вычислительной системе, все этапы которых автоматизированы.

4. Разработан программный комплекс, реализующий распределенное моделирование РИСУ на многопроцессорной платформе, включающий: а) программный инструментарий АСОРИМ, автоматизирующий процесс организации вычислительного процесса распределенного моделирования РИСУ. Разработаны алгоритмы технологических этапов АСОРИМ:

- распараллеливания программного обеспечения ИМ РИСУ;

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

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

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

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

По теме диссертации опубликована 41 научная работа.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2003, МГУ), II и V Международных научно-практических Семинарах "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, 2002, 2005), I и II Международных конференциях "Математика, ее приложения и математическое образование", (Улан-Удэ, 2002, 2005); V, VI, VII и VIII Международных конференциях по мягким вычислениям и измерениям (Санкт-Петербург, 2002, 2003, 2004, 2005), I и II Межрегиональной школе - семинаре "Распределенные и кластерные вычисления" (Красноярск, 2001, 2002), Всероссийской конференции «Высокопроизводительные вычисления и технологии» (Ижевск, 2003), Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2000, 2001, 2003), IV Международной электронной научно-технической конференции «Технологическая системотехника» (Тула, 2005), Международной научно-технической конференции «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта» (Вологда, 2001), Международной научно-технической конференции «Моделирование, оптимизация и интенсификация производственных процессов и систем» (Вологда, 2001), Международной научно-технической конференции «Автоматизированная подготовка машиностроительного производства, технология и надежность машин, приборов и оборудования» (Вологда, 2005), Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (Новосибирск, 2000), межвузовской научно-технической конференции «Управляющие вычислительные системы» (Вологда, 2000), Региональной межвузовской научно-практической конференции «Новые информационные технологии» (Владивосток, 2000), Региональной научно-практической конференции «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, 2005), Всесоюзной научно-технической конференции «Методы и средства решения задач в интегрированных АСУ» (Ташкент, 1984), Всесоюзной научно-технической конференции «Системы и средства передачи данных», (Черкассы, 1985), Всероссийской научно-технической конференции «Повышение эффективности и помехоустойчивости систем связи» (Севастополь, 1984), 15-ой научно-технической конференции «Проблемы создания новых и совершенствования старых существующих систем, средств связи и АСУ» (Киев, 1984), научно-технических конференциях ЛЭТИ им. В.И. Ульянова (Ленина) в 1983-1985 гг., научно-технических конференциях ВосточноСибирского государственного технологического университета (Улан-Удэ, 1986-2005) Исследования, выполненные в диссертационной работе, проводились в рамках научно-исследовательских работ кафедры «Автоматизированных систем обработки информации и управления» Санкт-Петербургского государственного электротехнического университета (ЛЭТИ) им. В.И. Ульянова (Ленина), а также хоздоговорных и бюджетных НИР кафедры «Электронно-вычислительных систем» ВосточноСибирского государственного технологического университета.

Выводы к главе 6

1. Предлагаемая методика ускоренного исследования распределенных информационных систем АСУ позволяет получать более подробные характеристики функционирования информационной сети по сравнению с топологически-подобным моделированием сети существенно меньших затратах машинного времени (табл. 6.4 и табл. 6.5). Уменьшение затрат машинного времени при использовании предлагаемой методики дает возможность исследования РИСУ большой размерности за приемлемые затраты машинных ресурсов.

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

3. Для реализации вычислительного процесса распределенного моделирования на локальной сети предлагается использовать интерфейс сокетов. Сокеты предоставляют самый полный доступ к возможностям локальной сети, непосредственно вызывая прерывания. По результатам проведенных исследований в качестве коммуникационного программного обеспечения для распределенных имитационных моделей РИСУ использовались низкоуровневые взаимодействия в сети на уровне сокетов протокола IPX (п. 6.2).

5. Применение методов распределенного имитационного моделирования позволяет значительно сократить количество затрат машинного времени при исследовании вероятностно-временных характеристик РИСУ большой размерности. Предлагаемые способы распределенного имитационного моделирования РИСУ позволяют использовать существующий парк компьютеров, причем без отрыва последних от повседневного использования (табл. 6.6, 6.7, 6.8).

Заключение

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

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

1. Развитие теории распределенного имитационного моделирования. В этом направлении:

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

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

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

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

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

- метод распределенного имитационного моделирования РИСУ, заключающийся в сочетании разработанного аналитико-статистического метода с моделью параллельных вычислений 8РМД отличающийся подходом к распараллеливанию данных, обрабатываемых единой программой на процессорах распределенной вычислительной системы;

- аналитико-статистический метод ускоренной имитации, заключающийся в преобразовании статистического метода расслоенного отбора к имитационному моделированию РИСУ;

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

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

3. Разработаны комплексные методики организации распределенного имитационного моделирования РИСУ с использованием модели параллельных вычислений 8РМР и модели параллельных вычислений МРМБ на многопроцессорной вычислительной системе, все этапы которых автоматизированы.

4. Разработан программный комплекс, реализующий распределенное моделирование РИСУ на многопроцессорной платформе, включающий: а) программный инструментарий АСОРИМ, автоматизирующий процесс организации вычислительного процесса распределенного моделирования РИСУ. Разработаны алгоритмы технологических этапов АСОРИМ:

- распараллеливания программного обеспечения ИМ РИСУ;

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

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

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

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

1. Аветисян А.И., Гайсарян С.С., Грушин Д.А.,. Кузюрин Н.Н,. Шокуров A.B. Эвристики распределения задач для брокера ресурсов Grid. // Труды Института системного программирования РАН.- 2003 г.

2. Аврамчук Е.А., Вавилов A.A., Емельянов C.B. Технология системного моделирования. /Под общ. ред. C.B. Емельянова/ М.: Машиностроение, Берлин: Техник, 1988, 520с.

3. Айвазян С.А., Бежаева Э.И., Староверов О.В. Классификация многомерных наблюдений. М.: Статистика, 1974 , 240 с.

4. Амосов A.A. Модель сети передачи данных. // Техника средств связи, сер. ТПС, 1979, вып. 8.

5. Андреев А, Воеводин В., Жуматий С. Кластеры и суперкомпьютеры близнецы или братья? "Открытые системы", №№ 5 -6, 2000г.

6. Андреев А.Н., Воеводин Вл. В. Методика измерения основных характеристик программно-аппаратной среды, http://parallel.ru

7. Анисков A.B., Пономаренко О.Н., Фисун В.А. Конверторы векторизаторы. / Языки и параллельные ЭВМ. М., Наука, 1990, с. 38 - 61.

8. Анни П. "Этот Grid — неспроста." // Открытые системы, №1, 2003 г.

9. Арапов Д. Можно ли превратить сеть в суперкомпьютер? Открытые системы, №4, 1997г.

10. Баронов B.B. и др. Автоматизация управления предприятием. М.: ИНФРА-М, 2000.-239 с.

11. Башарин В. Г. Анализ очередей в вычислительных сетях. М.: Наука, 1989. -334 с.

12. Башарин В. Г. Модели Информационно-вычислительных систем. М.: Наука, 1993.-69 с.

13. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высшая школа, 1976, 392 с.

14. Бигдан В.В., Гусев В.В., Марьянович Т.П., Сахнюк М.А. Становление и развитие имитационного моделирования на Украине. Тр. Международн. Сим-поз. по моделированию систем. К., 1998, с. 182 - 193.

15. Блэк Ю. Сети ЭВМ: протоколы, стандарты и интерфейсы / Пер. с англ. М.: Мир, 1990. 506 с.

16. Богуславский JI. Б., Дрожжинов В. И. Основы построения вычислительных сетей для автоматизированных систем. М.: Энергоатомиздат, 1990. - 256 с.

17. Боровков A.A. Математическая статистика. М., Наука, 1984, 472 с.

18. Борщев A.B. Практическое агентное моделирование и его место в арсенале аналитика. // Материалы Межд. конф. ИММОД'2005, Санкт-Петербург, 2005, http://www.gpss.ru

19. Браунли К.А. Статистическая теория и методология в науке М.: Наука, 1977, 407с.

20. Бродский В.З. Введение в факторное планирование эксперимента. М., Наука, 1976, 223 с.

21. Бусленко Н.П. Моделирование сложных систем М.: Наука, 1978 - 400с.

22. Бусленко Н.П., Коваленко И.Н., Калашников В.В. Лекции по теории сложных систем М.: Сов. Радио, 1973, - 430с.

23. Бушуев П. А. 1 : 0 в пользу ATM./ Сети и системы связи. № 9. 1998, с. 108111.

24. Ван-дер-Варден Б.Л. Математическая статистика М.: Издательство Иностр. лит., 1960, 283 с.

25. Варжапетян А.Г., Глущенко В.В. Системы управления. Исследование и компьютерное моделирование.- М.: Вузовская книга, 2000.- 328 с.

26. Вендров A.M. Один из подходов к выбору средств проектирования баз данных и приложений. "СУБД", 1995, №3.

27. Воеводин В.В. Математические модели и методы в параллельных процессах. М., Наука, Гл. ред. физ. мат. лит., 1986, 296 с.

28. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ -Петербург, 2002, 608 с.

29. Воеводин Вл., Филамофитский М. Суперкомпьютер на выходные. // Открытые системы, № 6,2003.

30. Вопросы анализа сложных систем: Математический анализ экономических систем. Сборник трудов.-Новосибирск:«Наука. Сибирское отделение», 1974

31. Вознесенская Т.В. Исследование эффективности методов синхронизации времени для распределенного имитационного моделирования. // Материалы конф. "Высокопроизводительные вычисления и их приложения". Черноголовка. 2000. С.208-211.

32. Вознесенская Т.В. Метод анализа алгоритмов синхронизации времени для распределенного имитационного моделирования системю //cmc.cs.msu.su/labs/lvk

33. Волохов В.М., Покатович Г.А. Основные классы современных параллельных компьютеров, http://parallel.ru

34. Вычислительные системы, сети и телекоммуникации /В.Л. Брейдо. СПб: Питер, 2003,-688 с.7

35. Гаскаров Д. В., Истомин Е. П., Кутузов О. И. Сетевые модели распределенных автоматизированных систем. СПб.: Энергоатомиздат, Санкт-Петербургское отделение, 1998. 353 с.

36. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие Нижний Новгород; из-во ННГУ им. Лобачевского, 2000, 176 с.

37. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М., Радио и связь, 1983, 273 с.

38. Горбатов В. А. Фундаментальные основы дискретной математики. Информационные основы. М.: Наука. Физматлит, 2000, 544 с.

39. Горбатов В.А. Теория частично упорядоченных систем. М.: Советское радио, 1976 г., 336 с.

40. Горелик Я.Е., Пранявичус Г.И. Система автоматизированного построения имитационных моделей агрегативных систем САПАС. Каунас: Каунасский политехнический институт, 1985 г.

41. Горчинская О.Ю. Designer/2000 новое поколение CASE-продуктов фирмы ORACLE. "СУБД", 1995, №3.

42. Гради Буч. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. -М.: Бином, 2001, 560 с.

43. Григорьев Р.Н., Панфилов П.Б. Построение распределенных обучающих систем на основе подходов HLA. http://www.imvs.ru

44. Гультяев А. Визуальное моделирование в среде МАТЛАБ: учебный курс. -СПб.: Питер, 2000,432 с.

45. Гусев В.В., Галаган Т.Н., Яременко В.В. Язык программирования с расширяемой грамматикой. // Институт Кибернетики им. Академика В.М. Глушко-ва АН Украины, 1994 г.

46. Девятков В.В. Практическое применение имитационного моделирования в России и странах СНГ: обзор, анализ перспектив, //www.gpss.ru

47. Динамика систем с дискретными событиями. Тематический выпуск ТИИЭР. -М.: Мир, том 77, № 1, 1989

48. Дюран Б., Одел П. Кластерный анализ. М.: Мир, 1977, 128 с.

49. Елисеева И.И., Рукавишников В.О. Группировка, коррелляция, распознавание образов. -М: Статистика, 1977, 143 с.

50. Емельянов В.В., Ясиновский С.И. Введение в интеллектуальное имитационное моделирование сложных дискретных систем и процессов. // Языки РДО. -М.:АНВИК, 1998, 427 с.

51. Задорожный В.Н. Анализ разомкнутых экспоненциальных сетей массового обслуживания: Методические указания к лабораторным работам по автоматизации проектирования АСУ/Омский политехнический институт. Омск, 1986.-32 с.

52. Захаров Г.П. Методы исследования сетей передачи данных. М.: Радио и связь, 1982, 208 с.

53. Зелигер Н.Б., Чугреев О.С., Яновский Г.Г. Проектирование сетей и систем передачи дискретных сообщений. М.: Радио и связь, 1984, 175 стр.

54. Зиндер Е.З. Бизнес-реинжиниринг и технологии системного проектирования. Учебное пособие. М., Центр Информационных Технологий, 1996

55. Иглхарт Д.Л., Шедлер Д.С. Регенеративное моделирование сетей массового обслуживания : Пер. с англ. М.: Радио и связь, 1984, 136с.

56. Йенсен П., Барнес Д. Потоковое программирование. М.: Радио и связь, 1984 г., 391 стр.

57. Казаков Ю.П., Смелянский Р.Л. Об организации распределенного имитационного моделирования. //Программирование. 1994. №2. С.45-63.

58. Калашников В.В. Организация моделирования сложных систем. М.: Зна-ние1982, 64 с.

59. Каменнова М.С. Инструментальная система моделирования параллельных процессов, описанных языком сетей Петри. / УС и М, №5, 1988 г., с. 16 20.

60. Керженцев Ю. А. и др. Телекоммуникационная инфраструктура систем автоматизированного обмена информацией. М.: ВНИИ, 1990. - 150 с.

61. Клейнен Дж. Статистические методы в имитационном моделировании. М., Статистика, 1978, с.221-335.

62. Клейнрок JI. Вычислительные системы с очередями. М.: Мир,1979, 600 с.

63. Клейнрок JT. Коммуникационные сети. Стохастические потоки и задержки сообщений. М.: Наука, 1970, 255 с.

64. Коваленко В., Корягин Д. Эволюция концепции Grid. Вычислительная инфраструктура будущего.- «Открытые системы», 2003, №1

65. Коваленко И.Н. Расчет вероятностных характеристик систем. Киев: Техника, 1982 г, 96 с.

66. Ковалерчик И. АТМ в реальном мире / Сети.- № 7. 1997. с. 14-23.

67. Комарцова Л.Г. Итерированная САПР распределенных вычислительных систем. // Труды Международн. Конференции CAD/CAM/PDM-2001 г.

68. Комолкин A.B., Немнюгин С.А. Курс лекций "Программирование для высокопроизводительных ЭВМ", http://parallel.ru

69. Котов В.Е. Теория параллельного программирования. Прикладные аспекты. / Кибернетика, 1974, №2, с. 1 18.

70. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложение. М.: Мир, 1965, 302 с.

71. Крейн М., Лемуан О. Введение в регенеративный метод анализа моделей. -М.: Наука, 1983, 104 с.

72. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978, 432 с.

73. Кульгин М. Технологии корпоративных сетей. СПб.: Питер, 1999.

74. Куперштох В.Л., Миркин Б.Г., Трофимов В.А. Сумма внутренних связей как показательклассификации. // Автоматика и телемеханика, 1976, № 3, стр. 133 -141.

75. Кутузов О.И., Головин Ю.А. Ускоренное статистическое моделирование сетей обмена информации. Уч. пособие /ТЭТУ СПб., 1997, 64с.

76. Кутузов О.И., Задорожный В.Н., Олзоева С.И. Имитационное моделирование сетей массового обслуживания. Улан-Удэ: ВСГТУ. 2001. 228 с.

77. Кутузов О. И., Хадцад М. Аналитико-статистический метод расчета малых вероятностей потерь в буфере конечной емкости // Телекоммуникационные технологии. 1994. Вып. 1. С. 36-48.

78. Липаев В.В. Проектирование программных средств М.: Высшая школа, 1990

79. Липаев В.В. Распределение ресурсов в вычислительных системах. М., Статистика, 1979, 248 с.

80. Литвинов В.В. Математическое обеспечение проектирования вычислительных машин и систем. Киев, Техника, 1982 г., 176 с.91