5 Dynamic control of DVM-directives

All data, which can be used in the DVM-program, are divided into the following classes:

• Private variables. Each parallel branch (the group of parallel loop iterations or parallel task) has its own local copy of the variable and works only with this copy. The variable has undefined value when entering and when leaving a parallel construction. Such variables must be initialized inside each loop iteration and each task.
• Read-only variables. These variables are used inside a parallel construction for reading only.
• Reduction variables. Each parallel branch has its own local copy of the variable. After the completion of parallel construction Lib-DVM calculates reduction function for all local copies of the variable. The result is broadcasted to all processors.
• Distributed array. The array elements are mapped on the different processors. Each parallel branch can read and modify only elements that are located on its own processor. It also can read elements of shadow edges.
• Remote data buffer. It contains part of distributed array elements used only for reading by the parallel branch on its own processor.

The control algorithms are based on these data classes.

5.1 Checking initialization of variables and elements of distributed arrays

This inspection is performed for all classes of data. Each variable has its initialization flag (the array has the array of flags). When variable is modified the flag is set. When the variable is read the flag setting is checked.

5.2 Checking access to elements of distributed arrays

Each element of created distributed array is provided by a correspondent structure, describing access type to the element (read or write) and a last loop iteration or last parallel task, where this access occurred. Entering a parallel construction all these structures are initialized by a default status that means that element is not used yet. When an element is used inside a arallel loop or task the number of iteration or task and access type are stored for this element. If an element is modified inside one iteration or task and then used inside another iteration or task the undeclared data dependence error is detected.

Note: Iterations of a parallel loop can depend from each other due to usage of reduction variables inside loop. But in this case such dependence doesn’t prevent parallel loop execution and should be declared by programmer when specifying the parallel loop. If a program hasn’t such declaration the variable will be considered as a private variable and private variable usage error will be detected.

When the program accesses to a distributed array inside a parallel construction the local part of the array is calculated.

If the local part of the array doesn’t contain the accessed element an error of access to non-local part is reported. If a shadow edge contains the accessed element the shadow edge renewal checking is performed.

The following three states are assigned to shadow edges of a distributed array: the renewal isn’t performed, renewal being started and renewal has been finished. The program can access to the shadow edges only for reading and only after the renewal has been completed.

The state “renewal isn’t performed” is set when exported elements are modified. It provides a detection of incorrect access to shadow elements before the next edge renewal will be performed. The error is reported when exported elements are modified before renewal of edges has been completed.

5.3 Checking private and read-only variables

The type of a variable is determined when the first use of the variable inside a parallel construction is detected. If the variable is not reduction variable or distributed array then its type is determined by the following way. If the variable is used for writing it will be registered as private. Otherwise it will be registered as read-only.

Each private variable has its initialization flag. The flag is set if the variable is initialized inside given loop iteration or task and otherwise flag is cleared. When variable is modified the flag is set. When the variable is read the flag setting is checked. The private variable flags are cleared after parallel loop exit.

Access type checking is performed for read-only variables. If the program attempts to write to read-only variable the error will be detected.

5.4 Checking reduction variables

Reduction variables are registered when included into a reduction group. The reduction variable has a flag that can assume the following states:

• The variable is used inside a parallel loop. This is initial state of the reduction variable.
• The parallel construction has been finished, but asynchronous reduction for the variable is not started yet.
• The asynchronous reduction for the variable being started.
• The asynchronous reduction for the variable has been completed. This is final state of reduction variable. The reduction variable will be deleted from the table of variables and can be used as a variable of other class.

The state of the reduction variable is checked when the variable is accessed. If reduction variable is used after a parallel construction leaving but before asynchronous reduction completion the error will be reported.

Note: Incorrect specification of a reduction function (for example, specifying MIN instead of MAX) is not detected by this method. Use the trace comparison method to detect such errors.

5.5 Checking usage of remote access buffer

The remote data buffer is used for pre-loading of non-local elements required for the each processor. The same verifications are performed for a remote data buffer and for a distributed array. But there are little exclusions:

