Alexey Kolosov , Andrey Karpov , Evgenii Ryzhkov

Apr 19 2009

VivaMP, system of detecting errors in the code of parallel C++ programs using OpenMP

• 1. Introduction
• 2. Using static analysis for debugging of parallel programs
• 3. Errors diagnosed
• 3.1. Absence of parallel key-word
• 3.2. Incorrect use of locks
• 3.3. Unprotected access to main memory
• 4. VivaMP analyzer
• References

The article lists the results of investigation of mistakes made by programmers using C++ and OpenMP. Static analysis is offered for automatic detection of these errors. The description of VivaMP analyzer integrating into Visual Studio environment and implementing the set task is described.

1. Introduction

According to the survey by Evans Data company conducting surveys among software developers, the general number of programmers will be 17 million people by 2009 [1]. Currently, 40% of them use C++ and 70% are involved in development of multi-thread applications now or are planning to start it during the year. According to the same survey 13,2% of these developers think that the main problem of these developments is the lack of software tools for creation, testing and debugging of parallel applications. Consequently, 630.000 programmers are directly interested in solving the task of automatic search of errors in the source code.

The aim of this work is to create a static code analyzer intended for automatic detection of such errors. The research considered C++ language for it is the code in this language to which high-performance requirements are made. As support of OpenMP technology is embedded into Microsoft Visual Studio 2005 and 2008 and some specialists believe that it is OpenMP that will gain the greatest popularity [3], we considered this very technology (which is used also for C and Fortran languages besides C++).

Analysis of reviews of debuggers for parallel programs shows that the situation in this sphere is far from an ideal. Concerning debugging of programs written in C++ and using OpenMP, TotalView and Intel Thread Checker are mentioned. But both tools are intended for dynamic operation mode. Until recently the procedure of static analysis of OpenMP programs hasn't been mastered. Perhaps, the only example we can give is rather a quality diagnosis provided by Sun Studio compiler. VivaMP static analyzer has taken this place.

2. Using static analysis for debugging of parallel programs

Most of the currently existing tools for debugging parallel programs are dynamic analyzers presupposing direct execution of the program being analyzed. This approach has some advantages but there are disadvantages too.

Dynamic analysis presupposes data collection only during execution of a program, and consequently it is not guaranteed that the whole code will be tested. Moreover, when using this approach a programmer must repeat the same actions many times or use tools of automatic testing to imitate user's actions.

Besides, during dynamic analysis the code of the application being debugged is tooled and this reduces the program's performance and sometimes can cause failures. As collection and analysis of information is performed, as a rule, at the end of dynamic analysis to increase performance, in case of a critical error in the analyzed application all the results will be lost.

Finally, dynamic analysis doesn't always allow you to detect a concrete code fragment leading to unexpected behavior.

Static analysis allows you to look through the whole source code of an application, detects dangerous code sections and doesn't require additional efforts from a programmer. The disadvantage of static analysis is that it doesn't allow you to check behavior depending on a user. False responses are one more problem and reduction of their number demands additional efforts when developing the analyzer. The issue of using static analysis when developing parallel programs is considered in detail in the article [4].

VivaMP analyzer uses tree walk analysis. Besides, there are other types of static analysis implying modeling of execution of a program, calculation of possible values of variables and ways of code execution. Static analysis as a means of diagnosing errors in parallel programs was chosen because this approach allows us to detect many errors which dynamic analyzers fail to diagnose. Now let's consider the errors themselves in detail.

3. Errors diagnosed

The list of possible errors not detected by Visual Studio compiler has been composed as the result of research of the works devoted to parallel programming using OpenMP and also on the basis of the authors' personal experience. All the errors can be divided into four main categories:

• Insufficient knowledge of OpenMP syntax.
• Insufficient understanding of OpenMP's operation principles.
• Incorrect work with memory (unprotected access to main memory, absence of synchronization, incorrect variable-access mode etc).
• Performance errors.

The first three types of errors are logic errors which lead to change of the program's working logic, to unexpected results and (in some cases) to program crash. The last category unites errors leading to performance decrease.

Let's give examples of errors of each category and their brief description.

3.1. Absence of parallel key-word

