Масштабирование дискретно-событийных имитационных моделей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Савенков, Константин Олегович

• Савенков, Константин Олегович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Савенков, Константин Олегович

Введение

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

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

Введение диссертации (часть автореферата) на тему «Масштабирование дискретно-событийных имитационных моделей»

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

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

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

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

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

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

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

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

РВС.15

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

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

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

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

2.6 Выводы.43

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

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

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

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

3.4 Выводы .73

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

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

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

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

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

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

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

4.7 Выводы.96

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

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

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

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

5.4 Выводы.103

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

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

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

Литература 106

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Савенков, Константин Олегович

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Савенков, Константин Олегович, 2007 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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