NORMA_DD (1158356), страница 12

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

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

If the line corresponds to the variable of scalar type then this line must contain only one record of the following type

If the line corresponds to the variable declared on domain then there checks emptiness of intersection of all <name-domains> mentioned in this line is checked.

Function fixes error:

error code 450 'in lines '<error context>'and in lines'<error context>' reassignment for variable'<error context>

Function strdep builds Data dependencies graph (DDG) based on Table of functional dependencies, which has only simple-nodes and hasn't iteration-nodes and ordered-groups-nodes yet. Each line of Table of functional dependencies of the type

corresponds to the line of dependencies DDG of the type

Corresponding line of Where-compute table is chosen for every variable <var>, mentioned in field <dependency>.

If this line corresponds to the variable of scalar type then <statement number>is chosen from the line. This <statement number> is the value of field <dependency-node>.

If the line corresponds to the variable defined on domain then emptiness of pair intersection of all <name-domains> mentioned in this line and <need-domain> is checked. The values of field <dependency-node> are the values of <statement number>, corresponding to non-empty intersection..

Function pre modifies Table of functional dependencies to the following form

eliminating all the dependencies of other types. Modified Table of functional dependencies will be used in processing maximum strongly connected subgraphs (MSCS).

Function posl reduces DDG, substituting all the nodes of DDG, included into ordered groups, for <ordered groups number>, and correcting dependencies corresponding to substitutions. Table of ordered groups is used for this purpose. Besides, function checks if the order of computations set for ordered groups and data dependencies for the variables from ordered groups defined in DDG aren't contradictory . It also copies DDG into temporary graph zav.

Function test reduces DDG, substituting all the nodes of DDG included into iteration for <iteration number>, correcting dependencies corresponding to substitutions.

Reduction algorithm consists of three stages and uses DDG and Table of iterations structure.

At the first stage only operators included into iterations are processed but embedded iterations if there are any aren't considered. For each iteration from Table of iterations structure <statement numbers> of operators included into <list of boundary operators>, <list of initial operators>, <body-of-iteration>,<exit-condition> are chosen. Lines of dependencies from DDG which have <graph-node>=<statement numbers> are put into temporary graph zavit .

The nodes which have <dependency-node>=<statement number> are eliminated from the list. Thus only dependencies on the operators which are not included into iteration are remained in the lines of dependencies of graph zavit.

At the second stage iterations containing embedded iterations are analysed because they were processed at the first stage only partially. The procedure of processing is recursive: if embedded iterations have been processed completely ( at start these are the most internal iterations), then data from the line of graph zavit, corresponding to such iteration are added to the line corresponding to enclosed iteration. Procedure is repeated till all the iterations are processed completely.

At the third stage reduced graph DDG is built using temporary graph zavit and DDG. It is created by eliminating all the dependencies corresponding to the operators from iterations and including new lines of dependencies of the following type

Besides in all the dependencies <statement numbers> of operators included into iteration are substituted for <iteration number> of iteration which contains these operators.

Thus in the result of function test work, graph DDG, temporary graph zavit and temporary graph zav are built. Temporary graphs will be used in determination of operators execution order in the iteration when parallel layer scheme is being built.

5.4.2RDDG constructor

Search for maximum strongly connected subgraphs (MSCS) is performed. MSCS is strongly connected subgraph of graph DDG, which is not contained in any other strongly connected subgraph of graph G. Reduction of graph DDG is done: all MSCS for special nodes are substituted.

Temporary graph zav is initial data for MSCS searching. Graph's nodes are set to be vÎV and arcs going out of node v are set to be Adj(v). Algorithm of MSCS searching (Reingold E.W, Nievergelt J., Deo N. Combinatorial algorithms. Prentice-Hall, Englewood Cliffs, New Jersey, 1997):

for vÎV do num(x)=0

i=j=k=0

for vÎV do if num(x)=0 then FNDCYC(x,0)

procedure FNDCYC(v,u)

i=i+1

num(v)=i

for wÎAdj(v) do

if num(x)=0

then k=k+1; stack _k ¬ w; FNDCYC(w,v); k=k-1

else

if num(w)<num(v) AND w¹u

then j=j+1; MSCS_j ¬ (w, stack _k , stack _k-1 ,…,stack _t )

/*comment stack _k = w, stack _t = v endcomment */

endif

endif

Entry point of RDDG constructor is function mssg.

General structure of function mssg control is given in the following scheme.

m ssg angr angr1 sumzav sumzv1 angr2

perud1

Function mssg realises algorithm given above builds List of MSCS.

Further processing reduces DDG and builds RDDG. All the nodes of graph DDG included into a MSCS are substituted for MSCS-number and dependencies are corrected considering this substitution.

All the lines of dependencies of DDG of the type

which have <graph node >=<statement number>, <statement number>ÎMSCS. One line is created from the lines this line gets number MSCS-number. Values <dependency nodes> for the line are the result of uniting all operator's <statement numbers> which the operators included into given MSCS are depended on. All the repeated includings <statement numbers> and the numbers of operators included into considered MSCS are eliminated.

After all MSCS are sorted out, in graph DDG dependencies on the numbers of operators included into a MSCS are substituted for MSCS-number of this MSCS.

Function angr chooses a MSCS from List of MSCS.

Function angr1 eliminates MSCS from processing, this MSCS consists of single <statement number> (loop in graph DDG).

Function sumzav unites all the dependencies of operators included into chosen MSCS. Result: <statement numbers> of operators which the operators from MSCS depend on. Repeated dependencies are eliminated.

Function sumzv1 eliminates <statement numbers> of operators included into considered MSCS from the dependencies given by the previous function.

Function angr2 adds new line of dependencies from corresponding MSCS (this line has <graph-node>=<MSCS-number>) to graph DDG.

Function perud substitutes dependencies from the numbers of the operators included into a MSCS for MSCS-number of this MSCS.

5.5Data dependencies graph analyser

Data dependencies graph analyser functions are:

1. partial ordering of reduced data dependencies graph (RDDG). If an edge from P to Q (P,Q from V) exists (in other words Q is used to calculate P), then P>Q (Q must be calculated earlier than P).

2. extraction of a natural parallelism. Parallel layer scheme is constructed: the computations corresponding to RDDG nodes of the same layer may be parallel and independent. Passage from a current layer to the next one is done after all computations of the current layer have been performed.

Structure of <layer> element:

<layer-number>::=<integer>

<node>::=<statement number> OR <iteration number><Parallel layer scheme>

OR <ordered group number> OR <MSCS number>

Algorithm of RDDG ordering .

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

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