Имитационное моделирование управляющих и вычислительных процессов в высокопроизводительных вычислительных системах Винс Дмитрий Владимирович

Содержание к диссертации

Введение

ГЛАВА 1. Функционирования кластерных и мультикластерных вычислительных систем и средства их моделирования (обзор) 13

1.1 Понятие о вычислительных системах 13

1.1.1 Модель коллектива вычислителей 13

1.1.2 Классификация архитектур вычислительных систем 16

1.2 Принципы функционирования кластерных и мультикластерных ВС ..19

1.2.1 Принципы построения кластерных ВС 19

1.2.2. Мультикластерные ВС и GRID-системы 20

1.2.3. Разработка параллельных программ для кластерных ВС

1.2.4 Классификация решаемых задач 21

1.2.5 Основные режимы функционирования кластерных и мультикластерных ВС 24

1.2.6 Организация управления ресурсами в кластерных вычислительных системах 26

1.3 Формирование расписания обработки потока заданий, поступающих на кластерные и мультикластерные ВС 29

1.3.1 Задача формирования расписаний 29

1.3.2 Обзор методов и алгоритмов планирования расписаний 31

1.3.3. Обзор существующих средств планирования 36

1.4 Имитационное моделирование высокопроизводительных вычислительных систем 36

1.4.1 Возможности имитационного моделирования 36

1.4.2 Принципы параллельного и распределенного имитационного моделирования 39 1.5 Агентно-ориентированный подход к моделированию вычислительных

систем 41

1.5.1 Понятие агентного моделирования и мультиагентных систем 41

1.5.2 Современные системы и платформы мультиагентного моделирования 46

1.5.3 Мультиагентна система моделирования AGNES 49

Выводы по главе 52

ГЛАВА 2. Моделирование системы управления потоком зададля для распределенных кластерных вычислительных систем 54

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

2.1.1 Общая схема модели функционирования распределенной кластерной ВС в режиме обработки потока задач 54

2.1.2 Виды и функции агентов в модели системы оперативного управления ВП ВС 56

2.1.3 Виды и функции доменов вычислительных узлов 56

2.2 Моделирование управляющих процессов с помощью мультиагентной модели 58

2.2.1 Формирование очередей задач и составление расписаний выполнения параллельных заданий 58

2.2.2 Осуществление динамической балансировки ресурсов 59

2.2.3 Обеспечение отказоустойчивости 61

2.2.4 Обеспечение энергоэффективности функционирования системы 62

2.3 Описание Сибирского суперкомпьютерного центра коллективного пользования СО РАН 64

2.3.1 Архитектура Сибирского суперкомпьютерного цента коллективного пользования СО РАН 64

2.3.2 Программное обеспечение сибирского суперкомпьютерного цента коллективного пользования СО РАН 66

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

Выводы по главе 70

ГЛАВА 3. Имитационное моделирование вычислительных процессов 72

3.1 Описание метода исследования вычислительных процессов 72

3.2 Исследование возможности масштабирования распределенного статистического моделирования. Метод Монте-Карло.. 76

3.3 Исследование возможности масштабирования численного моделирования. Сеточные методы.

3.3.1 Общая схема исследования сеточных методов численного моделирования 84

3.3.2 Исследование алгоритма численного моделирования 3D сейсмических полей в изотропной неоднородной упругой среде 88

3.3.3 Исследование алгоритмов численного моделирования динамики трехмерных газовых объектов в самосогласованном гравитационном поле 93

3.3.4 Исследование алгоритма численного моделирования взаимодействия электронного пучка с плазмой 97

Выводы по главе 101

Заключение 103

Список литературы

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

Введение к работе

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

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

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

Мощности и возможности вычислительных систем также с каждым годам возрастают. По расчетам, приведенным Д. Донгарра¹, производительность в экзафлопс будет достигнута к 2018 – 2020 году. Суперкомпьютер к тому времени сможет обслуживать одновременно 1 млрд потоков вычисления. Количество ядер у него будет 10-100 млн.

