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

Московский государственный университет им. М. В. Ломоносова Факультет Вычислительной математики и кибернетики

На правах рукопвд

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

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

05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Москва 2007

003158808

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

Научный руководитель

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

Ведущая организация

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

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

Институт прикладной математики им М В Келдыша РАН

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

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ имени M В Ломоносова http //www eme msu tu в разделе «Наука» - «Работа диссертационных советов» - «Д 501 001 44»

Автореферат разослан ¿¿o/LR 2007 г

Ученый секретарь Диссертационного Совета Д 501 001 44

профессор ^by-v H П Трифонов

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

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

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

• детальное моделирование сложных систем,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанный метод оценки времени выполнения программ для

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

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

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

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

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

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

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

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

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

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

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

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

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

Требования к решению

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

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

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

Декомпозиции задачи

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

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

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

в

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

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

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

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

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

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

область формальных рассуждений

Рис 1 Основные понятия и отношения между ними

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

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

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

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

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

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

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

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

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

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

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

Теперь рассмотрим ситуацию, кбгда мы желаем наблюдать поведение ИМ на более высоком уровне абстракции а1 Для формального описания подобной ситуации на множестве уровней абстракции задается частичный порядок (9) Воспользовавшись операцией порождения поведения на заданном уровне абстракции (10), можно построить экземпляры 72-ст и 1Z<,l поведения, порождаемого одной и той же логической схемой на разных уровнях абстракции (2, 11), связанных отношением порядка Для того чтобы сделать возможным рассуждение о корректности операции наблюдения ЛС на более высоком уровне абстракции, вводится понятие эквивалентности на заданном уровне абстракции (12) двух экземпляров наблюдаемого поведения

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

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

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

Теорема 2 4 22 (о бисимуляционной эквивалентности ЛС) Пусть даны логические схемы Ь\ и Ь^ и уровни абстракции и такие что <7\ < <тг При этом выполняется условие Ьг <-> Ь2 Тогда

а

для образцов наблюдаемого поведения В\ и В2, таких что Ьг Вг и

а1

¿2 * &г верно, что "2

<*

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

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

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

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

Разработанные алгоритмы построены на базе алгоритмов

и

Ранганата-Дайера и Ахо-Ульмана Вместо прямой зависимости по управлению, чувствительной к зацикливанию, мы предлагаем использовать для сечения транзитивную зависимость по управлению В данной главе предлагается определение такой зависимости и доказывается, что ее достаточно для построения корректного сечения Предлагается алгоритм построения таких зависимостей, доказывается его корректность Сложность алгоритма по используемой памяти совпадает со сложностью алгоритма для прямой зависимости, вычислительная сложность -существенно меньше (0(D2 х |JV|2) против 0(D х |iV|4 х ¿g|iV|))

Учитывая, что сложность шагов построения логической схемы ИМ и генерации кода по логической схеме ИМ не превосходит 0(|iViV|2), общую вычислительную сложность алгоритма масштабирования можно оценить как 0(\СС\ + \Р\2 х JV¿ax х (Vmax + D2)), где

Р - количество последовательных процессов исходной ИМ,

Nmax ~ максимальное количество операторов в последовательном процессе исходной ИМ,

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

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

D - максимальная степень ветвления управляющего графа последовательного процесса исходной ИМ Сложность по памяти можно оценить как 0(]СС\ + |Р| х N^ax х

CD + V™»))

Доказана следующая теорема о корректности масштабирования Теорема 3 3 5 (о корректности масштабирования) Пусть нам дана J1C имитационной модели L, моделирующая поведение РВС на уровне абстракции а Тогда для любого уровня абстракции а', такого что а < а', достаточная ЛС модели La' бисимуляционно эквивалентна JIC модели L

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

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

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

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

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

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

Алгоритм масштабирования дискретно-событийных имитационных моделей, описанный в Главе 2, реализован в виде инструментального

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

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

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

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

1 Савенков К О , Ющенко Н В Методика описания поведения процессора для оценки времени выполнения программы //Труды 1й Всероссийской научной конференции Методы и Средства Обработки информации Москва, 2003 С 486-491

2 Савенков К О Использование зависимостей при масштабировании имитационных моделей // Труды 2й Всероссийской научной конференции Методы и Средства Обработки информации Москва, 2005 С 428-434

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

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

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 19 09 2007 г Формат 60x90 1/16 Услпечл 1,25 Тираж 70 экз Заказ 449 Тел 939-3890 Тел/Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им MB Ломоносова, 2-й учебный корпус, 627 к

Введение

Задача масштабирования имитационной модели.

Цель диссертационной работы.

Основные результаты.7

Структура работы.8

1 Постановка задачи 9

1.1 Имитационное моделирование.9

1.2 Детализация задачи.11

1.3 Декомпозиция задачи.12

2 Основные понятия и определения 14

2.1 Дискретно-событийное имитационное моделирование

