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

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

36

Keldysh Institute of Applied Mathematics
Russian Academy of Sciences

C-DVM Compiler

Detailed design

December, 1999

Contents

1 Purpose of the Compiler 3

1.1 Running Compiler 4

2 The Structure of the Compiler 4

2.1 Data Structures of the Compiler 5

2.2 The Linked Memory 5

2.3 The Scanner and the String Memory 6

2.4 Tokens and their symbolic names 7

2.4.1 Terminals 7

2.4.2 Delimiters and operators 7

2.4.3 Keywords 8

2.4.4 C-DVM keywords and identifiers 9

2.5 The Parser 10

2.6 The parsing tree structure 10

2.6.1 Terminals, lists and braces 10

2.6.2 Declarations (of C) 11

2.6.3 Statements (of C) 12

2.6.4 Expressions (of C) 12

2.6.5 Directives (of C-DVM) 13

2.6.6 Clauses and subdirectives (of C-DVM) 14

2.7 The Tree Transformation 14

2.8 The Unparser 14

3 Compilation of C-DVM constructs 14

3.1 Data distribution 15

3.1.1 DISTRIBUTE directive 15

3.1.2 GENBLOCK distribution format 16

3.1.3 ONTO clause 16

3.1.4 REDISTRIBUTE directive 17

3.1.5 ALIGN directive 17

3.1.6 REALIGN directive 18

3.1.7 TEMPLATE clause 18

3.1.8 CREATE_TEMPLATE directive 19

3.2 Distribution of computations (loops and tasks) 19

3.2.1 PARALLEL directive 19

3.2.2 ACROSS clause 20

3.2.3 PROCESSORS directive and NUMBER_OF_PROCESSORS() function 20

3.2.4 TASK directive 21

3.2.5 MAP directive 21

3.2.6 TASK_REGION directive 22

3.2.7 ON-block construct 22

3.2.8 ON-loop construct 22

3.3 Shadow edges 23

3.3.1 SHADOW clause 23

3.3.2 SHADOW_RENEW clause 23

3.3.3 SHADOW_GROUP directive 24

3.3.4 CREATE_SHADOW_GROUP directive 24

3.3.5 SHADOW_START directive 25

3.3.6 SHADOW_START clause 25

3.3.7 SHADOW_WAIT directive 25

3.3.8 SHADOW_WAIT clause 26

3.4 Remote access 26

3.4.1 REMOTE_ACCESS directive and clause 26

3.4.2 REMOTE_GROUP directive 27

3.4.3 PREFETCH directive 27

3.4.4 RESET directive 27

3.4.5 Remote references 28

3.5 Reduction operations 28

3.5.1 REDUCTION_GROUP directive 28

3.5.2 REDUCTION clause 28

3.5.3 Reduction variables and operations 29

3.5.4 REDUCTION_START directive 29

3.5.5 REDUCTION_WAIT directive 30

3.6 Implicit constructions 30

3.6.1 Creation and deletion of distributed arrays 30

3.6.2 Static distributed arrays 31

3.6.3 References to distributed data 31

3.6.4 Own computation 32

3.6.5 Initialization and completion of parallel execution 32

3.6.6 Input-output functions 33

3.7 Debugging extensions 34

3.7.1 Performance analyzer. Loops 34

3.7.2 Performance analyzer. INTERVAL directive 34

3.7.3 Debugger. Data tracing 35

3.7.4 Debugger. Computation tracing 35

3.7.5 Sequential code 36

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 can produce an "extended" debugging code to use features of the performance analyzer (PPPA) and debugger, and also a "sequential" code (i.e. without RTL calls) with such debugging extensions.

1.1Running Compiler

For portability the compiler is written in ANSI-C and runs in command line mode (under OS UNIX and WINDOWS) using the following command:

c_dvm [ options ] [ -o outfile ] infile

where:

infile - an obligatory parameter; a source C-DVM file; it is suppoused that a program is valid C program, compilied by any usual C compiler.

-o outfile -- an optional parameter: the name of output file with converted program; it is cdvm_out.c by default;

options - one or more from the following options:

-s - produce sequential program (no DVM, trace or statistics only); a parallel program is generated by default;

tracing modes:

-d1 - tracing distirbuted data updates,

-d2 - tracing all accesses to distributed data,

-d3 - tracing all data updates,

-d4 - tracing all accesses to all data.

trace accumulation modes:

-e1 - parallel loops and surrounding sequential loops,

-e2 - parallel loops and user defined INTERVALs;

-e3 - e1 + e2,

-e4 - e3 + all sequential loops.

others:

-v - Verbose mode, output messages to the screen,

-w - enable all Warnings,

-w- - disable all Warnings,

-xNNN - eXtent of internal tables (-x16 by default).

2The Structure of the Compiler

The main program of the Compiler performs the following steps:

• gets and verifies command line parameters (the function cmd_line());

• allocates variable-size data (buffers) and initializes lexical and syntactical tables;

• opens input and output files;

• invokes a scanner to read the source program and to build a token stream;

