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

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

DVM(DISTRIBUTE [BLOCK][BLOCK]) float (*C)[N];

/* two-dimensional distributed dynamic array */

4.2.3. Simulation of multidimensional arrays via one-dimensional ones.

If it is necessary to use multidimensional arrays with calculated sizes in C language, programmers apply the following method. Instead of multidimensional array a one-dimensional array of required size is created. Access to elements of the simulated multidimensional array is carried out using notation of the form arrid(ind₁,...,ind_n) similar to array element designators in Fortran. This notation is interpreted as reference to the corresponding elements of the one-dimensional array by means of C preprocessor macro features.

When C-DVM compiler is used, such notations are considered as multidimensional array element designators, if this one-dimensional array is specified as multidimensional distributed array by DISTRIBUTE or ALIGN directive. Macro providing access to elements of the simulated array is ignored in this case.

An example of array declaration (one-dimensional for sequential execution and two-dimensional for parallel execution) and references to its elements:

int Cdim2; /* The second dimension of array C */

DVM (DISTRIBUTE [BLOCK][]) float *C;

#define C(x,y) C[(x)*Cdim2+(y)]

. . .

C(i,j) = (C(i,j-1)+C(i,j+1))/2;

4.3. Distributing by aligning

Aligning array A with distributed array B brings in accordance to each element of A an element or a section of array B. When distributing array B the array A will be distributed simultaneously. If element of B is mapped on the processor, then the element of A, corresponding to element B via alignment, will be also mapped on the same processor.

Method of mapping via alignment performs the following two functions.

1. The same distribution of the arrays of the same shape on one processor arrangement does not always guarantee allocation of corresponding elements on the same processor. It forces to specify remote access (see section 6) where it is possible not exist. Only alignment of corresponding elements of the arrays guarantees their allocation on the same processor.

2. Several arrays can be aligned with the same array. Redistribution of one array by REDISTRIBUTE directive will cause corresponding redistribution of the array group.

4.3.1. ALIGN and REALIGN directives

The following directives describe array aligning:

Constraints:

• A length of the align-source-string must be equal to the rank of aligned array.

• A length of the align-subscript-string must be equal to the rank of base array align-target.

• If align-directive-stuff is omitted in ALIGN directive, then the distributed array can be used only after execution of REALIGN directive.

Let the alignment of two arrays is specified by the directive

DVM(ALIGN [d₁]…[d_n] WITH B[ard₁]…[ard_m]) float A[100]…[100];

where d_i is specification of i-th dimension of aligned array А,

ard_j is specification of j-th dimension of base array В,

If d_i is specified by integer variable I, then there must be one and the only dimension of array B, specified by linear function ard_j = a*I + b. Therefore, the number of array A dimensions, specified by identifiers (align-dummy) must be equal to the number of array B dimensions, specified by the linear function.

Let i-th dimension of array A has bounds LA_i : HA_i , and j-th dimension of array B, specified by linear function a*I + b, has the bounds LB_j : HB_j. Since the parameter I is defined on the value set LA_i : HA_i, then the following conditions must be satisfied:

a*LA_i + b  LB_j , а* HA_i + b  HB_j

If d_i is empty, the i-th dimension of array А will be local on each processor independently from array B distribution (it is analogue of local dimension in DISTRIBUTE directive).

If ard_i is empty, then the array А will be replicated along the j-th dimension of the array В.

If ard_i is integer, then the array А is aligned with the section of the array В.

Example 4.7. Aligning arrays

DVM(DISTRIBUTE [BLOCK ][BLOCK ]) float B[10][10];

DVM(DISTRIBUTE [BLOCK ]) float D[20];

/* aligning with the array section (the vector is aligned with the first line of B) */

DVM(ALIGN [i] WITH B[1][i] ) float A[10];

/* replication of the vector aligning it with each line */

DVM(ALIGN [ i] WITH B[][ i]) float F[10];

/* the matrix is collapsed; each matrix column corresponds to the vector element */

DVM(ALIGN [][ i] WITH D[ i]) float C[20][20];

/* alignment of vector with vector using stretching */

DVM(ALIGN [ i] WITH D[ 2*i]) float E[10];

/* alignment vector with vector using reverse ordering */

