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

Введение.:.

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

2. Алгоритмы синхронизации модельного времени.

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

2.2.Строго синхронные АС.

2.3.Консервативные АС и АС с синхронизацией взаимодействий.

2.4. Оптимистические АС.

3. Математическая модель взаимодействия приложения и АС.

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

3.2.Математическая модель взаимодействия приложения со строго синхронным АС.'.

3.3.Математическая модель взаимодействия приложения с консервативным АС и с АС с синхронизацией взаимодействий.

3.4.Математическая модель взаимодействия приложения с оптимистическим АС.

3.4.1. Классический оптимистический АС.

3.4.2. Оптимистический АС с временным окном.'.

3.4.3. Оптимистический АС с периодическим сохранением состояний.

3.5. Сохранение свойств моделируемого объекта в математической модели.

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

5. Экспериментальное применение метода сравнения эффективности разлйчныхАС.

5.1. Выбор наиболее эффективного АС для системы распределенного имитационного моделирования DYANA.

5.2. Архитектура системы распределенного имитационного моделирования.•

5.3. Результаты моделирования.

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

Отличительной особенностью программ имитационного моделирования является то, что поведение всех процессов должно быть согласовано в едином модельном времени, то есть в том времени, в котором "живет" объект моделирования. Говоря об имитационном моделировании, далее везде будем иметь в виду дискретно-событийное имитационное моделирование[47].

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

Будем рассматривать имитационные модели, которые

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

2. имеют частично упорядоченное в едином модельном времени множество событий [14, 24]: если модельное время события а меньше модельного

•времени события Ь, значит, событие а наступило раньше события Ь, и наоборот; одновременные события, вообще говоря, не упорядочены. Последовательный прогон таких моделей происходит следующим образом [47]. Вначале вычисляются временные метки готовых к обработке событий. Такие события заносятся в список (календарь) событий и упорядочиваются по неубыванию модельного времени. Затем модельное время устанавливается равным метке первого события, а само событие 1 обрабатывается. В результате появляются новые готовые к обработке события. Они заносятся в календарь. Причем события со временем, меньшим текущего появиться не могут. И так до тех пор, пока в календаре есть события.

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

На сегодняшний день разработан ряд алгоритмов синхронизации (в главе 2 дан обзор основных из них). При проектировании распределенной системы имитационного моделирования необходимо выбрать АС, который будет в ней использован. Если в системе реализовано несколько АС, необходимо уметь выбирать наиболее эффективный из них для конкретной модели. Для некоторых АС надо уметь настраивать параметры для заданной модели. Однако, выбор АС для конкретной задачи затруднен, поскольку не существует ни единого метода сравнения АС из всех четырех классов [2], ни способа их формального описания.

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

Структура данной работы такова. В главе 1 формулируется задача • исследования. В главе 2 дан обзор существующих АС. В главе 3 разрабатываются математические модели взаимодействия пар (АС, имитационная модель) для различных АС. В главе 4 приводится метод сравнения АС на основе этих моделей. В главе 5 данный метод применяется для выбора АС для РСИМ DYANA [5].

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

Целью данной работы является разработка метода выбора наиболее эффективного алгоритма синхронизации модельного времени для заданной имитационной модели.

Критерий эффективности: " Лучшим для данной имитационной модели является тот АС, который быстрее других продвигает ее модельное время, то есть такой АС^Млс, для которого Т(АС) = max Т,(АС.). Где Т(АС) - модельное время

ACj<=MAC 1 J имитационной модели в заданный момент физического времени t при алгоритме синхронизации АС.еМлс, Млс - множество анализируемых алгоритмов синхронизации.

Для достижения указанной цели необходимо решить следующие задачи:

1. Построить формальную модель, описывающую взаимодействие • имитационной модели и АС.

2. Определить параметры имитационных моделей, влияющие на эффективность АС.

3. Разработать методику выбора наиболее эффективного АС для заданной имитационной модели.

Далее опишем формально понятие имитационной модели. Во второй главе будет разъяснена суть проблемы синхронизации модельного времени и дан обзор основных АС.

