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

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

Constraints.

• Repeated usage of PREFETCH directive is correct, if the remote reference group characteristics (the loop parameters, distribution of arrays and the values of index expressions in remote references) are not updated;

• PREFETCH directive can be executed for several loops (several REMOTE_ACCESS directives), if there are no data dependencies between the loops for distributed arrays, specified in REMOTE_ACCESS directives.

If remote reference group characteristics are updated it is necessary to assign to the group undefined value using RESET directive. The new accumulation of remote reference group will be performed.

Consider the following fragment of multi-block problem. Simulation area is split on 3 blocks as is shown in fig. 6.3.

	M
N1	A1
				D
N2	A2	A3
	M1	M2

Fig. 6.3. Splitting simulation area.

Example 6.6. Using named group of regular remote references.

DVM (DISTRIBUTE [BLOCK][BLOCK])

float A1[M][N1+1], A2[M1+1][[N2+1], A3[M2+1][N2+1];

DVM (REMOTE_GROUP) void *RS;

DO(ITER,1, MIT,1)

{

. . .

/* edge exchange by split line D */

DVM (PREFETCH RS);

. . .

DVM ( PARALLEL[i] ON A1[i][N1]; REMOTE_ACCESS RS: A2[i][1])

DO(i,0, M1-1,1)

A1[i][N1] = A2[i][1];

DVM (PARALLEL[i] ON A1[i][N1]; REMOTE_ACCESS RS: A3[i-M1][1])

DO(i,M1, M-1,1)

A1[i][N1] = A3[i-M1][1];

DVM (PARALLEL[i] ON A2[i][0]; REMOTE_ACCESS RS: A1[I][N1-1])

DO(i,0, M1-1,1)

A2[i][0] = A1[i][N1-1];

DVM(PARALLEL[i] ON A3[i][0]; REMOTE_ACCESS RS: A1[I+M1][N1-1])

DO (i,0, M2-1,1) A3[i][0] = A1[i+M1][N1-1];

. . .

if (NOBLN) {

/*array redistribution to balance loading */

. . .

DVM (RESET RS);

}

. . .

} /*DO ITER*/

6.4Remote references of REDUCTION type

6.4.1Synchronous specification of remote references of REDUCTION type

If in a parallel loop REDUCTION specification hasn't group name, it is synchronous specification and executed in two steps.

• Local reduction calculation: During the loop execution on each processor local value of reduction is calculated for the data part, located at the processor.

• Global reduction calculation: After the loop completion interprocessor reduction of local values is calculated. Resulted value is assigned to the reduction variable on each processor.

6.4.2Asynchronous specification of remote references of REDUCTION type

Asynchronous specification allows:

• to joint in one group reduction variables, calculated in different loops,

• to overlap execution of global group reduction with other computations.

For asynchronous specification besides REDUCTION directive (with group name) the following additional directives are required.

Constraints.

• Before executing REDUCTION_START directive, the reduction variables of the group may be used in reduction statements of parallel loops only.

• REDUCTION_START and REDUCTION_WAIT directives must be executed after the completion of the loop (loops) where the local values of the reduction variables were calculated. The only statements allowed between these directives are those that don't use the reduction variable values.

• REDUCTION_WAIT directive deletes the reduction operation group.

Example 6.7. Asynchronous reduction of REDUCTION type.

DVM(REDUCTION_GROUP) void *RG;

. . .

S = 0;

X = A[1];

Y = A[1];

MINI = 1;

DVM(PARALLEL[I] ON A[I]; REDUCTION RG: SUM(S), MAX(X), MINLOC(Y,MIMI))

FOR(I, N)

{ S = S + A[I];

X =max(X, A[I]);

if(A[I] < Y) THEN { Y = A[I]; MINI = I;}

}

DVM(REDUCTION_START RG);

DVM(PARALLEL[I] ON B[I])

FOR( I, N)

B[I] = C[I] + A[I];

DVM(REDUCTION_WAIT RG);

printf("%f %f %f %d\n", S, X, Y, MINI);

While the reduction group is executed the values of array B elements will be computed.

7Task parallelism

DVM parallelism model joins data parallelism and task parallelism.

Task parallelism is implemented by independent computations processor arrangement sections.

Let us define a set of virtual processors, where a procedure is executed, as current virtual processor system. For main procedure the current system consists of total set of virtual processors.

The separate task group is defined by the following directives.

• Description of task array (TASK directive).

• Mapping task array on the sections of the processor arrangement (MAP directive).

• Creation of data arrays and their distribution over the tasks and thus over the processor arrangement sections (malloc statement and REDISTRIBUTE and REALIGN directives).

• Distribution of computations (statement blocks or parallel loop iterations) over tasks (TASK_REGION construction).

Several task array can be described in one procedure. Nested tasks are not allowed.

7.1Description of task group

A task array is described by the following directive:

Task group description defines one-dimensional array of the tasks, which will be mapped then on the processor arrangement sections.

7.2Mapping tasks on processors. MAP directive

The task mapping on processor arrangement section is performed by MAP directive

Several tasks can be mapped on the same section, but different sections can not have common processors.

7.3Array distribution on tasks

Array distribution over the tasks are performed by REDISTRIBUTE directives with the following extension:

The array is distributed on processor arrangement section, assigned to the task.

7.4Distribution of computations. TASK_REGION directive

Distribution of statement blocks over the tasks is described by construction TASK_REGION:

Task region and each on-block are sequences of the statements with one entrance (the first statement) and one exit (after the last statement). For the statement blocks construction TASK_REGION is semantically equivalent to parallel section construction for shared memory systems. The difference is that the statement block can be executed on several processors in data parallel model.

A distribution of the parallel loop iterations on tasks is performed by the following construction:

Distributed computation unit is an iteration of one-dimensional parallel loop. The difference from usual parallel loop is the distribution of the iteration on the processor arrangement section, the section being defined by reference to the element of the task array.

Semantics of reduction-clause is the same as for paralle-loop-directive. Reduction variable value must be calculated in each task. After task completion (END TASK_REGION) in the case of synchronous specification the reduction over all values of reduction variable on all the tasks are automatically performed. In the case of asynchronous specification the reduction is started by REDUCTION_START directive.

7.5Data localization in tasks

A task is on-block or loop iteration. The tasks of the same group have the following constraints on data

• there are no data dependencies;

• all used and computed data are allocated (localized) on the processor arrangement section of given task;

• after the task completion each array must have same distribution as before the task startup. If the array distribution is changed in the task, it must be restored after the task completion.

• there is no input/output;

• task can update only the values of arrays, distributed on the section, and private variable values.

7.6Fragment of static multi-block problem

The program fragment, describing realization of 3-block task (fig.6.2) is presented below.

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

/* arrays A1,A2,A3 - the values on the previous iteration */

/* arrays В1,В2,В3 - the values on the current iteration */

DVM(DISTRIBUTE) float (*A1)[N1+1],(*A2)[N2+1],(*A3)N2+1];

DVM(ALIGN) float (*B1)[N1+1], (*B2)[N2+1], (*B3)[N2+1];

/* description of task array */

DVM(TASK) void *MB[3];

DVM (REMOTE_GROUP) void *RS;

. . .

/* distribution of tasks on processor arrangement */

/* sections and distribution of arrays on tasks */

/* (each section contain third of all the processors) */

NP = NUMBER_OF_PROCESSORS()/3;

DVM(MAP MB[1] ONTO P(0: NP-1));

A1=malloc(M*(N1+1)*sizeof(float));

DVM(REDISTRIBUTE A1[][BLOCK] ONTO MB[1]);

B1=malloc(M*(N1+1)*sizeof(float));

DVM(REALIGN B1[i][j] WITH A1[i][j]);

DVM(MAP MB[2] ONTO P( NP : 2*NP-1));

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

DVM(REDISTRIBUTE A2[][BLOCK] ONTO MB[2]);

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

DVM(REALIGN B2[i][j] WITH A2[i][j]);

DVM(MAP MB[3] ONTO P(2*NP : 3*NP-1));

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

DVM(REDISTRIBUTE A3[][BLOCK] ONTO MB[3]);

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

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