РВС.15

2.2 Схема формальных понятий.16

2.3 Формальная модель наблюдаемого поведения РВС.18

2.4 Логическая схема имитационной модели.22

2.5 Формальная постановка задачи.42

2.6 Выводы.43

3 Алгоритмы масштабирования 44

3.1 Зависимости между операторами логической схемы ИМ.44

3.2 Алгоритмы построения зависимостей.49

3.3 Алгоритм масштабирования J1C по заданному уровню абстракции.65

3.4 Выводы .73

4 Оценка времени выполнения ассемблерных инструкций 75

4.1 Задача оценки времени выполнения программы.76

4.2 Простая модель без вычислительных ресурсов.79

4.3 Операторное представление .83

4.4 Простая модель с вычислительными ресурсами.88

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

4.6 Возможные модификации модели процессора.95

4.7 Выводы.96

5 Реализация и апробация метода 97

5.1 Описание входного языка.97

5.2 Описание программной реализации.99

5.3 Апробация инструментального средства.101

5.4 Выводы.103

6 Результаты и направления дальнейших исследований 104

6.1 Основные результаты.104

6.2 Направления дальнейших исследований.105

Литература 106

Список иллюстраций

2.1 Основные понятия и отношения между ними.16

2.2 Пример последовательного процесса.28

2.3 Управляющий граф процесса Simple.29

3.1 Алгоритм транзитивного распространения символа по ориентированному графу. 50

3.2 Алгоритм построения прямой зависимости по управлению, чувствительной к зацикливанию.54

3.3 Алгоритм построения транзитивной зависимости по управлению, чувствительной к зацикливанию.57

3.4 Алгоритм построения транзитивной зависимости по управлению, чувствительной к зацикливанию.61

3.5 Алгоритм построения межпроцессных зависимостей.65

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

4.1 Схема обработки инструкции на конвейерном вычислителе.76

4.2 Схема обработки инструкции на конвейерном вычислителе.78

5.1 Синтаксис описания ММ-процесса.98

5.2 Схема интерфейсной части инструментального средства.99

5.3 Схема ядра инструментального средства.100

Введение

Задача масштабирования имитационной модели

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

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

Обычно для решения конкретной задачи ИМ требуется исследовать лишь ряд свойств поведения системы. Это означает, что не требуется наблюдать за всем поведением существующей сложной модели, а достаточно ограничиться наблюдением её поведения на некотором уровне абстракции. Часто бывает так, что и моделировать всё поведение системы для проверки заданных свойств её поведения не требуется [36].

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

Однако, если ИМ реализована в виде компьютерной программы, то приходится выполнять всю модель, что приводит к излишним затратам вычислительных ресурсов и времени, а в случае моделирования в реальном времени - к снижению точности результатов моделирования. Возникает необходимость такого преобразования программы имитационной модели, которое позволит снизить вычислительную сложность её анализа без потери точности моделирования её поведения на заданном уровне абстракции. Будем называть подобное преобразование имитационной модели, уменьшающее её детальность, масштабированием [12, 6].

Цель диссертационной работы

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

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

Актуальность работы

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

• детальное моделирование сложных систем [44],

• использование имитационного моделирования для поддержки принятия решений в реальном времени [36, 37, 18],

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

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

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

Существует несколько иной подход, основанный на использовании многоуровневых моделей [33,30]. Здесь достаточный уровень моделирования поведения выбирается непосредственно в ходе выполнения имитационного эксперимента. Однако это - также ad hoc подход, поскольку построение и валидация многоуровневой модели выполняются вручную. Более того, все возможные уровни абстракции должны быть известны в момент построения исходной модели, а это не всегда возможно.

Существует формализация операции абстракции для CSS [17], однако автору не удалось сформулировать алгоритм применения данной операции.

Существует ряд автоматических и полуавтоматических подходов к масштабированию для стохастических, непрерывных и аналитических моделей. Так, в стохастическом моделировании существует подходы к повышению вероятности возникновения редких событий [27, 31, 46]. В непрерывном моделировании можно изменять разрешение временной шкалы, заставляя модель выполняться быстрее [32, 21]. В имитационном моделировании, использующем аналитические компоненты, можно снизить точность аппроксимации аналитических функций, повысив тем самым скорость их вычисления [25, 39].

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

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

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

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

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

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

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

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

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

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

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

Структура работы

Работа состоит из введения и шести глав.

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

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

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

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

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

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

6.1 Основные результаты

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

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

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

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

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

6.2 Направления дальнейших исследований

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

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

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

1. Молонов В. Г., Смелянский Р. Л. Комплексный подход к моделированию распределенных вычислительных систем. Программирование, 6, 1987.

2. Котов В. Е., Сабельфельд В. Н. Теория схем программ. М., Наука, 1989.

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

4. Ершов А. П. Современное состояние теории схем программ. Проблемы кибернетики, 27:87-110, 1973.

