50

Keldysh Institute of Applied Mathematics

Russian Academy of Sciences

C-DVM

Version 2.0

Language description

April, 2001

Contents

1 Introduction 4

2 Language overview 5

2.1 Programming model and model of parallelism 5

2.2 Syntax of DVM-directives 6

3 Virtual processor arrangements. PROCESSORS directive 7

4 Data Mapping 8

4.1 DISTRIBUTE and REDISTRIBUTE directives 8

4.1.1 Format BLOCK 9

4.1.2 Format GENBLOCK 9

4.1.3 WGTBLOCK format 10

4.1.4 Format [] 11

4.1.5 Multidimensional distributions 11

4.2 Multidimensional dynamic arrays 11

4.2.1 Dynamic arrays in C program 11

4.2.2 Using C-style multidimensional arrays 12

4.2.3 Simulation of multidimensional arrays via one-dimensional ones 12

4.3 Distributing by aligning 13

4.3.1 ALIGN and REALIGN directives 13

4.3.2 TEMPLATE and CREATE_TEMPLATE directives 15

4.4 Undistributed data 16

5 Distribution of computations 16

5.1 Parallel loops 16

5.1.1 Parallel loop definition 16

5.1.2 Distribution of loop iterations. PARALLEL directive 17

5.1.3 Private variables 18

5.1.4 Reduction operations and variables. REDUCTION specification 18

5.2 Calculations outside parallel loop 19

6 Remote data specification 20

6.1 Remote reference definition 20

6.2 Remote references of SHADOW type 21

6.2.1 Specification of array with shadow edges 21

6.2.2 Specification of independent references of SHADOW type for one loop 22

6.2.3 ACROSS specification of dependent references of SHADOW type for single loop 23

6.2.4 Asynchronous specification of independent references of SHADOW type 24

6.3 Remote references of REMOTE type 25

6.3.1 REMOTE_ACCESS directive 25

6.3.2 Synchronous specification of remote references of REMOTE type 26

6.3.3 Asynchronous specification of remote references of REMOTE type 26

6.4 Remote references of REDUCTION type 28

6.4.1 Synchronous specification of remote references of REDUCTION type 28

6.4.2 Asynchronous specification of remote references of REDUCTION type 28

7 Task parallelism 29

7.1 Description of task group 30

7.2 Mapping tasks on processors. MAP directive 30

7.3 Array distribution on tasks 30

7.4 Distribution of computations. TASK_REGION directive 30

7.5 Data localization in tasks 31

7.6 Fragment of static multi-block problem 31

7.7 Fragment of dynamic multi-block problem 32

8 Procedures 33

9 Input/output 34

10 Restrictions on C language usage 34

11 The difference between CDVM versions 1.0 and 2.0 35

11.1 Array section copy 36

References 37

Appendix 1. Examples of C-DVM programs 37

Example 1. The Gauss elimination algorithm 38

Example 2. Jacobi algorithm 39

Example 3. Jacobi Algorithm (asynchronous version) 40

Example 4. Red-Black Successive Over-Relaxation 41

Example 5. Multigrid method program 43

Example 6. Task Parallelism for Multiblock Code 44

Appendix 2. Syntax summary 46

1Introduction

C-DVM language was designed to support the development of portable and efficient parallel computational applications. The language is an extension of C language according to DVM model developed in Keldysh Institute of Applied Mathematics [1].

Traditionally applications for serial computers were created using Fortran and C languages. At present such applications are created for multiprocessor computers with distributed memory and networks using as a rule Fortran 77 and C extended by message transfer libraries (PVM, MPI). The development of such parallel applications requires from a programmer far more efforts than development of sequential ones, as the programmer has to distribute data and computations between different processors and also provide interaction of processors via message passing. Actually, the parallel application is a system of interacting programs, each program running at its own processor. The programs running at different processors may be either quite different, or may differ a little, or may be the same program whose behavior depends on the processor number. However, even in the last case the programmer is forced to develop and maintain two versions of the program - the sequential and parallel ones.

Using C-DVM language the programmer deals with the only version of the program both for sequential and parallel execution. Besides algorithm description by means of usual C features the program contains rules for parallel execution of the algorithm. These rules are syntactically organized in such a manner that they are "transparent" for standard C compilers at serial computers. Therefore it is possible to execute and to debug the C-DVM program at workstations as a usual sequential one.

Thus the C-DVM language is a standard C language extended by features to describe the rules of parallel program execution. The C-DVM language provides:

• distribution of array elements over the processors;

• distribution of loop iterations over the processors;

• specification of parallel executed program sections (parallel tasks) and their mapping on the processors;

• organization of efficient access to remote data (the data located at other processors);

• organization of efficient execution of reduction operations, that is global operations on the data located at different processors (such as summing values or finding their maximal and minimal values).

To create C-DVM programs the special system of parallel program development automation, named DVM-system, is provided.

DVM-system provides unified toolkit to develop parallel programs of scientific-technical calculations in C and Fortran 77.