• Verifying the data dependencies in a parallel construction takes into account that the remote data buffer is used instead of distributed array.
• Verifying the array initialization is performed both for remote data buffer elements and elements of related distributed array. The initialization of remote data buffer is copying of distributed array elements to remote data buffer.
• Only read operations are allowed for elements of the remote data buffer.

5.6 Dynamic control of DVM directive implementation

Dynamic control subsystem includes the following components:

• Table of variables – provides methods to accumulate the information about variables of various types and quick find this information by address.
• Module of dynamic control – performs DVM directive checking. Functions of this module are called form some functions of Lib-DVM and for each variable or array accessing. The table of variable is used as auxiliary module, which accumulates and provides information about variables during dynamic control.

5.6.1 Use the table of variables by dynamic control module

The dynamic control subsystem uses such concept as execution level.

The root level is a level of the initial sequential branch of the program. This level has zero number. When entering a parallel construction the number of current level is incremented by one unit. When leaving parallel construction the number of current level is decrement by on unit. Thus, the number of current level defines a depth of parallel constructions.

The number of the current level is important for work with variables, since the ideology of using variables depends on current level. This level is taken into account with registering a new variable in the dynamic control and is kept together with basic information about a variable.

There are three variants when dynamic control finds a variable in table of variables:

1. There is no variable information in the table. In this case a new record for the variable is created. The type of usage this variable is detected dependently on context of variable accessing. The current executed level is set as level for this variable. The formed record is returned as result of searching.
2. There is variable information in the table but its level does not correspond to current. In this case also a new record will be created. The reference to a variable information on the previous level is stored in the formed record. The context of variable accessing and class of using of variable on previous level defines a new class of variable usage. The formed record is returned as result of searching. After removing variable information from the table the necessary information will be updated for a variable on the previous level.
3. There is variable information in the table and its level corresponds to current. In this case the found record is returned as result of searching.

Also some functions of Lib-DVM create records in the table of variables. For example the definition of a distributed DVM array or including variable into reduction groups automatically creates a records in table of variables with respective class of usage.

After completion of each parallel structure, all records, which level is equal to level of completed structure, are removed from that table of variables. Thus the lifetime of executed parallel structure defines the lifetime of record in the table of variables.

5.6.2 Base functions of dynamic control module

The following functions performs dynamic control:

The function initializes all required structures and variables for dynamic control subsystem.

The function un-initializes all dynamic control structures and prints all detected errors.

The function is called when a parallel structure is completed. It removes all registered variables for the current execution level.

The function removes all data that is used by dynamic control module.

The function finds variable information by its address. The function returns NULL if variable is not registered.

This is general function of dynamic control module. The function checks all variable accessing for read and write.

The function validates the variable information for current executed level. If the Current is not valid for current level then it creates a new variable information structure, which is returned as result of the function. Otherwise, the Current pointer is returned.

The function checks access to read-only variables.

The function checks access to private variables.

The function checks access to reduction variables.

The function checks access to distributed DVM-arrays.

This is general function of variable registration.

The function registers a reduction variable.

The function registers a distributed DVM array.

The function registers a variable with private type of access.

The function registers a variable with read-only type of access.

The function registers the remote access buffer for several elements of the source distributed array. The remote access buffer is created as a distributed array.

The function registers the remote access buffer for a single element of the source distributed array. The remote access buffer is created as a scalar variable.

Destructor of a reduction variable. The function of reduction variable registration assigns this destructor for variable information structure.

Destructor of a private variable. The function of private variable registration assigns this destructor for variable information structure.

Destructor of a read-only variable. The function of read-only variable registration assigns this destructor for variable information structure.

Destructor of a distributed DVM array. The function of distributed DVM array registration assigns this destructor for variable information structure.

The function removes variable information for the current execution level.

The function sets initialization flag for the variable or element of distributed array.

The function clears initialization flag for the variable or all elements of distributed array.

The function checks initialization of variable or element of distributed array. It returns 1 if variable or element has been initialized.

The function sets the flag of using the specified array in the parallel loop with ACROSS type of data dependency. The dynamic control will not check data dependency for this array within the limits of executed loop.

The function calculates the current local part of the distributed array allocated on the current abstract machine and checks whether the element belongs to this local part or its edges or not. In addition, the correctness of edge usage is checked.