5. Смелянский Р. Л. Математическая модель функционирования распределённых ВС. Вестник МГУ, сер. 15, ВМиК, 3, 1990.

6. Капитонова А. П. Методы и средства прогнозирования времени выполнения последовательных фрагментов программ на вычислителях с различной архитектурой(диссертация к.ф.-м.п.). Московский государственный университет им. М.В. Ломоносова, 1997.

7. Царьков Д. В. Верификация распределённых программ методом проверки на модели (диссертация к.ф.-м.п.). Московский государственный университет им. М.В. Ломоносова, 2002.

8. Alio А. V., Sethi R., Ullman J. D. Compilers: principles, techniques, and tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1986.

9. Bakhmurov A., Kapitonova A., Smeliansky R. Dyana: An environment for embedded system design and analysis. In Proc. of 32-nd Annual Simulation Symposium, San Diego, California, USA, April 11-15 1999.

10. Bruns G. R. Process Abstraction in the Verification of Temporal Properties. Ph.D. thesis, University of Edinburgh, 1997.

11. Burris S., Sankappanavar H. A Course of Universal Algebra. Springer-Verlag, New York, 1981.

12. Corman Т. H., Leiserson С. E., Rivest R. L. Introduction to Algorithms. MIT Press/McGraw Hill, 1990.

13. Drewry D. Т., Emanuel W. R. An optimization-bazed multi-resolution simulation methodology. In et al. Y. C. S., editor, Proceedings of the 2002 Winter Simulation Conference, 2002.

14. Ferrante J., Ottenstein K., Warren J. The program dependence graph and its use in optimization. In ACM Transactions on Programming Languages and Systems, volume 9, pages 319-349, 1987.

15. Fokkink W., Fokkink W. Introduction to Process Algebra. Springer-Verlag New York, Inc., 2000.

16. Groote J. F. The syntax and semantics of timed pCRL. In 216, page 42. Centrum voor Wiskunde en Informatica (CWI), ISSN 1386-369X, 30 1997.

17. Guo Y., Gong W., Towsley D. Time-stepped hybrid simulation (tshs) for large scale networks. In Proceedings of the IEEE Infocom, March 2000.

18. Harrold M., Rothermel G. Syntax-directed construction of program dependence graphs. Technical report osu-cisrc-5/96-tr32, The Ohio State University, 1996.

19. Heidelberger P. Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul., 5(l):43-85, 1995.

20. Kim H. Y., Kim T. G. Performance simulation modeling for fast evaluation of pipelined scalar processor by evaluation reuse. In DAC '05: Proceedings of the 42nd annual conference on Design automation, pages 341-344, New York, NY, USA, 2005. ACM Press.

21. Krinke J. Advanced Slicing of Sequential and Concurrent Programs (PhD thesis). PhD thesis, Facultat fur Mathematik und Informatik, Universitat Passau, 2003.

22. Law A. M., Kelton W. D. Simulation Modeling and Analysis. McGraw-Hill, New York, third edition, 2000.

23. L'Ecuyer P. Efficiency improvement and variance reduction. In WSC '94: Proceedings of the 26th conference on Winter simulation, pages 122-132, San Diego, CA, USA, 1994. Society for Computer Simulation International.

24. Liu В., Guo Y., Kurose J., Towsley D., Gong W. Fluid simulation of large scale network: Issues and tradeoffs. Technical Report UM-CS-1999-038, 1999.

25. Nance R. A history of discrete event simulation programming languages. In Proceedings of the Second ACM SIGPLAN History of Programming Languages Conference, pages 149-175, Cambridge, MA, April 20-23, 1993.

26. Page E. H. Simulation Modeling Methodology: Principles And Etiology of Decision Support. PhD thesis, Virginia Polytechnic Institute and State University, 1994.

27. Penzl T. Algorithms for model reduction of large dynamical systems. Sfb393/99-40, Sonderforschungsbereich 393 Numerische Simulation auf massiv parallelen Rechnern, TU Chemnitz, 09107 Chemnitz, FRG, 1999.

28. Podgurski A., Clarke L. A. A formal model of program dependences and its implications for software testing, debugging, and maintenance. IEEE Trans. Softw. Eng., 16(9):965-979, 1990.

29. Ranganath V., Amtoft Т., Banerjee A., Dwyer M., Hatcliff J. A new foundation for control-dependence and slicing for modern program structures. Technical report 8, santos lab, Kansas State University, 2004.

30. Reshadi М., Dutt N., Mishra P. A retargetable framework for instruction-set architecture simulation. Trans, on Embedded Computing Sys., 5(2):431—452, 2006.

31. Townsend J., Haraszti Z., Freebersyser J., Devetsikiotis M. Simulation of rare events in communications networks. IEEE Communications Magazine, Vol.36 No.8(August):36-41,1998.