Scribd
Upload
57 views8 pages

Understanding PRAM in Parallel Computing

This document describes the Parallel Random Access Machine (PRAM) model of parallel computation. The PRAM model consists of multiple processors that can access a shared memory in parallel. It is classified based on whether reads and writes to the shared memory are exclusive or concurrent. Algorithms for the PRAM are designed to solve problems in parallel using log(n) time and n/2 processors. While simple, the PRAM model provides a theoretical framework but may not reflect realistic parallel architectures.

Uploaded by

Vickey Vignesh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
57 views8 pages

Understanding PRAM in Parallel Computing

This document describes the Parallel Random Access Machine (PRAM) model of parallel computation. The PRAM model consists of multiple processors that can access a shared memory in parallel. It is classified based on whether reads and writes to the shared memory are exclusive or concurrent. Algorithms for the PRAM are designed to solve problems in parallel using log(n) time and n/2 processors. While simple, the PRAM model provides a theoretical framework but may not reflect realistic parallel architectures.

Uploaded by

Vickey Vignesh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

PRAM

(Parallel Random Access Machine)


PRAM (Parallel RAM)
Some subset of the processors can remain
idle
P0 P1 P2 PN

Shared Memory Cells

Two or more processors may read


simultaneously from the same cell
A write conflict occurs when two or more
processors try to write simultaneously into
the same cell
Share Memory Access Conflicts
PRAM are classified based on their
Read/Write abilities (realistic and useful)
◦ Exclusive Read(ER) : all processors can
simultaneously read from distinct memory
locations
◦ Exclusive Write(EW) : all processors can
simultaneously write to distinct memory locations
◦ Concurrent Read(CR) : all processors can
simultaneously read from any memory location
◦ Concurrent Write(CW) : all processors can write
to any memory location
◦ EREW, CREW, CRCW
PRAM Algorithm (Parallel
Addition)

P0 + P1 + P2 + P3 + Step 1

P0 + P2 + Step 2

P0 + Step 3
PRAM Algorithm (Parallel
Addition)
Log (n) steps = time needed
n / 2 processors needed
Speed-up = n / log(n)
Efficiency = 1 / log(n)
Applicable for other operations
◦ +, *, <, >, etc.
Example 2

CRCW
EREW CREW
(common)
Inform everyone what x is log(p) 1 1
Every processor checks [n/p]
n/p n/p n/p
numbers and sets a flag
Check if any of the flag are
log(p) log(p) 1
set to 1
Some variants of PRAM
Bounded number of shared memory cells.
Small memory PRAM (input data set
exceeds capacity of the share memory i/o
values can be distributed evenly among the
processors)
Bounded number of processor Small PRAM.
If # of threads of execution is higher,
processors may interleave several threads.
Bounded size of a machine word. Word size
of PRAM
Handling access conflicts. Constraints on
simultaneous access to share memory cells
Conclusions
We need some model to reason, compare,
analyze and design algorithms
PRAM is simple and easy to understand
Rich set of theoretical results
Over-simplistic and often not realistic
The programs written on these machines
are, in general, of type MIMD. Certain
special cases such as SIMD may also be
handled in such a framework

You might also like