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

Текст из файла

49

C-DVM

Language description

March 25, 1999

Version 2.0

Keldysh Institute of Applied Mathematics

Russian Academy of Sciences

Contents

1. Introduction 4

2. Language overview 5

2.1. Programming model and model of parallelism 5

2.3. The difference between CDVM versions 1.0 and 2.0 5

2.4. Syntax of DVM-directives 6

3. Virtual processor arrangements. PROCESSORS directive 7

4. Data Mapping 7

4.1. DISTRIBUTE and REDISTRIBUTE directives 7

4.1.1. Format BLOCK 8

4.1.2. Format GEN_BLOCK 9

4.1.3. Format [] 10

4.1.4. Multidimensional distributions. 10

4.2. Multidimensional dynamic arrays 11

4.2.1. Dynamic arrays in C program 11

4.2.2. Using C-style multidimensional arrays. 11

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

4.3. Distributing by aligning 12

4.3.1. ALIGN and REALIGN directives 13

4.3.2. TEMPLATE and CREATE_TEMPLATE directives 14

4.4. Non-distributed data 15

5. Distribution of Computations 16

5.1. Model of computation distribution 16

5.2. Distribution of loop iterations with regular computations 16

5.2.1. Definition of distributed loop with regular computations 16

5.2.2. Distribution of loop iterations. PARALLEL directive 16

5.2.3. Private variables. 17

5.2.4. Reduction operations and variables. REDUCTION specification 18

5.2.5 Distribution of the loop with regular data dependence. ACROSS specification 18

5.3. Distribution of the loop iterations with irregular computations. 19

5.3.1. Model of irregular computations 19

5.3.2. Distributed loop with irregular computations 20

5.4. Non-distributed (replicated) computations 21

6. Access to remote data 22

6.1. Regular remote references 22

6.1.1. Shadow edges group. SHADOW_RENEW specification. 22

6.1.2. Group of regular remote references. REMOTE_ACCESS directive 24

6.2. Group of irregular remote references. INDIRECT_ACCESS directive 27

6.3. Overlapping computations with data exchange between processors. 28

6.3.1. Asynchronous updating of shadow edges 28

6.3.2. Asynchronous group reduction 30

7. Task parallelism 31

7.1. Description of task group 31

7.2. Mapping tasks on processors. MAP directive 32

7.3. Array distribution on tasks 32

7.4. Distribution of computations. TASK_REGION directive. 32

7.5. Data localization in tasks 33

7.6. Fragment of static multi-block problem 33

7.7. Fragment of dynamic multi-block problem 34

8. Procedures 35

9. Input/output 36

References 36

Appendix 1. Examples of C-DVM programs. 36

Example 1. The Gauss elimination algorithm. 37

Example 2. Jacobi Algorithm 38

Example 3. Jacobi Algorithm (asynchronous version) 39

Example 4. Irregular Calculations Based on Jacobi Algorithm 41

Example 5. Red-Black Successive Over-Relaxation 43

Example 6. Multigrid method program. 44

Example 7. Task Parallelism for Multiblock Code 46

Appendix 2. Syntax summary 48

1. Introduction

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 (Distributed Virtual Machine, Distributed Virtual Memory) model developed in Keldysh Institute of Applied Mathematics [1].

The DVM name originates from two main notions - Distributed Virtual Memory and Distributed Virtual Machine. The former reflects the global address space, and the latter reflects the use of an intermediate abstract machine for the two-step mapping of the parallel program onto a real parallel computer. This distributed virtual machine consists of one or several multidimensional arrays of virtual processors, and defines the parallelism of the program. The programmer creates a suitable virtual machine for his program, then specifies the mapping of the program and data onto his virtual machine and describes the rules of mapping this virtual machine onto the real parallel computer. This mapping is performed during run-time and does not require recompilation of the source code.

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). 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. 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 execution of programs (DVM-directives).

The C-DVM language provides the following main features of parallel program execution specification:

distribution of array elements over the processors;

distribution of loop iterations over 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 operation on data located at different processors (such as summing values of distributed array elements, or finding maximal and minimal values of them).

2. Language overview

2.1. Programming 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 a macro DVM(<directive>) which in sequential program is expanded to empty string. DVM-directives may be conditionally divided on three subsets:

• Data distribution (sections 2, 3, 4, 8, 9)

• Computation distribution (sections 5, 7)

• Remote data specification (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.

First, in DVM model a user defines multidimensional arrangement of virtual processors, on which sections data and computations will be mapped. 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 are mapped by one copy per each processor (replicated data). A value of replicated variable must be the same on all processors concerned. (For two exceptions of this rule see section 5.2.3 and 5.2.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 performs only those assignment statements that calculate values of its own variables.

DVM model defines two levels of parallelism:

• data parallelism on a processor arrangement section;

• task parallelism: independent computations on disjoined sections of processor arrangement

Data parallelism is implemented by distribution of tightly enclosed loops over the processors (distributed computations) (see section 5). The loop iteration is executed on one processor entirely. Therefore the rule of own computations must be carried out for all the statements of single iteration. The statements located outside of the distributed loop are implemented by the identical computations on all the processors of the section (replicated distributions). The exception is own computation statements (section 5.4).

Task parallelism is implemented by distribution of data and independent computations over disjoined sections of processor arrangement (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 (section 6).

2.3. The difference between CDVM versions 1.0 and 2.0

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

• Explicit definition of processor arrangements (section 3).

• Task parallelism (section 7).

• Format GEN_BLOCK for array distribution (section 4.1.2).

• Distribution of a loop with regular dependence on data (section 5.2).

• Distribution of a loop with irregular computations (section 5.3).

• Remote data specification without data replication (section 6.1.2, 6.2).

2.4. Syntax 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,

[ ] optional construct

[ ]… repetition of the construct from 0 to several times,

x-string x [ x ]…

x-list x [ ; x ]…

Syntax of the directive.

Constraints:

• Specification-directives must be followed by C declaration (of data arrays or DVM-objects).

• Executable-directives must be followed by C operator (or semicolon).

3. Virtual processor arrangements. PROCESSORS directive

The PROCESSORS directive declares one or more rectangular virtual processor arrangements.

Syntax.

Function NUMBER_OF_PROCESSORS () can be used to determine a number of real processors, provided to a program.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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