Roman's Law and Fast Processing with Multiple CPU Cores

And, don't forget to add -xopenmp to the set of command-line options:

$ cc -fast -xloopinfo -xautopar -xopenmp prime.c -o prime
"prime.c", line 14: not parallelized, loop has multiple exits
"prime.c", line 14: not parallelized, loop has multiple exits 
                    (inlined loop)
"prime.c", line 31: PARALLELIZED, and serial version generated
"prime.c", line 35: PARALLELIZED, user pragma used

Nice! We've got two out of three loops in our application now completely parallelized. Let's see how much faster it runs:

$ collect ./prime 2000000
Creating experiment database test.3.er ...
Number of prime numbers between 2 and 2000000: 146764
$ er_print -statistics test.3.er | grep Duration 
                              Duration (sec.): 1.132

No doubt, 294% is an impressive speedup, but how come we lost some prime numbers? We now have 146,764 of them reported instead of 148,933. Maybe the compiler was right in being conservative and not parallelizing that pesky loop. Should we go back and remove our OpenMP pragma? Not yet. Even though we've just caught a bug in our parallelized version of the same application (which only goes to show how easy it is to introduce bugs and how much more important regression testing becomes when you try to parallelize anything), we still are on the right track. The question is, how do we find the actual problem?

The trouble with parallel programming is that it makes some sections of your application nondeterministic. That means now you have to deal with all sorts of problems you didn't have to deal with before, such as race conditions, and deadlock and resource allocation issues are the chief nemeses. The amount of nondeterminism introduced is, in fact, something that makes POSIX threads quite fragile in most real-life situations—so much so, that one of the key parallel computing researchers, Professor Edward A. Lee, made a pretty scary prediction in his article “The Problem with Threads”:

As you can see, OpenMP, even though it introduces significantly less nondeterminism than POSIX threads do, is still not a panacea. After all, even our simplistic usage of it was enough to introduce a bug. It seems that regardless of how we express parallelism, what we need is a tool that would help us uncover concurrency bugs.

I know of two such tools freely available on Linux: Intel Thread Checker and Sun Studio Thread Analyzer. And, here's how you can use the latter one to combat data races (note that we need an extra compile-time command-line option -xinstrument=datarace to make thread analysis possible and that we have to ask collect for recording data race events by specifying -r on):

$ cc -fast -xloopinfo -xautopar -xopenmp -xinstrument=datarace 
 ↪prime.c -o prime   
$ collect -r on ./prime 2000000
Creating experiment database tha.1.er ...
Number of prime numbers between 2 and 2000000: 148933
$ er_print -races tha.1.er
No race information recorded in experiments

Weird. Not only did we get the correct result, but also the thread analyzer didn't seem to notice anything unusual. Is it broken? Not really. You see, what makes concurrent bugs so notoriously difficult to track down is the fact that most of them are intermittent. As with most manifestations of a nondeterministic behavior, they come and go depending on how applications are run, what else runs on the system and whether you use tools such as a conventional debugger. Thread analyzer reports only those problems that did actually occur. Well, if at first you don't succeed:

$ collect -r on ./prime 2000000
Creating experiment database tha.2.er ...
Number of prime numbers between 2 and 2000000: 114833
$ er_print -races tha.2.er
Total Races:  2 Experiment:  tha.2.er

Race #1, Vaddr: (Multiple Addresses)
   Access 1: Write, main -- MP doall from line 34 
    [_$d1B34.main] + 0x00000172, line 37 in "prime.c"
   Access 2: Write, main -- MP doall from line 34 
    [_$d1B34.main] + 0x00000172, line 37 in "prime.c"
Total Traces: 1

Race #2, Vaddr: 0xbffff28c
   Access 1: Write, main -- MP doall from line 34 
    [_$d1B34.main] + 0x00000189, line 38 in "prime.c"
   Access 2: Write, main -- MP doall from line 34 
    [_$d1B34.main] + 0x00000189, line 38 in "prime.c"
Total Traces: 1

Bingo! We reproduced the bug and our tool dutifully reported the actual location of where the race condition happened: lines 37 and 38. Things go wrong when two threads find prime numbers and they try to update the primes array and total variable—a textbook example of a race condition. But, it's pretty easy to fix. We have to serialize threads entering these two lines of code. Can we do that with OpenMP? Sure we can:

37 #pragma omp critical
38 {
39    primes[total] = i;
40    total++;
41 }    

With that, let's see what the final speedup is going to be:

$ cc -fast -xloopinfo -xautopar -xopenmp prime.c -o prime
$ collect ./prime 2000000
Creating experiment database test.4.er ...
Number of prime numbers between 2 and 2000000: 148933
$ er_print -statistics test.4.er | grep Duration 
                              Duration (sec.): 1.130

It's 2.95 times faster. Not bad for 15 minutes of work and four extra lines of OpenMP pragmas giving hints to the compiler!