Silicon Graphics has implemented parallel extensions to the C compiler for the 4D Power Series computers that enable both SIMD (loop) and MIMD (independent block) parallelization. Code containing these extensions can be ported into serial C environments, recompiled, and executed without change. In direct contrast to older methods of parallelization that generally involved heavy use of platform-specific system calls combined with code restructuring, parallelized code using IRIS Power C retains its serial structure. In this article, I will introduce you to the basics of parallelizing C code with IRIS Power C, discuss data dependence as an important limitation, and end with two program examples to convince you that the phrase "portable parallel C" is not an oxymoron.

I'll start this discussion by describing in general terms how SGI does parallelism on a shared-memory multiprocessor workstation. A parallelized program is a serial program that contains regions of parallel execution. On entering a parallel region, the serial program is transformed from a single process to multiple processes, each running one of the parallel-execution threads. These regions and their parallel-execution behavior are determined by #pragma directives included in the code and interpreted by the compiler with the -mp option; otherwise they are ignored.

At the system level, changes have been made to UNIX to support process-based parallelism on one hand and multiple processors on the other, while maintaining system generality. A parallel program's processes (threads) are allowed access to shared memory. They maintain data structures that transparently coordinate interprocess data access and process synchronization. Otherwise, they behave like other processes in the scheduler's queue. Parallel execution itself is done in sched, the UNIX preemptive-multitasking scheduler, which has been modified to distribute processes over multiple processors rather than the usual one. A parallelized program's threads timeshare with other tasks run by the system, either parallel or serial, resulting in a flexible execution environment. On an eight-processor system, this environment can execute eight serial programs in the time of one, a single parallelized program up to eight times faster, or a mix of serial and parallel programs significantly faster.

SGI implements the SIMD and MIMD parallel models. SIMD is the easiest to understand and implement. In a for loop that processes members of an array, all threads execute the same code on different array elements. The individual iterations of the loop are divided between the available threads and executed on them. For instance, if four threads are available, a 1000-iteration loop is parallelized by executing iterations 0-249 by thread 0, 250-499 by thread 1, and so forth. If each iteration has the same execution time, a four-thread system can be close to four times faster than serial execution. IRIS Power C currently limits loop parallelization to the for-loop construct because it is the only loop construct within C which lets you define an index, a maximum number of iterations, and an increment.

MIMD is implemented as independent-block parallelism. A block of code within a function can be executed on its own thread, independent of other blocks. In contrast to loop parallelization, the code in each block may operate differently on global and local (private) data. Program speedups are less easily determined, being highly dependent on the nature of the code. Implementation of MIMD parallelization is limited by the lack of a suitable programming landmark, such as a loop, to attract attention.

The two models can be mixed and matched in a program either in separate parallel regions or even within a single parallel region. Two threads might execute independent blocks of code using the MIMD model, while six threads execute a for loop using the SIMD model. The limiting factor seems to be keeping the program structure straight. To avoid confusion, I use one model per parallel region.

Variables within code executed in parallel are either shared between threads or local to a specific thread. Shared means just that: Each execution thread points to a single location in shared memory associated with that variable. The values within the variable persist past the parallel region of the program. Unless access to the code containing the shared variable is restricted, all threads can read or write to the variable. Shared array variables are common in loop parallelism.

Local variables within the thread point only to a private copy of the variable. The local variable exists in all threads created within the parallel region. The values within a local variable are not defined beyond the parallel region. Local variables are used exclusively within the parallel region and can be of any data type. Loop indexes and temporary variables are often local.

For parallelism to work correctly, the code in each thread must not modify the values of variables in use by other threads. If this happens, the variable becomes dependent on more than one thread, its value becomes unpredictable, and the results possibly incorrect. An example in SIMD parallelization is when each iteration processes a unique array element, such that the iteration's execution order does not affect the results: Iteration i processes shared variable a[i], iteration i+1 does a[i+1], and so forth.

  for (sum=i=0; i<max; i++)
      sum += a[i];

  for (i=1; i<max; i++)
      a[i] = b[i] * a[i-1];

To test for dependence in loop parallelization, index the for loop backwards during serial execution. If the result is correct, there are probably no dependencies.

You introduce parallelism into a program in two steps. First, define the region in the source code in which parallelism will be active and declare the parallel behavior of all variables for the region. Second, select for loops or blocks located within the parallel region for parallelization. The first step establishes the environment and the second speeds up execution. Multiple for loops, independent blocks, or combinations can be established within a single parallel region, and a program can have as many parallel regions as necessary.

The most time-consuming part of the program is the best place to introduce the parallel region. Speedup of this block will generally result in a dramatic improvement in overall program performance, even if it is a relatively small amount of code. Parallelization of less-sensitive blocks may yield little if any performance return. Profiling serial execution locates the desired "hot spots."

  Code Block

  becomes

  #pragma parallel
  #pragma shared (arrayvar1, arrayvar2..., grandtotal)
  #pragma local (index1, index2, subtotal1,...)
  #pragma byvalue (shared_constant1,...)
  {
     Code Block
  }
  or, the equivalent

  #pragma parallel shared (list) local (list) byvalue (list)
  {
     Code Block
  }

