Channels ▼
RSS

Parallel Lint


Andrey Karpov is PhD candidate in the field of mathematical modeling, numerical methods, and complexes of the programs. Andrey defended his thesis in the Institute of Mathematical Modelling under Russian Academy of Sciences. The theme of his thesis is "Data Processing in Parallel Computer Complexes".


Static code analysis is a process of software verification without actual execution of programs being examined. Usually it is the source code of the program that is directly analyzed, although sometimes one type of object code is analyzed.

Static analysis is a kind of software testing with the help of code review. With code review, the code being tested must be looked through by a person. With static analysis, specialized software called a "static analyzer" takes part of the work. A static analyzer detects potentially unsafe places in the program code and suggests the user perform further analysis and correction of these places. It helps reduce the amount of work of code review.

One of the first static analyzers (and most popular) was the Lint utility, which appeared in 1979 as part of Unix 7 distribution kit as the main tool of controlling the quality of software written in C (see Checking C Programs with lint, by Ian F. Darwin, and Wikipedia Lint). This tool is so popular that the word "lint" has become synonymous of "static analyzer".

Some time later, new analysis tools -- both general-purpose and specialized -- began appearing: Coverity Prevent, PC-Lint, Klocwork K7, PolySpace, Viva64, FXCop, C++Test, JLint, and UNO, to name a few. These static analyzers detect numerous varieties of errors, and they are constantly being modified to detect even more types of errors.

As multicore microprocessors came on the scene, so did parallel programming. However, parallel programming requires specialized tools for creating, testing, and debugging programs. And while the tools for creating parallel applications are already pretty good, tools for verification and testing are less so. In other words, we've its time for tools that enable the verification of parallel applications. It's time for "Parallel Lint".

Parallel Lint is not a name of a concrete tool. But it is a good phrase which describes the new class of tools for analyzing parallel code. In this article, I will acquaint you with some tools in which diagnosing of the new class of parallel errors is implemented and which can be justly called "Parallel Lint".

PC-Lint

Version 9 of Gimpel Software's PC-lint diagnoses errors in parallel programs built on POSIX threads. In other words PC-Lint tool is not focused on a particular parallel technology and can be adapted by a user for the programs built on various libraries implementing parallelism. This flexibility is achived due to arrangement of auxiliary comments for PC-Lint in the code and its settings. As usual, the price of this flexibility is a higher complexity.

Still, complex settings are needed only if you use a parallel technology unknown to PC-Lint. PC-Lint supports POSIX threads and can detect errors relating to locks by itself if such functions as pthread_mutex_lock() and pthread_mutex_unlock() are used.

PC-Lint requires some hints from the programmer's side and is helpless without them. The point is that the static analyzer does not know if some code section is executed in parallel mode and can only make some suggestions. Here are the two main reasons for this behavior:

  • Like compilers, static analyzers operate each .cpp file separately. And that's why if f() function is called in parallel mode in file A from file B, we cannot know this when analyzing file B. Of course, there are static analyzers which analyze the whole set of files at once but it is a very difficult task. At least, PC-Lint operates each file separately.

  • Even if the call of f() function is located in the same file, it is still not easy to understand whether this is a parallel call or not. The call can depend on the logic of the algorithm and input data which the static analyzer lacks.

Let's consider an example of the function (originally presented in PC-Lint 9.0 manual):


void f()
{
  static int n = 0;
  /* ... */
}

The problem is that if f() function is called from parallel threads, an initializing error n variable may occur. To diagnose this case, you need to explicitly tell PC-Lint analyzer that f() function can be called in parallel mode. To do so you need to use a construction like:


//lint -sem(f, thread)

Then, when diagnosing the code, you will see the warning:

Warning 457: "Thread 'f(void)' has an unprotected write access to variable 'n' which is used by thread 'f(void) ."

If the parallelizing mechanism isn't built on POSIX threads, you will have to use special additional directives to provide hints to PC-Lint about what functions cause locks and unlocks:


-sem(function-name, thread_lock)
-sem(function-name, thread_unlock)

In this case you can detect errors in the code like the following:


//lint -sem( lock, thread_lock )
//lint -sem( unlock, thread_unlock )
extern int g();
void lock(void), unlock(void);
void f()
{
  //-------------
  lock();
  if( g() )
    return; // Warning 454
  unlock();
  //-------------
  if( g() )
  {
    lock();
    unlock();
    unlock(); // Warning 455
    return;
  }
  //-------------
  if( g() )
    lock();
  { // Warning 456
    // do something interesting
  }
}

PC-Lint analyzer can efficiently find errors relating to parallelism if you give the necessary "hints" to it beforehand. Otherwise, it can perform analysis of a parallel code as of a sequential one and therefore fail to detect some errors.

Despite the necessity of additional work of arranging the hints, PC-Lint tool is a convenient and powerful tool able to detect many parallel errors. It can be especcialy useful when used together with Visual Lint shell providing a more convenient user interface to this analyzer.

To learn more about diagnostic abilities of PC-Lint 9.0, see PC-lint/FlexeLint 9.0 Manual Excerpts.

Among the tool's disadvantages, however, I should mention its inability to diagnose parallel code built on OpenMP technology. It does not process OpenMP directives and hints will not help here. But there are other static analyzers for diagnosing OpenMP programs and I examine them further (see Peaceful Coexistence of PC-Lint and VivaMP.

VivaMP

VivaMP is a powerful specialized tool intended for verification of the code of applications built on OpenMP technology. This tool has been initially developed with the purpose of testing OpenMP parallel code and that's why it can claim to be called "Parallel Lint" more than all the others.

