WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 |

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

-- [ Страница 1 ] --

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

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

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

САВЕНКОВ Константин Олегович

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

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

05.13.11 математическое и программное обеспечение

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

ДИССЕРТАЦИЯ

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

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

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

МОСКВА Оглавление Введение Задача масштабирования имитационной модели...................... Цель диссертационной работы................................ Актуальность работы..................................... Основные результаты..................................... Структура работы....................................... 1 Постановка задачи 1.1 Имитационное моделирование............................. 1.2 Детализация задачи................................... 1.3 Декомпозиция задачи.................................. 2 Основные понятия и определения 2.1 Дискретно-событийное имитационное моделирование РВС............................................ 2.2 Схема формальных понятий.............................. 2.3 Формальная модель наблюдаемого поведения РВС................. 2.4 Логическая схема имитационной модели....................... 2.5 Формальная постановка задачи............................ 2.6 Выводы.......................................... 3 Алгоритмы масштабирования 3.1 Зависимости между операторами логической схемы ИМ.............. 3.2 Алгоритмы построения зависимостей......................... 3.3 Алгоритм масштабирования ЛС по заданному уровню абстракции........ 3.4 Выводы.......................................... 4 Оценка времени выполнения ассемблерных инструкций 4.1 Задача оценки времени выполнения программы................... ОГЛАВЛЕНИЕ 4.2 Простая модель без вычислительных ресурсов.................... 4.3 Операторное представление.............................. 4.4 Простая модель с вычислительными ресурсами................... 4.5 Модель с многоступенчатым конвейером и вычислительными ресурсами.... 4.6 Возможные модификации модели процессора.................... 4.7 Выводы.......................................... 5 Реализация и апробация метода 5.1 Описание входного языка................................ 5.2 Описание программной реализации.......................... 5.3 Апробация инструментального средства....................... 5.4 Выводы.......................................... 6 Результаты и направления дальнейших исследований 6.1 Основные результаты.................................. 6.2 Направления дальнейших исследований....................... Литература Список иллюстраций 2.1 Основные понятия и отношения между ними..................... 2.2 Пример последовательного процесса.......................... 2.3 Управляющий граф процесса Simple.......................... 3.1 Алгоритм транзитивного распространения символа по ориентированному графу. 3.2 Алгоритм построения прямой зависимости по управлению, чувствительной к зацикливанию....................................... 3.3 Алгоритм построения транзитивной зависимости по управлению, чувствительной к зацикливанию................................... 3.4 Алгоритм построения транзитивной зависимости по управлению, чувствительной к зацикливанию................................... 3.5 Алгоритм построения межпроцессных зависимостей................. 3.6 Алгоритм построения достаточного и вспомогательного уровней абстракции логической схемы...................................... 4.1 Схема обработки инструкции на конвейерном вычислителе............. 4.2 Схема обработки инструкции на конвейерном вычислителе............. 5.2 Схема интерфейсной части инструментального средства.............. 5.3 Схема ядра инструментального средства....................... Введение Задача масштабирования имитационной модели В настоящее время для исследования различных процессов и операций широко используется компьютерное имитационное моделирование (ИМ). При ИМ свойства физической системы проверяются при помощи компьютерной программы, воспроизводящей её поведение. С момента появления ИМ вычислительная мощность компьютеров возросла на порядки. Это позволяет строить и запускать всё более сложные и детальные модели. В то же время, существует класс задач ИМ, для решения которых вычислительной мощности традиционно не хватает. Также можно отметить общею проблему, связанную с тем, что объёмы данных, с которыми могут работать компьютеры, растут быстрее производительности.



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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует ряд автоматических и полуавтоматических подходов к масштабированию для стохастических, непрерывных и аналитических моделей. Так, в стохастическом моделировании существует подходы к повышению вероятности возникновения редких событий [27, 31, 46].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pаспpеделенной вычислительной системой (PВС) называется объект, состоящий из следующих компонентов [8]:

• Физическая сpеда (ФС), котоpая состоит из аппаpатных сpедств PВС и сpедств связи печивающих выполнение пpогpамм пользователей.

• Pабочая нагpузка, котоpая состоит из совокупности процессов прикладных программ (пpикладных пpоцессов). Пеpвые два компонента PВС (т.е. ФС+ЛС) обpазуют объект, называемый вычислительной сpедой (ВС).

Функциониpование PВС заключается во взаимодействии прикладных процессов с вычислительной средой.

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

В имитационном моделировании существует три различных понятия времени. Физическим временем называется астрономическое время моделируемой физической системы. Модельное время – это абстракция, которая испольуется для отображения моментов выполнения имитационной модели на физическое время. Инструментальное время – это астрономическое время инструментальной машины (т.е. время выполнения имитационной модели).

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

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

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

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

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

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

Для построения методики масштабирования необходимо выбрать язык описания имитационной модели. В данной работе был выбран язык ММ, используемый в среде имитационного моделирования DYANA для описания имитационных моделей распределённых вычислительных систем [2]. Как отмечалось выше, моделирование РВС хорошо подходит для апробации методик, связанных с дискретно-событийным моделированием. Существует ряд работ, в которых проводится формальное исследование свойств имитационных моделей, описанных при помощи данного языка [4, 10]. Это позволило надеяться, что для моделей, описанных на языке ММ, получится подобрать формальное представление, пригодное для описания алгоритмов масштабирования и доказательства их корректности.

Операторы описания имитационной модели можно разделить на две группы. Первая группа – это служебные операторы, выполнение которых не увеличивает модельное время. Вторая группы – это операторы, от которых зависит модельное время выполнения всех последующих операторов. Для того, чтобы операция абстракции была корректной с учётом возможного недетерминизма при захвате ресурсов, разделяемых между несколькими процессами имитационной модели, единственным способом абстрагироваться от операторов, увеличивающих модельное время, является замена их на задержку модельного времени на соответствующую величину. Операция задержки модельного времени есть практически во всех языках описания взаимодействия систем параллельных процессов [2, 24, 35]. Необходимо отметить, что используемый подход к оценке времени выполнения участков кода должен позволять комбинировать при выполнении имитационной модели оценки, полученные на статическом этапе, без потери точности оценки времени выполнения всей модели.