The function validates the access to an element of distributed DVM array in the sequential part of a program.

The function checks the undeclared loop data dependence when the specified distributed array element is used.

The function checks out-of-range access for the specified distributed array. It returns 1 if the element with the index LI belongs to the local array part.

The function calculates the block of a distributed array, elements of which can be accessed inside the current iteration of a parallel loop. It returns 0 in case of a successful evaluation of the block.

The function registers the shadow definition of the distributed array in the dynamic control module and links they to the specified bound exchange structure.

The function sets the flag of completion of bound exchange for edges that are included into the specified bound group.

The function removes all shadow definitions for the specified distributed array. It is called after modification of an exportable element of the array.

The function finds index of a shadow description that contains the specified array’s element.

5.6.3 The parameters of dynamic control

There is the special set of parameters that manages the dynamic control module. By using these parameters user can turn on/off some validations, tune the effectiveness of algorithms, manage diagnostic output, and so on.

The parameters are specified in files that are located in the special DVM-system directory. The parameters has the following form:

<Parameter name>=<Value>

The dynamic control module uses the following parameters:

EnableDynControl – flag of dynamic control If it is equal to 0 then dynamic control is disabled.

DebugOptions.ErrorFile – the name of diagnostic output file. This file is used if parameter DebugOptions.ErrorToScreen is equal to 0. If system cannot open the file, the error messages will be output to the screen.

DebugOptions.HashIndexSize – size of hash-index for the dynamic control variable table.

DebugOptions.HashTableSize – increment size of hash-array of the table of variables.

DebugOptions.VarTableSize – increment size of the variable-table.

DebugOptions.ErrorToScreen – if this parameter is not equal to 0 then all diagnostic messages will be output to the screen.

DebugOptions.PrintStatistic – flag to enable or disable output of the variable-table usage statistics.

DebugOptions.AppendErrorFile – the mode of a diagnostic file usage. The file will be cleared each time before program running if this parameter is equal to 0.

DebugOptions.MaxErrors – the maximum count of errors after that the dynamic control is disabled.

DebugOptions.CheckVarInitialization – flag to enable or disable checking scalar variables initialization.

DebugOptions.CheckVarReadOnly – flag to enable or disable checking usage of variables with read-only access mode.

DebugOptions.CheckReductionAccess – flag to enable or disable checking usage of reduction variables.

DebugOptions.CheckDisArrInitialization – flag to enable or disable checking distributed array elements initialization.

DebugOptions.CheckDisArrLimits – flag enable or disable checking access out of distributed array range.

DebugOptions.CheckDisArrEdgeExchange – flag to enable or disable checking edge exchange for distributed arrays.

DebugOptions.CheckDisArrSequentialAccess – flag to enable or disable checking usage of distributed array elements in the sequential program part.

DebugOptions.CheckDisArrLocalElm – flag to enable or disable checking membership of an element to the distributed array local part.

DebugOptions.CheckDataDependence – flag to enable or disable checking undeclared loop data dependence.

DebugOptions.CheckRemoteBufferAccess – flag to enable or disable checking usage of remote access buffers.

HashMethod – this parameter defines algorithm that is used for the hash-value calculation. If it is equal to 0 then the StandartHashCalc algorithm is used, if it is equal to 1 then the OffsetHashCalc algorithm is used.

HashOffsetValue – offset value for the OffsetHashCalc algorithm. The values from 0 up to 16 are supposed.

6 The “Comparing execution results” method

6.1 Trace accumulation

The following trace information is accumulated in a trace file:

• Values of all variables accessed for reading.
• Values of all variables accessed for writing.
• Results of reduction operations.
• Beginning of a task region or parallel and sequential loop.
• Beginning of iteration or parallel task.
• End of a task region or parallel and sequential loop.

Each record in the trace file has reference to a line of the source program.

Since this method requires considerable overhead the means to control trace detailing are provided.

The content of a special file (trace configuration file) determines detailing of the trace. This file contains description of all program loops and task regions.

To decrease trace size the following accumulation levels are provided:

