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

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

26

Keldysh Institute of Applied Mathematics
Russian Academy of Sciences

C-DVM Compiler

Preliminary design

December, 1999

Contents

1 Purpose of the Compiler 6

1.1 Parallelization 6

1.2 Debugging extensions 6

2 The sequence of compilation 7

3 Compilation of C-DVM constructs 7

3.1 Distribution of data 8

3.1.1 DISTRIBUTE directive 8

3.1.2 GENBLOCK distribution format 8

3.1.3 ONTO clause 8

3.1.4 REDISTRIBUTE directive 9

3.1.5 ALIGN directive 9

3.1.6 REALIGN directive 9

3.1.7 TEMPLATE clause 9

3.1.8 CREATE_TEMPLATE directive 10

3.2 Distribution of computations (loops and tasks) 10

3.2.1 PARALLEL directive 10

3.2.2 ACROSS clause 11

3.2.3 PROCESSORS directive and NUMBER_OF_PROCESSORS() function 12

3.2.4 TASK directive 13

3.2.5 MAP directive 13

3.2.6 TASK_REGION directive 13

3.2.7 ON-block construction 14

3.2.8 ON-loop construction 14

3.3 Shadow edges 14

3.3.1 SHADOW clause 14

3.3.2 SHADOW_RENEW clause 14

3.3.3 SHADOW_GROUP directive 15

3.3.4 CREATE_SHADOW_GROUP directive 15

3.3.5 SHADOW_START directive 16

3.3.6 SHADOW_START clause 16

3.3.7 SHADOW_WAIT directive 16

3.3.8 SHADOW_WAIT clause 16

3.4 Remote access 17

3.4.1 REMOTE_ACCESS directive and clause 17

3.4.2 REMOTE_GROUP directive 17

3.4.3 PREFETCH directive 18

3.4.4 RESET directive 18

3.4.5 Remote references 18

3.5 Reduction operations 18

3.5.1 REDUCTION_GROUP directive 18

3.5.2 REDUCTION clause 19

3.5.3 Reduction variables and operations 19

3.5.4 REDUCTION_START directive 20

3.5.5 REDUCTION_WAIT directive 20

3.6 Implicit constructions 21

3.6.1 Creation and deletion of distributed arrays 21

3.6.2 Static distributed arrays 21

3.6.3 References to distributed data 22

3.6.4 Own computation 22

3.6.5 Initializing and finalizing of program execution 22

3.6.6 Input-output functions 23

3.7 Debugging extensions 23

3.7.1 Performance analyzer. Loops 23

3.7.2 Performance analyzer. INTERVAL directive 24

3.7.3 Debugger. Data tracing 24

3.7.4 Debugger. Computation tracing 25

3.7.5 Sequential code 26

1Purpose of the Compiler

C-DVM is the C language extended by special annotations for specifying parallel execution of a program. These annotations are called DVM-directives. C-DVM compiler translates an annotated C-DVM program to a SPMD stile program that contains calls to Run-Time Library (RTL).

Besides "pure" parallel code the compiler should be able to produce an "extended" debugging code to use features of the performance analyzer and debugger, and also a "sequential" code (i.e. without RTL calls) with such debugging extensions.

1.1Parallelization

Compiler should recognize the following four types of constructs and perform corresponding actions and code transformations:

• Declarative directives. Provided information should be kept for use in code transformation. Declaration should be modified.

• Executable directives. These should be transformed to calls of RTL functions.

• Structured directives. These require transformation of program structure.

• Implicit (i.e. not explicitly marked by any DVM-directive).
  These include:

• allocation and destruction of distributed arrays ;

• access to distributed data;

• input-output functions;

• initializing and finalizing of program execution;

• own computations;

• sequential loops.

1.2Debugging extensions

For the Performance Analyzer the Compiler should process:

• special directive INTERVAL;

• beginning and finishing of execution of (local part of) parallel loops;

• beginning and finishing of execution of some sequential loops.

All of these are implemented as invocations of corresponding functions of the analyzer.

For the Debugger the Compiler should provide:

• tracing of accesses to data;

• registration of initialized variables;

• tracing of starting of every iteration of a loop or starting of a task.

All of these are implemented as invocation of corresponding functions of the debugger. A point of registration of initialized variables is determined by the compiler.

Sequential execution mode is required to obtain performance characteristics of source program and so called "reference" trace to debug in trace comparison mode. All DVM-directives are ignored except for the following:

• parallel loop are marked for the analyzer;

• reduction groups are created for the tracer work properly;

• distribution directives are used to distinguish ordinary and distributed data for selective tracing.

2The sequence of compilation

Program compilation is accomplished in the following steps.

• Compiler reads source annotated program, parses it and builds its internal representation (a parsing tree and a token table).

• The tree is analyzed to gather global information.

• The tree is extended and transformed.

• The tree is unparsed with generation of output code.

For convenience and flexibility output code is written without direct use of RTL functions. Output code contains macros providing all necessary information at a given point of output program, hiding low-level details of RTL library interface. The final generation is performed by the C preprocessor using macrodefinitions of C-DVM macros (File cdvm_c.h.)

3Compilation of C-DVM constructs

