Parallel Algorithms

Parallel Algorithms notes from CMSC751 with Uzi Vishkin. See File:CMSC751 Classnotes.pdf

XMT Language

XMTC is a single-program multiple-data (SPMD) extension of C.

• Spawn creates threads
• Threads expire at Join

Models

PRAM

Parallel Random-Access Machine/Model
You're given n synchronous processors each with local memory and access to a shared memory.
Each processor can write to shared memory, read to shared memory, or do computation in local memory.
You tell each processor what to do at each time step.

Types of PRAM

• exclusive-read exclusive-write (EREW)
• concurrent-read exclusive-write (CREW)
• concurrent-read concurrent-write (CRCW)
  • Arbitrary CRCW - an arbitrary processor writing succeeds
  • Priority CRCW - the lowest numbered processor writing succeeds
  • Common CRCW - writing succeeds only if all processors write the same value

Drawbacks

• Does not reveal how the algorithm will run on PRAMs with different number of proc
• Fully specifying allocation requires an unnecessary level of detail

Work Depth

You provide a sequence of instructions. At each time step, you specify the number of parallel operations.

WD-presentation Sufficiency Theorem

Given an algorithm in WD mode that takes x=x(n) operations and d=d(n) time, the algorithm can be implemented in any p-processor PRAM with O(x/p + d) time