Declare the behavior of variables within the parallel region with the modifiers to #pragma parallel. The lists consist of the variables of any given type, separated by commas. The byvalue modifier is a special shared type used for scalars that maintain constant value within the parallel region, such as a for loop bounds limit, yielding a net savings on overhead. All values not declared are assumed to be shared, but fully declaring all variables helps clarify intent.

  /* strictly local code */
  #pragma parallel
  #pragma local (i, j)
  {
      for (i=sum=0; i<1000; i++)
           sum += i;
      printf ("sum = %d\n", sum);
  }

Within the parallel region, one or more for loops can be set for loop parallelization. Only those for loops in which the exact number of iterations is known at compile time can be parallelized. To take advantage of loop parallelization, while and do while loops must be rewritten into for loops, if possible.

  for (i=0; i<max; i++)
           b[i] = const*a [i];

  becomes

  #pragma parallel shared (a,b) local (i) byvalue (max, const)
  {
  #pragma pfor iterate (i=0; max; 1)
      for (i=0; i<max; i++)
          b[i] = const*a [i];
  }

The above transformations can be ported from the Power Series environment to other serial environments. In a serial environment, the compiler ignores the two pragmas (typically with warning messages), as well as the additional code block created by the added braces, and compiles the original for loop. The resulting code executes as expected without removal of the parallelism directives. The compiler on a Power Series machine, with multiprocessing (-mp) active, transformed the code for parallel execution.

Block parallelization allows for parallelization of C constructs like linked-list manipulation and other operations not amenable to loop parallelization. The principal weakness is a lack of an attention-drawing landmark, such as a for loop, to provide hints as to the parallelization approach.

Independent blocks are created by placing the selected block code within a code block preceded by #pragma independent. Each independent block created executes on a single thread. Any number of blocks can be created in a single parallel region. If the available threads outnumber the blocks, each executes on its own thread and the remaining threads move on to the next parallel construct in the parallel region. If blocks outnumber threads, then the independent blocks execute as threads become available. If a pfor block follows a group of independent blocks in a single parallel region, the execution behavior can potentially become complex.

  code block 1
  code block 2

  becomes

  #pragma parallel shared (list) local (list) byvalue (list)
  {

      #pragma independent
      {
          code block 1
      }
      #pragma independent
      {
          code block 2
      }
  }

Independent-block parallelization is also portable. A serial compiler ignores the pragmas (again with warning messages) and the added code blocks created by the braces and processes the original two code blocks. The serial execution behavior remains block 1, then block 2. Block order is important for maintaining portability: If, for instance, block 1 adds elements to a linked list, and block 2 removes elements off the same linked list, parallel execution may be correct regardless of the starting order. However, serial behavior will be wrong if block 2 tries to remove elements from a linked list not yet filled with elements by block 1.

  sum = 0.0;
  #pragma parallel shared (sum, a) local (i) byvalue (max)
  {
      #pragma pfor iterate (i=0; max; 1)
          for (i=0; i <max; i++)
              sum += a[i];
  }

Isolate data dependencies by placing the statement containing the dependence within a code block preceded by #pragma critical. Only one thread at a time has access to the code within the critical block; threads that arrive at the critical block while it is occupied wait until it is free. The code within the critical block is ultimately executed by all threads.

Portability for the critical block into the serial environment is maintained. The serial compiler ignores both #pragma critical and the additional code blocking and sees only the simple for loop conducting a summation. Critical blocks make it possible to parallelize code afflicted with dependencies. This mechanism can also be applied to independent blocks, local code, and mixed constructs.

  Case            Execution times      % CPU    Speedup  Sum
                  user  sys  total  utilization
  -------------------------------------------------------------------------

  1. Example 1
     (serial)     73.8  3.4     77      100       1.00   6039797.7653373638
  2. Example 1
     (parallel)  147.9  5.0     46      326       1.67   6039797.7643598625
  3. Example 2
     (serial)     74.0  3.2     77       99       1.00   6039797.7653373638
  4. Example 2
     (parallel)   77.7  3.4     27      295       2.85   6039797.7641029358

                                     Employed Threads
                                  4     3      2       1
  --------------------------------------------------------

                   Consumer 1  3,333  3,863  5,913  10,000
  Distribution*    Consumer 2  3,333  3,863  4,087
                   Consumer 3  3,334  2,274
  List depth*                  6,001  6,826  8,178  10,000
  Time                (s)         26     31     47      94
  CPU utilization     (%)        362    294    198      99
  Speedup             (x)       3.62   3.03   2.00    1.00

   *Units are "products."

Independent block ordering is critical for successful portability. The producer (the first independent block) completely fills the queue, then quits. The first consumer (the second independent block) then consumes all the products in the queue, then quits. The remaining two consumers are left only with their stop tokens.

Bauer, B.E. Practical Parallel Programming. San Diego, CA: Academic Press, 1992.