Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

B3=malloc((M1+1)*(N2+1)*sizeof(float));

DVM(REALIGN B3[i][j] WITH A3[i][j]);

. . .

FOR(IT,MAXIT)

{. . .

DVM(PREFETCH RS);

/* exchanging edges of adjacent blocks */

. . .

/* distribution of statement blocks on tasks */

DVM(TASK_REGION MB)

{

DVM(ON MB[1]) JACOBY(A1, B1, M, N1+1);

DVM(ON MB[2]) JACOBY(A2, B2, M1+1, N2+1);

DVM(ON MB[3]) JACOBY(A3, B3, M2+1, N2+1);

} /* TASK_REGION */

} /* FOR */

7.7Fragment of dynamic multi-block problem

Let us consider the fragment of the program, which is dynamically tuned on a number of blocks and the sizes of each block.

#define NA 20 /* NA - maximal number of blocks */

DVM(PROCESSORS) void *R[NUMBER_OF_PROCESSORS()];

int SIZE[2][NA]; /* sizes of dynamic arrays */

/* arrays of pointers for A and B */

DVM(* DISTRIBUTE) float *PA[NA];

DVM(* ALIGN) float *PB[NA];

DVM(TASK) void *PT[NA];

. . .

NP = NUMBER_OF_PROCESSORS( );

/* distribution of arrays on tasks */

/* dynamic allocation of the arrays */

/* and execution of postponed directives */

/* DISTRIBUTE and ALIGN */

FOR(i,NA)

{

DVM(MAP PT[I] ONTO R[ i%(NP/2) : i%(NP/2)+1] );

PA[i] = malloc(SIZE[0][i]*SIZE[1][i]*sizeof(float));

DVM(REDISTRIBUTE (PA[i])[][BLOCK] ONTO PT[I]);

PB[i] = malloc(SIZE[0][i]*SIZE[1][i]*sizeof(float));

DVM(REALIGN (PB[i])[I][J] WITH (PA[i])[I][J])

} /*FOR i */

. . .

/* distribution of computations on tasks */

DVM(TASK_REGION PT) {

DVM(PARALLEL[i] ON PT[i])

FOR(i,NA)

JACOBY(PA[i], PB[i], SIZE[0][i], SIZE[1][i]);

}

} /* TASK_REGION */

The arrays (blocks) are cyclically distributed on 2-processor sections. If NA > NP/2, then several arrays will be distributed on some sections. The loop iterations, distributed on the same section, will be executed sequentially in data parallel model.

8Procedures

Procedure call inside parallel loop.

A procedure, called inside parallel loop, must not have side effects and contains processor exchanges (purest procedure). As a consequence, the purest procedure doesn't contain nput/output statements and DVM-directives.

Procedure call outside parallel loop.

If the actual argument is explicitly distributed array (by DISTRIBUTE or ALIGN), it should be passed without shape changing. It means, that actual argument is the reference to the array beginning, and the actual and corresponding formal arguments have the same configuration.

Formal parameters.

If an actual parameter of a procedure may be a distributed array then corresponding formal parameter must be specified in the following way:

• If the actual parameter is a distributed array with known distribution rules, then

DVM(*DISTRIBUTE rd1...rdN);

• If the rank is known, but the distribution is not, then

DVM(*DISTRIBUTE[*]...[*]);

• If the actual parameter is an arbitrary array (distributed array or non-distributed), then

DVM(*).

Such formal parameters may be used only in fread/fwrite functions.

Local arrays.

In the procedure local arrays can be distributed by DISTRIBUTE and ALIGN directives. A local array can be aligned with formal parameter. The DISTRIBUTE directive distributes the local array on the processor subsystem, on which the procedure was called (current subsystem). If a processor arrangement section is specified in DISTRIBUTE directive, then the number of the processors must be equal to the number of processors of the current subsystem.

Example 9.1. Distribution of the local arrays and formal arguments.

void dist(

/* explicit distribution of formal argument */

DVM(*DISTRIBUTE[][BLOCK]) float *A /* N*N */,

/* aligned formal argument */

DVM(*ALIGN [i][j] WITH A[i][j]) float *B /* N*N */,

/* inherited distribution of the formal argument */

DVM(*) float *C /* N*N */ ,

int N)

{

DVM(PROCESSORS) void *PA[ACTIVE_NUM_PROC()];

/* local array aligned with formal argument */

DVM(ALIGN[I][J] WITH C[I][J]) float *X;

/* distributed local array */

DVM(DISTRIBUTE [][BLOCK] ONTO PA) float *Y;

}

Note. The sizes of actual parameter arrays are unknown. So the technique of dealing with dynamic multidimentional arrays described in section 4.2.3 should be used.

9Input/output

In C-DVM, the following I/O statements are allowed for replicated data:

fopen, fclose, feof, fprintf, printf, fscanf, fputc, putc, fputs, puts, fgetc, getc, fgets, gets, fflush, fseek, ftell, ferror, clearerr, perror, as well as fread, fwrite.

These statements are executed on the certain processor (input/output processor). Output values are taken from this processor, and input data are input on this processor and sent to others.

Only unformatted I/O of the whole array by fread/fwrite functions is allowed for distributed arrays.

The I/O functions cannot be used in a parallel loops and in TASK_REGION blocks. because output data will be written in the file (printed) in arbitrary order.

10Restrictions on C language usage