• No trace information.
• Only the information about loops, task regions, tasks and iterations are accumulated.
• In addition to the previous level the information about variable modifications are accumulated.
• In addition to the previous level the information about all usage of the variables are accumulated.

Furthermore, you can specify for each loop an iteration range and for each task region a task range, which the information about variable usage will be accumulated for.

6.2 Trace comparing

In the comparing mode the trace-file is read into the memory before program startup. The structure of trace in the memory is formed by the same functions that are used in the accumulation mode. As result, we have the same trace structure in the memory both after accumulating and after reading the trace.

Then during program execution the occurred events are compared with reference ones.

There are the following singularities of parallel program execution:

• Values of reduction variables inside a parallel construction can be different in the sequential and parallel modes. Therefore comparing values of reduction variables inside a parallel constructions isn’t performed.
• In the parallel mode an order of parallel loop iterations and parallel tasks can be changed. Therefore at the iteration and task beginning the corresponding reference trace record is searched for and set as current.
• In the parallel mode a sequential branch can miss statements, which calculate and assign values to non-local elements of distributed arrays.
• Inside the parallel construction some references to variables used for calculation of reduction maximum or minimum may be missed in the sequential or parallel modes.

6.3 Checking reduction operations

Reduction variable accumulation has a special implementation. The values of reduction variables inside a parallel constructions aren’t compared with reference ones. Comparison is performed only for reduction result.

There are two ways to calculate a reduction operation. The first way is a standard method of reduction performance. Program statements inside an iteration or task perform all computations of a reduction variable on its own processor. The final result of reduction operation between processors is computed by Lib-DVM. If a program is performed on a single processor only program statements will compute the reduction.

The second way is emulation of performing each iteration and parallel task on a separate processor. At the beginning of iteration and task the initial value is assigned to reduction variable. The initial value is stored before parallel construction beginning. Upon end of iteration and task the reduction is performed by Lib-DVM according to specified reduction function.

To perform reduction checking the comparing of program execution results is performed for each method that described above. If a program specifies the reduction function correctly the reduction results will be the same for both ways. Otherwise the error of differences of reduction results will be reported for user.

6.4 Formats of input and output files

6.4.1 Trace configuration file

The trace configuration file is used to specify the level of trace details and show volumes of trace for the specified parameters. The user can tune the level of trace details by running the program several times in the mode of forming the trace configuration file and modifying each time the formed file.

As was said before, there are the following levels of trace details:

• absence of trace (NONE level);
• tracing beginning and ending of loops and task regions, and tracing beginning iterations and parallel tasks (MINIMAL level);
• the previous level plus tracing modification of variables and results of reduction (MODIFY level);
• tracing all events (FULL level).

The trace level of the whole program is assigned in the trace parameter file. The trace level for the each program structure (parallel and sequential loop, task region) is assigned in the trace configuration file. If the level of trace details for the structure is not assigned then the level of the parent structure is accepted. If the parent structure does not exist then the level of the whole program is accepted.

The trace configuration file contains the following additional information for the full trace and each program structure: number of trace strings, trace size in bytes and number of traced iterations (or tasks for task region). If a structure is performed several times then the trace configuration file contains summary information for the structure.

Additionally, for the each structure the structure number, numbers of beginning and completion structure lines, trace level and traced iteration range is presented. The user can change the trace level and traced iteration range. If trace level is not set then the trace level of the whole program are accepted.

The comments in the trace configuration file are marked by the ‘#’ character. All symbols after ‘#’ will be ignored.

The structure of the trace configuration file is the following:

# Trace size = <full trace size>
# String count = <number of trace strings>

<SL | PL | TR> <structure number> (<number of parent structure>) [<structure rank>] {<file name>, <line number>} = <NONE | MINIMAL | MODIFY | FULL>, (<dimension>:<first iteration>, < last iteration >, <iteration step>), …

# Trace size = <structure trace size>
# String count = <number of structure trace strings>
# Count of traced iterations = <number of traced iterations or tasks>

EL: <structure number>

………

<SL | PL | TR> <N> (<P>) [<R>] {<FILE>, <LINE>}= <NONE | MINIMAL | MODIFY | FULL>, (<I0>:<L0>, <R0>, <S0>), (<I1>:<L1>, <R1>, <S1>), …