Всё это приводит нас к следующей детализации постановки задачи диссертационной работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

Сообщение обладает типом и может содержать поля для данных. Тип сообщения представляет собой класс эквивалентности на множестве допустимых сообщений.

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

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

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

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

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

В данной работе мы предполагаем, что каждый процесс выполняется на выделенном исполнителе. Тем самым, мы рассматриваем только ситуацию истинного параллелизма, при которой у каждого последовательного процесса есть своя временная шкала. Мы не будем сколь-нибудь детально рассматривать характеристики исполнителей и физических каналов передачи данГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ных и сведём их к функции, ставящей в соответствие оператору имитационной модели время его выполнения. При этом данные оценки обладают свойством дистрибутивности относительно последовательной композиции операторов (т.е. время выполнения последовательной композиции операторов имитационной модели равно последовательной композиции их времён выполнения). Более подробно об подходе к оценке времени выполнения линейных участков кода имитационной модели, обладающем указанными свойствами см. Главу 4.

2.2 Схема формальных понятий Изложенная в данном разделе схема формальных понятий для наглядности приведена на рис.

2.1. Стрелками обозначены отношения между формальным и неформальными понятиями.

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

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

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

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

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

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

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

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

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

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

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

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

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

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

2.3.1 Основные понятия формальной модели функционирования РВС В работе [8] распределённой вычислительной системой (РВС) R называется объект, состоящий из вычислительной среды и рабочей нагрузки. Под вычислительной средой понимается множество E вычислителей (процессоров), среда их взаимодействия, а также множество PL процессов базового ПО (операционной системы). Рабочей нагрузкой называется

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

множество P процессов прикладных программ (последовательных процессов) и процессов.

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

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

Несколько упрощая [8], объединим процессы вычислительной среды в единое множество A, обозначив 1. P – множество прикладных процессов в РВС, PL – множество процессов базового ПО.

2. Stop PL – фиксированный процесс, обращение к которому вызывает остановку обратившегося последовательного процесса.

4. IA – алфавит внутренних действий процессов из P. В данной работе примем, что 5. M – множество типов сообщений, которыми могут обмениваться процессы из P.

s – сообщение-воздействие шага s, qs – последовательность внутренних действий шага s, s – сообщение-реакция шага s,

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

ps – процесс, которому шаг s отправляет сообщение s и передаёт управление.

Подробнее о шагах процесса см. [8].

Каждый процесс p из множества P представлен деревом поведения последовательного процесса, которое есть ациклический ориентированный граф bhp = (Vp, Rp, v0, labelp ), где вершины Vp – это множество состояний последовательного процесса, а Rp – отношение достижимости, v0 – выделенная корневая вершина. labelp – функция разметки элементов множества Vp шагами из множества S. Дерево поведения процесса может быть бесконечным, однако из каждой его вершины может исходить лишь конечное число дуг [8].

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

2.3.2 Формальная модель наблюдаемого поведения РВС Данная работа касается вопросов преобразования прикладных процессов из множества P (см.

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

В рамках данной работы рассматриваются РВС с взаимно однозначным отношением Bind (см. Раздел 3.1). Это означает, что на каждом вычислителе может выполняться лишь один процесс. Таким образом, все процессы в РВС выполняются в режиме истинного параллелизма.

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

Всё это позволяет нам рассматривать гораздо более простую и общую формальную модель наблюдаемого поведения РВС.

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

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Наблюдаемое поведение РВС B описывается следующей сигнатурой:

где = pP p – алфавит наблюдаемых событий РВС, при этом – ненаблюдаемое событие, введённое для удобства описания эквивалентности двух деревьев с разными множествами наблюдаемых событий (см. ниже).

P – множество последовательных процессов, которые наблюдатель выделяет в системе, RI p q - множество причинно-следственных связей между событиями в различных процессах, T – множество модельного времени.

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

Последовательный процесс p P описывается пятёркой (Np, Rp, Lp, Dp, n0 ), где Np – вершины дерева поведения последовательного процесса p (экземпляры событий), Rp Np Np – множество причинно-следственных связей между экземплярами событий Lp : Np p – функция разметки вершин дерева поведения процесса наблюдаемыми Dp : Rp T – продвижение модельного времени между выполнением двух событий, n0 Np – первое событие процесса.

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

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

Последовательный процесс можно представить в виде дерева с вершинами Np и дугами Rp. Тогда отображение Dp будет задавать разметку на дугах.

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

Если при этом события-потомки не зависят от событий в других процессах, то это – внутренний недетерминизм [8].

Он возникает, если действительная причина ветвления процесса в РВС лежит на более низком уровне абстракции чем тот, на котором описано её поведение. Если же недетерминированное выполнение событий зависит от событий в других последовательных процессах, то такой недетерминизм называется внешним [8].

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

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

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

Будем называть такое представление логической схемой описания имитационной модели. Понятие логической схемы имитационной модели близко к понятию схемы программы [3]. Логическая схема включает в себя только те аспекты описания имитационной модели,

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

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

1. Логическая схема должна однозначно соответствовать описанию имитационной модели.

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

Требование соблюдения обратного условия не накладывается.

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

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

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

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

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

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

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

2.4.2 Предварительные соглашения Из существующих формализмов для описания логической схемы более всего подходит алгебра процессов [23]. Однако для описания алгоритмов масштабирования и доказательства их корректности необходимо рассматривать атомарное действие более детально, чем это делается в стандартной ACP [23]. Так, для оператора языка описания имитационной модели нам необходимо отражать не только информацию о соответствующем ему атомарном действии последовательного процесса (как это происходит в ACP), но и информацию об используемых и определённых переменных (для учёта зависимостей по данным при трансформации имитационной модели). Также необходимо уметь оценивать влияние различных операторов на значения переменных процесса и выбор пути выполнения в управляющем графе процесса.

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

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

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

2.4.3 Специальные обозначения В данном разделе используется нотация универсальной алгебры [19], со следующими расширениями:

Определение 2.4.1 Множество всех (строго) упорядоченных подмножеств некоi= торого множества D, которое в нотации универсальной алгебры можно записать как D, обозначается выражением 2, по аналогии с обозначением множества всех подмножеств.

Определение 2.4.2 (Строго) упорядоченное множество элементов некоторого множества D будем обозначать как d 2 D.

Определение 2.4.3 Для упорядоченного множества d элементов множества D, некоторого множества E определим операцию подстановки где | d |=| e |.

обозначается значение истина, символом – значение ложь.

Символом 2.4.4 Сигнатура логической схемы Опишем логическую схему имитационной модели как многоосновную алгебраическую систему.

Сигнатура многоосновной алгебраической системы – это набор множеств и операций, заданных над элементами этих множеств. Будем называть сигнатурой логической схемы структуру (Data, Func, P roc, Comm, ), элементы которой определяются далее по тексту.

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

0 Data – минимальный элемент Data.

Func – множество функций (операторов) вида f : 2 Data Data над векторами (упорядоченными подмножествами) значений из Data.

При этом выполняются следующие аксиомы:

0=0 (базис отношения равенства),

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

равенства).