Создание экзафлопсных суперкомпьютеров идет по двум направлениям: эволюционному и инновационному. Первое предполагает постепенное улучшение существующих суперкомпьютеров на легких и тяжелых суперскалярных процессорных ядрах. Подход с тяжелыми ядрами более доступен и популярен в сочетании с применением графических сопроцессоров (GPU), сопроцессоров типа Xeon Phi и ускорителей на программируемых логических матрицах (FPGA).

Задача инновационных проектов — поиск новых решений и технологий для создания эффективных и отказоустойчивых суперкомпьютеров с реальной экзафлопсной производительностью на широком круге задач. По ряду причин такие технологии называют экзамасштабными, и одно из их главных свойств — обеспечение удельной энергетической эффективности в 50 GFLOPS/Вт, что в десятки раз ниже, чем у нынешних суперкомпьютеров².

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

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

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

¹ HPC Challenge: Design, History, and Implementation Highlights, J. Dongarra and P. Luszczek, Ed. Jeffrey S.
Vetter, Contemporary High Performance Computing: From Petascale Toward Exascale, Taylor and Francis, Boca
Raton, CRC Computational Science Series, 2013

² В.С.Горбунов, Л.К.Эйсымонт, А.В.Речинский, В.С.Заборовский, П.В.Забеднов. Суперкомьютеры для
промышленности – вопросы тестирования, анализа и разработки. Материалы 2-й Всесоюзной конференции
“Суперкомпьютерные технологии” (СКТ-2012), стр.360-364.

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

Задачи исследования

1. Анализ и разработка подходов к имитационному моделированию организации функционирования ВС в мультипрограммных режимах.

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

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

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

Методы исследования

5. Имитационное моделирование с использованием системы мультиагентного моделирования AGNES³ процесса оперативного управления ВС для исследования управляющих алгоритмов и процесса выполнения параллельных программ на ВС для исследования вычислительных алгоритмов.

6. Статистическая обработка данных реальной работы алгоритмов и модельного эксперимента с использованием электронных таблиц Microsoft Excel.

Научная новизна работы заключается в том, что в ней впервые

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

8. Экспериментально обоснован набор алгоритмов управления, позволяющий уменьшить время ожидания в очереди до 10%.

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

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

Личный вклад автора состоит

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

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

13. В совместных публикациях конфликта интересов нет.

Научное и практическое значение работы

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

³ Podkorytov, D., Rodionov, A., Choo, H.: Agent-based simulation system AGNES for networks modeling: review and researching. Proc. of the 6th Int. Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2012), ISBN 978-1-4503-1172-4, Paper 115, 4 pages, ACM (2012).

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

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

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

Результаты диссертации нашли применение в работах по развитию ЦКП ССКЦ СО РАН.

Результаты исследований были применены при выполнении Федеральной целевой
программы «Исследования и разработки по приоритетным направлениям развития
научно-технологического комплекса России на 2007 – 2013 гг.» (ГК № 07.514.11.4016
«Исследования и разработка методов имитационного моделирования функционирования
гибридных экзафлопсных вычислительных систем»). Исследования проводились в

рамках грантов Российского фонда фундаментальных исследований № 13-07-00589, 16-07-00434.

Внедрение результатов диссертационного исследования подтверждается

соответствующими актами.

Научные положения, выносимые на защиту, соответствуют пунктам 2, 4, 6 паспорта специальности 05.13.15 – «Вычислительные машины, комплексы и компьютерные сети».

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

15. Экспериментально обоснован набор управляющих алгоритмов, который на реальной статистике ЦКП ССКЦ СО РАН показал лучшие параметры распределения ресурсов, возможности корректной обработки отказов и возможности обеспечения энергоэффективности.