The analyzer integrates into Visual Studio 2005/2008 environment and allows you to start work immediately without complicated settings or arrangement of comments in the program code. It is a great advantage of the tool for it allows you to try and master the product easily. Like any other static analyzer VivaMP will require additional setting while operating it to reduce the number of false responses. But this is an inevitable sacrifice all the static analyzers demand.

A description of OpenMP directives provides information about the program's structure -- which part is executed in parallel mode, which resources are local and which are general etc. This lets the analyzer perform a thorough analysis without demanding assistance of the programmer.

To illustrate the basic VivaMP operations, here are several simple examples.

Example N1


#pragma omp parallel for
for (size_t i = 0; i != n; ++i)
{
  float *array =
    new float[10000]; // V1302
  delete [] array;
}

In this code, the VivaMP analyzer diagnoses the following error:

V1302. "The 'new' operator cannot be used outside of a try..catch block in a parallel section."

The error relates to throwing an exception from a parallel block. According to the OpenMP specification, if you use exceptions inside a parallel block all these exceptions must be processed inside this block. If you use the new operator inside parallel code, you must provide catching of the exception which will be generated according to C++ standard when a memory allocation error occurs.

This example leads to incorrect program behavior and most likely to program crash if an error of memory allocation occurs.

Correction of the code lies in processing of exceptions inside the parallel block and transferring of information about the error via other mechanisms or refusing to use new operator.

The following corrected code is safe from the viewpoint of VivaMP analyzer:


#pragma omp parallel for
for (size_t i = 0; i != n; ++i)
{
  try {
    float *array =
      new float[10000]; // OK
    delete [] array;
  }
  catch (std::bad_alloc &) {
    // process exception
  }
}

Example N2


int a = 0;
#pragma omp parallel for num_threads(4)
for (int i = 0; i < 100000; i++)
{
	a++; //  V1205
}

This is an example of a typical race condition error. This is a programming error of a multi-taskubg system where operation of the system depends on the order in which the code parts are executed. A race condition appears when several threads of a multithread application try to get access to data simultaneously and one thread is performing writing. Race conditions can lead to unexptected results and are often difficult to detect. Sometimes the consequences of the race condition can occur only in a very large time period and in quite a different place of the application. To avoid race conditions, synchronization means are used which let you arrange operations executed by different threads in a right way.

In this code VivaMP analyzer diagnoses the following error:

V1205. Data race risk. Unprotected concurrent operation with the "a" variable.

As all the threads are writing into the same memory space and reading from it simultaneously, the value of the variable after this cycle cannot be predicted. To make this operation safe, you must put it into a critical section or (for in this example the operation is elementary) use #pragma omp atomic directive:


int a = 0;
#pragma omp parallel for num_threads(4)
for (int i = 0; i < 100000; i++)
{
	#pragma omp atomic
	a++; // OK
}

To learn more about type errors occurring when developing OpenMP applications, see the article 32 OpenMP Traps for C++ Developers. Diagnosing of most of the errors described in the article is already implemented in VivaMP analyzer or will appear in new versions.

Static Analysis Implemented in Intel C++ Compiler

The capability of diagnosing parallel OpenMP errors is implemented in the Intel C++ 11.0 compiler. The static analyzer embedded into Intel C++ compiler lets you diagnose various synchronization errors, race conditions, and the like. For this, you must define the key /Qdiag-enable:sc-parallel{1|2|3} to the compiler, where numbers define the level of analysis. An additional parameter which is important when analyzing parallel programs is the compiler's key /Qdiag-enable:sc-include which points to the compiler to search errors in header files as well.

When testing a parallel program, the compiler does not generate the code being executed. At the compilation stage, special pseudo-object files (*.obj) are created which contain data structures including information necessary for analysis instead of object code. Then these files are sent to the input of the static analyzer which performs analysis of the parallel code.

Again, the executed code is not generated when setting the compiler for static analysis of parallel OpenMP programs. That's why it would be a convenient solution to keep separate configurations for building of a project and for its static analysis.

As a result, developers can, for example, detect an error in the following code:


#include <stdio.h>
#include "omp.h"
int main(void)
{
  int i;
  int factorial[10];
  factorial[0]=1;
  #pragma omp parallel for
  for (i=1; i < 10; i++) {
   factorial[i] = i * factorial[i-1]; // warning #12246
  }
  return 0;
}

In static analysis mode Intel C++ compiler will show the following warning:

omp.c(13): warning #12246: flow data dependence from (file:omp.c line:13) to (file:omp.c line:13), due to "factorial" may lead to incorrect program execution in parallel mode".

To learn more about the technology of Intel C++ static analysis, see Dmitriy Petunin's webinar Static Analysis and Intel? C/C++ Compiler ("Parallel Lint" Overview).

As you see, functionality of Intel C++ static analyzer is similar to VivaMP's. I cannot say which one is better and can be useful for your tasks. On one hand, the analyzer in Intel C++ is a tool you get together with the compiler. On the other hand, there are a lot of various functions in Intel C++ compiler and "Parallel Lint" is only one of them while VivaMP analyzer is a highly tailored product which is rapidly developing.

Most likely, VivaMP analyzer would be useful for those developers who use Visual C++ as it allows performing analysis without any changes in a project's configurations and source code. To use Intel C++ abilities, developers will have to adapt their project for building it by this complier at first. That's why "Parallel Lint" in Intel C++ would be useful first of all for those developers who have been already using Intel C++ compiler to build their applications.

Conclusion

Of course, there are other tools which can claim to be called "Parallel Lint". But these tools are mostly dynamic analyzers or combine static and dynamic analysis. So it would be incorrect to describe them in this article. You can get acquainted with some of them in the article Tools And Techniques to Identify Concurrency Issues.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video