Talk:Parallel computation

Proposed Outline

I just did a quick brain-dump for the initial cut at this page. I think a reasonable initial sectioning is as follows:

• Introduction
  1. Concept of parallel vs. serial computation.
  2. Concept of coarse vs. fine/instruction level parallelism.
  3. Mention parallel, cluster, distributed computing.
  4. Growing importance of parallel computation in light of increasing cores in consumer cpus.
  5. Increased difficulty of coding and debugging parallel programs.

• Problem Domain
  1. Give a few classic examples (ray tracing and n-body problem).
  2. Introduce concept of embarrassingly parallel

• Algorithms
  1. Give some classic examples
  2. Communication overhead
  3. Lower performance than serial algorithms when run on single CPU

• Hardware
  1. The need for atomic operations in hardware for parallel code to work.
     • CPU Level Test and Set (TAS)
     • CPU Level Test and Swap (Lockfree programming)
     • Alternative method using memory interlock (classic CS paper)

• Software
  1. Low level primitives
     • Semaphores
     • Mutexes
  2. Language support
     • Specialty languages
     • Pure functional languages (no side effects = auto parallelization)
  3. Library support
     • OpenMP
     • OpenMPI
     • Parallel LAPACK.

• Research
  1. • Bunch of major research topics
     • DNA computing

• Related topics
  1. • Bunch of related topic links, possibly organized by some coherent categories.

• Citations
  1. Survey and overview papers/pages

Niek Sanders 19:07, 26 March 2007 (CDT)

Dekker's Algorithm

T.J. Dekker made a historically significant mutual exclusion algorithm. He showed that is possible to use memory interlock alone to enforce a critical section. (Note that this no longer works on modern processors).

Tracking down a citation for this algorithm has been a pain in the ass. He apparently wrote it in 1959 but both these two webpages indicate it was published in a book by Dijkstra:

• http://www.cs.uiowa.edu/~jones/syssoft/notes/17conc.html
• http://portal.acm.org/citation.cfm?doid=945526.945527 (citation 9)

I'm going to steal the ACM citation for now, but it needs verification.