В работах [1, 3] предложен понятийный аппарат для формального описания дискретно-событийной имитационной модели. Приведем ниже его на содержательном уровне.

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

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

Замечание. Обмен сообщениями между процессами происходит всегда через систему моделирования. Отправляя сообщение, процесс имитационной модели передает его соответствующему процессу системы моделирования. При получении сообщения модельный процесс также запрашивает его у системы моделирования. Далее везде говоря о том, что модельный процесс Р1 посылает (получает) сообщение модельному процессу (от модельного процесса) Р2, будем иметь в виду описанный выше механизм.

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

Поведение программы - это множество возможных развитий программы.

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

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

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

Каждый процесс имеет свои локальные часы для отсчета модельного времени. Все события одного процесса упорядочены между собой. События посылки и получения одного сообщения также упорядочены. Одновременные события могут возникать только в разных процессах. Они, вообще говоря, не упорядочены. Таким образом, все события модели частично упорядочены [14, 24].

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

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

• имеет распределенную структуру: узлы, соединенные линиями связи;

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

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

Заключение.

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

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

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

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

1. Р.Л. Смелянский. Модель функционирования распределенных вычислительных систем//Вестник Московского Университета, серия 15, вычислительная математика и кибернетика, 1990 г., №3, с.3-18.

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

3. Ю.П. Казаков. Распределенное имитационное моделирование на 'магистрально-модульных вычислительных системах// Диссертация на соискание ученой степени к.ф.м.н., 1992 г., г. Москва.

4. Райтер Р., Ж. С. Вальран. Распределенное имитационное моделирование дискретно-событийных систем J/M. Мир, ТИИЭР, т.77, N1, янв. 1989, с. 245-262.

5. A.Bakhmurov, A.Kapitonova, R.Smelinasky DYANA: An Evironment for Embedded System Design and Analysis, in Proc. of 32-nd Annual Simulation Symposium, San Diego, California, USA, April 11-15,1999, pp.50-57

6. Venkatesh К., T. Radhakrishnan, and H.F. Li. Discrete event simulation in a distributed system// IEEE COMPSAC, 1986, pp.123-129

7. Baik D., B.P. Zeigler. Performance evaluation of hierarchical distributed simulators// Proc. 1985 Winter Sim. Conf., 1985, pp.8-13

8. Concepcion A.I. A hierarchical computer architecture for distributed simulation//Proc. SCS Dist. Sim. Conf., 1985, pp.8-13

9. Chamberlain R.D., M.A. Franclin. Hierarchical discrete-event simulation on hypercube architecture// IEEE Micro, aug. 1990, pp. 10-20

10. Soule L. Parallel logic simulation: an evaluation of centralized-time and distributed time algorithms// technical report CSL-TR-92-527, Stanford University, С A, June 1992

11. Christopher Т., M. Evens, R.R. Gargeya, T. Leonhard. Structure of a distributed simulation system// IEEE COMPSAC, 1982, pp.548-589.

12. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system// Comm. ACM, vol.21, no 7,1978, pp.558-565.

13. Peacock, J.K., Wong, J.W. and E. Manning, "Distributed Simulation Using a Network of Processors, " Computer Networks, 3, North Holland Pub., 1979, 4456.

14. K.M. Chandy and J. Misra, "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs" IEEE Trans, on Soft. Engi. vol. se-5, no. 5,'September 1979.

15. Wentong Cai, Stephen J. Turner. An algorithm for reducing null messages of the CMB approach in parallel discrete event simulation// university of Exeter, research report №333, August 1995.

16. J.Misra. Distributed discrete-event simulation// ACM Сотр. Surveys, vol.18, nol, pp.39-65, March 1986.

17. K.M. Chandy and R. Sherman. The conditional event approach to distributed simulation// Proc. Of the SCS Simulation Multiconference on Distributed Simulation, March 1989, pp.93-99.

18. K.M. Chandy , J. Misra and L.M.Haas. Distributed deadlock detection//ACM transactions on computer systems, vol.1, №2, pp. 144-156, May 1983. .