В терминах подобных операторов описываются изменения переменных процессов. Это позволит в дальнейшем рассуждать об эквивалентности изменений переменных последовательного процесса, выполненных различными последовательностями операторов. Алгебру (Data, Func) можно рассматривать как алгебру термов [19], где {Func 0} – алфавит, P roc – множество последовательных процессов модели, подробное описание данного множества приведено в следующем разделе, Comm – отношение взаимодействия по данным и управлению между операторами последовательных процессов (см. раздел 2.4.6), – операция порождения наблюдаемого поведения в терминах формальной модели наблюдаемого поведения (выполнение одного оператора последовательным процессом, см. раздел 2.4.8).

2.4.5 Последовательные процессы Каждому последовательному процессу имитационной модели РВС соответствует элемент множества P roc. Последовательный процесс p P roc представлен в виде структуры (G, V ar, Ast, Est, F unc, P red), где G – управляющий граф последовательного процесса G = (N, E, n0 ), где N - множество вершин, каждая из которых соответствует оператору описания имитационной модели, E - множество дуг, соответствующих переходу управления в программе описания имитационной модели; множество N состоит из двух непересекающихся подмножеств, N S и N P, где N S – операторы, и у каждого ns N S есть не более одной вершины-потомка, а N P – условные операторы, и у каждого np N P есть не более чем конечное число потомков; у стартовой вершины n0 нет входящих дуг, и все вершины в графе G достижимы из неё;

V ar – множество переменных процесса имитационной модели;

Ast – множество деревьев разбора операторов описания имитационной модели, при этом существует элемент (t) Ast, соответствующий дереву разбора оператора продвижения модельного времени на величину t Est;

Est – множество статических оценок времени выполнения инструкций;

P red 2V ar {, } – множество предикатов над значениями переменных процесса;

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

F unc Func – множество операторов изменения значений переменных процесса.

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

ast : N Ast – каждой вершине управляющего графа n N соответствует поддерево в дереве синтаксического разбора программы описания имитационной модели. Все элементы сигнатуры процесса, кроме N и E, а также отношения разметки, строятся на основе элементов множества Ast. Таким образом, для каждого языка описания имитационной модели должны быть описаны свои алгоритмы построения элементов множеств V ar, Est и F unc на основе множества Ast.

f unc : N V ar {Func}2 V ar – каждой вершине управляющего графа n N соответствует набор функций из множества Func (по одной на каждую переменную процесса) и векторов переменных на которых вычисляется значение данных функций; если паре (вершина, переменная) соответствует, то данная переменная не изменяется в ходе выполнения оператора описания имитационной модели, соответствующего данной вершине управляющего графа процесса. Будем считать, что если переменная изменяется в ходе взаимодействия с другим процессом, то её значение становится недетерминированным.

est : N Est – каждой вершине управляющего графа n N соответствует статическая оценка времени выполнения данной инструкции. Статическая оценка для оператора описания имитационной модели – это информация о времени выполнения данного оператора, которую можно получить на основе информации о вычислителе, на котором будет выполняться последовательный процесс и машинном коде, который будет сгенерирован для данного оператора. При выполнении имитационной модели статические оценки для отдельных участков кода компонуются, в результате чего получается точное модельное время. Подробнее о различных подходах к оценке времени в дискретно-событийном имитационном моделировании см. Главу 4.

use : N 2V ar – каждой вершине управляющего графа n N ставится в соответствие набор используемых в ней переменных последовательного процесса. Это отношение строится на основе отношения f unc следующим образом:

def : N 2V ar – каждой вершине управляющего графа n N ставится в соответствие набор определяемых в ней переменных последовательного процесса. Это отношение строится на основе отношения f unc следующим образом:

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

L1: process Simple { L2: int a = 0, b = 1;

L3: while (a < 3) L4: a += b;

L5: stop;

L6: } f lags : N P red 2 V ar – каждой вершине управляющего графа n N ставится в соответствие предикат, значение которого при выполнении программы вычисляется на значениях переменных программы. Семантика данных предикатов близка к семантике регистра флагов: если из вершины, в которой вычисляется данный предикат, ведёт две дуги, то управление передаётся через дугу, которая помечена вычисленным значением или ). Подробнее см. в разделе 2.4.8 (“Операционная семантика”).

f lag : E {, } – каждой дуге e E ставится в соответствие значение (истина) или (ложь). Если из некоторой вершине n выходит две дуги, то после её выполнения управление передаётся на дугу e, разметка которой совпадает с результатом вычисления предиката в вершине (f lags(n) |V ar = f lag(e)). Подробнее см. в разделе 2.4.8 (“Операционная семантика”).

На рис. 2.2 приведён пример простейшего последовательного процесса, описанного на языке ММ [2]. Операторы L2 и L3 объявляют и определяют две переменных (a и b), оператор L увеличивает значение переменной a на значение переменной b. Оператор L5 останавливает выполнение процесса.

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

V arSimple = {a, b} AstSimple = {astL2, astL3, astL4, astL5 } EstSimple = {| L2 |, | L3 |, | L4 |, | L5 |} F uncSimple = {0”(0), 1”(0), ”+ = ”(1)}(в скобках обозначена арность функции) P redSimple = {_ < 3(1)} Элементы сигнатуры будут размечены следующим образом:

