Разработка алгоритмов и программ имитационного моделирования для решения задач системного анализа на слабосвязанных многопроцессорных системах тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Тэй Зар Хтун

• Тэй Зар Хтун
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Тэй Зар Хтун

Введение.

Глава 1. Моделирование — как средство исследования сложных систем.

1.1 Виды моделирования и их сравнительные характеристики.

1.1.1. Статические и динамические модели.

1.1.2. Непрерывные и дискретные модели.

1.1.3. Детерминированные и стохастические модели.

1.1.4. Аналитические и имитационные модели.

1.2 Имитационное моделирование сложных систем. Основные проблемы.

1.2.1 Система, модели и имитационное моделирование.

1.2.2 Общая характеристика имитационного моделирования.

1.2.3 Основные преимущества имитационного моделирования.

1.2.4 Основные проблемы и этапы.

1.3 Параллельное и распределённое имитационное моделирование.

1.3.1 Мотивация перехода к параллельному и распределённому имитационному моделированию.

1.3.2 Параллельные и распределённые вычислительные системы.

1.3.3 Распределённые системы имитационного моделирования.

1.4 Выводы.

Глава 2. Аппаратные средства систем моделирования. Применение параллельных вычислительных систем для задач моделирования.

2.1 Современные классы ВВС.

2.1.1 Симметричные мультипроцессорные системы (SMP).

2.1.2 Системы с неоднородным доступом к памяти (NUMA).

2.1.3 Кластерные системы.

2.2. Примеры параллельных вычислительных систем.

2.2.1 Суперкомпьютеры.

2.2.2. Кластеры.

2.3 Сети для суперкомпьютеров и кластеров.

2.3.1 Ethernet.

2.3.2 Myrinet.

2.3.3 SCI (Scalable Coherent Interconnect).

2.3.4 QsNet.

2.3.5 Infmiband.

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

2.5 Выводы.

Глава 3. Распределение нагрузки в задачах моделирования, реализуемых на слабосвязанных ВВС.

3.1 Управление временем в распределённых системах имитации.

3.2 Последовательное моделирование.

3.3 Распределённое моделирование.

3.3.1 Консервативное управление временем.

3.3.2 Оптимистическое управление временем.

3.3.3 Выбор алгоритма для реализации системы моделирования.

3.4 Методы передачи данных в слабосвязанных ВВС.

3.5 Экспериментальная модель.

3.5.1 Последовательная реализация моделирования.

3.5.2 Методы распределения нагрузки.1.

3.5.3 Архитектурные особенности экспериментального кластера.

3.5.4 Особенности программной реализации метода.

3.6 Выводы.

Глава 4. Исследование программного комплекса для параллельного моделирования.101

4.1 Исследование масштабируемости модели.

4.2 Исследование функциональности модели.

4.2.1 Исследование влияния фрагментации поля на результат моделирования.

4.3 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка алгоритмов и программ имитационного моделирования для решения задач системного анализа на слабосвязанных многопроцессорных системах»

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

Применительно к вычислительной технике это означает, что новые задачи, связанные с большими объемами вычислений, которые постоянно возникают в различных сферах человеческой деятельности, стимулируют разработку все более мощных компьютеров. Но, появившись, такой компьютер позволяет использовать более точные математические модели и ставить еще большие задачи. До недавнего времени исследователи для их решения могли использовать только чрезвычайно дорогие суперкомпьютеры. Сегодня многопроцессорные вычислительные системы, обеспечивающие высокую производительность за счет параллельных вычислений, стали доступны широкому кругу исследователей. Кластерная архитектура на сегодняшний день является наиболее востребованной при создании новых высокопроизводительных вычислительных комплексов: в списке самых мощных суперкомпьютеров ТОР500 более 70% систем являются кластерами.

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

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