16. Создан метод исследования эффективности параллельных алгоритмов и программ при их исполнении на суперкомпьютерах высокой производительности. Метод основывается на создании для каждого типа вычислительного алгоритма мультиагентной модели его исполнения на разном числе вычислительных узлов ВС.

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

Степень достоверности научных положений достигается

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

19. Объемом информации получаемой в модельном эксперименте, достаточной для корректной статистической обработки.

3. Хорошим качественным согласием результатов модельного эксперимента с соответствующими данными реальной статистики ЦКП ССКЦ СО РАН и данными реального исполнения исследуемых вычислительных алгоритмов.

4. Экспертизами работы, прошедшими при получении грантов.

Апробация

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

Международная конференция "Суперкомпьютерные дни в России" (RuSCDays 2015), 28-29 сентября 2015, Москва, Россия.

4th International Young Scientists Conference. (YSC -2015). June 25 - July 03 2015. Athens, Greece.

15th IEEE/ACM International Symposium Cluster, Cloud and Grid Computing (CCGrid). May 4-7 2015. Shenzhen, China.

VII Международная научная конференция Параллельные вычислительные технологии (ПаВТ), 1-5 апреля 2013, Челябинск, Россия.

«Научный сервис в сети интернет» Международная суперкомпьютерная конференция и конференции молодых ученых. 17- 22 сентября 2012. Новороссийск (Абрау-Дюрсо), Россия.

14th IEEE International Conference on High Performance Computing and communications (HPCC-2012), June 25-27, 2012, Liverpool, UK.

VI Международная конференция «Параллельные вычисления и задачи управления» (PACO’2012). 24 - 26 октября 2012 г. Москва, Россия.

Национальный Суперкомпьютерный Форум (НСКФ-2015). 24-27 ноября 2015 года. Переславль-Залесский, Россия.

8-я Всероссийская Мультиконференция по проблемам управления (МКПУ-2015). 28 сентября - 3 октября 2015. Геленджик, Россия.

X Всероссийская школа-конференция молодых ученых "Управление большими системами" 5-7 июня 2013г., Уфа, Россия, работа награждена дипломом третьей степени.

Публикации. Автором по теме диссертации опубликовано 14 работ. Основные результаты диссертации полностью опубликованы в 6 статьях рецензируемых изданий, рекомендованных ВАК, 3 статьи в других рецензируемых журналах, 5 статей - в трудах конференций.

Структура и объем диссертации Диссертация состоит из введения, трех глав, заключения, списка литературы из 159 наименований. Общий объем диссертации - 137 страниц. Работа содержит 28 рисунков и 2 таблицы.

Принципы функционирования кластерных и мультикластерных ВС

Модель вычислителя сформулирована в [Евреинов, 19621] и описана в [Евреинов и др., 1978]. Для нее характерны последовательное выполнение операций, фиксированная структура и неоднородность связей и функциональных элементов. Использование этой модели для создания высокопроизводительных вычислительных средств ограничено теоретическими и техническими пределами скорости выполнения операций (возможности элементной базы и фундаментальные физические законы) [Хорошевский, 2008].

Модель коллектива вычислителей сформулирована в работах [Евреинов и др., 1978; Дмитриев и др., 1982; Хорошевский, 2008; Корнеев, 1985, 2001] и позволяет описать структуру связей между элементами системы. Под коллективом вычислителей будем понимать совокупность программно-аппаратных вычислителей, объединенных в вычислительную систему.

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

