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 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.
• Abnormal parallel program termination (GPFs, infinite looping, hanging) due to errors that not appear 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 of the checks can cause considerable overhead and therefore are performed by 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 parallel 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 a 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 because of incorrect specification of parallelism by DVM-directives or an error of sequential algorithm, appeared only during parallel execution. Unlike the first method, only part of program can be compiled in the special debug mode.

The facilities of parallel program tracing that are included into DVM-debugger may be also useful to detect errors of fourth class. Moreover the system tracing facilities are intended to detect these errors (the tracing of DVM Run-Time library calls).

1.1 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 only.

1.2 Kinds of detected errors

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

• Undeclared cross-iteration data dependencies in a parallel loop or task region.
• Using non-initialized variables.
• Modification of non-distributed variables not specified as reduction or private ones.
• Using reduction variables after the asynchronous reduction startup but before its completion.
• Violation of the distributed array bounds.
• Undeclared access to non-local elements of the distributed array.
• Writing to shadow edges of the distributed array.
• Reading shadow elements before completion of their updating.

1.3 The “Comparing execution results” method

First of all the dynamic control is intended to check 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 parallel execution of the program. 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.

To detect such errors another control method is provided. This method is based on an accumulation of trace results for different conditions of execution and these results comparison. When using 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 taking into account that values of some variables may differ (for example, values of reduction variables inside parallel construction).

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 the following base subsystems: tables allowing storing large volumes of uniformed information, hash-tables for fast data lookup by key, and diagnostic output module.

Other systems of higher level are based on these two subsystems.

The dynamic control system consists of the following components:

• The table of variables. It provides means for gathering 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 to accumulate the trace information in the memory. It accumulates and structures trace events during program execution.
• Unit to write the trace to a file. Accumulation unit uses it when trace writing mode is specified during the program execution.
• Unit to read the trace information from the files. It uses accumulation unit as auxiliary one.
• Unit to compare traces. It compares events of traced program with the reference trace previously formed in the memory by trace accumulation unit.
• Unit to check reduction variables. It emulates execution of each iteration of parallel loop and each parallel task on the separate processor for manual calculation of reduction operation. It works only when corresponding mode is specified.

3 Prototypes of debugger functions

The Lib-DVM system contains additional system functions relating to dynamic debugger that are responsible for dynamic control and comparing of execution results. The C-DVM and Fortran-DVM compilers insert calls of these functions in special debugging mode.

The prototypes of debugger functions is the following:

The function marks beginning of a variable or array element modification. The call should be inserted before a variable modification and up to an evaluation of expression to be assigned. The system call should be accompanied by dstv_ ().

The function marks the completion of a variable or array element modification. The call should be inserted after a variable modification and should be conjugate with dprstv_().

The function marks access to a variable or array element for reading.

The function marks parallel loop beginning. The function should be called before mapping the parallel loop on the abstract machine.

The function marks sequential loop beginning. The sequential loop rank is always equal to 1.

The function marks task region beginning. The task region rank is always equal to 1.

The function marks completion of a sequential or parallel loop or task region. The function should be called after completion of the last iteration of the loop or last parallel task in task region.

The function marks beginning of new iteration of a sequential or parallel loop or beginning of new parallel task. The function should be called after modification of all iteration variables of the loop (for multidimensional loops). For task region the variable, containing a number of current executed parallel task should be passed as the function argument.

The function marks remote access buffer creation for dynamic control system. This call is necessary to correct monitoring of access to the elements of a DVM-array through the remote access buffer. The call should be used after creation of the buffer and initialization of its elements.

The function marks the completion of own computation block in sequential branch of the program. The function should be called after execution of corresponding statement group.

4 Base modules implementation

4.1 Table

The table is intended to keep large volume of data. A peculiarity of the implementation is that the memory is allocated not for each element but for several ones. The number of elements the memory will be allocated for is defined by parameters of table initialization. The table is expanded automatically, when the current allocated memory block is exhausted.

The following structure is defined for the table:

The following calls are intended for work with the table:

Table initialization. This function should be called before using the table.

Table destructor. This function should be called upon usage of the table to free allocated memory. It calls element destructor for each element of the table.

The function returns number of used table elements.

The function returns the pointer to the specified table element.

The function inserts a new element into the table.

The function allocates a space for new element into the table and returns a pointer to this memory. The function is more effective then table_Put() because no memory copy operation is performed.

The function removes elements of the table starting from number Index+1. The element with the number Index itself remains in the table.

The function removes all elements from the table and frees allocated memory.

The function applies the same operation to each element of the table.

4.2 Hash-table

The hash-table is intended to fast lookup of records by a key. The hash-table is organized as an index of fixed size and chains of records, associated with each element of the index. Each record contains a value, placed into the hash-table, its key and pointer to the next record in the chain.

When new element is placed into the hash-table, hash-value in [0, IndexSize] range is calculated for its key. This value is a number of the element in the index of the hash-table, the pointer to new element of the chain will be placed into. Previous pointer is kept in placed element.

The search is performed as follows. The hash-value is calculated using the key. The pointer to the first element of the chain is extracted from the index by the hash-value. Then all elements of the chain is examined and compared with target element by the specified key. If the keys are matched, the found element is returned as result of the search.

The following algorithms can be used to calculate hash-values:

• StandartHashCalc. The following function is used: HASH-VALUE = (long)Key % HashIndexSize, where Key is the element's key, HashIndexSize is the size of the hash-index, % is operator to take the reminder of integral division.
• OffsetHashCalc. The following function is used: HASH-VALUE = ((long)Key >> Offset)% HashIndexSize, where Key is the element's key, HashIndexSize is the size of the hash-index, Offset is an offset specified as parameter, % is operator to take the reminder of integral division, and >> is shift left operator. If Offset = 0, this algorithm is identical to StandartHashCalc.