DVM parallel model. DVM parallel model is based on data parallel model. The DVM name reflects two names of the model - Distributed Virtual Memory and Distributed Virtual Machine. These two names show that DVM model is adopted both for shared memory systems and for distributed memory systems. DVM high level model allows not only to decrease cost of parallel program development but provides unified formalized base for supporting Run-Time System, debugging, performance analyzing and prediction.

Languages and compilers. As distinct from HPF standard the goal of full automation of computation parallelization and the common data access synchronization is not assumed in DVM system. Using high-level specifications, a programmer has full control of parallel program performance.

Unified parallel model is built in C and Fortran 77 language on the base of the constructions that are "transparent" for standard compilers that allows to have single version of the program for sequential and parallel execution. C-DVM and Fortran DVM compilers translate DVM-program in C or Fortran 77 program correspondently, including parallel execution Run-Time Support system calls. So only requirement to a parallel system is availability of C and Fortran 77 compilers.

Execution and debugging technics. Unified parallel model allows to have unified Run-Time Support system for both languages and, as result, unified system of debugging, performance analyzing and prediction. There are following modes of DVM-program execution and debugging:

• Sequential execution and debugging using standard C and Fortran 77 compiler tools.

• Pseudo-parallel execution and debugging on work station (WINDOWS and UNIX environment).

• Parallel execution and debugging on parallel computer.

Following debugging modes are provided in pseudo-parallel and parallel execution modes:

• automatic verification of parallel directive correctness;

• tracing and comparing the results of parallel and sequential execution;

• accumulation and visualization of data trace;

• performance information accumulation and parallel execution performance prediction.

2Language overview

2.1Programming model and model of parallelism

C-DVM language is an extension of ANSI-C language with annotations named DVM-directives. The directives are implemented as parameters of

DVM(<directive>)

macro, which in sequential program is expanded to empty string.

DVM-directives may be conditionally divided on three subsets:

• Data distribution directives (sections 4);

• Computation distribution directives (sections 5, 7);

• Remote data specifications (section 6).

DVM model of parallelism is based on specific form of data parallelism called SPMD (Single Program, Multiple Data). In this model all the processors concerned execute the same program, but each processor performs its own subset of statements in accordance with the data distribution.

In DVM model at first a user defines multidimensional arrangement of virtual processors, which sections data and computations will be mapped on. The section can be varied from the whole processor arrangement up to a single processor.

Then the arrays to be distributed over processors (distributed data) are determined. These arrays are specified by data mapping directives (section 4). The other variables (distributed by default) are mapped by one copy per each processor (replicated data). A value of replicated variable must be the same on all the processors concerned. Single exception of this rule is variables in parallel loop (section 5.1.3 and 5.1.4).

Data mapping defines a set of local or own variables for each processor. A set of own variables determines the rule of own computations: the processor assigns the values to its own variables only.

DVM model defines two levels of parallelism:

• data parallelism;

• task parallelism.

Data parallelism is implemented by distribution of tightly enclosed loop iterations over the processors of the processor arrangement (or the arrangement sections) (see section 5). The loop iteration is executed on one processor entirely. The statements located outside of the parallel loop are executed according to the rule of own computations (see section 5.2).

Task parallelism is implemented by the distribution of data and computations over disjoined sections of processor arrangement (see section 7).

When calculating the value of own variable, the processor may need in values of both own and other (remote) variables. All remote variables must be specified in remote data access directives (see section 6).

2.2Syntax of DVM-directives

The syntax of DVM-directives is described using a Backus-Nour grammar and the following notations:

::=	is by definition,
|	an alternative construct,
[ x ]	optional element/construct,
[ x ]…	repeat 0 or more times
x…	repeat 1 or more times; it is equivalent to x [ x ]…

Syntax of the directive.

directive	::=	DVM ( DVM-directive [ ; DVM-directive ]… )
DVM-directive	::=	specification-directive | executable-directive
specification-directive	::=	processors-directive | align-directive | distribute-directive | template-directive | shadow-directive | shadow-group-directive | reduction-group-directive | remote-group-directive | task-directive
executable-directive	::=	realign-directive | redistribute-directive | create-template-directive | parallel-directive | remote-access-directive | create-shadow-group-directive | shadow-start-directive | shadow-wait-directive | reduction-start-directive | reduction-wait-directive | prefetch-directive | reset-directive | map-directive | task-region-directive | on-directive

Constraints:

• Specification-directives (descriptive directives) must preceed C declarations of data arrays or DVM-objects to be distributed.

• Executable-directives (executable directives) must preceed C statements (or semicolon - that is empty statement).

3Virtual processor arrangements. PROCESSORS directive

The PROCESSORS directive declares one or more rectangular virtual processor arrangements on the current set of real processors.

Syntax.

processors-directive

::= PROCESSORS

It is possible to define several virtual processor arrangements of different shape if the number of processors in every arrangement will be equal to the number of real processors. If two virtual processor arrangements have the same shape, then corresponding elements of the arrangements are referred to the same processor. Built-in function NUMBER_OF_PROCESSORS () can be used to determine the number of real processors, provided to a program (or subtask).