DVM(ALIGN [ i] WITH D[ -i + 19] float G[20];

/* alignment matrix with matrix using rotation and stretching */

DVM(ALIGN [i][ j] WITH C[ 2*j][ 2*i] ) float H[10,10];

Let the sequence of alignments A f1 B f2 C, be specified; f2 is alignment of the array В with the array С , and f1 is alignment of the array А with the array В. The arrays А and В are considered as aligned with array C by definition. The array B is aligned by function f2 directly and array A is aligned by composite function f1(f2) indirectly. Therefore applying REALIGN directive to the array B does not cause redistribution of array A.

4.3.2. TEMPLATE and CREATE_TEMPLATE directives

If values of linear function a*I + b are beyond base array dimension, it is necessary to define a dummy array - referred to as an alignment template – using the following directive.

Then it is necessary to align both arrays with the template. The template is defined using DISTRIBUTE directive. The template elements are mapped among processors without real memory allocation. They specify a processor on which elements of aligned arrays must be mapped.

In the following example to avoid exchange between processors, it is necessary to allocate the elements A[i], B[i+1], C[i-1] on the same processor. It is impossible to align arrays C and B with array A, because alignment functions I-1 and I+1 cause bounds violation of array A. Therefore the template TABC is described. The elements of arrays A, B and C, which must be on the same processor, are aligned with the one element of the template.

Example 4.8. Aligning with template.

DVM(DISTRIBUTE [BLOCK]; TEMPLATE [102]) void * TABC;

DVM(ALIGN B[i] WITH TABC[ i ]) float B[100];

DVM(ALIGN A[i] WITH TABC[ i + 1] ) float A[100];

DVM(ALIGN C[i] WITH TABC[ i + 2] ) float C[100];

. . .

DO(i ,1, 98,1) A[i] = C[i-1] + B[i+1];

If the size of template (and arrays) is not known statically the following executable-directive should be used:

Example 4.9. Aligning dynamic arrays with template.

DVM(DISTRIBUTE [BLOCK]; TEMPLATE ) void * TABC;

DVM(ALIGN B[i] WITH TABC[ i ]) float *B;

DVM(ALIGN A[i] WITH TABC[ i + 1] ) float *A;

DVM(ALIGN C[i] WITH TABC[ i + 2] ) float *C;

int N;

…

N=…;

DVM(CREATE_TEMPLATE TABC[N]);

A=malloc(N*sizeof(float));

B=malloc(N*sizeof(float));

C=malloc(N*sizeof(float));

. . .

DO(i ,1, N-2,1) A[i] = C[i-1] + B[i+1];

4.4. Non-distributed data

If DISTRIBUTE or ALIGN directive (see section 4.3) is not specified for the data, then the data are placed on each processor (full replication). For arrays the difference with DISTRIBUTE []… (with format [] for each dimension) is that the access to the data is not controlled by the RTL-system.

5. Distribution of Computations

5.1. Model of computation distribution

The execution model of CDVM program as the programs in other languages with data parallelism is SPMD (single program, multiple data). All the processors are loaded by the same program, but each processor performs only those assignment statements that modify its own variables, that is, the variables located on this processor. This order is named the rule of own computations.

Thus computations are distributed in accordance with data mapping (data parallelism). In the case of a replicated variable, the assignment statement is performed at all the processors. In the case of a distributed array, the assignment statement is performed only at the processor (or processors) where the corresponding array element is located.

Identification of "own" statements and missing "others" can cause essential overhead when a program executing. Therefore CDVM requires explicit specification of distributed computations. Computations to be distributed are iterations of the loops, declared as "parallel" by the programmer. It is necessary to distinguish two kinds of distributed loops:

• loops with regular computations,

• loops with irregular computations.

The other computations are defined as non-distributed or replicated computations.

5.2. Distribution of loop iterations with regular computations

5.2.1. Definition of distributed loop with regular computations

A distributed loop with regular computations has to satisfy the following requirements:

• the loop is tightly nested one with rectangular index space;

• distributed dimensions are indexed only by linear expressions of the form a*I + b , where I - is loop index.

• left sides of assignment statements of one loop iteration are allocated at the same processor (non-distributed iteration of the loop)

• there is no data dependencies except reduction dependence and regular dependence along distributed dimensions;

• left side of assignment statement is an element of distributed array, reduction variable or private variable (see section 5.2.3);

• there are no I/O statements, REDISTRIBUTE and REALIGN directives in the loop.

5.2.2. Distribution of loop iterations. PARALLEL directive

If a loop satisfies to conditions of distributed loop with regular computations, then it is specified by the following directive:

PARALLEL directive is placed before loop header and distributes loop iterations in accordance with array or template distribution. The directive semantics is similar to semantics of ALIGN directive, where index space of distributed array is replaced by loop index space. The order of loop indexes in list do-variable-list corresponds to the order of corresponding DO statements in tightly nested loop. Note that loop headers should be written with macros DO and FOR.

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

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