Lecture 5 PRAM Algorithms

Parallel Computing
Spring 2021

1
 Four Subclasses of PRAM
 Depending on how concurrent access to a single memory cell (of the shared
memory) is resolved, there are various PRAM variants.
 ER (Exclusive Read) or EW (Exclusive Write) PRAMs do not allow concurrent access of the
shared memory.
 It is allowed, however, for CR (Concurrent Read) or CW (Concurrent Write) PRAMs.
 Combining the rules for read and write access there are four PRAM variants:
 EREW:
 access to a memory location is exclusive. No concurrent read or write operations are allowed.
 Weakest PRAM model
 CREW
 Multiple read accesses to a memory location are allowed. Multiple write accesses to a memory
location are serialized.
 ERCW
 Multiple write accesses to a memory location are allowed. Multiple read accesses to a memory
location are serialized.
 Can simulate an EREW PRAM
 CRCW
 Allows multiple read and write accesses to a common memory location.
 Most powerful PRAM model
 Can simulate both EREW PRAM and CREW PRAM

2
Resolve concurrent write access
 (1) in the arbitrary PRAM, if multiple processors write into a single
shared memory cell, then an arbitrary processor succeeds in writing
into this cell.
 (2) in the common PRAM, processors must write the same value into
the shared memory cell.
 (3) in the priority PRAM the processor with the highest priority
(smallest or largest indexed processor) succeeds in writing.
 (4) in the combining PRAM if more than one processors write into the
same memory cell, the result written into it depends on the combining
operator. If it is the sum operator, the sum of the values is written, if it
is the maximum operator the maximum is written.

Note: An algorithm designed for the common PRAM can be executed on a

priority or arbitrary PRAM and exhibit similar complexity. The same
holds for an arbitrary PRAM algorithm when run on a priority PRAM.

3
PRAM Parallel Algorithm Assumptions
 Convention: In this subject we name processors arbitrarily
either 0, 1, . . . , p − 1 or 1, 2, . . . , p.
 The input to a particular problem would reside in the cells of the
shared memory. We assume, in order to simplify the exposition
of our algorithms, that a cell is wide enough (in bits or bytes) to
accommodate a single instance of the input (eg. a key or a
floating point number). If the input is of size n, the first n cells
numbered 0, . . . , n − 1 store the input.
 We assume that the number of processors of the PRAM is n or a
polynomial function of the size n of the input. Processor indices
are 0, 1, . . . , n − 1.

4
 Parallel Sum: EREW PRAM solution 1
(Compute x0 + x1 + . . . + xn−1)
Algorithm Parallel Sum.
M[0] M[1] M[2] M[3] M[4] M[5] M[6] M[7]
x0 x1 x2 x3 x4 x5 x6 x7 t=0
x0+x1 x2+x3 x4+x5 x6+x7 t=1
x0+...+x3 x4+...+x7 t=2
x0+...+x7 t=3

 This EREW PRAM algorithm consists of lg n steps. In step i, if j can be exactly divisible by
2i, processor j reads shared-memory cells j and j + 2i-1 combines (sums) these values and
stores the result into memory cell j. After lgn steps the sum resides in cell 0. Algorithm
Parallel Sum has T = O(lg n), P = n and W = O(n lg n), W2 = O(n).
Processing node used:
P0, p2, p4, p6 t=1
P0, p4 t=2
P0 t=3

5
Parallel Sum: EREW PRAM solution 1
(Compute x0 + x1 + . . . + xn−1)
// pid() returns the id of the processor issuing the call.
begin Parallel Sum (n)
1. i = 1 ; j = pid();
2. while (j mod 2i == 0)
3. a = C[j];
4. b = C[j + 2i-1];
5. C[j] = a + b;
6. i = i + 1;
7. end
end Parallel Sum

6
Parallel Sum: PRAM solution
(Compute x0 + x1 + . . . + xn−1)
 A sequential algorithm that solves this problem requires n − 1
additions.
 For a PRAM implementation, value xi is initially stored in shared
memory cell i. The sum x0 + x1 + . . . + xn−1 is to be computed in T =
lgn parallel steps. Without loss of generality, let n be a power of two.
 If a combining CRCW PRAM with arbitration rule sum is used to solve
this problem, the resulting algorithm is quite simple. In the first step
processor i reads memory cell i storing xi. In the following step
processor i writes the read value into an agreed cell say 0. The time is
T = O(1), and processor utilization is P = O(n).
 A more interesting algorithm is the one presented below for the EREW
PRAM. The algorithm consists of lg n steps. In step i, processor j < n /
2i reads shared-memory cells 2j and 2j +1 combines (sums) these
values and stores the result into memory cell j. After lgn steps the sum
resides in cell 0. Algorithm Parallel Sum has T = O(lg n), P = n and W
= O(n lg n), W2 = O(n).

7
Parallel Sum: EREW PRAM solution 2
An example

Algorithm Parallel Sum.

M[0] M[1] M[2] M[3] M[4] M[5] M[6] M[7]
x0 x1 x2 x3 x4 x5 x6 x7 t=0
x0+x1 x2+x3 x4+x5 x6+x7 t=1
x0+...+x3 x4+...+x7 t=2
x0+...+x7 t=3

8
Parallel Sum: EREW PRAM solution 2
(Compute x0 + x1 + . . . + xn−1)

// pid() returns the id of the processor issuing the call.

begin Parallel Sum (n)
1. i = 1 ; j = pid();
2. while (j < n / 2i)
3. a = C[2j];
4. b = C[2j + 1];
5. C[j] = a + b;
6. i = i + 1;
7. end
end Parallel Sum

9
Parallel Sum: MPI solution
Algorithm Parallel Sum.
Step 1:
P0 P1 P2 P3 P4 P5 P6 P7
x0 <= x1 x2 <= x3 x4 <= x5 x6 <= x7
x0+x1 x1 x2+x3 x3 x4+x5 x5 x6+x7 x7

Step 2:
P0 P2 P4 P6
x0+x1 <= x2+x3 x4+x5 <= x6+x7

x0+...+x3 x2+x3 x4+...+x7 x6+x7

Step 3:
P0 P4
x0+...+x3 <= x4+...+x7

x0+...+x7
10
Parallel Sum: MPI solution

11
 Parallel Sum
 Algorithm Parallel Sum can be easily extended to include the case
where n is not a power of two. Parallel Sum is the first instance of a
sequential problem that has a trivial sequential but more complex
parallel solution. Instead of operator Sum other operators like Multiply,
Maximum, Minimum, or in general, any associative operator could have
been used. As associative operator ⊗ is one such that (a ⊗ b) ⊗ c = a
⊗ (b ⊗ c).
 Exercise 1 Can you improve Parallel Sum so that T remains the same, P =
O(n/ lg n), and W = O(n)? Explain.
 Exercise 2 What if i have p processors where p < n ? (You may assume
that n is a multiple of p).
 Exercise 3 Generalize the Parallel Sum algorithm to any associative
operator.

12
End

Thank you!

13