On the Question of 3d Decomposition Efficiency for the Numerical Solution of Transport Equation with the Use of Multiprocessor Computer with Distributed Memory .pdf Математическое моделирование и численный эксперимент широко распространены в научных и прикладных исследованиях. В последнее время появились и широко используются разнообразные программные продукты для математического моделирования, например для изучения процессов гидродинамики и тепломассообмена (FLUENT, ANSYS CFX, OpenFOAM). В институтах и университетах для подобных целей разрабатываются свои математические модели и вычислительные приложения, но уже более узконаправленные. При этом основная идея математического моделирования - это описание исследуемого процесса с помощью системы дифференциальных уравнений. От модели к модели меняются лишь коэффициенты в уравнениях и способы их аппроксимации, при этом сами уравнения остаются неизменными.Ни одна математическая модель гидро- или газодинамики не обходится без уравнения переноса, будь это перенос примеси или уравнение движения для одной из компонент скорости. Поэтому в данной статье сравнение различных способов декомпозиции будет осуществляться на примере уравнения переноса.Задачи математического моделирования требуют большого количества компьютерного времени. Одним из способов преодоления этой проблемы является использование многопроцессорных вычислительных систем (МВС). В данной работе будут рассматриваться МВС с распределенной памятью, так как в настоящее время большинство супер-ЭВМ, которыми мы располагаем, построены именно по такому принципу. Наиболее общим подходом равномерного распределения вычислительной нагрузки между узлами МВС при решении сеточных уравнений является разделение вычислительной области на подобласти, количество которых совпадает с числом используемых процессов, т.е. использование принципа геометрической декомпозиции [1]. Причем самым простым способом решения этих разделенных на подобласти конечно-разностных задач является применение явных разностных схем, которые и будут рассматриваться здесь для численного решения поставленной задачи. Такие схемы отличаются относительно небольшим шагом интегрирования по времени для нестационарных задач, ограничение на который накладывает условие устойчивости.Математическая постановкаТребуется решить трехмерное уравнение переноса в единичном кубе (x, y, z) е (0,1) х (0,1) х (0,1):с граничными условиями второго рода и заданными начальными условиямидФдхдФдх x=10; дФФуду= 0;y=00; дфФzdz^= 0;'.=i■ 0; Ф|= 0.t=00;(2)Функции u, v, w, Г > 0 и S определены в рассматриваемой области.Аппроксимация и численное решениеАппроксимация дифференциальной задачи осуществляется на основе метода конечного объема [2]. Основная идея этого метода заключается в разбиении расчетной области на непересекающиеся, граничащие друг с другом конечные объемы так, чтобы один узел расчетной сетки содержался только в своем конечном объеме. Разбив таким образом расчетную область, интегрируем уравнение по каждому конечному объему. При вычислении интегралов используются кусочно-полиномиальные приближения для зависимых величин. Аппроксимация конвективных членов уравнений переноса выполняется с использованием противопото-ковой схемы. Для расчета применялась явная схема, поэтому результатом приближенного интегрирования по одному конечному объему является готовая для вычислений формула:aP°®"j,k = т. j,k ф" j,k + aei, j,k ф"+и ,k + ani, j,k Ф" j+u + ati,j ,k ФЪ ,k+i +(3)+ awi,j,k фГ-1, j,k + asi,j,k 3>tj-i,k + asi,j,k 3>tj,k-i + bi,j,k ■Полученная разностная схема имеет первый порядок аппроксимации по времени и по пространству и является условно устойчивой и монотонной.РаспараллеливаниеВ рассматриваемом примере возможны три различных способа разделения значений сеточной функции по вычислительным узлам - одномерная, или ленточная, схема, двухмерное, или блочное, разбиение или трехмерное разбиение узлов вычислительной сетки.Каждому процессорному элементу вместе с выделенной сеточной подобластью распределяются все значения сеточной функции из этой подобласти, в томчисле и Ф"j k .После этапа декомпозиции, когда производится разделение данных на блоки для построения параллельного алгоритма, переходим к этапу установления связей между блоками, вычисления в которых будут выполняться параллельно, - планированию коммуникаций. Из-за используемого шаблона явной разностной схемы для вычисления очередного приближения в приграничных узлах каждой подобласти необходимо знать значения сеточной функции с соседнего граничащего процессорного элемента. Для этого на каждом вычислительном узле создаются фиктивные ячейки для хранения данных с соседнего вычислительного узла и организуются пересылки этих граничных значений, необходимых для обеспечения однородности вычислений по явным формулам (3) [3] (рис. 1). Пересылка данных осуществляется с использованием процедур библиотеки MPI [4].1 D-декомпозиция1РиктапныеОбратимся к предварительному теоретическому анализу эффективности различных способов декомпозиции расчетной области для рассматриваемого случая. Будем оценивать время работы параллельной программы как время работы последовательной программы Tcalc, деленное на количество используемых процессоров, плюс время пересылок: Tp = Tcalc/p + Tcom. Время пересылок для различных способов декомпозиции можно приблизительно выразить через количество пересылаемых данных:T 1Dcom = tSend'N2x2; T2Dcom = WN^1'2; T^om = WN^/p23; (4)где N3 - размерность задачи, p - количество вычислительных узлов, tsend - время пересылки одного числа.Из формулы (4) видно, что для разных способов декомпозиции затраты на пересылку данных можно представить в виде Tcom = tsend-N2*k(p), где коэффициент пропорциональности k(p) зависит от способа декомпозиции и числа используемых процессорных элементов.В табл. 1 представлены числовые значения k(p). Видно, что при p > 5 более эффективными будут 2D- и 3Б-декомпозиции, а при p > 11 в случае 3Б-декомпо-зиции потребуется пересылать между процессорными элементами меньшее количество сеточных значений функции Ф и можно ожидать, что в этом случае затрачиваемое на пересылку время будет минимально.РезультатыРасчеты производились на кластерной системе ТГУ СКИФ Cyberia на сетках 240 х 240 х 240 и 360 х 360 х 360 при использовании до 144 процессоров. Результаты вычислительного эксперимента показали наличие хорошего ускорения при решении задач данного класса. Основное внимание уделялось сравнению времени пересылок и времени вычислений при различных способах декомпозиции.На первом этапе использовалась одна общая программа, размеры массивов от запуска к запуску не менялись, на каждом процессорном элементе нумерация элементов массивов начиналась с нуля. Несмотря на то, что в соответствии с теоретическим анализом 3Б-декомпозиция является оптимальным вариантом распараллеливания, вычислительные эксперименты показали, что лучших результатов можно достичь, используя 2Б-декомпозицию при числе используемых процессов от 25 до 144 (рис. 2).60 90 120 150 030 60 90 120 150Число процессоровЧисло процессоровРис. 2. Ускорение для различных способов декомпозиции расчетной областиИсходя из предварительного теоретического анализа, на графиках должны присутствовать следующие закономерности. Время вычислений без учета межпроцессорных коммуникационных затрат при разных способах декомпозиции должно примерно совпадать для одинакового числа процессоров и уменьшаться как Tcalc/p. В реальности же расчетные данные (рис. 3) указывают на то, что использование 2Б-декомпозиции на различных сетках дает минимальные затраты на проведение вычислений и расчетные графики зависимости времени вычислений от числа используемых процессоров размещаются существенно выше, чем ТЫс/р.Для объяснения полученных результатов необходимо обратить внимание на допущения, которые были сделаны при предварительном теоретическом анализе поставленной задачи. Во-первых, предполагалось, что независимо от способа распределения данных на одном процессорном элементе выполняется одинаковый объем вычислительной работы, который должен приводить к идентичным временным затратам. Во-вторых, принималось, что время, затраченное на межпроцессорную пересылку любой последовательности одинакового количества данных, не зависит от способа их выборки из оперативной памяти.Для того чтобы разобраться, что происходит в реальности, был проведен следующий набор тестовых расчетов. Для оценки состоятельности первого допущения был рассмотрен случай, когда программа запускалась в однопроцессорном варианте и при этом имитировались различные способы геометрической декомпозиции данных при одинаковом объеме вычислений, выполняемом каждым процессором. Было реализовано две версии программы: в первой использовались статические массивы размером N3, во второй - «динамические», когда размеры массивов специально подбирались в соответствии со способом декомпозиции для того, чтобы минимизировать временные затраты, связанные с выборкой данных из оперативной памяти.В табл. 2 представлено время в секундах, которое требуется процессору для проведения вычислений в своей сеточной подобласти при моделировании различных способов геометрической декомпозиции. От расчета к расчету объем вычислительной работы сохраняется, меняется лишь характер расположения обрабатываемых данных в оперативной памяти.Проанализировав представленные результаты, можно сделать вывод, что при написании параллельной программы целесообразно использовать «динамические» массивы с подстраиваемыми под выделенное число процессоров размерами. В большей степени это существенно для ЗБ-декомпозиции. Преимущества использования «динамических» массивов, на наш взгляд, определяется меньшими временными затратами на выборку обрабатываемых данных из оперативной памяти и их передачу через КЭШ-память.Для оценки реализуемости второго допущения (Tcom = tsend-N2*k(p)) был рассмотрен тест, в котором измерялось время MPI-пересылки различных сечений массива с размерностью 3. Заметим, что решение этой задачи (пересылки, скажем, i - j-, i - k-, j - k-сечений массива, элементы которого имеют индексы i, j, k) в стандарте MPI может осуществляться различными способами в зависимости от того, какие сечения массивов рассматриваются.Вычислительный эксперимент был организован следующим образом. В параллельной программе многократно выполнялась пересылка сечения массива одного типа между двумя процессорными элементами и фиксировалась продолжительность этого процесса. Использовались функции MPISEND и MPIRECV и процедуры создания производных типов MPI_TYPE_VECTOR и MPI_TYPE_INDEXED [5]. В тестовых расчетах рассматривались массивы с количеством элементов 303, 603, 1203. Полученные результаты показали, что и при организации межпроцессорной передачи данных также решительное преимущество имеет использование «динамических» массивов, поскольку в этом случае допускается использование производного типа MPI_TYPE_VECTOR, который для пересылки сечения j - k в несколько раз по времени предпочтительней, чем болееуниверсальный тип MPI_TYPE_INDEXED.Таблица 2В табл. 3 представлено время, затрачиваемое на 100-кратную пересылку данных из разных сечений массива, осуществляемую с помощью производного типа MPITYPEVECTOR. Анализируя данные, можно отметить, что время пересылки сечений массивов в MPI-FORTRAN-программе зависит от их типа. Поэтому наименьшие затраты на передачу данных дает ID-декомпозиция, наибольшие -ЗБ-декомпозиция, причем это отличие становится более существенным при увеличении размера сечения от 30 х 30 до 120 х 120. Последнее связанно с увеличением времени на выборку передаваемых данных из оперативной памяти. Таким образом, в формулах (4) необходимо вводить дополнительные коэффициенты, которые бы учитывали тип пересылаемых сечений массивов сеточных функций.На рис. 4 представлен график ускорения параллельной программы, использующей «динамические» массивы, для различных способов декомпозиции. Здесь, также как и на рис. 2, наилучшие показатели демонстрирует 2D-декомпозиция, причем имеет место прирост ускорения. Незначительно ей уступает 3D-декомпо-зиция, проблемы которой в маштабируемости параллельной программы связаны, главным образом, с большими, чем в 1D- и 2D-случаях, затратами на выборку, обработку и пересылку данных из оперативной памяти.70 60 50 40* 30 20100150ЗаключениеДля явных разностных методов решения уравнения переноса возможно применение одномерной, двумерной и трехмерной декомпозиции, однако результаты тестирования программ показали, что 3D-декомпозиция не дает выигрыша во времени по сравнению с 2D-декомпозицией, по крайней мере, для количества процессоров, не превышающего 250, при этом 3D-декомпозиция отличается более трудоемкой программной реализацией.

Скачать электронную версию публикации