Московский государственный университет

им. М. В. Ломоносова

Факультет Вычислительной математики и кибернетики

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

Савенков Константин Олегович

МАСШТАБИРОВАНИЕ ДИСКРЕТНО-СОБЫТИЙНЫХ

ИМИТАЦИОННЫХ МОДЕЛЕЙ

05.13.11 – математическое и программное обеспечение вычислительных

машин, комплексов и компьютерных сетей

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

Москва 2007

Работа выполнена на кафедре Автоматизации систем вычислительных комплексов факультета Вычислительной математики и кибернетики МГУ им. М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук профессор, академик РАЕН Смелянский Руслан Леонидович.

Официальные оппоненты: доктор физико-математических наук профессор Томилин Александр Николаевич;

кандидат физико-математических наук доцент Захаров Владимир Анатольевич.

Ведущая организация: Институт прикладной математики им. М.В. Келдыша РАН

Защита диссертации состоится 26 октября 2007 г. в 11:00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В.Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет Вычислительной математики и кибернетики, аудитория

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ имени М.В.Ломоносова http://www.cmc.msu.ru в разделе Наука – Работа диссертационных советов – Д 501.001. Автореферат разослан 2007 г.

Ученый секретарь Диссертационного Совета Д 501.001. профессор Н. П. Трифонов

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

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

Примерами могут служить:

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

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

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

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

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

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

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

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

';

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

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

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

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

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

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

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

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

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

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

• На основе предложенных алгоритмов реализовано программное средство масштабирования имитационных моделей, описанных на языке ММ (среда моделирования ДИАНА) для ОС Linux. Эксперименты на моделях бортовых систем летательного аппарата показали снижение времени выполнения преобразованной имитационной модели от 10 до 103 раз.

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

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

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

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

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

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

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

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

На основе разработанных алгоритмов была спроектирована и реализована система масштабирования в рамках среды моделирования ДИАНА, опробованная на тестовых примерах и реальных задачах имитационного моделирования.

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

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

• Научные конференции Ломоносовские чтения (Москва, апрель 2005, 2006 и 2007 годов);

• Всероссийские конференции Методы и средства обработки информации (Москва, октябрь 2003 и 2005 годов).

Работа была выполнена при поддержке фонда РФФИ.

Публикации. По теме диссертации имеется 4 публикации, список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, шести глав и списка литературы. Объем работы 109 страниц. Список литературы содержит 52 наименования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здесь необходимо отметить, что детальность любого формального описания поведения РВС ниже, чем детальность натурного образца системы. Часть информации о поведении физической системы неизбежно теряется. Именно с этим связано понятие недетерминизма. При недетерминированном выборе того или иного варианта развития событий истинная причина выбора остаётся за рамками детальности описания системы. Будем говорить, что детальность формального описания поведения РВС характеризуется уровнем абстракции 1 (3). Данный уровень абстракции сам по себе – достаточно неформален, поскольку оперирует неформальными объектами.

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

Для того чтобы строго описать алгоритмы масштабирования и показать их корректность, нам необходимо формальное представление программы, реализующей имитационную модель, поскольку алгоритм масштабирования работает с текстом программы. Это представление должно содержать в себе всю информацию, необходимую для построения алгоритмов и доказательства их корректности. В данной работе предлагается такое представление – логическая схема имитационной модели (далее ЛС ИМ) M (6). Логическая схема имитационной модели строится (7) по описанию программы имитационной модели на языке высокого уровня (4). В рамках данной работы рассматриваются имитационные модели, описанные на языке моделирования ММ. Детальность 3 (7) логической схемы определяется информацией, необходимой для проведения корректного масштабирования и генерации описания абстрактной модели после масштабирования. Необходимо отметить, что программа на конкретном языке программирования (4) содержит в себе много информации, связанной с конкретным языком описания моделей.

Эта информация не используется при масштабировании (13), однако нужна для генерации корректного описания ИМ (19) по абстрактной ЛС ИМ (14), полученной в результате масштабирования.

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

