Сравнение различных способов декомпозиции сеточной области при численном решении уравнения переноса Е.А. Данилкин, А.В. Старченко Томский государственный университет

2 Цель работы Целью данной работы было достижение максимальной эффективности при распараллеливании данного класса задач. Две парадигмы параллельного программирования: - распараллеливание по физическим процессам - распараллеливание по данным

3 i k j i k j 1 ПЭ 2 ПЭ 3 ПЭ i k j 1 ПЭ 2 ПЭ 4 ПЭ 7 ПЭ 5 ПЭ 8 ПЭ 9 ПЭ 3 ПЭ 6 ПЭ i,j,k i+1,j,k i-1,j,k i,j+1,k i,j-1,k i,j,k+1 i,j,k-1 i,j,k+2 i,j,k-2 i,j-2,k i,j+2,k i-2,j,k i+2,j,k Фиктивные ячейки 1D-декомпозиция ленточная схема 2D-декомпозиция блочное разбиение 3D-декомпозиция Виды декомпозиции Наиболее общим подходом равномерного распределения вычислительной загрузки между вычислительными узлами при решении сеточных уравнений является распределение вычислительных областей на подобласти. Так называемый принцип геометрической декомпозиции.

4 Математическая постановка Требуется решить трехмерное уравнение переноса в единичном кубе с граничными условиями второго рода и заданными начальными условиями Функции u, v, w, Г>0 и S - определены в рассматриваемой области.

5 Аппроксимация PEW T B N S b e w n s t Аппроксимация дифференциальной задачи осуществляется на основе метода конечного объема. Аппроксимация конвективных членов уравнений переноса выполняется с использованием противопотоковой схемы. Для расчета применялась явная схема, поэтому результатом приближенного интегрирования по одному конечному объему является готовая для вычислений формула:

6 Данные распределены, следующий этап построения параллельной программы – это планирование коммуникаций. В силу используемого шаблона схемы, для вычисления очередного приближения в приграничных узлах подобласти необходимо знать значения с соседнего процессора. Это процедура хорошо известна и поэтому долее детально остановимся на результатах сравнения различных способов декомпозиции. Y Z 0 Планирование коммуникаций

7 Теоретический анализ Число процессов d декомпозиция d декомпозиция d декомпозиция n 3 – размерность задачи p – количество процессоров t send – время пересылки одного числа 1D 2D 3D

8 Вычислительный кластер имеет 283 вычислительных узла, один узел включает два двухъядерных процессора Intel 5150, 2,66ГГц, 4 Гб оперативной памяти, 80 Гб жесткий диск, дополнительно 10 Тб быстрой памяти, сеть - Infiniband

9 Распараллеливание Основное внимание уделялось сравнению времени пересылок и времени вычислений при различных способах декомпозиции. Несмотря на теоретический анализ, практика показала, что лучших результатов можно достичь, используя 2D декомпозицию. a)b)

10 Для оценки состоятельности первого допущения был рассмотрен случай, когда программа запускалась в однопроцессорном варианте, и при этом имитировались различные способы геометрической декомпозиции данных при одинаковом объеме вычислений, выполняемом каждым процессором. Для объяснения полученных результатов необходимо обратить внимание на допущения, которые были сделаны при предварительном теоретическом анализе поставленной задачи. - Во-первых, предполагалось, что независимо от способа распределения данных на одном процессорном элементе выполняется одинаковый объем вычислительной работы, который должен приводить к идентичным временным затратам. - Во-вторых, принималось, что время, затраченное на межпроцессорную пересылку любой последовательности одинакового количества данных, не зависит от способа их выборки из оперативной памяти. Do k=1,n a Do j=1,n a Do i=1,n a 3 1 1

11 Выборка данных из памяти p1d2d3d 89,38,110,4 243,12,63,7 601,21,01,6 Без учета размерности массивов C учетом размерности массивов p1d2d3d 88,87,57,3 243,02,5 601,20,91,0 1D 2D 3D

12 Для оценки реализуемости второго допущения (Tcom = tsend·N2 *k(p)) был рассмотрен тест, в котором измерялось время MPI-пересылки различных сечений массива с размерностью 3. Заметим, что решение этой задачи (пересылки, скажем, i-j, i-k, j-k – сечений массива, элементы которого имеют индексы i, j, k) в стандарте MPI может осуществятся различными способами в зависимости от того, какие сечения массивов рассматриваются. Количество элементов в массиве\ сечение i-ji-kj-k ,001890,001920, ,004020,005560, ,016010,021510,03563 Выборка данных из памяти buf

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

14 Тестовая задача, Lyn (1995). Тестовая задача, Lyn (1995). NAKAYAMA

15 Сравнение результатов.

16

17 Спасибо за внимание.