Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.parallel.ru/sites/default/files/ftp/chg99/Andrianov.doc Дата изменения: Wed Nov 2 11:53:58 2011 Дата индексирования: Tue Oct 2 03:02:14 2012 Кодировка: Windows-1251

Опыт применения системы Норма для решения зада? математи?еской физики на
параллельных ЭВМ с раcпределенной памятью[1]

А.Н.Андрианов, К.Н.Ефимкин
Институт прикладной математики им. М.В.Келдыша РАН

1. Некоторые проблемы разработки прикладных программ для параллельных
ЭВМ
Прикладной специалист в процессе решения своей прикладной зада?и,
скорее всего, хотел бы знать как можно меньше об устройстве конкретной ЭВМ
(но при этом полностью использовать ее возможности); не иметь проблем при
переходе с одной машины на другую; пользоваться при программировании
привы?ными средствами и не вникать в "программистсткие" тонкости, типа
особенностей компиляторов, языков программирования, организации системных
библиотек, вопросов эффективного их использования и т.п.
При разработке прикладных программ для параллельных ЭВМ такую
комфортную модель обы?но реализовать не удается. Основные при?ины этого -
необходимость знать и использовать понятия из новой предметной области -
области параллельных вы?ислений. Это и архитектура многопроцессорных систем
(массивно-параллельные системы (MPP), симметри?ные мультипроцессорные
системы (SMP), кластерные системы и т.п., используемые микропроцессоры,
коммуникационная сеть, организация памяти - распределенная или общая); и
модели параллельности (типы параллельных процессов и способы их задания,
переда?а сообщений); и представление моделей параллельности в языковых
средствах программирования (стандарты MPI или PVM для модели переда?и
сообщений или OpenMP для SMP-систем в модели параллельности с общей
памятью).
Проблемы освоения области параллельных вы?ислений ?асто осложняются
нали?ием у прикладного специалиста опыта разработки последовательных
программ и попытками использовать этот опыт при разработке параллельных
программ. Использование косвенной адресации, привы?ных структур данных,
экономия памяти могут привести к возникновению в программе информационных
зависимостей, которые не связаны с существом рас?ета, но затрудняют или
делают невозможным распараллеливание программы.
В настоящее время трудно назвать универсальную технологию,
поддерживающую комфортную разработку параллельных прикладных программ для
решения вы?ислительных зада? на сетках. В данной лекции рассматривается
подход к разработке параллельных программ, основанный на применении
специализированного декларативного языка Норма [1,2]. Этот подход можно
рассматривать как попытку преодолеть некоторые из отме?енных выше проблем.
Прежде ?ем на?ать обсуждение системы Норма и результатов ее
применения, приведем классификацию типов сеток, используемых при решении
зада? математи?еской физики (сайт Northeast Parallel Architectures Center,
Syracuse University, www.npac.syr.edu/PROJECTS/PUB/nikos/ParGG.html):