Специальные виды организации вычислителей позволяют увеличить пропускную способность и уменьшить задержки при обмене информацией. Выделяют две важные характеристики графа, соответствующего структуре связей между вычислителями: порядок вершины неориентированного графа равен количеству ребер, инцидентных ему; диаметром графа называется максимальное число вершин на пути между двумя произвольными вершинами графа. Структуры, соответствующие графам с меньшим диаметром, обеспечивают меньшие задержки при передаче данных, так как меньшее число вычислителей участвуют в передаче данных между источником и получателем. Наименьшим диаметром обладает полный граф. Однако при достаточно большом числе вычислителей в системе (современные параллельные системы включают 100 - 106 вычислителей) реализовать полный граф при помощи аппаратных средств невозможно вследствие большого числа связей каждого вычислителя с другими, равного числу вычислителей в системе. Возникает задача минимизации диаметра графа, описывающего структуру связей, при сохранении небольшого порядка вершин. Оптимальными в этом смысле графами являются графы Мура [Hoffman, 1960].

Частными случаями графа Мура являются, например, граф Петерсена и граф Хоффмана-Синглтона. Примеры использования алгоритмов глобальной оптимизации для поиска оптимальной конфигурации связей вычислителей в параллельных системах можно найти в работах [Maekawa, 1981; Kotsis, 1993]. При разработке вычислительных систем используются следующие виды структур связей между вычислителями: - нульмерные структуры, в которых взаимодействие между вычислителями осуществляется посредством общей шины (например, кластеры рабочих станций, объединенных с помощью Ethernet); - решетки, одномерные – линейные, двумерные и большей размерности; - тороидные структуры различной размерности (структура связей BlueGene/L является трехмерным тором); - гиперкубические структуры, обладающие достаточно простой структурой и достаточно небольшим диаметром (порядка логарифма от числа вычислителей) при большом количестве вычислителей в системе; - иерархические структуры, например, деревья, используются при построении распределенных и GRID-систем. Алгоритм A работы коллектива вычислителей S обеспечивает согласованную работу вычислителей и связей между ними в процессе решения общей задачи. Алгоритм может быть формально представлен в виде A = A(P(D)) , где D - исходные данные для параллельной программы P. В модели коллектива вычислителей обычно полагается, что каждый вычислитель выполняет одну и ту же программу, но разные ее ветви в зависимости от исходных данных. Поэтому массив исходных данных представим в виде объединения индивидуальных массивов, данных Di для каждого вычислителя N D=Di i=1 Параллельная программа представляется как совокупность ветвей Pi, выполняемых разными вычислителями: NN . P= Pi , Pi = i=1 i=1 Данный подход к организации параллельных вычислений называется параллелизм по задачам (MIMD, согласно классификации Флинна) – вычислители выполняют разные программы на различных входных данных.

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

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

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

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

В отличие от одиночного вычислителя, коллектив вычислителей обладает теоретически неограниченной производительностью, обусловленной отсутствием ограничений на увеличение их числа. Кроме того, построенная на модели коллектива вычислительная система способна обладать заданной надежностью и живучестью [Евреинов и др., 1978; Додонов и др., 1990; Хорошевский, 1983, 1987, 2008 2011], т.е. возможностью функционировать при отказах ее элементов, а также допускает простоту наращивания производительности.

Общая схема модели функционирования распределенной кластерной ВС в режиме обработки потока задач

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

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

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

Рассмотрим некоторые платформы мультагентного моделирования: The REcursive Porous Agent Simulation Toolkit (Repast) [North et al., 2006] – это ведущий открытый и свободный источник библиотек для крупномасштабного агентного моделирования. Repast поддерживает разработку чрезвычайно гибких моделей агентов и используется в моделировании социальных процессов. Пользователь строит свою модель, включая в свои программы компоненты из библиотеки Repast или используя визуальный Repast для среды Python Scripting. Существует три версии Repast, названных Repast for Python (Repast Py), Repast for Java (Repast J) и Repast for the Microsoft.NET framework (Repast .NET).

Repast имеет сложный встроенный планировщик, который поддерживает дискретно-событийное моделирование. Repast позволяет использовать большой набор коммуникационных механизмов с разнообразными топологиями взаимодействия, включает полный набор утилит для хранения и отображения состояния агентов. В систему также включены утилиты для автоматической интеграции как с коммерческими, так и свободно доступными географическими информационными системами (ГИС). Интеграция с коммерческими ГИС включает в себя автоматическое подключение к широко используемым географическим информационным системам, таким как ESRI и ArcGIS. Более того, так как Repast базируется на языке Java, платформе Microsoft .NET и на скриптах Python, он полностью объектно-ориентирован.