Necessity of program transformation for parallel execution is caused by distribution of data and computations.

Distribution of data consists in splitting of arrays into parts and placing such parts to local memories of different processors. On each processor RTL defines size of local part (considering shadow edges) and allocates memory for it. For program this local part is accessible through array handler. So original sequential statements for allocating and accessing distributed data should be found in source code and replaced.

Distribution of computation consists in splitting of the whole index space of a loop to parts and execution on different processors of different set of loop iterations. In every processor local part of parallel loop is described by a loop handler. So sequential loop headers should be replaced.

In this section all transformations of C-DVM program performed by the compiler are described.

3.1Distribution of data

3.1.1DISTRIBUTE directive

Context and syntax.

DVM( ["*"] DISTRIBUTE [ format...] [ ONTO target ]

[ ; SHADOW-clause ] [ ; TEMPLATE-clause ] )

C-declaration ;

Proposed compiler output.

long array-id [ rank+1 ];

Note. Source declaration is substituted. All other information from the declaration and directive will be used later in other constructions generating and distributed data references recognizing.

3.1.2GENBLOCK distribution format

Context and syntax.

DVM(DISTRIBUTE ... "[" GENBLOCK( int-array ) "]"... )

DVM(REDISTRIBUTE ... "[" GENBLOCK( int-array ) "]"... )

Proposed compiler output.

DVM_GENBLOCK(am,ps,k,gbs);

Note. The macro is generated not at the point of DISTRIBUTE directive, but in a sequence of (explicit or implicit) array creation. Macro DVM_GENBLOCK(am,ps,k,gbs) is expanded to

DVM_AM=am? am : getam_();

DVM_PS=ps? ps : getps_(NULL);

genbli_(&DVM_PS, &DVM_AM, (AddrType*) gbs, k);

3.1.3ONTO clause

Context and syntax.

DVM(DISTRIBUTE ... ONTO target ... )

Proposed compiler output.

DVM_ONTO(ps,k,ls,hs)

Note. The macro is generated not at the point of DISTRIBUTE directive, but in a sequence of (explicit or implicit) array creation. It creates a processors subsystem that will be used instead of the current one (default). Macro DVM_ONTO(ps,k,ls,hs) is expanded to

DVM_PS=ps;

DVM_PS=crtps_(&DVM_PS, ls, hs, DVM_0000);

3.1.4REDISTRIBUTE directive

Context and syntax.

DVM(REDISTRIBUTE array format... [ NEW ] ) ;

Proposed compiler output.

DVM_REDISTRIBUTE(amv,ps,k,axs,new);

Note. The executable directive is converted to a statement. Macro DVM_REDISTRIBUTE(amv,ps,k,axs,new) is expanded to

{DVM_PS=ps;

redis_((AMViewRef*) amv, &DVM_PS, k, axs, 0, new);

}

3.1.5ALIGN directive

Context and syntax.

DVM(["*"] ALIGN [ "["dummy-var"]"... ]

WITH base "["align-expr"]"...

[ ; SHADOW-clause ] )

C-declaration ;

Proposed compiler output.

long array-id [ rank+1 ];

Note. Source declaration is substituted. All the other information from the declaration and directive should be used later in generating other constructions and recognizing of references to distributed data.

3.1.6REALIGN directive

Context and syntax.

DVM( REALIGN array "["dummy-var"]"...

WITH base "["align-expr"]"... ) ;

Proposed compiler output.

DVM_REALIGN(arr,base,k,i,a,b,new);

Note. The executable directive is converted to a statement. Macro DVM_REALIGN(arr,base,k,i,a,b,new) is expanded to

{realn_(arr, (PatternRef*)(base), i, a, b, new);

}

3.1.7TEMPLATE clause

Context and syntax.

DVM(DISTRIBUTE ... ; TEMPLATE [ "["size"]"... ] )

void * template-id ;

Proposed compiler output.

AMViewRef template-id;

Note. Source declaration is substituted. Distribution formats will be used in creation of the template. If sizes present creation will be implicit.

3.1.8CREATE_TEMPLATE directive

Context and syntax.

DVM(CREATE_TEMPLATE template-id "["size"]"... ) ;

Proposed compiler output.

DVM_CREATE_TEMPLATE(am,t,r,di);

DVM_DISTRIBUTE(amv,ps,k,axs);

Note. The executable directive is converted to a statement. Macro DVM_CREATE_TEMPLATE(am,t,r,di) is expanded to

{if(am==0) DVM_AM=getam_();

else DVM_AM=am;

t=crtamv_( (AMRef*)DVM_AM, r, di, 0);

}

Macro DVM_DISTRIBUTE(amv,ps,k,axs) is expanded to

{DVM_PS=ps;

DVM_AMV=amv;

distr_( &DVM_AMV, &DVM_PS, k, axs, 0);

}

These macros are also generated to create and distribute an implicit template for any distributed (not aligned) array.

3.2Distribution of computations (loops and tasks)

3.2.1PARALLEL directive

Context and syntax.

DVM ( PARALLEL "["loop-var"]"...

ON base "["align_expr"]"...

[ ; sub-directives]... )

loop-nest

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

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

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

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

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

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