19. B. Kroger, R. Ltiling, B. Monien, O. Vornberger. An Improved Algorithm to Detect Communication Deadlocks in Distributed Systems// Proc. Of 4th Int.

20. Workshop on Distributed Algorithms, 1990, Lecture Notes in Computer Science 486, pp.90-101

21. David Jefferson. Virtual time// IEEE, 1983, pp.384-394.

22. Jefferson, David R. and Sowizral, Henry A., Fast Concurrent Simulation Using the Time Warp Mechanism, Part II: Global Control, The Rand Corporation, Santa Monica, California, Technical Report, August 1983.

23. Peter L. Reiher, Frederick Wieland, David Jefferson. Limitation of optimism in the time warp operating system// Winter simulation conference, pp.765-770, SCS, December 1989.

24. J. Fleischmann, Philip A. Wilsey. Comparative analysis of periodic state saving techniques in Time Warp simulation// PADS-1995

25. A.C. Palaniswamy and Philip A. Wilsey. An analytical comparison of periodic chekpointing and incremental state saving// PADS-1993

26. A.C. Palaniswamy. Dynamic parameter adjustment to speedup Time Warp. simulation//Ph. D. Dissertation , university of Cincinnati ,1994.

27. J. Fleischmann, Philip A. Wilsey. Comparative analysis of periodic state saving techniques in Time Warp simulation// PADS-1995 (1995, IEEE)

28. R. Radhakrishnan, T.J. McBrayer, K. Subramani, M. Chetlur, V. Balakrishnan and Philip A. Wilsey. A comparative analysis of various Time Warp algorithms implemented in the WARPED simulation kernel// 1998, IEEE (& ASS-1996) '

29. Luis Barriga, Robert Ronngren and Rassul Ayani. Benchmarking parallel simulation algorithms// Proc. Of the IEEE First ICAAAPP-95, 1995, pp. 611620.

30. А.С. Palaniswamy and Philip A. Wilsey. An analytical comparison of periodic chekpointing and incremental state saving// PADS-1993 (& 1993, IEEE).

31. Отчет ВТК по НИР: "Оценка применения среды DYANA длямоделирования вычислительных комплексов "Багет""//Москва 1997г.

32. Методы и средства для разработки и анализа распределенных встроенных вычислительных систем реального времени//http:// cmc.cs.msu. su/labs/lvk/drtesv.html.

33. Вознесенская Т.В. Исследование интегрированного БВК JIA методом имитационного моделирования// Дипломная работа, 1994 г., г. Москва.

34. Вознесенская Т.В., Факанов А.Е. Распределенное имитационное моделирование МС-моделей на сетях рабочих станций// Методы •математического моделирования, М., ВМиК МГУ, 1997, No. 2.

35. R. Е. Bryant. A switch-level model and simulator for MOS digital systems// IEEE Transactions on Computers, vol.C-33, № 2, pp.160-177, February 1984.

36. Andrew S. Tanenbaum. Modern operating systems. 10.3. Remote procedure call// Prentice-Hall International, Inc. 1992.

37. MPI: Message Passing Interface Standard// Message Passing Interface Forum. June 12, 1995.

38. Vladimir Vlassov, Hallo Ahmed and Lars-Erik Thorelli.mEDA: Parallel programming environment//Proc. Of the 21stEUROMICRO Conf.,Como,• Italy,,September 1995, pp.253-260

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

40. David Nicol, Richard Fujimoto. Parallel simulation today// 1994 r.

41. Fujimoto R. M. Performance measurements of distributed simulation strategies// Distributed Simulation, Simulation Series, vol 19 no 3; The Society for Computer Simulation International; 1988.

42. Jha, V., and R. L. Bagrodia. Transparent Implementation of Conservative Algorithms in Parallel Simulation Languages// Technical Report UCLA-CSD-93007, Computer Science Department, UCLA, Los Angeles, May 1993

43. Ю.П. Казаков, P.Л. Смелянский. Упорядоченность событий и методы синхронизации в распределенном имитационном моделировании// •Системное программирование и модели исследования операций. М.: МГУ.1993 г., с.128-132.