The following picture schematically shows realization of hash-table:

pIndex - index of hash-table
IndexSize - size of the index of hash-table
hTable - dynamic array, keeping hash-table elements
NextElem - pointer to the next element of the chain
Value - key of element
Assign - value, kept in the table and associated with the key

Figure 1. Foundation of hash-table

The following types are defined for the hash-table:

Hash-value:

Data type, used for associative search. A hash-value is calculated by this type:

Structure of the hash-table element:

Structure of the hash-table:

The following functions are intended for working with hash-table:

The function performs all required initialization operations for hash-table.

The function destructs the hash-table. The function frees all allocated memory for hash-table elements.

The function finds a value by the specified key.

The function inserts a new element into the hash-table.

The function updates an associated value for the specified key.

The function removes an element with the specified key.

The function applies the same operation for all the hash-table elements.

The function removes all elements from the hash-table.

4.3 Table of variables

The table of variables is intended to store information about variables and to fast access to it using the variable address.

Each element of a table of variables keeps the reference to the same variable at the previous level (if the variable is used at several levels), address of variable, class of using, and additional information that depends on class of using.

Figure 2. The variable-table representation

The following structure is used to store elements of table of variables:

The following structure describes a variable table:

The following functions are intended for work with table of variables:

The function initializes the table of variables.

The function destructs table of variables.

The function returns the variable information from the table of variables by variable number. The NoVar should point to a valid table of variables element.

The function returns the variable information from the table of variables by variable address. The function returns NULL if a variable with such address is not registered.

The function returns the variable number by variable address. The function returns –1 if a variable with such address is not registered.

The function registers of a new variable in the table of variables and returns a number of the registered variable.

The function uninitializes variable information structure. The function sets the Busy flag to 0 and calls corresponding variable information destructor if available.

The function removes variable information from the table of variables.

The function removes all variables from the table of variables.

The function removes all variables with the specified variable level.

The function applies the same operation for all the elements of the table of variables.

The function applies the same operation for all the elements of the table of variables with specified variable level.

4.4 Diagnostics output module

The module of diagnostics output has special requirements. The special requirements are demanded to the module of diagnostics. In the first, the detailed context of detected error should be reported. In the second, it is necessary to prevent output of many errors of the same type and in the same execution context that is possible when examining a program with the large loops.

At last, it is necessary to allow the user to output diagnostics both on a screen, and in a file for the consequent analysis.

The diagnostics module consists of two modules. The sub-module of context processing monitors current execution context of the program and allows to get a detailed current context description for diagnostics. The sub-module of diagnostics output prints detected errors and filters errors of the same type.

4.4.1 Processing diagnostics context

The program execution context represents description of all current executed loops and current values of all their iteration variables. The current context varies each time, when entering or leaving the parallel or sequential loop or when new iteration execution begins.

The following structure is used to describe program execution context:

Each CONTEXT structure describes one loop of the program. The sequence of such structures completely describes a current program execution context and order of a loop enclosure.

The global table gContext is used for storage the sequence of CONTEXT structures in the system. The root context with number zero is put to the gContext when system is initialized. This context corresponds to main() program procedure.

Figure 3. Program execution contexts representation

The following functions are intended to work execution context:

The function initializes global variables that are used to work with execution contexts. This function also initializes the root context with zero number corresponding to the main program branch.

The function uninitializes global variables used for the work with execution contexts.

The function defines a new program execution context. The function is called when the program begins execution of a new parallel or sequential loop or task region.

The function defines completion of the current program execution context. The function is called when leaving a parallel or sequential loop or task region.

The function updates values of iteration variables. The function is called when a new iteration or parallel task begins.

The function returns pointer to current context definition.

The function returns pointer to context definition with the specified context number.

The function returns count of registered program execution contexts.

An enclosure depth of program parallel constructions (parallel loops and task regions) is returned.

The function returns current parallel structure execution state.

The function returns absolute index of current executed loop iteration. For task regions the function returns number of current executed task.

The function returns not zero value if it is called in the context of parallel loop or parallel task.

The function returns most nested executed parallel context. It returns NULL if there is no currently executed parallel context.

The function forms description of current loop execution context and puts it into the Str string. The function returns pointer to the end of formed string.

4.4.2 Diagnostics output functions

Dynamic debugger outputs error diagnostic when it is detected. The messages are printed to a screen or file dependently on parameters of dynamic debugger and modes of DVM system. The repeated error in the same context is printed only once. After completion of a program the dynamic debugger outputs summary information about all found errors with a count of error repetition.

The common structure of error message is following:

(<process number>)<context> File: <file>, Line: <line>

(<count> times)<error message>

where:

The following structure is intended to store an error description:

The following structure is intended to store detected errors:

The following functions are intended for work with diagnostics output:

The function initializes the table of diagnostics.

The function uninitializes the table of diagnostics and frees memory allocated for table of diagnostics.

The function puts a new error message into the table of diagnostics. The function returns pointer to error diagnostic record in the table.

The function searches the error message with the specified parameters in the table of diagnostics. The function returns pointer to found error diagnostic record or NULL if error message was not found.

The function registers a new error message in the table of diagnostics. If the table does not have a message with the specified parameters then the message will be put into the table and written into the specified file. Otherwise, the Count field of the corresponded record will be incremented only.

The function writes the specified error message into the file.

The function writes all error messages from the table of diagnostics into the specified file.

The function registers a new detected error of dynamic control module.

The function outputs all error messages of dynamic control module.

The function registers a new detected error about trace or loop description file structure.

The function registers a new detected error of comparing execution results module.

The function outputs all error messages of comparing execution results module.