DEB_pdes (Раздаточные материалы)

DVM Debugger
Preliminary design

1. The Functions of DVM debugger

DVM debugger is used for debugging DVM-program (written in Fortran DVM or C-DVM languages). The following approach is used to debug DVM-programs. First, the program is debugged on a workstation as a sequential program using ordinary debugging methods and tools. Then the program is executed at the same workstation in the special mode of checking DVM-directives. At the next step the program may be executed on a parallel computer in the special mode, when intermediate results of its execution are compared with reference results (for example, the results of its sequential execution).

The DVM-program can contain the errors of different kinds. The DVM-debugger is used to detect errors not appeared during a sequential execution. In the common case the following three classes of errors can be considered:

• Syntax errors in DVM-directives (incorrect usage of an operator, missing of brackets and so on). Violation of static semantics belongs to this class also.

• Incorrect order of DVM-directives or invalid parameters of DVM-directives.

• Wrong computation due to DVM-directive incorrectness and errors, not detected during program execution in sequential mode.

A compiler detects the errors of the first class.

Only simple errors of second class such as wrong parameter type may be detected by static analysis. To detect the errors of this class each Lib-DVM function checks the correctness of DVM-directives order and parameters. The checks are done dynamically, during program execution. Some from these checks can cause considerable overhead therefore they are done only by a special request.

It is impossible to detect errors of third class without special compilation mode and considerable overhead in the parallel program. Unspecified data dependence in loop is example of the error of the third class. To detect this error it is necessary to fix all data modifications and usage on different processors and to determine the cases, when a variable is modified on one processor and used on the other. This detection can be more effectively performed on a single processor by emulation of parallel execution of the program.

The DVM-debugger is intended to detect errors of third class. It is based on the following two methods.

The first method, method of dynamic control of DVM-directives, allows verifying the correctness of the program parallelization specified by DVM-directives. It is based on the analysis of sequence of Lib-DVM function calls and references to the variables during parallel program execution simulated on a single processor.

The second method is based on the comparison of parallel and sequential program execution trace results. It allows to localize the program point and moment, when the results are beginning to differ.

The “Dynamic control of DVM-directives” method

The dynamic control is based on simulation of DVM-program parallel execution on a single processor. This method using can slow down the program execution significantly and requires large volumes of additional memory. Therefore it can be applicable to a program with specially chosen test data of limited size only.

Kinds of detected errors

The dynamic control allows to detect the following kinds of errors:

1. Undeclared cross-iteration data dependencies in a parallel loop.

2. Using of non-initialized private variables inside or outside of a parallel loop.

3. Modification of non-distributed variables not specified as reduction or private.

4. Using reduction variables after the asynchronous reduction startup but before its completion.

5. Undeclared access to non-local elements of the distributed array.

6. Writing to shadow edges of the distributed array.

7. Reading shadow elements before completion of their updating.

The “Comparing execution results” method.

The dynamic control is intended first of all for checking DVM-directives correctness. The control area is limited by DVM-programs compiled in the special debug mode only. However, the program can contain calls of procedures written in ordinary sequential languages (including assembler). The procedure execution is not controlled and can cause incorrect program execution. Besides, correctness of reduction operation descriptions is not checked. And finally, the program can have errors (not related with its parallelization) which appear only during a parallel execution.

There is another control method aimed to detect such errors. This method is based on an accumulation of trace results for different conditions of execution and these results comparison. With this method the program may be executed in two modes. In the first mode, trace results (intermediate variable values) are accumulated and written to a file as the reference trace results. In the second mode, execution results are compared with the reference ones.

2. The Content of DVM debugger

The DVM-debugger consists of two parts: the dynamic control system and the trace comparison system.

Both systems use two base subsystems: tables allowing storing large volumes of uniformed information, and hash-tables for fast data lookup.

The dynamic control system consists of the following components:

• The table of variables. It provides means for saving information about usage of various variables and for fast retrieval of the information by the variable address.

• The dynamic control module. It performs DVM-directives verification. The functions of the module are called from certain Lib-DVM functions each time when a variable or array is accessed. This module uses the table of variables as auxiliary module to accumulate and retrieve information about variables.

The trace comparison system consists of the following components:

• Unit accumulating the trace information in the memory. It accumulates and structures trace events during program execution.

• Unit writing the trace to a file. Accumulation unit uses it when program is running with trace writing mode specified.

• Unit reading the trace information from the files. It uses accumulation unit as auxiliary module.

• Unit comparing traces. It compares trace events of executing program with the reference trace previously formed in the memory.

• Unit checking reduction variables. It emulates execution of each iteration on the separate processor for checking of correctness of reduction operation descriptions. It works only in the special mode and with Lib-DVM support.

3. Approach and Principle for DVM debugger Implementation

The “Dynamic control of DVM-directives” method.

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) 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.

• 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 broadcasts to all processors.

• Distributed array. The array elements are mapped on the different processors. Each parallel branch can modify only elements that are located on its own processor.

• 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.

Undeclared data dependence in parallel loop

This checking is performed only when elements of distributed array are accessed. 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 (see below).

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, where this access occurred. Entering a parallel loop all these structures are initialized by a default status that means that element is not used yet. When an element is used inside a parallel loop the iteration number and access type are stored for this element. If an element is modified inside one iteration and then used inside another iteration the undeclared data dependence error is detected.

Checking private and read-only variables.

The type of a variable is determined when the first use of the variable inside a parallel loop 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 array has the array of flags). The flag is set if the variable is initialized inside given loop iteration 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.

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 before or inside a parallel loop. This is initial state of the reduction variable.

• The parallel loop 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 loop leaving but before asynchronous reduction completion the error will be detected.

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

Checking accesses to non-local or shadow elements of array.

The checking is performed only for distributed arrays.

When the program accesses to a distributed array inside a parallel loop 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.

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 few exclusions:

• Verifying the data dependencies in a parallel loop 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.

• Only read operations are allowed for elements of the remote data buffer.

The “Comparing execution results” method.

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 parallel or sequential loop.

• Beginning of iteration.

• End of a parallel or 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.