Parallel computation

In parallel computation, multiple code (programming) instructions are executed at the same time. This parallelism can range from coarse to fine grained. An example of coarse parallelism is a ray tracer rendering a separate output pixel on each available CPU. An example of fine grained parallelism is found in multiplying an n-dimensional vector by a scalar. The vector is cut up and a chunk is distributed to each CPU, the multiplication is done on each chunk, and the result is reassembled.

These examples illustrate key limitations to parallel computing. First, there is the overhead of distributing and reassembling the computation. Second, there is the challenge of developing parallel algorithms. In the ideal case, such as in a ray tracer, elements of the problem (pixels to be rendered) do not depend on one another. That is, the computing one output pixel does not require information or affect any of the other output pixels. These uncoupled problems are referred to as Embarrassingly Parallel. Many problems do not fit in to this category, an example being the classic N-body.

Parallel algorithms and programs are significantly more difficult to write and debug. However, as multicore processors (many armed with SIMD commands) become increasingly common, parallel computation is finding its way in to more mass-consumer code . (e.g. mp3 encoders using SIMD, photoshop multiprocessor support, etc).

Note that it is generally possible to run parallel code on a single processor. Multiple processors are simulated through context switching. When running on a single processor, parallel algorithms typically have worse performance than their serial analogues, mainly because of the overhead of the distribution/communication logic.

Algorithms

A challenge in writing parallel software is decomposing the problem domain so that multiple portions can be solved simultaneously. In some cases, this is very easy. With ray tracing, the radiance computation for each output pixel is completely independent from the other output pixels. Thus a separate computation stream can be used to generate each pixels output. Because the streams do not need to communicate with each other, the only overhead is in collating the results. This scenario is often referred to as embarrassingly parallel.

Many problems do not decompose quite so easily. Computing the nth digit of Pi using a traditional series expansion requires computing all the preceeding digits. Thus it is not possible the parallelize the computation of digits n,n+1,n+2,etc because each output depends on the one before. However, using the BBP digit-extraction algorithm allows digits of Pi to be computed independently, so now the problem has become parallelizable.

Another issue is managing the communication overhead between parallel processes. Having two processors does not make a computer twice as fast as having one. Only in the ideal case can double-performance be achieved. In reality, there are diminishing returns as more processors are added.

Hardware

For critical sections of code to properly handle shared resources, some method for mutual exclusion must be in place. On single processor (and single core) machines, it may be possible to turn off interrupts on the CPU. This prevents the operating system's scheduler from swapping out the current process. Since the process can't be swapped out, it has exclusive access to all the system variables.

In situations where simple interrupt disabling is not possible, the CPU must typically offer some atomic operations to allow for parallel code to be written. A traditional example is the "test and set" operation, which can be used to build up semaphores. Note that there are methods which do not use the CPU for mutual exclusion. One of the first examples of such a code was Dekker's Algorithm , which takes advantage of memory interlock to achieve mutual exclusion.

Additional skeletal content:

• Compare and Swap (for Lockfree programming)
• SIMD, MIMD instructions
  • SIMD: Intel SSE3 instructions. Operate on 128-bit register which can hold 4-floats/2-doubles/etc.

Software

Low Level Primitives

• Semaphores
  • Introduced by Dijkstra.
  • Normally represented by an integer initialized to either 0 or 1
  • P operation - decreases value of semaphore by one; if result is nonnegative, process may continue; if result is negative, process stopped and added to process waiting list for semaphore
  • V operation - increases value of semaphore by one; if result is positive, no further effect; if result is nonpositive, one of the processes on semaphore waiting list is removed from list (and this removed process may proceed with its execution).
  • Supported in POSIX standard
• Monitors
• Special purpose languages for parallel computation
  • Occam
• Pure functional languages

Compiler Support

• Auto vectorizing compilers
  1. Compiler attempts to analyze loops to see which ones can be done in parallel
  2. Exists in Intel and GCCv4 compilers
• Speciality languages for Parallel programming

Library Support

• OpenMP
  1. Open standard
  2. Can be used to implement fine grained parallelism
  3. Built in support in many commercial compilers (Intel C/C++/FORTRAN, GCCv4, Sun CC)
  4. Uses meta-code to annotate which parts of a C or FORTRAN program can be parallelized.
  5. In C this is accomplished through the use of preprocessor pragmas
  6. Pragmas indicate things like "execute loop in parallel" or this variable has no dependency between iterations.

• Message Passing Interface (MPI)
  1. Well suited to cluster computing.
  2. Major library is LAM/MPI. Some vendors (e.g. Sun) also roll their own, optimized versions.

Research

A major recent development has been the advancement of Lock-Free programing. This allows for the development of thread-safe code with out the use of locking mechanisms such as semaphores . While implementing correct lock-free algorithms is considered extremely difficult, they show significant performance advantage over their traditional counterparts. For example, the lock-free dynamic memory allocator implemented in shows up to a 331% speedup over a traditional lock-based allocator when operating on 16 processors under maximum contention. This lock-free allocator also offers better scalability and latency than traditional allocators.

Related Topics

• Distributed computation