程序代写代做代考 algorithm Microsoft PowerPoint – lecture28 [Compatibility Mode]

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’