# Trace size = <structure trace size>
# String count = <number of structure trace strings>
# Count of traced iterations = <number of traced iterations or tasks>

EL: <N>

All structure parameters are assigned after the ‘=’ symbol. The SL record corresponds to a sequential loop, the PL record corresponds to a parallel loop, and the TR record corresponds to a task region.

The traced iteration range is set in the brackets. If these parameters are absent, the all iterations will be traced. For the excluded iterations the variable accessing is not traced but iteration beginning events are traced.

The traced iteration range is assigned as the following:

(<dimension> : [<first iteration>] , [<last iteration >] , [<iteration step>])

<dimension> – structure dimension (beginning from 0) to which the limitations are assigned. This parameter is required.

<first iteration> – iteration number from which the iterations are traced. By default, the iterations are traced from the first.

<last iteration> – iteration number up to which the iterations are traced. By default, the iterations are traced up to the last.

< iteration step> – the step with which the iterations will be traced. By default, the 1 is used.

Iteration ranges examples:

• (0:2,10,) – trace iteration from 2 up to 10.
• (0:,10,) – trace iterations up to 10.
• (0:4,,) – trace iterations from 4.
• (0:,,3) – trace iterations with the 3 step.

Empty iterations will be removed from the trace in the special mode. This mode can be specified by using the trace parameters file.

6.4.2 Trace file

The comparing execution results puts to begin of the trace file a special trace header. This header contains information about trace parameters, which was used during trace accumulation. When the trace-comparing mode is specified, the trace parameters are read from the trace header and are used instead of the trace configuration file.

The format of the header the following:

MODE = <NONE | MINIMAL | MODIFY | FULL>, [EMPTYITER]
# Begin trace header. Don't modify these records
<SL | PL | TR> <N> (<P>) [<R>] {<FILE>, <LINE>}= <NONE | MINIMAL | MODIFY | FULL>, (<I0>:<L0>, <R0>, <S0>), (<I1>:<L1>, <R1>, <S1>), …
EL: <N>

…

<SL | PL | TR> <M> (<P>) [<R>] {<FILE>, <LINE>}= <NONE | MINIMAL | MODIFY | FULL>, (<I0>:<L0>, <R0>, <S0>), (<I1>:<L1>, <R1>, <S1>), …
EL: <M>

END_HEADER
# End trace header

The MODE line specifies the trace level and a mode of empty iterations accumulation. All other records specify the parameters for the each structure and have the same format as records of the trace configuration file.

The following trace information is accumulated during execution result tracing:

• The values of all read variables:
  RD: [<variable type>] <variable name> = <value>; {<file name>, <line number>}

• Expression calculation beginning:
  BW: [<variable type>] <variable name>; {<file name>, <line number>}

• The values of all variables assigned in:
  AW: [<variable type>] <variable name> = <value>; {<file name>, <line number>}

• The values of all read reduction variables:
  RV_RD: [<variable type>] <variable name> = <value>; {<file name>, <line number>}

• Beginning of expression calculation of a reduction variable:
  RV_BW: [<variable type>] <variable name>; {<file name>, <line number>}

• The values of all reduction variables assigned in:
  RV_AW: [<variable type>] <variable name> = <value>; {<file name>, <line number>}

• Result of reduction operation:
  RV: [<variable type>] <value>; {<file name>, <line number>}

• Completion of self-execution block in he sequential part of a program:
  SKP: {<file name>, <line number>}

• Parallel loop beginning:
  PL: <structure number> (<parent structure number>) [<structure rank>] ; {<file name>, <line number>}

• Sequential loop beginning:
  SL: <structure number> (<parent structure number>) [<structure rank>] ; {<file name>, <line number>}

• Task region beginning:
  TR: <structure number> (<parent structure number>) [<region rank (always equals one)>] ; {<file name>, <line number>}

• Iteration beginning:
  IT: <absolute iteration index (calculated from all values of all iteration variables)>, (<iteration variable value>,<iteration variable value>,…).

• End of loop or task region execution:
  EL: <structure number>; {<file name>, <line number>}