• invokes a parser to read the token stream and to build a parsing tree; the parser in its turn invokes semantic functions to analize the source program and to build required output constructions;

• if the parser successfully built the tree (syntax errors were not detected) the main program invokes (tree) transformer to substitute source nodes by output ones;

• then an unparser generates an output file.

2.1Data Structures of the Compiler

Compilation is made upon an internal representation of a program.The main data structures used for the internal representation are the following:

• string memory for character representation of tokens (LX);

• linked memory in which a parsing tree is built (NDs);

• hash tables for fast search of tokens and nodes (HT0, HT1).

Sizes of these structures determines the maximal size of a source program. If the size is not enough it can be "scaled" by command line parameter -xNNN.

The hash tables are accessed by the function HTfind(item,len,ht,ht_cmp,ht_new). It searches an item of length len in a hash table ht using ht_cmp function to compare items and ht_new function to write new item to the table. It returns the cell number in the hash table where the item is kept. The cell contents is interpreted by a calling function and ht_cmp and ht_new functions.

2.2The Linked Memory

The linked memory is used to store the following data:

• syntactic tables of the parser;

• the token stream;

• the parsing tree;

• a stack for the parser and semantic functions;

• scopes and declarations lists.

Each node of the linked memory has the following four fields:

• C - code of the node, usually it is an internal number of C statement or expression, or DVM-directive;

• A, B - references to subtrees of operands or components; they may be equal to zero for optional subconstructs or unary operations; sometimes these fields are not references to subtrees, e.g. for a node, representing a token, it contains a reference to the string memory;

• D - list of the node attributes; the main "attribute" of node is NEW attribute - an output form of the corresponding source construction.

The linked memory is implemented by the following functions:

• NDinit() cleans the linked memory buffer and creates the free node list;

• NDD(c,a,b,d) creates and filles a new node;

• mk(c,a,b) creates or finds a node (c,a,b,?);

• NDdel(N) deletes the node N;

• wN(N,c,a,b) fills the fields C, A and B fields of the node N.

• A, B, C and D(N) read the corresponding field of the node N;

• wA, wB, wC and wD(N,x) write a value x to the corresponding field of the node N;

• NDget(N,path) gets subtree by the "path"; for example NDget(N, 122) means C(A(A(N))).

The attribute list is supported by the functions:

• set(c,N,V) sets the value V to the c attribute of the node N;

• get(c,N) gets the value of c attribute of the node N;

• del(c,N) deletes c attribute of the node N.

Semantic stack is implemented as a B-linked list in the linked memory with the root Stack and functions SSpush and SSpop. There are functions walk(N,sfun) and walkR(N) which implement standard walk throught the parsing tree invoking a given semantic function sfun for every visited node.

To handle declarations a stack of visibility scopes (as a list in the linked memory) and lists of currently defined variables for every scope are built. These structures are supported by the following functions:

• openScope() entering new scope, pushes scope stack;

• closeScope() leaving a scope, popes scope stack;

• addDecl(N,spec,dvm) stores a declaration in the current scope;

• Decl(lx) returns 0 if lx is not declared;

• whatis(N) finds and unpacks declaration and DVM-directive (if it exists) into global variables for use by semantic functions;

• and some others.

2.3The Scanner and the String Memory

The main scanner function is scan() function. On every invocation it:

• skips blank characters; in particular, comments;

• reads next line if it is necessary;

• determines the type of next token by the first character;

• moves over characters belonging to the next token;

• finds it in (or write to) the token table;

• sets global variables LXcode and LXval.

LXcode is the code of the current token, namely: for C and C-DVM keywords and C delimiters it is their internal number; and for identifiers or constants it is their lexical category number. In the latter case LXvalue is an internal number of the identifier or constant, i.e. a reference to a node with the code TOKEN. String representation of identifiers and constants are kept in the string memory and used in generation step. For parser they are represented by their internal numbers. Internal number is assigned to an identifier at its first occurence. The scanner looks for the current token in the token table (hash function is used), and adds new token to it if necessary.

Other scanner functions:

• LXinit() initializes scanner tables;

• LX_get(t) selects next token skipping characters with type t (defined in table LXcd: e.g. decimal digit, hexadecimal digit, letter);

• comment() skips a comment;

• LXfind(lxcode) finds the current token in the token table; writes new one;

• LXW(token) gets character representation of a token by its code;

• Token(s) makes a TOKEN node for string s;

• LxiS(s) makes an LXI (identifier) node for string s;

• Lxi(token) makes an LXI (identifier) node for a token;

• Lxn(n) makes an LXN (number) node for a number n.

2.4Tokens and their symbolic names

2.4.1Terminals

LXEOF "LXEOF" -- end of file

TOKEN "TOKEN" -- token in the input stream

DLM "DLM" -- delimiter in the input stream

KWD "KWD" -- keyword in the input stream

LXX "LXX" -- undelimited list item and tail

LXI "IDENT" -- identifier

LXN "NUMBER" -- numeric constant

LXC "LXC" -- character constant

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

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

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

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

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

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