Теперь рассмотрим ситуацию, когда мы желаем наблюдать поведение ИМ на более высоком уровне абстракции. Для формального описания подобной ситуации на множестве уровней абстракции задаётся частичный порядок (9). Воспользовавшись операцией порождения поведения на заданном уровне абстракции (10), можно построить экземпляры R и R поведения, порождаемого одной и той же логической схемой на разных уровнях абстракции (2, 11), связанных отношением порядка.

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

Далее для решения поставленной задачи нам необходимо формально описать операцию масштабирования (13) ЛС по заданному уровню абстракции. Для того чтобы не требовалась валидация полученной модели (19), нам нужно показать, что ЛС M и M (6, 14) эквивалентны на заданном уровне абстракции. Для этого мы вводим понятие эквивалентности двух ЛС на заданном уровне абстракции и показываем, что наблюдаемое поведение (11, 15), порождаемое (10, 16) такими ЛС, также будет эквивалентно на соответствующем уровне абстракции (17). Тем самым, для доказательства корректности операции масштабирования остаётся показать, что она сохраняет эквивалентность поведения ЛС ИМ на уровне абстракции (13).

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

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

Теорема 2.4.22 (о бисимуляционной эквивалентности ЛС) Пусть даны логические схемы L1 и L2 и уровни абстракции 1 и 2, такие что 1 < 2. При этом выполняется условие L1 L2. Тогда для образцов наблюдаемого поведения B1 и B2, таких что L1 B1 и L2 B2 верно, что Третья глава посвящена предлагаемому подходу к масштабированию имитационных моделей. Здесь описываются зависимости, возникающие между операторами логической схемы ИМ. Здесь же описывается предлагаемый алгоритм масштабирования дискретно-событийных имитационных моделей РВС. Приводится описание основных шагов алгоритма, оценка их сложности и доказательство корректности.

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

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

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

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

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

Сложность алгоритма по используемой памяти совпадает со сложностью алгоритма для прямой зависимости, вычислительная сложность – существенно меньше (O(D2 |N |2 ) против O(D |N |4 lg|N |)).

Учитывая, что сложность шагов построения логической схемы ИМ и генерации кода по логической схеме ИМ не превосходит O(|N N |2 ), общую вычислительную сложность алгоритма масштабирования можно оценить как O(|CC| + |P |2 Nmax (Vmax + D2 )), где P – количество последовательных процессов исходной ИМ, Nmax – максимальное количество операторов в последовательном процессе исходной ИМ, CC – количество информационных связей между операторами различных процессов исходной ИМ, Vmax – максимальное количество переменных последовательного процесса исходной ИМ, D – максимальная степень ветвления управляющего графа последовательного процесса исходной ИМ.

Сложность по памяти можно оценить как O(|CC| + |P | Nmax (D + Vmax )).

Доказана следующая теорема о корректности масштабирования.

Теорема 3.3.5 (о корректности масштабирования) Пусть нам дана ЛС имитационной модели L, моделирующая поведение РВС на уровне абстракции. Тогда для любого уровня абстракции, такого что <, достаточная ЛС модели L бисимуляционно эквивалентна ЛС модели L.

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Савенков К.О., Ющенко Н.В. Методика описания поведения процессора для оценки времени выполнения программы. //Труды 1й Всероссийской научной конференции Методы и Средства Обработки информации. Москва, 2003. С. 486– 2. Савенков К.О. Использование зависимостей при масштабировании имитационных моделей. // Труды 2й Всероссийской научной конференции Методы и Средства Обработки информации. Москва, 2005.

С. 428- 3. Бахмуров А.Г., Егисапетов Э.Г., Новиков О.В., Прус В.В., Савенков К.О., Смелянский Р.Л. Инструментальная поддержка процесса разработки ПО для спецвычислителей на основе процессора Л1879ВМ1. // Труды 2й Всероссийской научной конференции Методы и Средства Обработки информации. Москва, 2005. С. 450-456.

4. Савенков К.О., Смелянский Р.Л. Масштабирование дискретно-событийных имитационных моделей // Журнал Программирование, 2006, No.6, стр. 14-