Microsoft PowerPoint – lecture28 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 28, 4/26/18
Parallel Computation
• PRAM model(s): Parallel Random Access Machine
• A set of RAMs (the processors) with a shared memory,
computing synchronously in parallel.
• In 1 step a processor can perform an operation or access
(read/write) a location of the shared memory
• Different variants of the PRAM model depending on
whether different processors are allowed to read/write a
common location at the same time (and conflict resolution
rule if concurrent writes are allowed)
• eg. EREW (Exclusive Read, Exclusive Write)
• CREW (Concurrent Read, Exclusive Write)
• CRCW (Concurrent Read, Concurrent Write)
• Variants are all close (up to log factor) in efficiency
Resources
• (Parallel) Time t
• # Processors p. Not assumed fixed: we allow #processors
to grow with the input size, and see how fast the problem
can be solved.
• If p processors can solve the problem in time t, then with
p’