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

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

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

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

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

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

Теоретический анализ
n3 – размерность задачи
p – количество процессоров
tsend – время пересылки одного числа
1D 2D 3D

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

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

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

Выборка данных из памяти
Без учета размерности массивов
C учетом размерности массивов
1D 2D 3D

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

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

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

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