C-DVM is intended for parallelization of computational programs, written in "Fortran-like" style. At that there are some restrictions on the usage of C language tools. First of all these restrictions concern the usage of the pointers to distributed arrays and their elements. C-DVM doesn't prohibit using the pointers, but some operations with them can become incorrect after the program conversion. For example:

• identifier of an array (or the array pointer) becomes the identifier of integer array (so called array handler);

• processor contains only the local part of the array, therefore relative access to its elements by the pointer arithmetic is impossible;

• when redistributing the array, the contents and location of the array local part are changed, so saved pointers to the array elements became invalid.

The second restriction concerns data types: distributed array elements can have only scalar types int, long, float and double.

Then some descriptions require execution of certain actions for parallelization. They are, for example:

• descriptions of processor sections and task arrays (but not the task mapping);

• description of distributed arrays or templates with constant dimensions ("static" ones);

• initialization of the variables (their registration is required for the debugger).

Such implicit actions for global objects are executed at the function main beginning immediately after Run-Time System initialization. Therefore at the time main function is generated all such objects must be known, that is they can't be located in separately compiled file or follow main function description. For objects, local in a function or in a program block, these actions are performed before first statement of the block. Moreover, note, that implicit actions are performed in the order of descriptions, and it causes certain semantic restrictions on the description order: the base of ALIGN must be described before aligned array and so on.

At last, preprocessor usage beyond header files requires a care for several reasons. First, C-DVM compiler operates before the preprocessor. So, for example, the pair of definitions

#define begin {

#define end }

can make the program absolutely not understandable for the compiler. For the same reason DVM-directives remain unknown to the compiler. Therefore, distributed data must be explicitly described in every file. Second, to deal with multidimensional arrays (see section 4.2) it is suggested to use the preprocessor for temporary redefinition of the array sizes as constants or for redefinition of the macrocomands, simulating multidimensional array via one-dimensional one. In converted program corresponding preprocessor directives must be excluded. It is implemented by placing all preprocessor directives in source order at the beginning of output file. (Note, that for every auxiliary directive #define the directive #undef, disabling it, is required.)

11The difference between CDVM versions 1.0 and 2.0

CDVM 1.0 is a subset of CDVM 2.0. The following new possibilities are provided:

• Explicit definition of processor arrangements (section 3).

• Task parallelism (section 7).

• GEN_BLOCK and WGT_BLOCK format for array distribution (section 4.1.2, 4.1.3).

• Distribution of a loop with regular dependences on data (section 6.2.3).

11.1Array section copy

C-DVM language provides the tools for distributed array (distributed array section) copy, that allow to ensure overlapping data exchange with computations.

Rectangular array section is specified by triplets (<first>:<last>:<step>) for every dimension of array. For assignement both sections should be of the same rank, i.e. the same number of nonsingular dimensions (arrays themselves may be of different ranks), and should have the same number of elements in corresponding nonsingular dimensions of the source and destination sections.

In order to C-DVM program can be compiled and executed as usual sequential program, an array (array section) copy is written as ordinary multidimensional loop. The loop body should consist of a single assignement statement. The loop headers should be written by the DO(v,first,last,step) or FOR(v,times) macros. All the loop variables should be used in index expressions in right and left sides of the assignement statement, and in the same order. Every index expression may contain only one loop variable and should depend on it linearly.

For asynchronous copy it is neccessary:

• to declare a copy operation completion flag variable by the COPY_FLAG directive;

• to specify the loop by the COPY_START directive with the address of the flag variable;

• to wait for completion of copy operation by the COPY_WAIT directive with the address of the same flag variable before using of copied values.

Example 11.1. Asynchronous array copy.

DVM(DISTRIBUTE [BLOCK][]) float A[N][N];

DVM(ALIGN [i][j] WITH [j][i]) float B[N][N];

. . .

DVM(COPY_FLAG) void * flag;

. . .

DVM(COPY_START &flag)

FOR(i,N)

FOR(j,N)

B[i][j]=A[i][j];

. . .

DVM(COPY_WAIT &flag);

If computation-communication overlapping is not required, it is possible slightly simplify the program using the synchronous copy directive COPY.

Example 11.2. Synchronous copy.

DVM(COPY)

FOR(i,N)

FOR(j,N)

B[i][j]=A[i][j];

Syntax rules.

References

1. N.A.Konovalov, V.A.Krukov, S.N.Mihailov and A.A.Pogrebtsov, “Fortran-DVM language for portable parallel programs development”, Proceedings of Software for Multiprocessors & Supercomputers: Theory, Practice, Experience (SMS-TPE 94), Inst. for System Programming RAS, Moscow, Sept. 1994. .

2. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 2.0, January 31, 1997.

Appendix 1. Examples of C-DVM programs

Six small scientific programs are presented to illustrate C-DVM language features. They are intended for solving a system of linear equations:

A x = b

where A - matrix of coefficients,

b - vector of free members,

x - vector of unknowns.

The following basic methods are used to illustrate CDVM language features.

Direct methods. The well-known Gaussian Elimination method is the most commonly used algorithm of this class. The main idea of this algorithm is to reduce the matrix A to upper triangular form and then to use backward substitution to diagonalize the matrix.

Explicit iteration methods. Jacobi Relaxation is the most known algorithm of this class. The algorithm performs the following computation iteratively

x_i,j^new = ( x_i-1,j^old + x_i,j-1^old + x_i+1,j^old + x_i,j+1^old ) / 4

Implicit iteration methods. Successive Over Relaxation (SOR) belongs to this class. The algorithm performs the following calculation iteratively

Характеристики

Список файлов учебной работы