Paralleli Zation

EditHint: this page title is UgLy. Maybe move?

From SynchronizationStrategies:

One way to look at parallelization is to consider the serial program to already be a parallel program, but one that acquires a single global lock at the start of execution, then releases it just before terminating.

From this perspective (sometimes called ``Giant Locks''), the idea is to move toward finer-grained locking until you reach the point where where the SpeedUp and ConTention forces balance the OverHead, Economics, and DevMaintCost forces. Each finer ``grain'', or CriticalSection, are usually identified by looking at the data structures used by the program, since the data is what must be protected from concurrent access. One approach is to provide a lock for the code accessing the data (CodeLocking), and another is to provide locks for the data items themselves (ParTition).

Other approaches (e.g., AtomicInstructions?, WaitFreeSynchronization, DataOwnership, ReadWriteLock) are also possible. These approaches are subject to other forces from the application (such as ReadToWriteRatio).

Parallelization efforts will often be subject to LaTency?, BandWidth?, and CacheArchitecture? forces (or maybe they are contexts, I am never sure, is there a ForceContextDuality?) from the underlying machine. In addition, parallelization efforts can easily lead to well-hidden DeadLock.

CurtSchimmel presents an excellent and thorough coverage of CacheArchitecture? forces in his book on parallelizing Unix kernels.

The GuideToParallelProgramming?, available from Sequent gives a good overview of software aspects of parallelization.

One need in patterns for parallelism, as (IMHO) patterns everywhere is a good way to index into them -- to find the pattern you need based on the context of the problem that you are trying to solve or the attributes of the job you are trying to get done. One possible index displays the hierarchy of concurrency primitives for a given computer system and application. The hierarchies that I have looked at tend to have few branch-points and therefore resemble saguaro cacti, hence, CactiOfConcurrency.

Book: PatternsForParallelProgramming

CategoryConcurrency CategoryConcurrencyPatterns