Cold Tachyon

A bit more than a month ago, the first Russian online-seminar "Intel Parallel Studio workflow" by Intel took place. Kirill Mavrodiev, who was participating in the event, demonstrated how one can parallelize an application as a black box.

In other words, a typical case was examined when a developer deals with an unfamiliar code that must be modified - for example, parallelized. As a demo-example, the program Tachyon was chosen implementing the algorithm of ray tracing and drawing a three-dimensional fractal on the screen. The parallel programming technology OpenMP, Intel C++ compiler, multithreaded application profiler Parallel Amplifier and the tool for searching for parallel errors Parallel Inspector were chosen as a toolkit. After the seminar a new note "On a hot scent of the online seminar "Intel(R) Parallel Studio workflow"" was added.

We thought it over and decided that if the post was "on a hot scent" this text should be called "cold" then. And there is one more reason for that. Dynamic analysis at the stage of program execution performed by Parallel Inspector is for some reason associated with the word "hot". And the alternative approach that will be shown here rests on the static analysis of the source code and is rather associated with the word "cold".

We have been wishing for a long time to give a new example of using VivaMP analyzer included into PVS-Studio to detect errors in parallel code. It turned out that this alternative approach to code analysis can be well demonstrated by the example of Tachyon. Let we remind you that it was the tool Parallel Inspector that was used to search for parallel errors at the webinar. Error diagnosis is performed in several steps. We will demonstrate how VivaMP tool works at these steps.

Initially, we had a serial code:

TachyonStep1\trace.serial.cpp
unsigned int serial = 1;
unsigned int mboxsize = sizeof(unsigned int)*(max_objectid() + 20);
unsigned int * local_mbox = (unsigned int *) alloca(mboxsize);
memset(local_mbox,0,mboxsize);
for (int y = starty; y < stopy; y++) { {
    drawing_area drawing(startx, totaly-y, stopx-startx, 1);
    for (int x = startx; x < stopx; x++) {
       color_t c = render_one_pixel (x, y,
               local_mbox, serial, startx, stopx, starty, stopy);
       drawing.put_pixel(c);
   } }
   if(!video->next_frame()) return;
}

The code is absolutely correct and does not look suspicious either to Parallel Inspector, or to VivaMP.

Further, the code was modified as follows:

TachyonStep2\trace.par1.cpp
unsigned int serial = 1;
int ison=1;
unsigned int mboxsize = sizeof(unsigned int)*(max_objectid() + 20);
unsigned int * local_mbox = (unsigned int *) alloca(mboxsize);
memset(local_mbox,0,mboxsize);
#pragma omp parallel for
for(int y = starty; y < stopy*ison; y++) { {
    drawing_area drawing(startx, totaly-y, stopx-startx, 1);
    for (int x = startx; x < stopx; x++) {
      color_t c = render_one_pixel (x, y,
                local_mbox, serial, startx, stopx, starty, stopy);
        drawing.put_pixel(c);
    } }
    if(!video->next_frame()) ison=0;
 }

This bold parallelization led to an error and drawing an incorrect image on the screen. Using Parallel Inspector, we found out that there were several errors of race condition occurring in the code. After analyzing the Parallel Inspector's diagnostic warnings we decided to define the variables 'ison', 'local_mbox' and 'serial' as private, i.e. unique for every thread. It is these variables that lead to race conditions when addressing them. Now let us see what warnings are given by VivaMP analyzer for this code:

1 error V1206: Data race risk. The value of the 'scene' variable can be changed concurrently via the 'camray' function. r:\src\tachyonstep2\trace.par1.cpp 87

2 error V1206: Data race risk. The value of the 'local_mbox' variable can be changed concurrently via the 'render_one_pixel' function. r:\src\tachyonstep2\trace.par1.cpp 157

3 error V1206: Data race risk. The value of the 'serial' variable can be changed concurrently via the 'render_one_pixel' function. r:\src\tachyonstep2\trace.par1.cpp 157

4 error V1205: Data race risk. Unprotected concurrent operation with the 'ison' variable. r:\src\tachyonstep2\trace.par1.cpp 160

Pay attention that VivaMP analyzer warned about potential errors of race conditions for the same three variables: 'ison', 'local_mbox' and 'serial'. There is one more potential error of using 'camray' variable in another function but this point will be considered later.

Proceeding from the diagnosis results by Parallel Inspector we changed the code as follows:

TachyonStep2\trace.par2.cpp
unsigned int serial = 1;
int ison=1;
unsigned int mboxsize = sizeof(unsigned int)*(max_objectid() + 20);
unsigned int * local_mbox = (unsigned int *) alloca(mboxsize);
memset(local_mbox,0,mboxsize);
#pragma omp parallel for firstprivate(ison,local_mbox,serial)
for(int y = starty; y < stopy*ison; y++) { {
  drawing_area drawing(startx, totaly-y, stopx-startx, 1);
  for (int x = startx; x < stopx; x++) {
    color_t c = render_one_pixel (x, y,
            local_mbox, serial, startx, stopx, starty, stopy);
    drawing.put_pixel(c);
  } }
  if(!video->next_frame()) ison=0
}

The modified program still behaves incorrectly although it shows in a different way. Reanalysis of the code with Parallel Inspector reveals an error of shared use of one array 'local_mbox'. The directive firstprivate(local_mbox) creates a unique pointer for each thread. But the array itself, these pointers point to, is still shared.

VivaMP analyzer also managed to find this issue (see the second warning):

1 error V1206: Data race risk. The value of the 'scene' variable can be changed concurrently via the 'camray' function. r:\src\tachyonstep3.1\trace.par2.cpp 87

2 error V1209: Warning: The 'local_mbox' variable of pointer type should not be private. r:\src\tachyonstep3.1\trace.par2.cpp 153

Below is the final variant of the function where all the shortcomings are removed and the program builds the image of a fractal correctly:

TachyonStep2\trace.par3.cpp
#pragma omp parallel
{
unsigned int serial = 1;
int ison=1;
unsigned int mboxsize = sizeof(unsigned int)*(max_objectid() + 20);
unsigned int * local_mbox = (unsigned int *) alloca(mboxsize);
memset(local_mbox,0,mboxsize);
#pragma omp for
for(int y = starty; y < stopy*ison; y++) { {
  drawing_area drawing(startx, totaly-y, stopx-startx, 1);
  for (int x = startx; x < stopx; x++) {
    color_t c = render_one_pixel (x, y,
            local_mbox, serial, startx, stopx, starty, stopy);
    drawing.put_pixel(c);
  } }
  if(!video->next_frame()) ison=0
 }
}

This code does not look suspicious to Parallel Inspector. But VivaMP still generates one diagnostic warning which is a false alarm:

1 error V1206: Data race risk. The value of the 'scene' variable can be changed concurrently via the 'camray' function. r:\src\tachyonstep3.2\trace.par3.cpp 87

This warning refers to the function render_one_pixel called in parallel. VivaMP cannot make it out that the object 'scene' is used in several threads only for reading. You can easily remove this warning by defining the function a bit smarter. It is enough just to make the function's parameter 'scenedef' constant. I.e. replace

ray  camray(scenedef *, int, int);

with

ray  camray(const scenedef *, int, int);

After this modification VivaMP analyzer will generate no more warnings.

So, the task of searching for shortcomings in the parallel code of Tachyon was solved with the alternative approach. The method we have shown is neither better nor worse than the static analysis. The static analysis is fast and allows you to detect many errors at the stage of coding already, while the dynamic analysis diagnoses more errors and more accurately. These two methods can efficiently complement each other at various stages of software development.