Swarm (стая, рой) [Minar et al., 1996] был первой средой разработки АМ приложений, впервые запущен в 1994 году Chris Langton at the Santa Fe Institute. Swarm – это открытый и бесплатный набор библиотек с открытым кодом и в настоящее время поддерживается Swarm Development Group (SDG). Swarm стремиться создать распределенную платформу для моделирования АМ и содействовать разработке широкого круга моделей. Пользователь создает модели включением компонент из библиотек Swarm в свои программы. Система моделирования Swarm состоит из двух основных компонентов. Компоненты ядра запускают код моделирования, написанный на языке общего назначения Objective-C, Tcl/Tk, и Java. В отличие от Repast, Swarm-планировщик поддерживает только продвижение времени через фиксированные промежутки. Swarm поддерживает полный набор коммуникационных механизмов и может моделировать все основные топологии. Swarm включает хороший набор утилит для хранения и отображения состояния агентов. Так как Swarm базируется на комбинации Java и Objective-C, то он объектно-ориентирован. Но эта смесь языков является причиной некоторых трудностей с интеграцией в некоторые крупномасштабные среды разработки, например, Eclipse.

NetLogo [Kornhauser et al., 2012] это другая кросс платформенная мультиагентная среда для моделирования, которая широко используется и поддерживается. Первоначально основанная на системе StarLogo, NetLogo приспосабливает агентные системы, состоящие из комбинации живых и программных агентов-участников.

AniLogic [Карпов, 2005] – это отечественная разработка. В настоящее время она нашла широкое применение среди отечественных и зарубежных пользователей. Продукт получил название AnyLogic, потому что он поддерживал все три известных метода моделирования: - системная динамика; - дискретно-событийное (процессное) моделирование; - агентное моделирование, а также любую комбинацию этих подходов в пределах одной модели. Первой версии был присвоен индекс 4 — Anylogic 4.0, так как нумерация продолжила историю версий предыдущей разработки — COVERS 3.0. Огромный шаг вперёд был сделан в 2003 году, когда был выпущен AnyLogic 5, ориентированный на бизнес-моделирование. С помощью AnyLogic стало возможным разрабатывать модели в областях производства, логистики и цепочки поставок, рынка и конкуренции, бизнес-процессов и сферы обслуживания, здравоохранения и фармацевтики, управления активами и

Программное обеспечение сибирского суперкомпьютерного цента коллективного пользования СО РАН

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

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

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

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

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

Для исследования масштабируемости такого класса алгоритмов будем исходить из следующих предположений. 1. M – общее число моделируемых ядер. 2. N – количество ячеек/частиц в подобласти на одном вычислительном узле. 3. Для каждого этапа вычислений заданы формулы расчета времени исполнения. 4. Время исполнения коммуникаций будем считать линейной функцией от числа передаваемых элементов с учетом задержек при передаче данных. 5. Достижение требуемого уровня точности достигается при совершении каждой нитью-вычислителем определенного числа итераций вычислений L. 6. Общее время выполнения алгоритма численного моделирования по методу сеток – TL(M). 7. При моделировании исследуются величина относительного ускорения от распараллеливания, определяемая следующим образом: TL (Mmin ) SL (M) = TL (M) где Mmin - наименьшее число ядер, использованных при расчетах. Для имитации выполнения алгоритма, численного моделирования методом сеток создается класс функциональных агентов Grid. Агенты этого класса производят итерации циклов вычислений, до достижения требуемого числа L.

В зависимости от геометрической декомпозиции расчетной области у каждого агента может быть разное число «соседей», таким образом логические схемы обмена граничными значениями между агентами этого класса могут быть абсолютно любыми («линейка», «матрица», «3D куб», «тор»).