astSimple = {(L2, astL2 ), (L3, astL3 ), (L4, astL4 ), (L5, astL5 )} estSimple = {(L2, | L2 |), (L3, | L3 |), (L4, | L4 |), (L5, | L5 |)}

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

f lagsSimple = {(L2, ), (L3, < 3, a ), (L4, ), (L5, )} f lagSimple = {(L2 L3, ), (L3 L4, ), (L3 L5, ), (L4 L3, )} useSimple = {(L2, ), (L3, {a}), (L4, {b}), (L5, )} defSimple = {(L2, {a, b}), (L3, ), (L4, {a}), (L5, )} 2.4.6 Взаимодействие последовательных процессов В описании имитационной модели на языке высокого уровня присутствуют 1) операторы (или вызовы библиотечных функций), выполнение которых приводит к действиям посылки и передачи сообщений, 2) механизм хранения и обработки сообщений, а также 3) механизм сопоставления действий посылки и приёма сообщений (логические каналы передачи сообщений).

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

Сопоставление операторов посылки и приёма сообщений выполняется при помощи отношения Comm, которое определяется следующим образом:

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Если дисциплина буфера недетерминирована или в один буфер могут писать сразу несколько процессов (как это может быть в языке ММ [2]), то в множество Comm включаются все возможные сочетания операторов посылки и приёма сообщений.

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

1. Из вершины n графа G выходит единственная дуга, которая помечена меткой, тогда и только тогда, когда эта вершина не содержит оператора условного ветвления: n 2. Из одной вершины не может выходить двух дуг, помеченных одинаковыми метками:

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

n1, n2 (est(n1 ) = 0 est(n2 ) = 0 (n1, n2 ) p.G.E |est(n1 )| |est(n2 )| = |est(n1 ) est(n2 )|).

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

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

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

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

Здесь принимается следующая семантика наблюдаемого события имитационной модели:

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

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

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

При этом если p (x) =, то оператор x является ненаблюдаемым (его выполнению не соответствует никакое событие наблюдаемого поведения РВС), если p (x) =, то существует единственное событие РВС, соответствующее выполнению данного оператора, если же p (x) =, то существует класс событий наблюдаемого поведения x B. процесса p B.P, соотp ветствующих выполнению данного оператора. События РВС, принадлежащие данному классу, соответствуют различным комбинациям значений переменных, принадлежащих p (x). Не ограничивая общности рассуждений, будем считать, что множество наблюдаемых событий последовательного процесса РВС можно разбить на классы эквивалентности по операторам, выполнение которых соответствует возникновению данных событий.

При этом множество можно разбить на классы эквивалентности по значению наблюдаp емых в данной точке переменных. Очевидно, это можно сделать k способами, где k =| p (n) |.

Уровнем абстракции наблюдения логической схемы L будет называться объединение уровней абстракции её последовательных процессов:

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

На множестве уровней абстракции логической схемы L введём отношение частичного порядка 0 (i = 1 lj = 0) Единственная непустая строка в операторе F 1 соответствует формуле 4.8, непустые строки в операторе F 2 соответствуют формулам 4.9 и 4.10.

ГЛАВА 4. ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ АССЕМБЛЕРНЫХ ИНСТРУКЦИЙ

4.4.5 Сложность поэлементной оценки На статическом этапе будет создано 2· | instruction_set(M1 ) | оператора для инструкций, для каждого из них будет использовано O(| resources(M1 ) |2 ) памяти. На динамическом этапе 2 · m · n раз оператор оценки будет применён к состоянию процессора, при этом сложность каждой операции можно оценить в O(| resources(M1 ) |2 ).

Таким образом, сложность статического этапа составит O(k · r2 ), сложность динамического – O(m · n · r2 ), где k =| instruction_set(M1 ) |, r =| resources(M1 ), m – максимальная длина линейного участка, а n – число линейных участков в программе. Общая сложность, таким образом, составит O((k + m · n) · r2 ).

4.4.6 Сложность блочной оценки Дополнительно к поэлементной оценке на статическом этапе будет выполнено 2 · n · (m 1) операций слияния операторов оценки. Сложность операции равна O(r3 ), поэтому суммарная сложность статического этапа составит O(k·r2 +n·m·r3 ), и будет использовано O(n·r2 ) памяти.

На динамическом этапе будет выполнено n операций изменения состояния процессора, и его сложность составит O(n·r2 ). Суммарная сложность блочной оценки равна O((k+n)·r2 +n·m·r3 ).

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

4.5 Модель с многоступенчатым конвейером и вычислительными ресурсами 4.5.1 Модель процессора Рассмотрим модель процессора M2, которая отличается от модели M1, наличием p ступеней конвейера инструкции. Покажем, как можно обобщить описание оператора оценки для

ГЛАВА 4. ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ АССЕМБЛЕРНЫХ ИНСТРУКЦИЙ

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

Для каждой инструкции I определим набор упорядоченных множеств reqi (I) = qj и locki (I) = lj для i = 1, p, j = 1, | resources(M1 ) | ресурсов, необходимых для выполнения и блокируемых инструкцией для i-ой ступени конвейера. По аналогии с предыдущим разделом определим функцию ti (r, I).

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

где i = 2, p.

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

4.5.3 Операторное представление Таким образом, изменение инструкцией состояния процессора будет описываться при помощи p операторов, по одному на каждую ступень процессора:

ГЛАВА 4. ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ АССЕМБЛЕРНЫХ ИНСТРУКЦИЙ

Время освобождения ресурсов, заблокированных инструкцией на некоторой ступени k конвейера, определяется в операторе для данной ступени по формуле:

Таким образом, операторы F k = fij будут определяться по формулам 4.5.4 Сложность поэлементной оценки На статическом этапе будет создано p· | instruction_set(M1 ) | оператора для инструкций, для каждого из них будет использовано O(| resources(M1 ) |2 ) памяти. На динамическом этапе p · m · n раз оператор оценки будет применён к состоянию процессора, при этом сложность каждой операции можно оценить в O(| resources(M1 ) |2 ).