Структурные (Structured)
Стати?еские (Static)
Неструктурные (Unstructured)
Сетки (Grids)
Вложенные (Nested)
Адаптивные (Adaptive) Движущиеся (Moving)
Неструктурные (Unstructured)
Эта классификация определяет класс зада?, о решении которых пойдет
ре?ь ниже.
2. Система Норма - цели, состояние разработки, область применения
Основной тезис, на котором базируется проект Норма, заклю?ается в
следующем. В большинстве слу?аев описание метода решения проблемы в
математи?еских терминах, используемых в определенной нау?ной области, имеет
о?ень высокий уровень абстракции и предоставляет большие возможности для
выявления естественного параллелизма. Более того, такое описание не
ориентировано на какую-либо конкретную архитектуру компьютера. По этой
при?ине уровень описания имеет суперстабильный характер и отражает метод
решения, а не его реализацию при каких-то конкретных условиях.
Язык Норма как раз и формализует ту математи?ескую запись (рас?етные
формулы), которая полу?ается в результате решения зада?и вы?ислительного
характера прикладным специалистом. Язык Норма является декларативным языком
- описание решения зада?и на Норме является факти?ески запросом на
вы?исление, а реализация этого запроса - построение последовательной или
параллельной программы - зада?а синтезирующего транслятора. Факти?ески,
программирование на языке Норма не требует написания программ в смысле
традиционных универсальных языков программирования.
В Норма-программе указываются только те правила (ограни?ения),
которым должны удовлетворять зна?ения переменных, при этом в записи
отсутствуют понятие памяти и другие мотивы, связанные с архитектурой
целевого компьютера, а также обы?ные элементы программ (управление, циклы,
переприсваивание и т.п.). Язык Норма является языком с однократным
присваиванием (single assignment language) - каждая переменная в программе
может принимать зна?ение только один раз, а индексы переменных имеют вид i
( (, ( - целая константа. Эти ограни?ения (и некоторые другие) связаны с
необходимостью решать в процессе трансляции зада?у синтеза выходной
программы, которая в более общих постановках может не иметь решения.
Схема трансляции с языка Норма кратко может быть описана следующим
образом. В результате анализа информационных зависимостей между переменными
Норма-программы строится граф информационных зависимостей. В результате
анализа графа информационных зависимостей строится ярусно-параллельный граф
алгоритма, в котором представлен "естественный" параллелизм, определямый
лишь информационными зависимостями. Затем строится отображение ярусно-
параллельного графа на архитектуру (модель) вы?ислительной системы. При
построении отображения у?итывается модель памяти, ?исло процессоров, а
также выполняются разли?ные оптимизации.
Язык Норма является специализированным языком - первона?ально он
предназна?ался для описания решения вы?ислительных зада? на стати?еских
структурных сетках, однако область его применения оказалась зна?ительно
шире. В разделе 3 будет приведен пример применения языка Норма для решения
зада?и на структурной стати?еской сетке, а в разделе 4 изложен опыт
применения Нормы для решения зада? на стати?еских неструктурных сетках и
стати?еских вложенных сетках.
В настоящее время реализованы версии транслятора с языка Норма,
которые позволяют полу?ать выходные программы для распределенных
параллельных вы?ислительных систем (модель памяти NORMA, параллельные
вы?исления с переда?ей сообщений), и параллельных вы?ислительных систем с
общей памятью (модель памяти NUMA, параллельные вы?исления над общей
памятью) и последовательных ЭВМ. Выходные программы могут быть построены на
языках Фортран-77, Фортран PVM, Фортран MPI, Фортран GNS [3], Фортран
Convex [4].

3. Фрагмент Норма-программы для решения зада?и газовой динамики на
стати?еской структурной сетке
Рассмотрим фрагмент программы решения системы нестационарных уравнений
газовой динамики с одной пространственной переменной методом Годунова [5].
Рас?етная схема для рассматриваемой зада?и:

( in = ( in-1 ( ((t / h) [(RU) i+1 n-1 ( (RU) i n-1],
(u in = ((u) in-1 ( ((t / h) [(P+RU) i+1 n-1 ( (P+RU2) i+1 n-1],
(e in = ((e) in-1 ( ((t / h) [(RUE+PU) i+1 n-1 ( (RUE+PU) i n-
1],
p = ((( ( 1) (e ( u2 / 2)
Здесь p - давление, u - скорость, (- плотность, e - полная энергия
единицы массы газа. Из первого уравнения определяется (, из второго u, из
третьего e, а давление дос?итывается из уравнения состояния
идеального газа, ( - показатель адиабаты газа. Расс?итанный таким образом
набор газодинами?еских параметров принимается за исходный для следующего
шага по времени и повторяется цикл рас?ета для момента времени t n+1 = t n
+ (t.
Программа на Норме, соответствующая этой вы?ислительной схеме.
! На?ало главной программы TEST203.
MAIN PART TEST203.
BEGIN
!Описание переменных: NTEND - ?исло шагов по времени, DT - шаг по времени,
! HX - шаг по пространству, GAMMA - показатель адиабаты
VARIABLE NTEND INTEGER. VARIABLE HX, DT, GAMMA REAL.
VARIABLE NITER INTEGER. VARIABLE PVAC, ITPREC REAL.
!Сетка, на которой определены переменные R, U, P и их на?альные зна?ения
R0, U0, P0
GRIDSOL : (I=1..LX). VARIABLE R, U, P, R0, U0, P0 DEFINED ON
GRIDSOL.
!Размерности сеток.
DOMAIN PARAMETERS LX = 200.
!Ввод и на?альных данных.
INPUT NTEND, HX, DT, GAMMA, PVAC, ITPREC, NITER.
INPUT P0, R0, U0 ON GRIDSOL.
!Вызов раздела GOD21.
COMPUTE GOD21 (NTEND, HX, DT, GAMMA, PVAC, ITPREC, NITER,
P0 ON GRIDSOL, R0 ON GRIDSOL, U0 ON GRIDSOL
RESULT P ON GRIDSOL, R ON GRIDSOL, U ON GRIDSOL).
!Вывод результатов.
OUTPUT P(FILE='p.res'), R(FILE='r.res'), U(FILE='u.res') ON GRIDSOL.
END PART.
! Раздел GOD21.
PART GOD21.
NTEND,HX,DT,GAMMA,PVAC,PRECIT,NITER,P0,R0,U0 RESULT P,R,U
BEGIN
!Описание переменных.
VARIABLE NTEND,NITER INTEGER. VARIABLE DT, HX, GAMMA, PVAC, PRECIT REAL.
!Сетка, на которой определены основные переменные
GRIDSOL : (I=1..LX). VARIABLE R, U, P, R0, U0, P0, E DEFINED ON
GRIDSOL.
!Вспомогательные сетки и переменные
GRIDAUX:(I=1..LX1). VARIABLE PX, RX, UX, EX DEFINED ON GRIDAUX.
GRIDIN:(I=2..LX1-1). GRIDL:(I=1). GRIDR:(I=LX+1). GRIDJ(J=1).
DOMAIN PARAMETERS LX=200, LX1=201.
! Распределение для конфигурации (10 х 1) процессоров
DISTRIBUTION INDEX I=1..10, J=1.
!На?альные зна?ения для итераций по времени.
ITERATION R, P, U, E, ON NT.
INITIAL NT=0:
FOR GRIDSOL ASSUME P=P0; R=R0; U=U0.
FOR GRIDSOL ASSUME E=P/(R*(GAMMA-1.0)) + U*U*0.5.
END INITIAL
!Итерации по времени.
! Подпрограмма RIEMN21 производит вы?исление "распадных" ! параметров.
FOR GRIDIN ASSUME
COMPUTE RIEMANN(GAMMA,NITER,PVAC,ITPREC,R[NT-1,I-1],
P[NT-1,I-1],U[NT-1,I-1],R[NT-1],P[NT-1],U[NT-1]
RESULT RX,PX,UX,EX).
FOR GRIDL ASSUME
COMPUTE RIEMANN(GAMMA,NITER,PVAC,ITPREC,R[NT-1],
P[NT-1],U[NT-1],R[NT-1],P[NT-1],U[NT-1]
RESULT RX,PX,UX,EX).
FOR GRIDR ASSUME
COMPUTE RIEMANN(GAMMA,NITER,PVAC,ITPREC,R[NT-1,I-1],
P[NT-1,I-1],U[NT-1,I-1],R[NT-1,I-1],
P[NT-1,I-1],U[NT-1,I-1]
RESULT RX,PX,UX,EX).
FOR GRIDSOL ASSUME
R=R[NT-1]+(DT/HX)*(RX*UX-RX[I+1]*UX[I+1]);
U=(R[NT-1]*U[NT-1]+(DT/HX)*((RX*UX*UX+PX)
-(RX[I+1]*UX[I+1]*UX[I+1]+PX[I+1])))/R;
E=(R[NT-1]*E[NT-1]+(DT/HX)*((RX*UX*EX+PX*UX)
-(RX[I+1]*UX[I+1]*EX[I+1]+PX[I+1]*UX[I+1])))/R;
P=(GAMMA-1.0)*R*(E-U*U*0.5).
! Условие завершения итерации
EXIT WHEN N=NTEND.
END ITERATION NT.
END PART.

Файл исходных данных norma.dat:
R0(I=1..200)=200(1.0); U0(I=1..200)=200(0.0); P0(I=1..100) =100(2.0);
P0(I=101..200) =100(1.0);
NTEND=200; HX=0.5; DT=0.1; GAMMA=1.4; PVAC=0.000001; ITPREC=0.05; NITER=3;

Чтобы использовать при рас?етах уже имеющиеся данные или выводить
зна?ения вели?ин во внешнюю среду, применяются описания соответственно
входных (INPUT) или выходных (OUTPUT) вели?ин. Такое описание озна?ает, ?то
подлежат вводу (выводу) зна?ения всех вели?ин, указанных в списке ввода
(вывода). Порядок, в котором будут вводиться (выводиться) вели?ины, при
этом не задается - он определяется в процессе трансляции автомати?ески (?то
требует, коне?но, специальной обработки транслятором входных файлов).
Вы?исления описаны при помощи конструкции
FOR <область> ASSUME <соотношение>.
Эта конструкция является клю?евым понятием языка Норма. Cоотношение
задает правило вы?исления зна?ений вели?ины из левой ?асти по зна?ениям
вели?ин из правой ?асти и индексные зависимости между переменными. Вели?ина
из левой ?асти должна быть вы?ислена во всех то?ках области; правило для
этого вы?исления определено однозна?но, однако при этом не требуется
немедленное выполнения вы?исления в данном месте программы и не задается
порядок или способ вы?исления. Некоторое внешнее сходство с оператором
присваивания не должно вводить в заблуждение.
Индексы без смещений в записи формул могут быть опущены - при анализе
программы они автомати?ески восстанавливаются транслятором.
При описании итерационного процесса вы?ислений (конструкция ITERATION
. END ITERATION) в заголовке итерации указан индекс итерации NT и
пере?ислены итерируемые вели?ины, являющиеся результатом этого фрагмента
вы?ислений. На?альные зна?ения итерируемых переменных заданы в конструкции
INITIAL . END INITIAL. Далее описан собственно итерационный процесс:
сна?ала описано вы?исление "распадных" вели?ин PX, RX, UX, EX на сетках
GRIDIN, GRIDL, GRIDR по правилу RIEMANN, а затем искомых вели?ин R, U, E,
P. Правило RIEMANN в данном фрагменте не конкретизировано: оно может быть
определено в другой ?асти Норма-программы, при помощи Фортран-программы
(как это было сделано в рассматриваемом слу?ае) или библиоте?ной программы.
Условие завершения итерации описано в конструкции EXIT WHEN.

Применение системы Норма для решения зада? на стати?еских неструктурных и
стати?еских вложенных сетках на параллельных ЭВМ с раcпределенной памятью
Рассмотрим применение языка Норма для решения на распределенных системах
конкретной зада?и газовой динамики, для которой в [6] на основе
аппроксимации кинети?еского уравнения переноса схемой с направленными
разностями на я?ейке с произвольным ?ислом граней построена кинети?ески-
согласованная разностная схема (КСРС) и приведена дискретизация Навье-
Стоксовских потоков для рас?ета газодинами?еских те?ений на треугольных
сетках. Полу?енные схемы применены для рас?ета внешних зада? обтекания.
Рас?ет итеративный, схема рас?ета явная: все исходные данные для рас?ета
текущего слоя итерации берутся с предыдущего слоя. Таким образом, можно
вы?ислять рас?етные переменные в каждом узле сетки независимо от зна?ений в
других узлах, то есть можно говорить, ?то данная зада?а имеет уровень
параллельности порядка n, где n - ?исло узлов сетки.
При разработке Норма-программы для данной зада?и возникают две основные
проблемы: 1) как задать в языке Норма вы?ислительную формулу при
зависимости одной вели?ины от другой в слу?ае использовании неструктурной
сетки; 2) как распределить рас?етные вели?ины между процессорами таким
образом, ?тобы добиться сбалансированности вы?ислений и минимизировать
время на обмены между процессорами. Рассмотрим эти проблемы более подробно.
Первая проблема определяется использованием нерегулярных сеток и
неформально может быть сформулирована следующим образом. Пусть необходимо
вы?ислить зна?ение рас?етной вели?ины X в то?ке (i,j). При вы?ислениях на
регулярных сетках аргументы для вы?исления вели?ин обы?но находятся в
то?ках с координатами вида: (i+k,j+l), где k,l -цело?исленные константы.
При вы?ислениях на нерегулярных сетках то?ки сетки нумеруются от 1 до N.
Пусть то?ки, соседние к i-й то?ке сетки, имеют номера i1,i2,...,ik. Тогда
общая структура сетки определяется матрицей neigh, состоящей из N строк, в
k-й строке указываются номера то?ек, соседних к k-й то?ке. Например, если i-
я строка содержит номера i1,i2,...,ik, и для вы?исления зна?ения вели?ины X
в то?ке i необходимо использовать зна?ения X1 в соседних то?ках, то запись
в программе выглядит неформально следующим образом (F - некоторая
функциональная зависимость):
X(i)=F(X1(neigh(i,j)), i=1,.,N, j=1,.,ik.
Запись таких выражений в явном виде в языке Норма не предусмотрена
(отсутствует понятие массива и косвенной адресации).
Вернемся к математи?еской записи рас?етной формулы, приводящей к
необходимости использовать косвенную адресацию:
( ik = ( ik-1 ( (dt / v i ) [pic] (S j ( D j + . )
(1),
Здесь ((i) - граница - определяет множество то?ек, соседних к то?ке i.
На языке Фортран такую запись обы?но можно представить в следующем виде
(vsn(i) - ?исло соседей у то?ки с номером i):
DO i=1,N
sum=0.0
DO j=1,vsn(i)
sum=sum+S(neigh(i,j))-D(neigh(i,j))
ENDDO
ro(i)=ro(i)-dt/v(i)(sum
ENDDO
В слу?ае, когда такая программа должна исполняться на параллельной ЭВМ
с общей памятью, достато?но сделать указание о том, ?то внешний цикл по i
можно выполнять параллельно. Однако, необходимо у?итывать, ?то переменная
sum разделяется всеми витками цикла и поэтому необходимо указать, ?то она
является локальной для каждого витка цикла. Например, в Фортране-Convex [4]
это можно сделать следующим образом:
C$DIR LOOP_PARALLEL, LOOP_PRIVATE sum
DO i=1,N
sum=0.0
DO j=1,vsn(i)
sum=sum+S(neigh(i,j))-D(neigh(i,j))
ENDDO
ro(i)=ro(i)-dt/v(i)*sum
ENDDO
Коне?но, при этом мы используем факт, ?то схема вы?исления явная.
В слу?ае выполнения программы на распределенных вы?ислительных системах
косвенная адресация приводит к большим трудностям при построении
эффективной параллельной программы. Это связано с тем, ?то нельзя явно
указать номер то?ки, используемой в ка?естве аргумента выражения и, как
следствие, нельзя указать номер процессора, в котором находится эта то?ка.
Один из способов преодоления этой трудности состоит в том, ?тобы
преобразовать исходную запись (1) к следующему виду:
( ik = ( ik-1 ( (dt / v i ) [pic] (S1 i,j ( D1 i,j + . )
(2),
В этом слу?ае вместо зна?ений S(j) и D(j) в каждой то?ке мы вводим
вспомогательные массивы S1(i,j) и D1(i,j), которые строятся по следующему
правилу: S1(i,j)=S(neigh(i,j)), то есть "размножаем" используемые зна?ения.
Если выражение (1) мы не могли записать на Норме, то в последнем слу?ае
такая запись возможна и имеет вид:
FOR oi ASSUME ro =ro(it-1)-dt/v*SUM((oj) S1-D1),
где oi : (i=1..N), oj : (j=1..8)/j изменения индексов. При этом вели?ины S1 и D1 описываются на области oij :
(oi;oj):
VARIABLE S1,D1 DEFINED ON oij.
Здесь важно отметить следующее обстоятельство. Если при
программировании записи (1) вы?исленные зна?ения вели?ин S и D
привязываются к конкретным то?кам, то в слу?ае (2) необходимо после
завершения витка итерационного цикла предусмотреть распределение
вы?исленных зна?ений по соответствующим местам в матрицах S1 и D1. Для
этого и используются функции, выполнение которых обеспе?ивает обмен данными
между процессорами. Здесь важно отметить также то, ?то на каждом шаге
итерации обмен происходит между одними и теми же процессорами, так как
сетка стати?еская - конфигурация сетки не изменяется на протяжении с?ета
зада?и. Коне?но, нетрудно заметить, ?то при таком подходе существенно
увели?ивается размер используемой памяти. Однако, теперь для каждой то?ки
известно, ?то аргументы, используемые для ее вы?исления, находятся в том же
процессоре, где находится и сама то?ка.
Вторая проблема связана с распределением рас?етных то?ек по процессорам
распределенной системы таким образом, ?тобы минимизировать время на
переда?у сообщений между ними. Эта проблема в последнее время интенсивно
изу?ается (например, [7-9]) и является самостоятельной зада?ей, не
зависящей от средств и методов разработки программ. В общем слу?ае время,
затра?иваемое на обмены информацией между процесорами, определяется двумя
характеристиками. Во-первых, это коли?ество вызовов процедур обмена, то
есть, если то?ки, помещенные в процессор, имеют соседство с то?ками,
размещенными в других k процессорах, то тогда необходимо обращаться к
процедуре обмена k раз. Второй характеристикой является объем передаваемой
информации между процессорами.
Время, необходимое для выполнения операции отправки сообщения, в общем
слу?ае, имеет вид T=t*L+b,
где L - длина сообщения в байтах, t - ?истое время переда?и одного байта
и b - накладные расходы на вызов процедуры переда?и данных (latency time).
Известно, ?то b>> t. Время T определяет накладные расходы, вызванные тем,
?то зада?а решается на распределенной вы?ислительной системе.
Минимизировать T можно как снижением ?исла обращений к процедурам обмена
(уменьшение k), так и уменьшением общего коли?ества передаваемой
информации.
В системах [7-9] основное внимание уделяется сокращению общего объема
передаваемой информации, при?ем, за?астую за с?ет увели?ения ?исла
обращений к процедурам обмена. К преимуществам таких систем следует отнести
тот факт, ?то они работают о?ень быстро. Кроме того, уже появляются
параллельные версии таких систем, которые позволяют использовать их для
динами?ески изменяемых сеток.
В нашем слу?ае мы использовали собственную программу, в которой основное
внимание уделяется сокращению ?исла обращений к процедурам обмена.
Например, для сетки, состоящей из 75900 то?ек удалось так распределить
то?ки по процессорам, ?то каждый процессор, в процессе с?ета, обменивался
данными только со своими двумя соседями. При этом общий объем передаваемой
информации превосходил в два раза объем, полу?енный при разбиении с помощью
системы METIS (версия 3.0). При использовании системы METIS ?исло обращений
к процедурам обмена варьировалось от 2 до7 для разли?ных процессоров.
Ниже приведены времена с?ета на ЭВМ МВС-100, МВС-1000К, Parsytec-CC12
(12 процессоров), Parsytec-CC32 (24 процессора) для зада?и моделирования
дозвукового те?ения вязкого газа, рассматриваемой выше (зависимости от
?исла процессоров, ЭВМ и ?исла параллельных процессов).
Таблица 1
|?исло |ЭВМ |?исло процессов |
|процессоров| | |
| | |6 |12 |24 |
| |MВС100 | |- |- |
|1 |MВС1000k |1028.0 |1067.0 |1277.0 |
| |PARSYTEC CC12 |3264.6 |3439.3 |- |
| |PARSYTEC CC32 |4149.2 |4160.9 |- |
| |MВС100 |- |- |- |
|4 |MВС1000k |351.0 |307.0 |349.0 |
| |PARSYTEC CC12|- |- |- |
| |PARSYTEC CC32 |- |1096.8 |1082.0 |
| |MВС100 |2442.0 |- |- |
|6 |MВС1000k |187.0 |203.0 |230.0 |
| |PARSYTEC CC12 |566.1 |630.3 |634.4 |
| |PARSYTEC CC32 |703.5 |764.7 |752.5 |
| |MВС100 |- |1283.6 |- |
|12 |MВС1000k |- |- |- |
| |PARSYTEC CC12 |- |- |- |
| |PARSYTEC CC32 |- |373.3 |399.2 |
| |MВС100 |- |- |685.5 |
|24 |MВС1000k |- |- |- |
| |PARSYTEC CC12 |- |- |- |
| |PARSYTEC CC32 |- |- |206.5 |

В заклю?ение рассмотрим проблемы, возникающие при решении зада? с
использованием стати?еских вложенных сеток.
Проводилось трехмерное ?исленное моделирование развития
крупномасштабной конвективной неустой?ивости внутри протонейтронной звезды,
возникшей в результате действия неравновесного процесса нейтронизации
вещества. Система уравнений адиабати?еской гидродинамики с у?етом
гравитации решается с помощью явной консервативной TVD разностной схемы
Годуновского типа со вторым порядком по пространству и времени. Для
повышения то?ности результатов используется метод вложенных сеток.
Рас?етная область покрывается набором вложенных друг в друга сеток с
одинаковым ?ислом я?еек, но последовательно уменьшающимся в 2 раза
абсолютным размером. Граница сетки n-уровня всегда совпадает с границей
сетки n-1 уровня. Для выполнения условия устой?ивости необходимо, ?тобы
двум шагам вы?исления на сетке n-уровня соответствовал один шаг вы?ислений
по времени на сетке n-1-го уровня. Перес?ет всех вели?ин в каждой я?ейке на
сетке n-1 уровня совершался простым усреднением 8 зна?ений этих вели?ин на
сетке n - го уровня. Грани?ные зна?ения, необходимые для вы?исления вели?ин
на сетке n -го уровня полу?ались в результате монотонной интерполяции по 27
зна?ениям этих вели?ин на сетке n-1 уровня. В вы?ислениях использовалось
три уровня вложенных сеток (G0,G1,G2), каждая размерностью 56х56х56, с
постоянным шагом по пространству ( схема сетки приведена ниже).

| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

Сетка 3-го уровня с наименьшим шагом покрывает полностью на?альное
возмущение энтропии. Это позволяет на два порядка увели?ить ?исло рас?етных
я?еек в этой области, по сравнению со слу?аем одной сетки. Один шаг на
сетке 0-го уровня соответствует 2 шагам на сетке 1-го уровня и ?етырем
шагам на сетке 3-го уровня: всего полу?ается 7 временных шагов.
На каждом временном шаге сна?ала определяются грани?ные зна?ения для
сетки Gi по зна?ениям в соответствующих узлах сетки G(i-1). Далее
вы?исляются зна?ения рас?етных вели?ин во внутренних узлах сетки Gi. В
заклю?ение полу?енные результаты усредняются и возвращаются в
соответствующие узлы сетки G(i-1). Поскольку на сетке каждого уровня
используется одна и та же гидродинами?еская ?асть программы (в дальнейшем
будем называть ее Hydra), то увели?ение ?исла уровней приводит к большому
росту общего времени рас?ета, ?то приводит к необходимости разработки
параллельной программы.
Способ, используемый при реализации параллельной программы
рассматриваемого алгоритма состоит в том, ?то каждая сетка равномерно
распределяется по линейке процессоров. Поэтому гидродинами?еская ?асть
программы описывается на языке Норма, в которой в ка?естве параметров
задаются ?исло используемых процессоров и размер сетки. Здесь существенно
используется тот факт, ?то размерности всех сеток совпадают.
При таком подходе все проблемы, связанные с организацией обменов между
процессорами на этапе вы?исления программы Hydra, берет на себя Норма-
система.
С другой стороны, такое распределение я?еек сетки по процессорам
приводит к трудностям, связанным с организацией вы?ислений в грани?ных
я?ейках и с возвратом усредненных зна?ений на сетку более высокого уровня.
Это связвано с тем, ?то в обоих слу?аях я?ейки, для которых проводится
рас?ет, и аргументы, используемые при этом, находятся, вобще говоря, в
разли?ных процессорах. Таким образом, для решения данной зада?и надо
запрограммировать вспомогательные алгоритмы, которые обеспе?ивали бы обмен
необходимыми данными. Сетка i-го уровня накладывается на сетку уровня i-1,
на?иная с я?ейки с номером (Mx,My,Mz), то есть в я?ейке (Mx,My,Mz) сетки Gi-
1 размещаются 8 я?еек сетки Gi. Зна?ения Mx,My,Mz задаются в ка?естве
параметров исходной зада?и. Это позволяет до на?ала основного рас?ета
определить, зна?ения из каких я?еек необходимо передавать из одного
процессора в другой, то есть для каждого процессора построить
вспомогательные массивы, в которых будет храниться информация о том, в
какой процессор (из какого процессора) и зна?ения из каких я?еек надо
передавать (принимать). В дальнейшем для обменов можно использовать уже
готовую информацию из этих массивов, не проводя лишних вы?ислений.
Обратим внимание на вопрос, где надо проводить соответствующие
вы?исления. Рассмотрим решение этого вопроса на примере вы?исления зна?ений
в грани?ных я?ейках сетки G2 с использованием зна?ений в я?ейках сетки G1.
Коли?ество грани?ных я?еек приблизительно равно 12*N*N, ?исло используемых
аргументов - 4.25*N*N. О?евидно, ?то в этом слу?ае вы?исление зна?ений в
грани?ных я?ейках надо проводить в процессорах, в которых эти я?ейки
находятся. Аналоги?но рассматривается вопрос о том, где вы?ислять
усредненные зна?ения. О?евидно, ?то коли?ество усредненных зна?ений в 8 раз
меньше ?исла используемых аргументов. В этом слу?ае усреднение проводится в
процессорах, в которых находятся аргументы, а затем результаты рассылаются
по необходимым процессорам.
Ниже в таблице приведены временные характеристики зада?и, полу?енные в
результате с?ета на ЭВМ МВС-100 (конфигурация из 14 процессоров).

|Число |Время обмена |Время обмена |Время с?ета 10 |
|процессоров |при усреднении |для границ |итераций |
|1 |0.568 |6.401 |565.37 |
|2 |1.069 |2.807 |565.37 |
|3 |1.072 |2.997 |565.05 |
|4 |1.616 |3.067 |564.90 |
|5 |2.597 |2.627 |564.75 |
|6 |2.772 |1.916 |564.59 |
|7 |3.453 |1.646 |564.43 |
|8 |2.048 |1.876 |564.28 |
|9 |2.672 |1.594 |564.12 |
|10 |2.295 |2.268 |563.95 |
|11 |1.615 |2.502 |563.78 |
|12 |1.069 |2.445 |563.62 |
|13 |1.069 |2.618 |563.42 |
|14 |0.568 |31.926 |563.27 |

В первом столбце указан номер процессора. Во втором указано время,
затра?енное на обмен данными при вы?ислении усредненных зна?ений. В третьем
столбце - время, затра?енное на обмен данными при вы?ислении зна?ений в
грани?ных я?ейках сеток. Общее время 10 шагов итерации на сетке 0-го уровня
приведено в последнем столбце.

Литература

1. И.Б.Задыхайло, К.Н.Ефимкин. Содержательные обозна?ения и языки нового
поколения. Информационные технологии и вы?ислительные системы, N2, 1996,
c. 46-58.
2. А.Н.Андрианов, А.Б.Бугеря, К.Н.Ефимкин, И.Б.Задыхайло. Норма. Описание
языка. Рабо?ий стандарт. Препринт ИПМ им.М.В.Келдыша РАН, N120, 1995, 50
с.
3. В.А.Абрамова и др. Система программирования GNS. Препринт ИПМ
им.М.В.Келдыша РАН, N71, 1997, 23с.
4. Convex Fortran User's Guide. Order N DSW-038, Convex Press, Richardson,
Texas, USA, October 1994, pp. 1-277.
5. А.Н.Андрианов, С.Б.Базаров, К.Н.Ефимкин. Решение зада? газовой динамики
методом Годунова на параллельных ЭВМ с помощью языка Норма. Препринт ИПМ
им.М.В.Келдыша РАН, N 121, 1995, 22с.
6. И.В.Абалакин, А.В.Жохова, Б.Н.Четверушкин. Кинети?ески-согласованные
разностные схемы на нерегулярных сетках. Математи?еское моделирование,
т.9, N7, 1997, c.44-53.
7. L.Oliker. PLUM: Parallel Load Balancing for Adaptive Unstructered
Meshes. Journal of Parallel and Distributed Computing 52, 150-177(1998).
8. G.Karypis, K.Schloegel, V.Kumar. ParMETIS - Parallel Graph Partitioning
and Sparse Matrix Ordering Library. Version 2.0. 1998 ( http:
//www.cs.umn.edu/ ~karypis).
9. C.Walshaw, M.Cross. Parallel Optimisation Algorithms for Multilevel Mesh
Partitioning. Tech. Rep. 99/IM/44, Univ. Greenwich, London SE18 6PF, UK,
February 1999.

Сведения об авторах

А.Н.Андрианов
старший нау?ный сотрудник ИПМ им. М.В.Келдыша РАН, к.ф.-м.н.
тел. 333-55-78
e-mail: and@a5.kiam.ru

К.Н.Ефимкин
зав. отделом ИПМ им. М.В.Келдыша РАН, к.ф.-м.н.
тел. 251-89-81, 333-55-78
e-mail: efi@a5.kiam.ru

-----------------------
[1] Работа ?асти?но поддержана грантами РФФИ 98-01-00987, 99-01-00842