| Оглавление | Часть 1 | Часть 2 | C-DVM - часть 3 |
Рассмотрим программу решения системы линейных уравнений Ax = B методом исключения Гаусса. Матрица коэффициентов А размещена в секции массива А[0:N-1][0:N-1], а вектор В в секции этого же массива A[0:N-1][N].
/* программа GAUSS */
#include <math.h>
#define DVM(dvmdir)
#define DO(v,l,h,s) for(v=l; v<=h; v+=s)
#define N 100
main ()
{
int i, j, k;
/* описание динамических распределенных массивов */
DVM(DISTRIBUTE [BLOCK] []) float (*A)[N+1];
DVM(DISTRIBUTE [BLOCK]) float (*X);
/* создание массивов */
A = malloc( N*(N+1)*sizeof(float));
X = malloc( N*sizeof(float));
/* инициализация массива A*/
DVM(PARALLEL [i][j] ON A[i][j])
DO(i,0,N-1,1)
DO(j,0,N,1)
if (i==j || j==N) A[i][j] = 1.;
else A[i][j]=0.;
/* исключение */
for (i=0; i<=N-1; i++)
{
DVM(PARALLEL [k][j] ON A[k][j]; REMOTE_ACCESS A[i][])
DO (k,i+1,N-1,1)
DO (j,i+1,N,1)
A[k][j] = A[k][j]-A[k][i]*A[i][j]/A[i][i];
}
/* обратная подстановка */
X[N-1] = A[N-1][N]/A[N-1][N-1];
for (j=N-2; j>=0; j-=1)
{
DVM(PARALLEL [k] ON A[k][]; REMOTE_ACCESS X[j+1])
DO (k,0,j,1)
A[k][N] = A[k][N]-A[k][j+1]*X[j+1];
X[j]=A[j][N]/A[j][j];
printf("j=%4i X[j]=%3.3E\n",j,X[j]);
}
}
Указание об удаленном доступе для ссылки А[i][] приводит к следующим действиям:
Задание Х[j+1] в указании об удаленном доступе означает:
Идея этого метода состоит в раскрашивании точек сетки в шахматном порядке в два цвета: красный и черный.
Выполнение параллельной программы на каждом процессоре происходит следующим образом (две полуитерации Якоби):
/* программа RED-BLACK */
#define DVM(dvmdir)
#define DO(v,l,h,s) for(v=l; v<=h; v+=s)
#include <stdlib.h>
#include <math.h>
#define ITMAX 20
main ()
{ int i, j, it, irb, N;
float eps;
float MAXEPS = 0.5E-5;
float w = 0.5;
/* Имя групповой операции обновления теневых элементов */
DVM(SHADOW_GROUP) void *sha;
/* временное переопределение для обычного компилятора Си */
#define N 8
/* описание распределенного динамического массива */
DVM (DISTRIBUTE [BLOCK] [BLOCK]) float (*A)[N];
#undef N /* отмена переопределения */
N = 100; /* вычисление размера массива */
/* создание массива */
A = malloc( N*N*sizeof(float));
/* Задание состава группы операций обновления теневых граней */
DVM (CREATE_SHADOW_GROUP sha:A);
/* параллельный цикл инициализации с опережающим вычислением и */
/* рассылкой экспортируемых данных */
DVM (PARALLEL [i][j] ON A[i][j]; SHADOW_START sha)
DO (j,0,N-1,1)
DO (j,0,N-1,1)
A[i][j] = 1.+i+j;
/* цикл итераций */
DO (it,0,ITMAX,1)
{
eps = 0.;
/* цикл по красным и черным переменным */
DO (irb,0,1,1)
{
/* параллельный цикл одной итерации с редукцией и */
/* отложенным использованием импортируемых элементов */
DVM (PARALLEL [i][j] ON A[i][j];
REDUCTION MAX(eps);
SHADOW_WAIT sha)
DO (i,1,N-2,1)
DO (j,1+(i+irb)%2,N-2,2)
{
float s;
s = A[i][j];
A[i][j] = (w/4)*(A[i-1][j]+A[i+1][j]+
A[i][j-1]+A[i][j+1])+(1-w)*A[i][j];
eps = max (abs(s-A[i][j]), eps);
}
DVM (SHADOW_START sha);
} /* DO irb */
if (eps < MAXEPS) break;
} /* по it */
DVM (SHADOW_WAIT sha);
return 0;
}
В этой программе применяется моделирование многомерных массивов с помощью одномерных.
/* программа MULTIGRID */
#include <stdio.h>
#include <stdlib.h>
#define DVM(dvm)
#define DO(v,l,h,s) for(v=(l); v<=(h); v+=(s))
void oper(
DVM(*DISTRIBUTE [*][*][*]) float *AA,
int AAN, int AAM, int AAK,
DVM(*DISTRIBUTE [*][*][*]) float *BB,
int BBN, int BBM, int BBK)
/* Параметры: два распределенных 3-хмерных массива и */
/* их фактические размерности */
{
#define AA(i,j,k) AA[((i)*AAM+(j))*AAK+(k)]
#define BB(i,j,k) AA[((i)*BBM+(j))*BBK+(k)]
int i, j,k;
/* Выравнивание массива BB на массив AA с раздвижкой */
DVM(REALIGN BB[i][j][k] WITH AA[2*i][2*j][2*k] NEW);
/* формирование массива BB из элементов */
/* массива AA с четными индексами */
DVM(PARALLEL [i][j][k] ON BB[i][j][k])
DO(i,0,BBN-1,1)
DO(j,0,BBM-1,1)
DO(k,0,BBK-1,1)
BB(i,j,k)=AA(i*2,j*2,k*2);
#undef AA
#undef BB
}
int main()
{
int N1=8,M1=12,K1=16;
int N2,M2,K2;
int Narr=5,Nit=5;
int grid=0;
int ACM,ACK;
int i,j,k;
int step_grid=1;
int f_DVM=0;
/* 20 распределяемых массивов */
DVM(DISTRIBUTE[BLOCK][BLOCK][]) float *A[20];
/* Указатель на текущий распределенный массив */
DVM(*DISTRIBUTE[*][*][*]) float *AC;
/* создание массива A[0] */
A[grid]=malloc(N1*M1*K1*sizeof(float));
AC=A[grid];
ACM=M1;
ACK=K1;
#define AC(i,j,k) AC[((i)*ACM+(j))*ACK+(k)]
/* инициализация исходного массива */
DVM(PARALLEL [i][j][k] ON AC[i][j][k])
DO(i,0,N1-1,1)
DO(j,0,M1-1,1)
DO(k,0,K1-1,1)
AC(i,j,k)=1.+i+j+k ;
#undef AC
while (N2>2 && grid<Narr)
{
printf("N1=%d M1=%d K1=%d \n",N1,M1,K1);
N2=N1/2;
M2=M1/2;
K2=K1/2;
grid++;
/* создание массива A[grid] */
A[grid]=malloc(N2*M2*K2*sizeof(float));
oper(A[grid-1],N1,M1,K1,
A[grid],N2,M2,K2);
N1=N2;
M1=M2;
K1=K2;
}
for(i=0;i<=grid;i++)
free(A[i]);
return 0;
}
Синтаксис указаний описывается грамматикой БНФ со следующими обозначениями:
| ::= | является по определению, |
| | | альтернативная конструкция, |
| {x} | необязательная конструкция, |
| {y} . . . | повторение конструкции у от 0 до нескольких раз, |
| ряд-у | у { y } . . . |
| последовательность_y | y { ; y } . . . |
| имя-z | идентификатор. |
Каждое DVM-указание оформляется в виде следующего макроса:
dvm-макрос ::= DVM (dvm-указание) dvm-указание ::= dvm-описание | dvm-директива dvm-описание ::= distribute-описание | align-описание | parallel-описание | remote-access-описание | shadow-group-описание | reduction-group-описание dvm-директива ::= redistribute-директива | realign-директива | create-shadow-group-директива | shadow-start-директива | shadow-wait-директива | create-reduction-group-директива | reduction-start-директива | reduction-wait-директива | create-template-директива
DVM ( distribute-описание ) список-определений-распределяемых-объектов определение-распределяемого-объекта ::= определение-массива | определение-указателя | определение-указателя-на-массив | определение-массива-указателей
distribute-описание ::= DISTRIBUTE
ряд-распределений-измерений
{; distribute-дополнение }
распределение-измерения ::= BLOCK | [ ]
distribute-дополнение ::= shadow_определение | template-определение
shadow-определение ::= SHADOW ряд-определений-граней
определение-граней ::= [нижняя-грань : верхняя-грань ] | [грань] | [ ]
нижняя-грань, верхняя-грань, грань ::= целая-константа
template-определение ::= TEMPLATE ряд-размеров-измерений
размер-измерения ::= [ выражение ]
DVM ( align-описание )список-определений-выравниваемых-объектов
определение-выравниваемого-объекта ::= определение-массива
| определение-указателя-на-массив
| определение-массива-указателей
align-описание ::= ALIGN ряд-выравниваемых-измерений WITH
имя-базы ряд-измерений-выравнивания
{; shadow-определение }
выравнимое-измерение ::= имя-измерения | [ ]
имя-базы ::= имя-массива | имя-указателя
измерение-выравнивания ::= [ целое-выражение ]
| [ использование-имени-измерения ] | [ ]
использование-имени-измерения ::= {знак-операции} операнд-с-именем-измерения
{знак-операции целое-выражение }
| {целое-выражение знак-операции }
операнд-с-именем-измерения
операнд-с-именем-измерения ::= {целое-выражение * } имя-измерения
| имя-измерения { * целое-выражение }
знак-операции ::= + | -
create-template-директива ::= CREATE_TEMPLATE имя-указателя ряд-размеров-измерений
Ограничение : имя-указателя должно быть объявлено с описанием DISTRIBUTE.
redistribute-директива ::= REDISTRIBUTE
имя-распределяемого-объекта
ряд-распределений-измерений
{ NEW }
имя-распределяемого-объекта ::= имя-массива
| имя-указателя
realign-директива ::= REALIGN имя-массива
ряд-выравниваемых-измерений WITH
имя-базы ряд-измерений-выравнивания {NEW}
DVM ( parallel-описание ) ряд-макрозаголовков-цикла макрозаголовок-цикла ::= DO ( v, l, h, t ) | FOR ( v, h ) v ::= переменная l, h, t ::= выражение #define DO ( v, l, h, s ) for ( v = (l); v <=(h); v += (s)) #define FOR ( v, h ) for ( v =0; v < ( h ); v++)
parallel-описание ::= PARALLEL ряд-идентификаций-циклов
ON имя-базы ряд-выравниваний-витков
{; последовательность-parallel-дополнений }
идентификация-цикла ::= [ индексная-переменная-цикла]
выравнивание-витков ::= [ целое-выражение ]
| [использование-индексной-переменной-цикла ] | [ ]
использование-индексной-переменной-цикла ::= {знак-операции}
операнд-с-индексом-цикла
{знак-операции целое-выражение }
| {целое-выражение знак-операции }
операнд-с-индексом-цикла
операнд-с-индексом-цикла ::= {целое-выражение * } индексная-переменная-цикла
| индексная-переменная-цикла {* целое-выражение }
parallel-дополнение ::= reduction-определение
| shadow-renew-определение
| shadow-start-директива
| shadow-wait-директива
| remote-access-описание
reduction-определение ::= REDUCTION ряд-редукций
редукция ::= имя-редукционной-операции
( редукционная-переменная )
| имя-редукционной-операции-loc
( редукционная-переменная
{, редукционный-индекс } . . .)
имя-редукционной-операции ::= SUM | PRODUCT | MAX | MIN | OR | AND
имя-редукционной-операции-loc ::= MAXLOC | MINLOC
DVM ( REDUCTION_GROUP ) void * имя-группы-редукций
create-reduction-group-директива ::= CREATE_REDUCTION_GROUP имя-группы-редукций : ряд-редукций
reduction-start-директива ::= REDUCTION_START имя-группы-редукций
reduction-wait-директива ::= REDUCTION_WAIT имя-группы-редукций
shadow-renew-определение ::= SHADOW_RENEW
ряд-массивов-с-обновляемыми-гранями
массив-с-обновляемыми-гранями ::= имя-массива { ряд-определений-граней }
{ CORNER }
DVM ( SHADOW_GROUP ) void * имя-группы-граней
create-shadow-group-директива ::= CREATE_SHADOW_GROUP
имя-группы-граней :
ряд-массивов-с-обновляемыми-гранями
shadow-start-директива ::= SHADOW_START имя-группы-граней
shadow-wait-директива ::= SHADOW_WAIT имя-группы-граней
DVM ( remote-access-описание ) оператор-языка-СИ
remote-access-описание ::= REMOTE_ACCESS ряд-удаленных-данных удаленные-данные ::= имя-массива ряд-удаленных-индексов удаленный-индекс ::= [ индексное-выражение ] | [ ]
DVM ( описание-косвенной-спецификации ) ссылки-на-распределенные-массивы
описание-косвенной-спецификации ::= * distribute-описание
| * DISTRIBUTE [ * ] { [ * ]} . . .
| *
ссылки-на-распределенные-массивы ::= определение-формальных_параметров-массивов
| определение-указателей-на-распределенные-массивы
| определение-заголовка-функции
| Оглавление | Часть 1 | Часть 2 | C-DVM - часть 3 |