Василенко Анатолий, 621 группа (3-й поток)

Исходный код: [https://github.com/phonexicum/DHP-PE-RA-FDM]

2 ветви:

1. master – mpi+openmp – 2-е задание суперпрактикума

2. mpi-cuda – 3-е задание практикума

Номер варианта: (2-й в списке группы)  2 mod 18 + 18* (2 mod 2) = 2

Первый набор функций, равномерная сетка, максимум норма.

Оглавление:

1. Сборка проекта 1

2. Математическая постановка задания 2

3. Инфограф 3

4. Распределение задач между процессами 5

5. Основные особенности при использовании технологий параллелизации 6

5.1. Использование MPI 6

5.2. Распределение задач между ядрами (OpenMP) 6

5.3. Использование технологии CUDA 6

6. Результаты тестирования на суперкомпьютерах 8

6.1. Численные результаты 8

6.2. Выводы из численных результатов 10

7. Точное решение диф. уравнения 13

8. Графическое изображение функции, погрешности вычислений 13

8.1. Графическое изображение точного аналитического решения и вычисленного решения дифференциального уравнения 13

8.2. Графическое изображение абсолютной погрешности 14

8.3. Графическое изображение относительной погрешности 14

8.4. Графическое изображение скорости сходимости. 15

9. Профилирование и анализ работы с графическим ускорителем 17

1. Сборка проекта

Есть Makefile,

lmount или jmount – подмонтируют в папку mount файловую систему нужного суперкомпьютера.

make upload – скопирует все нужные файлы (все .cpp, .h, .cu) в подмонтированную файловую систему.

На суперкомпьютере тем же make-файлом можно скомпилировать программу

make lcompile или make jcompile или make jcompile-omp

В коде есть некоторое количество комментариев, но ещё там все имена – user-friendly.

Немного об особенностях используемых технологий (особенно cuda) можно прочитать ниже в параграфе «Основные особенности при использовании технологий параллелизации».

1. Математическая постановка задания

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

Можно выписать основные математические формулы с учётом моего варианта задания:

1. Инфограф

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

1. Красным выделены начальные состояния и проверка критерия останова

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

3. Зелёным цветом пронумерован некоторый порядок вычисления операций

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

5. После вычисления коэффициентов \tao и \alpha необходимо их разослать между всеми процессами

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

Картинка ниже показывает граф вычисления 1-й итерации алгоритма:

Нетрудно видеть, что 1-я итерация может быть легко сведена к k-й итерации, если исключить вычисление 4, 5, 6 операций, а в качестве \alpha взять “1”.

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

1. Вычислить скалярное произведение.

2. Вычислить 5-ти точечную аппроксимацию.

3. Разослать коэффициент между всеми процессами.

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

5. Проверить критерий останова.

1. Распределение задач между процессами

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

Разделение происходит следующим образом:

1. Выбирается, разбиение по количеству процессов по вертикали и горизонтали (например, если всего дано 512 процессов, то по горизонтали можно выделить 16, а по вертикали – 32 процесса) (соотношение между процессами не должно превышать 2:1, чтобы результирующая область, сопоставленная с каждым из процессов, имела соотношение не более 2:1)

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

Картинка ниже наглядно показывает пример при распределении 1000 столбцов между соответствующими 32 процессами:

Аналогичное разбиение применяется и по вертикали.

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

1. Основные особенности при использовании технологий параллелизации

1. Использование MPI

В момент инициализации вычислений, все участвующие процессы объединяются в свой отдельный коммуникатор, в рамках которого происходят операции send/recv и broadcast (MPI_Reduce) операции.

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

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

1. Распределение задач между ядрами (OpenMP)

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

Возможность распараллеливания между нитями присутствует в следующих операциях:

1. Вычисление скалярного произведения (aggregate sum)

2. Вычисление 5-ти точечной аппроксимации

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

   2. распределённые между нитями различные независимые участки кода (подготовка данных к отправке посредством MPI другим процессам, и обработка принятых данных)

3. Вычисление критерия останова (нахождение нормы (в моём случае – нахождение максимума из множества чисел))

4. Вычисление функций r, g, p – т.к. каждый раз вычисление каждой ячейки – это независимая операция.

Основные используемые возможности openmp: распараллеливание циклов (#pragma omp for) и разбиение независимых вычислительных задач на секции между несколькими нитями.

Также используется reduce для агрегации результата между нитями, однако на BlueGene работает reduce для сложения, и не работает для находения max (по-видимому не поддерживается компилятором intel – «mpixlcxx_r»), поэтому для вычисления глобального максимума пришлось задействовать критическую секцию.

Согласно заданию – каждый mpi процесс запускался отдельно на 4-х ядреном процессоре и разбивал себя на 3 openmp нити.

1. Использование технологии CUDA

На Ломоносове (с видеокартой Tesla X2070) поддерживаются следующие технологии: MemoryMapping и UAC. (полный перечень ТТХ можно посмотреть в README git-репозитория).

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

Основные типы вычислительных ядер:

1. Независимое вычисление каждой ячейки в матрице (хорошо параллелится между нитями)

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

3. Копирование вертикального столбца данных из матрицы (необходимо для формирования буфера данных для дальнейшей MPI пересылки)

Буфера данных, для MPI приёма-передачи выделяются с использованием MemoryMapping (т.е. без механизма виртуальных функций). Это сделано для того, чтобы видеокарта могла записывать (считывать) туда данные, формируя массив для отправки (приёма) сообщений по MPI. Это позволяет записывать (считывать) их не используя ресурс центрального процессора (это сделает за нас контроллер через PCI шину (т.к. asyncEngine=2)).

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

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

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

Рассчёт размера грида и размера блоков:

1. Размер блока = 512, по 2-м причинам:

   1. На один мультипроцессор влазит ровно 3 блока

   2. Блок максимального размера в 1024 нитей требует регистров в данной реализции больше, чем доступно на видеокарте.

2. Я рассматриваю вычисление значения в каждой точке сетки - как отдельное вычисление, предназначенное для одного из ядер мультипроцессора. Однако количество мультипоцессоров =14, а максимальное количество нитей в 1-м мультипроцессоре =1536, таким образом я могу одновременно запустить максимум 21504 нити, которые будут соответственно обрабатывать столько же узлов сетки. Однако, если я одной видеокартой область, например, 2000x2000, то у меня узлов сетки будет 4 миллиона, что больше, чем 21504, и поэтому я делю одно число на другое и тем самым вычисляю, сколько узлов сетки приходится на 1 нить, чтобы количество нитей после этого уложилось в 21504.

Этим вычислением занимается класс GridDistribute.

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

1. Результаты тестирования на суперкомпьютерах

Программное средство (вместе с benchmark результатами) может быть найдено по адресу:

[https://github.com/phonexicum/DHP-PE-RA-FDM]

(Реализация программы для CUDA находится в ветке «mpi-cuda»)

Через двоеточие в таблице указаны минуты и секунды.

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

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

Вычисление для 1-го mpi процесса проводилось той же программой, что и вычисление для p процессов. Отдельная последовательная реализации отсутствует.

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

Компиляция на BlueGene/P производилась компилятором IBM для версии с openmp, и компилятором g++ для версии без openmp.

1. Численные результаты

BlueGene/P (mpi) (c оптимизациями компилятора «-O3»)

число процессоров	разбиение сетки	время решения (мс)	ускорение	число итераций
1	1000x1000	877509 мс = 14:37	1 раз	1416
2	1000x1000	439510 мс = 7:19	2.00 раза	1416
128	1000x1000	7330 мс = 0:7	119.71 раз	1416
256	1000x1000	3884 мс = 0:3	225.93 раза	1416
512	1000x1000	2100 мс = 0:2	417.86 раза	1416
1	2000x2000	7090953 мс = 118:10	1 раз	---
2	2000x2000	3547949 мс = 59:7	2.00 раз	2828
128	2000x2000	57079 мс = 0:57	124.23 раза	2828
256	2000x2000	28838 мс = 0:28	245.89 раза	2828
512	2000x2000	14626 мс = 0:14	484.82 раза	2828

BlueGene/P (mpi) (без оптимизаций компилятора «-O3»)

число процессоров	разбиение сетки	время решения (мс)	ускорение	число итераций
1	1000x1000	3015294 мс = 50:15	1 раз	1416
2	1000x1000	1297439 мс = 21:37	2.32 раза	1416
128	1000x1000	24258 мс = 0:24	124 разa	1416
256	1000x1000	12416 мс = 0:12	243 разa	1416
512	1000x1000	6495 мс = 0:6	464 разa	1416
1	2000x2000	превышен лимит 2-х часов	---	---
2	2000x2000	превышен лимит 2-х часов	---	---
128	2000x2000	190366 мс = 3:10	1 раз	2828
256	2000x2000	95653 мс = 1:35	1.99 раза	2828
512	2000x2000	48431 мс = 0:48	3.93 раза	2828

BlueGene/P (mpi + openmp (режим openmp использовался с 3-мя нитями на 4-х ядерном процессоре))