Таким образом, сложность статического этапа составит O(p · k · r2 ), сложность динамического – O(p · m · n · r2 ), где k =| instruction_set(M1 ) |, r =| resources(M1 ), m – максимальная длина линейного участка, n – число линейных участков в программе, а p– число ступеней конвейера M1. Общая сложность, таким образом, составит O((k + m · n) · p · r2 ).

4.5.5 Сложность блочной оценки Дополнительно к поэлементной оценке на статическом этапе будет выполнено p · n · (m 1) операций слияния операторов оценки. Сложность операции равна O(r3 ), поэтому суммарная сложность статического этапа составит O(p · k · r2 + p · n · m · r3 ), и будет использовано O(n · r2 ) памяти. На динамическом этапе будет выполнено n операций изменения состояния процессора, и его сложность составит O(n · r2 ). Суммарная сложность блочной оценки равна O((k + n) ·

ГЛАВА 4. ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ АССЕМБЛЕРНЫХ ИНСТРУКЦИЙ

Теорема 4.5.1 (условия эффективности блочной оценки) Сравним сложность поэлементной и блочной оценки для того, чтобы определить условия эффективности блочной оценки. Учитывая, что p r, получаем:

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

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

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

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

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

ГЛАВА 4. ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ АССЕМБЛЕРНЫХ ИНСТРУКЦИЙ

3. Чтение инструкций и данных по одной шине. Память команд и память данных вычислительного устройства могут находиться на одной шине. при этом в различных вычислительных устройствах могут быть различные правила арбитража данной шины. Так, в процессоре Л1879ВМ1 приоритетным является выборка инструкций в буфер. Для поддержки данного механизма оператор изменения состояния процессора представляется в виде последовательной композиции двух операторов, один из которых описывает изменение состояния процессора при выборке инструкции, а второй – операции с памятью, производимые инструкцией (считывание аргументов или запись результата).

4.7 Выводы Разработанный подход к моделированию процессора основан на существующем подходе к описанию целевого вычислителя как набора ресурсов, разделяемых между инструкциями [9]. Однако он обладает двумя существенными преимуществами:

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

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

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

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

5.1 Описание входного языка В качестве языка описания имитационных моделей, подлежащих масштабированию, выполненная реализация использует язык ММ [2], который применяется для описания имитационных моделей РВС в среде моделирования ДИАНА. Приведём кратное описание основных структур языка [11].

На рис. 5.1 описан синтаксис ММ-процесса. Здесь и далее при описании семантики ММязыка S описывает оператор, in – имя входного буфера, out – имя выходного буфера, T – тип переменной (int, bool, msg, и т.д.), v – имя переменной, и E – выражение. Неформально смысл ММ-выражений определяется следующим образом:

ГЛАВА 5. РЕАЛИЗАЦИЯ И АПРОБАЦИЯ МЕТОДА

P ::= process name() S S ::= T v; | complex {S} | while(E) S1 | delay(E); | send(v,out); | receive(v,in); | select(nm) {(case inj : Sj ) [timeout E:S0 ]} • T v; определяет новую переменную с именем v и типом T ;

• v = E; оценивает выражение E и присваивает переменной v его значение;

• complex {S} определяет оператор, время выполнения которого вычисляется системой оценки времени;

• if (E) S1 [else S2 ] и while(E) S1 имеют обычный смысл условного оператора и оператора цикла соответственно;

• stop; немедленно прекращает выполнение процесса;

• delay(E); приостанавливает выполнение процесса на указанное модельное время;

• send(v,out); посылает сообщение, хранящееся в переменной v, в выходной буфер out;

• receive(v,in); получает сообщение из входного буфера in и присваивает его значение переменной v; если буфер не содержит сообщений, то процесс приостанавливается до тех пор, пока сообщение не появится;

• оператор select {...} позволяет получить сообщение по одному из указанных в нём входных буферов inj ; дополнительная секция timeout E:S0 выполняется в случае, если по прошествии указанного времени (E) ни один из каналов не содержит сообщения.

ГЛАВА 5. РЕАЛИЗАЦИЯ И АПРОБАЦИЯ МЕТОДА

Рис. 5.2: Схема интерфейсной части инструментального средства 5.2 Описание программной реализации Программная реализация алгоритма масштабирования состоит из двух частей. Ядро программной реализации (см. рис. 5.3) включает в себя реализацию алгоритмов построения зависимостей по логической схеме имитационной модели, а также алгоритм, который по множеству зависимостей и требуемому уровню абстракции строит достаточный и вспомогательный уровни абстракции ЛС. Множество зависимостей логической схемы представляется в виде графа, вершинами которого являются операторы последовательных процессов ЛС, а дугами – различные зависимости между ними. Интерфейсная часть отвечает за сопряжение ядра системы с конкретным языком описания ИМ и уровня абстракции наблюдаемого поведения.

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

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

1. Транслятор: производит разбор исходного текста ММ-программы и выполняет построение абстрактного синтаксического дерева (AST), 2. Конструктор логической схемы ИМ: при помощи шаблона Visitor осуществляет обход AST, в ходе которого создаются логические схемы последовательных процессов ЛС, а

ГЛАВА 5. РЕАЛИЗАЦИЯ И АПРОБАЦИЯ МЕТОДА

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

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

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

Ядро системы масштабирования отвечает за генерацию множества зависимостей ЛС ИМ, данному требуемому уровню абстракции её наблюдаемого поведения. В её состав входят соответствующие компоненты:

1. Конструктор внутрипроцессных зависимостей: реализует алгоритмы 3.3-3.4, выполняя построение зависимостей по данным, управлению и времени выполнения между операторами в рамках одного последовательного процесса для всех процессов ЛС ИМ. Отношения зависимости представляются в виде графа, в вершинах которого находятся вершины управляющего графа последовательного процесса логической схемы, а дуги размечены в соответствии с зависимостями, связывающими вершины, 2. Конструктор межпроцессных зависимостей: на основании топологии ЛС строит множества зависимостей между операторами различных последовательных процессов ЛС (алгоритм 3.5). Данные зависимости объединяют графы зависимостей последовательных процессов ЛС в общий граф зависимостей ЛС, который и подаётся на вход генератору 3. Генератор сечения графа зависимостей: по общему графу зависимостей ЛС и требуемому уровню абстракции, заданному в терминах данной ЛС, выполняет построение достаточного и вспомогательного уровней абстракции наблюдаемого поведения ЛС, реализуя алгоритм 3.6.

Инструментальное средство написано на С++ под операционную систему Debian Linux, для реализации графического интерфейса используется библиотека Qt4.2, для реализации алгоритмов масштабирования – библиотеки STL и Boost, для визуализации графов – средство graphviz. Транслятор и кодогенератор построены при помощи генератора парсеров для LR(1) грамматик Whale.

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

Модель насчитывает около 27500 отдельных операторов, разбитых на 139 последовательных процессов. Основными компонентами модели являются четыре бортовых вычислительных машины (БЦВМ), на которых выполняются различные функциональные задачи (ФЗ), а также система потоковой обработки телесигнала (БПТС). Компоненты бортовой сети объединены при помощи нескольких видов шин, среди которых FiberChannel и PCI.

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

ГЛАВА 5. РЕАЛИЗАЦИЯ И АПРОБАЦИЯ МЕТОДА

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

Апробация проводилась на двухпроцессорном сервере 2xXeon 2.8ГГц с 6Гб оперативной памяти.

После консультации с разработчиками ИМ для апробации были выбраны два практически важных уровня абстракции: выделение отдельной подсистемы (БПТС) и выделение части ИМ, необходимой для точного воссоздания работы одной из функциональных задач. Ниже приводятся результаты численных экспериментов в сравнении с работой исходной модели.

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

Первый уровень абстракции AL1 включает в себя все операторы передачи сообщений в последовательном процессе одной функциональной задачи (ФЗ), работающей на одной из БЦВМ, вместе со значениями пересылаемых данных. В результате масштабирования исходной модели по уровню абстракции AL1 получена модель AM1, в которую в полном объёме входят модели выбранной ФЗ и БЦВМ, заглушки для других ФЗ, работающих на данной БЦВМ (в них вошли операции передачи сообщений без значения передаваемых данных), а также заглушки компонентов БЦВМ, взаимодействующих с ними.

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

Уровень AL1 включает в себя 30 операторов, принадлежащих одному последовательному процессу, AL2 – 15 операторов из двух последовательных процессов.

Построение ЛС имитационной модели и её масштабирование занимало около 40 секунд для обоих уровней абстракции. Верхний предел модельного времени одного имитационного эксперимента установлен в 1Е+09 тактов. Результаты сравнения производительности исходной модели и моделей AM1, AM2, соответствующих описанным выше заданным уровням абстракции AL1 и AL2, представлены в таблице 5.1. В обоих случая временные диаграммы, полученные для исходной и абстрактной моделей совпадают на заданном уровне абстракции.

ГЛАВА 5. РЕАЛИЗАЦИЯ И АПРОБАЦИЯ МЕТОДА

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

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

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

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

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

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

ГЛАВА 6. РЕЗУЛЬТАТЫ И НАПРАВЛЕНИЯ ДАЛЬНЕЙШИХ ИССЛЕДОВАНИЙ

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

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

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

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

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

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

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

[4] Захаров В. А., Кончаков Р. В. Теоретико-автоматный подход к определению формальных семантик языков программирования. In Труды Международной конференции "Параллельные вычисления и задачи управления"(РАСО’2001), pages 107–114. -М. Институт проблем управления им. В.А.Трапезникова РАН, 2001.

[5] Савенков К. О., Ющенко Н. В. Методика описания поведения процессора для оценки времени выполнения программы. In Труды Всероссийской научной конференции "Методы и средства обработки информации"(1 октября - 3 октября 2003 г., г. Москва), pages 486– 491. -М.: Издательский отдел факультета ВМиК МГУ, 2003.

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

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

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

Методы и средства прогнозирования времени выполнения поКапитонова А. П.

рой(диссертация к.ф.-м.н.). Московский государственный университет им. М.В. Ломоносова, 1997.

[10] Царьков Д. В. Система формальной верификации распределенных программ в среде имитационного моделирования dyana. In Труды Международной конференции "Параллельные вычисления и задачи управления"(РАСО’2001), pages 161–182. -М. Институт проблем управления им. В.А.Трапезникова РАН, 2001.

[11] Царьков Д. В. Верификация распределённых программ методом проверки на модели (диссертация к.ф.-м.н.). Московский государственный университет им. М.В. Ломоносова, [12] Савенков К. О. Использование зависимостей при масштабировании имитационных моделей. In Методы и средства обработки информации. Труды второй Всероссийской научной конференции, pages 428–434. -М.: Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В. Ломоносова, 2005.

[13] Aho A. V., Sethi R., Ullman J. D. Compilers: principles, techniques, and tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1986.

[14] 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.

[15] Balashov V. V., Kapitonova A., Kostenko V., Smeliansky R., Youshchenko N. Modeling of digital signal processors based on the static-dynamic approach.

rst International Conference "Digital sigmal processing and its applications Moscow, MCNTI, volume IV-E, pages 79–83, 1998.

[16] Boesel J., Royce O. Bowden J., Glover F., Kelly J. P., Westwig E. Panel: simulation optimization: future of simulation optimization. In WSC ’01: Proceedings of the 33nd conference on Winter simulation, pages 1466–1469, Washington, DC, USA, 2001. IEEE Computer Society.

[17] Bruns G. R. Process Abstraction in the Verication of Temporal Properties. Ph.D. thesis, University of Edinburgh, 1997.

[18] Bruzzone A., Taylor S. J. E., Fujimoto R., Gan B. P., Strauburger S., Paul R. J. Panel discussion on distributed simulation and industry: potentials and pitfalls: distributed simulation and industry: potentials and pitfalls. In WSC ’02: Proceedings of the 34th conference on Winter simulation, pages 688–694. Winter Simulation Conference, 2002.

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

[20] Corman T. H., Leiserson C. E., Rivest R. L. Introduction to Algorithms. MIT Press/McGraw Hill, 1990.

[21] Drewry D. T., 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.

[22] 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.

[23] Fokkink W., Fokkink W. Introduction to Process Algebra. Springer-Verlag New York, Inc., [24] Groote J. F. The syntax and semantics of timed µCRL. In 216, page 42. Centrum voor Wiskunde en Informatica (CWI), ISSN 1386-369X, 30 1997.

[25] Guo Y., Gong W., Towsley D. Time-stepped hybrid simulation (tshs) for large scale networks.

In Proceedings of the IEEE Infocom, March 2000.

[26] Harrold M., Rothermel G. Syntax-directed construction of program dependence graphs.



Pages:     || 2 |


Похожие работы:

«Диссертация на соискание ученой степени доктора технических наук Xвaлин Aлeкcaндр Львoвич Aнaлиз и cинтeз интeгрaльныx мaгнитoупрaвляeмыx рaдиoтeхничecкиx уcтрoйcтв нa фeрритoвыx peзoнaтopax 05.12.04 Радиотехника, в том числе системы и ycтpoйcтва телевидения Самара – 2014 2 Стр. Содержание Содержание 2 Термины и определения 6 Обозначения и сокращения Введение Глава 1 Исследования в диапазонах УВЧ, СВЧ по созданию интегральных...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Букаева, Ирина Николаевна Обстановка совершения преступления, получение и использование информации о ней при расследовании уголовных дел Москва Российская государственная библиотека diss.rsl.ru 2006 Букаева, Ирина Николаевна Обстановка совершения преступления, получение и использование информации о ней при расследовании уголовных дел : [Электронный ресурс] : Дис. . канд. юрид. наук  : 12.00.09. ­ Тюмень: РГБ, 2006 (Из фондов Российской...»

«Мальцева Юлия Михайловна ЕВРОПЕЙСКИЙ АВАНГАРДНЫЙ ДРАМАТИЧЕСКИЙ ТЕАТР: КОНЦЕПТУАЛЬНЫЕ КОНСТАНТЫ И ДИСКУРСИВНЫЕ ТРАНСФОРМАЦИИ. Специальность: 09.00.13. – философская антропология, философия культуры Диссертация на соискание ученой степени кандидата философских наук Научный руководитель : доктор философских наук профессор кафедры культурологии СПбГУ Соколов Евгений Георгиевич Санкт-Петербург Содержание. Введение... Глава I....»

«УДК 619:636.1 ДАВААДОРЖИЙН ЛХАМСАЙЗМАА ЭТИОПАТОГЕНЕЗ, СИМПТОМЫ И ЛЕЧЕНИЕ ОСТРОГО РАСШИРЕНИЯ ЖЕЛУДКА МОНГОЛЬСКОЙ ЛОШАДИ 06.02.01 – диагностика болезней и терапия животных, патология, онкология и морфология животных. Диссертация на соискание ученой...»

«Гуревич Павел Леонидович УДК 517.95 ЭЛЛИПТИЧЕСКИЕ ЗАДАЧИ С НЕЛОКАЛЬНЫМИ КРАЕВЫМИ УСЛОВИЯМИ И ПОЛУГРУППЫ ФЕЛЛЕРА специальность 01.01.02 — дифференциальные уравнения Диссертация на соискание ученой степени доктора физико-математических наук Научный консультант : доктор физико-математических наук, профессор А. Л. Скубачевский Москва — 2008 Оглавление Введение Глава I. Нелокальные эллиптические задачи с нелинейными преобразованиями переменных...»

«Моргоева Зарина Зейналовна КЛИНИКО-ЛАБОРАТОРНАЯ ОЦЕНКА ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ ИММОБИЛИЗОВАННОГО ФТОРИДА ОЛОВА В КОМПЛЕКСНОЙ ТЕРАПИИ ВОСПАЛИТЕЛЬНЫХ ЗАБОЛЕВАНИЙ ПАРОДОНТА 14.01.14 – стоматология диссертация на соискание ученой степени кандидата медицинских наук научный руководитель:...»

«Татарчук Александр Игоревич БАЙЕСОВСКИЕ МЕТОДЫ ОПОРНЫХ ВЕКТОРОВ ДЛЯ ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ С УПРАВЛЯЕМОЙ СЕЛЕКТИВНОСТЬЮ ОТБОРА ПРИЗНАКОВ 05.13.17 – Теоретические основы информатики диссертация на соискание учёной степени кандидата физико-математических наук Научный руководитель д.т.н., профессор Моттль Вадим Вячеславович Москва, 2014 -2Содержание...»

«Малькевич Мария Сергеевна РЕАЛИЗАЦИЯ ПРИНЦИПА РАВЕНСТВАПРАВ РОДИТЕЛЕЙ 12.00.03 – гражданское право; предпринимательское право; семейное право; международное частное право ДИССЕРТАЦИЯ на соискание ученой степени кандидата юридических наук Научный руководитель : кандидат юридических наук, доцент Т.И. Хмелева Саратов – ОГЛАВЛЕНИЕ...»

«Казакова Анна Игоревна ОСОБЕННОСТИ ФОРМИРОВАНИЯ ФРАЗЕОЛОГИЧЕСКОЙ СЕМАНТИКИ В ДИСКУРСИВНОМ ПРОСТРАНСТВЕ ОТЕЧЕСТВЕННОГО КИНОИСКУССТВА Специальность 10.02.01 – русский язык Диссертация на соискание ученой степени кандидата филологических наук Научный руководитель – Золотых Лидия Глебовна, доктор филологических наук, профессор Астрахань...»

«Шарафутина Светлана Федоровна ОСОБЕННОСТИ БУХГАЛТЕРСКОГО УЧЕТА ЗАТРАТ И КАЛЬКУЛИРОВАНИЯ СЕБЕСТОИМОСТИ ЗАСТРОЙЩИКОМ ПРИ ДОЛЕВОМ СТРОИТЕЛЬСТВЕ Специальность 08.00.12 – Бухгалтерский учет, статистика Диссертация на соискание ученой степени кандидата экономических наук Научный руководитель доктор экономических наук, профессор Ю.Ю. Кочинев Санкт-Петербург Введение Глава 1. Анализ затрат застройщиков при долевом строительстве: правовое и методическое обеспечение 1.1 Основные...»

«Стасенко Наталья Михайловна ОРГАНИЗАЦИЯ ВНЕУЧЕБНОЙ ВОСПИТАТЕЛЬНОЙ РАБОТЫ В ПЕДАГОГИЧЕСКОМ КОЛЛЕДЖЕ 13.00.01 – общая педагогика, история педагогики и образования Диссертация на соискание ученой степени кандидата педагогических наук Научный руководитель доктор педагогических наук, профессор Малашихина И.А. Ставрополь – 2004 СОДЕРЖАНИЕ стр. ВВЕДЕНИЕ.. ГЛАВА 1. Теоретические аспекты исследования организации внеучебной воспитательной...»

«ГАЛИМОВА ЛЕЙСАН ХАЙДАРОВНА Идиоматическое словообразование татарского и английского языков в свете языковой картины мира 10.02.02 – Языки народов Российской Федерации (татарский язык) 10.02.20 – Сравнительно-историческое, типологическое и сопоставительное языкознание ДИССЕРТАЦИЯ на соискание ученой степени кандидата филологических...»

«Сорокин Павел Сергеевич КАРЬЕРА РУКОВОДИТЕЛЕЙ НИЖНЕГО И СРЕДНЕГО ЗВЕНА РОССИЙСКИХ БИЗНЕСОРГАНИЗАЦИЙ КАК СОЦИАЛЬНОЕ ЯВЛЕНИЕ Специальность 22.00.03 – Экономическая социология и демография Диссертация на соискание ученой степени кандидата социологических наук Научный руководитель – доктор философских наук...»

«Кофиади Илья Андреевич ИММУНОГЕНОТИПИРОВАНИЕ И ГЕНОДИАГНОСТИКА В БИОМЕДИЦИНЕ: ФУНДАМЕНТАЛЬНЫЕ И ПРИКЛАДНЫЕ АСПЕКТЫ 03.03.03 – иммунология диссертация на соискание ученой степени доктора биологических наук Москва, 2013 1 ОГЛАВЛЕНИЕ СПИСОК ИСПОЛЬЗОВАННЫХ В РАБОТЕ СОКРАЩЕНИЙ ВВЕДЕНИЕ 1. ОБЗОР ЛИТЕРАТУРЫ 1.1 ИСТОРИЯ РАЗВИТИЯ...»

«КОМАРОВА ЕЛЕНА ВАСИЛЬЕВНА РУССКАЯ РЕЦЕПЦИЯ АЛДЖЕРНОНА ЧАРЛЗА СУИНБЁРНА (ПОСЛЕДНЯЯ ЧЕТВЕРТЬ XIX – ПЕРВАЯ ТРЕТЬ XX В.) 10.01.01 – Русская литература ДИССЕРТАЦИЯ на соискание учёной степени кандидата филологических наук Научный руководитель – доктор филологических наук, профессор Д.Н.Жаткин Саратов – Оглавление Введение.. Глава 1. Восприятие творчества А.-Ч.Суинбёрна русской литературой и литературной критикой...»

«Дидигов Мурат Тамерланович ОРГАНОСОХРАНЯЮЩИЕ ХИРУРГИЧЕСКИЕ ТЕХНОЛОГИИ В ЛЕЧЕНИИ БОЛЬНЫХ ДЕКОМПЕНСИРОВАННЫМ РУБЦОВО-ЯЗВЕННЫМ СТЕНОЗОМ ДВЕНАДЦАТИПЕРСТНОЙ КИШКИ Хирургия – 14.01.17 Диссертация на соискание ученой степени доктора медицинских наук Научный консультант : Заслуженный врач РФ...»

«Тощаков Александр Михайлович ИССЛЕДОВАНИЕ ГАЗОДИНАМИЧЕСКОЙ ЭФФЕКТИВНОСТИ СИСТЕМЫ МЕЖТУРБИННОГО ПЕРЕХОДНОГО КАНАЛА И ДИАГОНАЛЬНОГО СОПЛОВОГО АППАРАТА ПЕРВОЙ СТУПЕНИ ТУРБИНЫ НИЗКОГО ДАВЛЕНИЯ Специальность 05.07.05 – Тепловые, электроракетные двигатели и энергоустановки летательных аппаратов Диссертация на соискание ученой степени кандидата...»

«Искужина Гульназ Расиховна КОНКУРЕНЦИЯ НА РЫНКАХ ПРОМЕЖУТОЧНОЙ ПРОДУКЦИИ Специальность: 08.00.01 – Экономическая теория Диссертация на соискание учёной степени кандидата экономических наук Научный руководитель – доктор экономических наук, профессор Нусратуллин В.К. Уфа – 2014 2 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ.. Глава 1. КОНКУРЕНТНЫЕ...»

«Кикин Андрей Борисович РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ ДЛЯ СТРУКТУРНОКИНЕМАТИЧЕСКОГО ПРОЕКТИРОВАНИЯ РЫЧАЖНЫХ МЕХАНИЗМОВ МАШИН ЛЕГКОЙ ПРОМЫШЛЕННОСТИ Специальность 05.02.13 - Машины, агрегаты и процессы (легкая промышленность) Диссертация на соискание ученой степени доктора технических наук V ;г, 7 Г.^ТЗ ~ \ Научный консультант ^' '^-^•'-^зн(->,1\^/1\. 1 и1'^А, 5 д.т.н. проф. Э.Е. Пейсах „, Наук...»

«Жданов Андрей Геннадьевич ПОВЫШЕНИЕ НАДЕЖНОСТИ АНАЛИЗА ДАННЫХ ВИХРЕТОКОВОГО КОНТРОЛЯ ТЕПЛООБМЕННЫХ ТРУБ ПАРОГЕНЕРАТОРОВ АЭС Специальность 05.11.13 – Приборы и методы контроля природной среды, веществ, материалов и изделий Диссертация на соискание ученой степени кандидата технических наук Москва – 2014 Оглавление Основные обозначения и сокращения Введение АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ НЕРАЗРУШАЮЩЕГО КОНТРОЛЯ ТРУБ 1 ПАРОГЕНЕРАТОРОВ АЭС Структура и принцип действия ПГ 1....»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.