В задачах анализа система часто рассматривается как некоторая обобщенная модель. Состояние системы можно описать сложной функцией F, зависящей от множества переменных {Z,.Zn), каждая из которых тоже описывается некоторой функцией, зависящей от времени. = 5 ' >.' ^п ) f\ C^l 5 ' '.' Хт ' О (-^1 ' Х2 ' '.' ' О п ~ fn (-^1' Х2 ' '.' Хт ' О

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

Y = F(Z,\, Z2, ,., Zn) i i

Z, t'7 l

Z ^max tTotal ~tY+ ^max

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

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

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

Цель работы и задачи исследования. Диссертация посвящена разработке алгоритма и программы имитационного моделирования на слабосвязанных многопроцессорных системах.

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

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

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

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

5. Проведение испытаний и анализ эффективности предложенного алгоритма.

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

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

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

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

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

Внедрение результатов. Результаты диссертационной работы используются на кафедре вычислительной техники МИЭТ при проведении лабораторных работ по курсу «Высокопроизводительные вычислительные системы».

На защиту выносятся следующие положения:

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

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

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

4. Параллельная программа моделирования взаимодействия объектов и окружающей среды.

5. Результаты экспериментальных исследований, испытаний и анализ эффективности предложенного алгоритма.

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

1. Двенадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2005», г. Москва, 2005г.

2. Международная школа-конференция по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ, г. Москва, 2005г.

3. Тринадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2006», г. Москва, 2006г.

4. Научная сессия «МИФИ-2007» г. Москва, 2007г.

5. Четырнадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2007», г. Москва, 2007г.

6. Всероссийская межвузовская научно-практическая конференция молодых ученых, специалистов, преподавателей, аспирантов и студентов «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем», г. Москва, 2007г.

Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ.

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Тэй Зар Хтун

4.3 Выводы

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

2. Функциональность модели обеспечивается при любых видах разбиения поля.

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

Заключение

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

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

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

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

4. Разработан программный модуль имитационного моделирования для слабосвязанных многопроцессорных систем и получено свидетельство о его официальной регистрации. Программный модуль реализован в среде mpC Workshop.

5. Эксперименты, проведенные на кластере 25*P-IV 2400, подтвердили практическую эффективность предложенного способа распределения вычислительной нагрузки и функциональность алгоритма имитационного моделирования.

Список литературы диссертационного исследования кандидат технических наук Тэй Зар Хтун, 2008 год

1. Ю. Г. Карпов. Имитационное моделирование систем. Введение в моделирование с Anylogic 5. Текст. / - СПБ.: БХВ-Петербург, 2006.

2. Имитационное моделирование. Электронный ресурс. / Режим доступа: http: // www. inter face .ru/home. asp? art 1 d= 15 5 7 — Загл. с экрана.

3. Аверилл M.Jloy, В. Дэвид Кельтон. Имитационное моделирование. Текст. / Классика CS. 3-е изд. СПБ.: Питер; Киев: Издательская группа BHV, 2004.

4. Ю.Б. Колесов, Ю.Б. Сениченков. Имитационное моделирование сложных динамических систем. Электронный ресурс. / Режим доступа: http://www.exponenta.ru/soft/others/mvs/dssim.asp

5. Имитационное моделирование. Электронный ресурс. / Режим доступа: http://www. interface.ru/home.asp?artld= 1558 - Загл. с экрана.

6. Компьютерное моделирование. Электронный ресурс. / Режим доступа: http://www.mista.ru/23 .htm

7. AnyLogic платформа для моделирования сложных систем. Электронный ресурс. / - Режим доступа: http://sedok.narod.ru/anylogic.html

8. Замятина Е.Б. Современные теории имитационного моделирования. Программа специального курса. Текст. / Пермь: ПТУ, 2007.

9. Richard М. Fujimoto. Distributed Simulation Systems. Текст. / In Proceedings of the 2003 Winter Simulation Conference S. Chick, P. J. Sanchez, D. Ferrin, andD. J. Morrice, eds. pp. 124-134. 2004.

10. Enver Yucesan, YahChuyn Luo, Chun-Hung Chen, Insup Lee. Distributed Web-based Experiments for optimization. Simulation Practice and Theory 9 Текст. / pp.73-90. 2001.

11. Richard A. Meyer, Rajive Bagrodia. Текст. / Parsec User Manual. Release 1.1., UCLA Parallel Computing Laboratory, 1998.

12. А.И.Миков, Е.Б. Замятина, А.Н.Фирсов. Инструментальные средства удалённого параллельного моделирования. В кн. Proceedings of XXII International Conference "Knowledge-Dialogue-Solution". Текст. / FOI-COMMERCE, Sofia, 2006.

13. B.B. Воеводин, Вл.В. Воеводин. Параллельные вычисления. Текст./ Научное издание. СПБ.: БХВ-Петербург, 2004.

14. Основные классы современных параллельных компьютеров, Лаборатория НИВЦ МГУ. Электронный ресурс. / Режим доступа: http://www.parallel.ru/computers/classes.html

15. Э. Таненбаум. Распределенные системы: принципы и парадигмы. Текст. /- СПб: Питер, 2003. 877 с.

16. Gerard Tel. Introduction to Distributed Algorithms. Second edition. Текст. / Cambridge University Press. 2000. 608 c.

17. J.C.Comfort. The Simulation of Master-Slave Event Set Processor. Simulation. Текст. / 42(3): 117-124, March, 1984.

18. Миков А.И. Моделирование вычислительных систем. Текст. / Учебное пособие по спецкурсу.-Пермь, Перм. ун-т., 1982, 96 с.

19. Е.Киндлер. Языки моделирования. Текст. / М.:Энергоатомиздат.,1985.-288с.

20. Шрайбер Т.Дж.Моделирование на GPSS. Текст. / -М.:Маширостроение, 1980. 592 с.

21. S.W. Reichenthal. The Simulation Reference Markup Language (SRML): a foundation for representing BOMs and supporting reuse, Текст. / Boeing, 2002.

22. B.B. Окольнишников. Представление времени в имитационном моделировании. Вычислительные технологии. Текст. / Т. 10, №5, Сибирское отделение РАН, 2005, стр. 57-77

23. Брейер М. Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных. Текст. / М.: Мир, 1979.-464с.

24. Томашевский В., Жданова Е. Имитационное моделирование в среде GPSS. Текст. / М.: Бестселлер, 2003-416 с.

25. Т. Дж. Шрайбер, С. Кокс, Дж. О. Хенриксен, П. Лоренц, Дж. Рейтман, И. Стол. GPSS 40 лет: перспективы развития. (Труды конференции WSC-2001, 9-12 декабря 2001 года). Электронный ресурс. / Режим доступа: www.gpss.ru

26. Якимов И. М., Девятков В. В. Развитие методов и систем имитации в СССР и России. (Казань, ноябрь 2001 год). Электронный ресурс. / -Режим доступа: www.gpss.ru

27. Лычкина Н. Н. Опыт применения GPSS в Государственном Университете Управления. (40-летию GPSS посвящается). (Москва, 2002 год). Электронный ресурс. / Режим доступа: wwvv.gpss.ru

28. Андрианов А.Н., Бычков С.П.,Хорошилов А.И. Программирование на языке Симула-67. Текст. / -М.:Наука, 1985.-370с.

29. Симметричные мультипроцессорные системы. Электронный ресурс. / -Режим доступа: http://rsusul.md.mrmet.ru/tutor/method/ml/page04.html

30. А. В. Богданов, В. В. Корхов, В. В. Мареев, Е. Н. Станкова. Архитектуры и топологии многопроцессорных вычислительных систем. Текст. / Курс лекций. Учебное пособие — М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2004.

31. Программа ASCI. Электронный ресурс. / Режим доступа: http://www.llnl.gov/asci/

32. Система ASCI White. Электронный ресурс. / Режим доступа: http ://www. llnl.gov/asci/platforms/white/

33. Тор500 List June 2008. Электронный ресурс. / - Режим доступа: http://www.top500.org/lists/2008/06

34. Система МВС-1000. Электронный ресурс. / Режим доступа: http://www.jscc.i-u

35. Суперкомпьютеры Тор 50. Электронный ресурс. / Режим доступа: http:// sup ercomputers.ru/index .php

36. Кластер АСЗ Velocity Cluster. Электронный ресурс. / Режим доступа: http://www.tc.cornell.edu

37. Hewlett-Packard Kayak XU PC workstation. Электронный ресурс. / -Режим доступа: http://www.hp.com/desktops/kayak/

38. NT Supercluster. Электронный ресурс. / Режим доступа: http://archive.ncsa.uiuc.edu/SCD/Hardware/NTCluster/

39. HPVM. Электронный ресурс. / Режим доступа: http://www-csag.ucsd.edu/projects/clusters.html

40. Кластера Thunder. Электронный ресурс. / Режим доступа: http://www.llnl.gov/linux/thunder/

41. Myrinet. Электронный ресурс. / Режим доступа: http://www.myri.com/myrinet/index.html

42. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. Текст. / -М.:Альтекс, 2004, 384 с.

43. Дал У., Мюрхауг Б., Нюгорд К. Симула-67. Текст. / М.:Мир, 1969.-100с.

44. Л.Н.Лядова. Имитационное моделирование. Методические указания по курсу «Системное и прикладное программное обеспечение» Текст. / /Перм.ун-т; Сост. Л.Н.Лядова.-Пермь, 2003.-60 с.

45. Клейнен Дж. Статистические методы в имитационном моделировании. Текст. /-М.: Статистика, 1978, вып.1. -204 с.

46. Калашников В.В. Организация моделирования сложных систем.- Текст. / М.:3нание, 1982.- 64 с.

47. С.Немнюгин, О.Стесик. Параллельное программирование для многопроцессорных вычислительных систем. Текст. / -СПб.:БХВ-Петербург, 2002.- 400с.

48. К. Ю. Богачев. Основы параллельного программирования. Текст. / М.: БИНОМ. Лаборатория знаний, 2003.

49. А.В. Баранов., А.О. Лацис., М.Ю. Храмцов. Организация многопользовательского режима работы многопроцессорных вычислительных систем. Текст. / Институт прикладной математики им. М.В. Келдыша, Москва 2000.

50. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. Текст. / -М.: МЦНТО, 2002. с 955.

51. Лунин С.А., Посыпкин М.А. Технологии параллельного программирования. Текст. / М.: ИД «ФОРУМ»: ИНФРА - М, 2008. -208 с. (Высшее образование).