Let's consider a simplest error which can occur because of incorrect writing of OpenMP directives. As these directives have rather a complex format, any programmer can make this mistake due to this or that reason.

Example of an error caused by absence of parallel key-word:

// Incorrect:
#pragma omp for
... // for loop
// Correct:
#pragma omp parallel for 
... // for loop
// Correct:
#pragma omp parallel
{
  #pragma omp for
  ... // for loop
}

The fragment of incorrect code given above will be successfully compiled by the compiler even without any warnings. The incorrect directive will be ignored and the loop following it will be executed only by one thread. No paralleling will take place and it will be difficult to see this in practice. But the static analyzer will point at this potentially incorrect code section.

3.2. Incorrect use of locks

If a programmer uses functions like omp_set_lock for synchronizing and/or protecting an object from simultaneous writing, each thread must contain calls of the corresponding functions omp_unset_lock and with the same variables. An effort to release a lock captured by another thread or absence of call of an unlocking function can lead to errors and an eternal waiting during program execution. Let's consider an example of code:

Example of incorrect use of locks:

// Incorrect:
omp_lock_t myLock;
omp_init_lock(&myLock);
#pragma omp parallel sections
{
    #pragma omp section
    {
          ...
          omp_set_lock(&myLock);
          ...
    }
    #pragma omp section
    {
          ...
          omp_unset_lock(&myLock);
          ...
    }
}
// Incorrect:
omp_lock_t myLock;
omp_init_lock(&myLock);
#pragma omp parallel sections
{
    #pragma omp section
    {
           ...
           omp_set_lock(&myLock);
           ...
    }
    #pragma omp section
    {
           ...
           omp_set_lock(&myLock);
           omp_unset_lock(&myLock);
           ...
    }
}
// Correct:
omp_lock_t myLock;
omp_init_lock(&myLock);
#pragma omp parallel sections
{
    #pragma omp section
    {
           ...
           omp_set_lock(&myLock);
           ...
           omp_unset_lock(&myLock);
           ...
    }
    #pragma omp section
    {
           ...
           omp_set_lock(&myLock);
           ...
           omp_unset_lock(&myLock);
           ...
    }
}

The first example of incorrect code will lead to an error during execution of the program (a thread cannot release the variable captured by another thread). The second example will sometimes work correctly and sometimes lead to a hang. It will depend on what thread finishes last. If it will be the thread in which lock of the variable is performed without its release, the program will give the expected result. In all the other cases there will be an eternal waiting for release of the variable captured by the thread working with the variable incorrectly.

Now let's consider another error in detail and give the corresponding rule for the analyzer.

3.3. Unprotected access to main memory

This error can occur in any parallel program written in any language. It is also called a race condition and consists in that the value of a shared variable changed simultaneously by several threads can be unpredictable as the result. Let's consider a simple example for C++ and OpenMP.

Example of a race condition:

// Incorrect:
int a = 0;
#pragma omp parallel
{ 
    a++;
}
// Correct:
int a = 0;
#pragma omp parallel
{ 
    #pragma omp atomic
    a++;
}

This error can be also detected with the help of the static analyzer. Here is a rule according to which VivaMP static analyzer can detect this error:

"Initialization or modification of an object (variable) in a parallel block must be considered dangerous if the object is global in relation to this block (shared for threads)".

To global objects in relation to a parallel block refer:

• Static variables.
• Static class members (not implemented in VivaMP 1.0).
• Variables defined outside a parallel block.

An object can be both a simple-type variable and a class-instance. To operations of object change refer:

• Passing of an object into a function by a non-constant link.
• Passing of an object into a function by a non-constant pointer (not implemented in VivaMP 1.0).
• Change of an object when performing arithmetic operations or assignment operations.
• Call of a non-constant method of an object.

At first sight there is nothing complicated. But to avoid false responses we have to introduce many exceptions. The code being checked should be considered safe if:

• The code is located outside a parallel block ("parallel" directive is absent).
• Modification of an object is protected by "atomic" directive.
• The code is located in a critical section defined by "critical" directive.
• The code is located in a critical section created by functions of omp_set_lock type.
• The code is located in the block of "master" directive.
• The code is located in the block of "single" directive.
• "threadprivate" directive or "private", "firstprivate", "lastprivate" or "reduction" expressions are applied to an object (variable). This exception doesn't concern static variables and static class fields which are always shared.
• Initialization or modification of an object is performed inside for operator (inside the operator itself and not inside the loop body). Such objects are automatically considered private according to OpenMP specification.
• Modification of an object is performed inside a section defined by section directive.

Following this rule and the listed exceptions the analyzer can detect an error by the code tree.

In conclusion we would like to say that you can find a more detailed list of the errors detected during researches and more detailed descriptions of them on the site of VivaMP project.

Now let's see the description of the analyzer itself.

4. VivaMP analyzer

VivaMP analyzer was developed on the basis of VivaCore code analysis library and together with Viva64 comprises a single line of products in the sphere of testing resource-intensive applications. Viva64 is intended for searching errors relating to porting 32-bit software on 64-bit platforms. VivaMP is intended for testing parallel applications built on the basis of OpenMP technology. Like Viva64, VivaMP integrates into Visual Studio 2005/2008 development environment adding new commands to the interface. Setting of the analyzer is performed through the environment-standard mechanism and diagnostic messages are displayed in the same way as those of a standard compiler - in the windows Error List and Output Window. Besides, there is a detailed description of errors given in the analyzer's Help system integrating into Visual Studio Help. Context help is implemented through the standard environment's mechanism. VivaMP analyzer's interface integrated into Visual Studio environment, is shown in Figure 1.

Figure 1. VivaMP interface

At present the first version of the analyzer is released and you can see information about it here: http://www.viva64.com/en/vivamp-tool/. The first VivaMP version diagnoses 19 errors, and the amount of materials collected and experiments' results allow us to significantly increase this number (minimum twice) in the next versions. Below are listed brief descriptions of the errors diagnosed:

• Absence of "parallel" key-word.
• Absence of "omp" key-word.
• Absence of "for" key-word (each thread will execute a loop completely, the work won't be shared between the threads).
• Embedded paralleling of "for" loop.
• Absence of "ordered" directive in an ordered loop.
• Redefining of the number of threads in parallel code.
• Asymmetrical use of locking/unlocking functions.
• Dependence of the code's behavior on the number of threads executing it (use of "omp_get_num_threads" function in an arithmetic operation).
• Redefining of the ability of embedding paralleling in parallel code.
• Simultaneous use of the shared resource (unprotected function call).
• Use of "flush" directive for pointers.
• Use "threadprivate" directive. The directive is dangerous as it influences the whole file. It is recommended to use local variables or explicitly define the type of access in each parallel block.
• Unprotected definition of a static variable in parallel code.
• Unprotected simultaneous operation with a variable.
• Simultaneous change of a variable by calling a function.
• Simultaneous change of an object by calling a function.
• A link-type variable cannot be defined as local.
• A pointer cannot be a local variable.
• A variable defined as "lastprivate" is not changed in the lexically last parallel section.

Besides already achieved results, we continue searching new errors. If you, dear colleagues, know some patterns of such errors we would be glad if you told us about them by using contact information on the above mentioned site of VivaMP project.

Besides, it would be interesting to test our analyzer on real serious projects using OpenMP technology. If you are developing such a project and need a code analyzer, please contact us.

References

• Timothy Prickett Morgan. Evans Data Cases. Programming Language Popularity: [https://www.itjungle.com/2006/12/11/tfh121106-story07/], 14.12.2006.
• Michael Suess. Why OpenMP is the way to go for parallel programming: [http://www.thinkingparallel.com/2006/08/12/why-openmp-is-the-way-to-go-for-parallel-programming/], 12.08.2006.
• E.A. Ryzhkov, O.S. Seredin. Using static code analysis technology when developing parallel programs. Izvestiya TSU. Technical sciences. Issue 3. - Tula: TSU Publishing House, 2008. - 267 pp. Pp. 191 - 196.
• Alexey Kolosov, Evgeniy Ryzhkov, Andrey Karpov. 32 OpenMP Traps for C++ developers. RSDN Magazine #2-2008. Pp. 3 - 17.

0

0

0

0

SHARE

We can email you a selection of our best articles once a month