В зависимости от исследуемого алгоритма агенты обмениваются сообщениями в синхронном или асинхронном режиме. Выполнение синхронизации организовано следующим образом – после отправки сообщения «соседу» агент ожидает сообщения подтверждения и только после этого продолжает работу (для продолжения вычислений важно чтобы все агенты получили граничные значения от соседей). В асинхронном режиме агент не приостанавливает вычисления (для продолжения вычислений одним агентом важно чтобы агент получил граничные значения от соседей). 3.3.2 Исследование алгоритма численного моделирования 3D сейсмических полей в изотропной неоднородной упругой среде

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

Численное моделирование 2D/3D сейсмических полей для сложнопостроенных моделей сред проводится на основе решения уравнений теорий упругости [Караваев и др., 2013; Глинский и др., 2010]. Такого вида задачи характеризуются большим объемом вычислений, поскольку область моделирования представляется достаточно подробно для проведения 3D моделирования. Схема параллельной реализации вычислений для алгоритма численного моделирования представлена на рис.3.11.

Общая схема исследования сеточных методов численного моделирования

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

Алгоритм, реализующий метод крупных частиц, обладает высокой степенью внутреннего параллелизма, так как имеет место только локальное взаимодействие между соседними элементами, и для вычисления потенциала в слое сетки требуются значения не более чем в двух соседних слоях. Схема взаимодействия вычислительных процессов для данной задачи представлена на рисунке TL N3 , то есть для каждого типа вычислителя мы знаем оптимальное время вычислений одной ячейки на обоих этапах численного метода. Общее время вычисления подобласти пропорционально числу узлов расчетной сетки. Время выполнения коммуникаций Тсотт =A + TcxN2 , где Л - задержка при передаче данных, Tс - среднее время передачи одного элемента данных. Коммуникации организованны в синхронном режиме. Общее число ячеек на один вычислительный узел iV3 = 2563 - 16х106.

Для имитации выполнения алгоритма численного моделирования столкновения галактик реализованы классы функциональных агентов AstroGrid — агенты-вычислители, имитирующий расчет сеточных методов на одном вычислительном узле. Каждый агент, на первом шаге рассчитывает подобласти на эйлеровом этапе, затем передает граничные ячейки «соседям». Получив подтверждение, что все агенты получили данные, он начинает вычислять подобласть на лагранжевом этапе. Затем также синхронно происходит обмен граничными ячейками. Схема логических связей для данной модели типа «линейка» представлена на рисунке 3.22.

Исходные данные для имитационного моделирования получены на кластере НКС-30Т ЦКП ССКЦ СО РАН и МСЦ РАН, произведена калибровка параметров модели и моделирование вычислений данного алгоритма для большого количества ядер M (на узлах с Intel Xeon E5-2697 до 5632 узла, 67 584 ядра; на узлах с GPU Nvidia Kepler до 1024 узлов, 1 048 576 ядер; на узлах с Intel Xeon Phi 7110 до 4096 узлов, 245 760-983 040 ядер) [Kulikov, Weins et al., 2015]. Результаты моделирования представлены на рисунке 3.18.

По рисунку 3.18 можно сделать следующие выводы: время выполнения растет несущественно (около 20%) для 5120 вычислительных узлов; лучшую масштабируемость показали вычислительные узлы с ускорителями Nvidia Kepler K40 и Intel Xeon Phi (native mode).

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

Программа распараллеливается методом декомпозиции. Расчетная область делится на равные части (подобласти) по направлению, перпендикулярному направлению пучка (рис 3.19). Каждая подобласть назначается группе процессов (в случае многоядерных систем отдельное ядро будем считать процессом). Кроме того, частицы каждой подобласти распределены равномерно между процессами группы без учета их координат [Вшивков и др., 2012].

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