Parallel Processing Distributed Systems.ppt

Parallel Processing Distributed Systems Chapter 2: Parallel Computer Models Classification Model of Parallel Computation: PRAM, BSP, Phase Parallel Pipeline, Processor Array, Multiprocessor, Data Flow Computer Flynn Classification: SISD, SIMD, MISD, MIMD Speedup: Amdahl, Gustafson Pipeline Computer Models of Parallel Computation PRAM BSP Phase Parallel RAM RAM (random access machine) Worst-case time complexity Expected time complexity Worst-case space complexity Expected space complexity Uniform cost criterion RAM instruction requires 1 time unit Every registrer requires 1 unit of space PRAM (1) PRAM PRAM (2) A control unit An unbounded set of processors, each with its own private memory and an unique index Input stored in global memory or a single active processing element Step: (1) read a value from a single private/global memory location (2) perform a RAM operation (3) write into a single private/global memory location During a computation step: a processor may activate another processor All active, enable processors must execute the same instruction (albeit on different memory location) Computation terminates when the last processor halts PRAM(3) Definition: The cost of a PRAM computation is the product of the parallel time complexity and the number of processors used. Ex: a PRAM algorithm that has time complexity O(log p) using p processors has cost O(p log p) Conflicts Resolution Schemes (1) PRAM execution can result in simultaneous access to the same location in shared memory. Exclusive Read (ER) No two processors can simultaneously read the same memory location. Exclusive Write (EW) No two processors can simultaneously write to the same memory location. Concurrent Read (CR) Processors can simultaneously read the same memory location. Concurrent Write (CW) Processors can simultaneously write to the same memory location, using some conflict resolution scheme. Conflicts Resolution Schemes(2) Common/Identical CRCW All processors writing t