DS C9 Parallelism

Overview

Machine parallelism

• Processor parallelism
• Pipelining
• Very-Long Instruction Word (VLIW)

Parallel algorithms

Parallel Random Access Machine (PRAM)

A Parallel Random Access Machine (PRAM) is a theoretical model of computation that is used to design parallel algorithms.

• It is a shared-memory model
• It allows multiple processors to access the same memory location simultaneously.

We define that a read/write/computation a unit time access.

for Pi, i >= 1 && i <= n pardo //pardo means the for is O(1)
	A(i) := B(i)

Access conflicts solution

solution	Read	Write
EREW	Exclusive	Exclusive
CREW	Concurrent	Exclusive
CRCW	Concurrent	Concurrent

There may be rules for CRCW to ensure compatibility:

• Arbitrary rule: allow write access of a random write-intensive processor
• Priority rule: allow write access for the write-intensive processor with highest priority
• Common rule: allow write access if all the processors are trying to write the same value.

Exp: The summation problem

Partitioning

• partitioning - partition the input into a large number, say p, of independent small jobs, so that the size of the largest small job is roughly $\frac{n}{p}$.
• actual work - do these small jobs concurrently using a separate (possibly serial) algorithm for each.

Exp: Merge sorted arrays

Merge sorted arrays problem merges two non-decreasing arrays $A(1), A(2), …, A(n)$ and $B(1), B(2), …, B(m)$ into another non-decreasing array $C(1), C(2), …, C(n+m)$.

Assume that

• the elements of A and B are pairwise distinct
• $n = m$
• both $\log n$ and $n\log n$ are integers

Transform the problem into a Ranking problem. We’ll know the position to set $B(j)$ if we know

• the number of the elements that less than $B(j)$ in array $A$, denoted as $RANK(j,A)$
• the number of the elements that less than $B(j)$ in array $B$, which is $j - 1$

Then indexing from $1$, $C(RANK(j,A) + j - 1 + 1) = B(j)$.

Similarly, $C(RANK(i,B) + i - 1 + 1) = A(i)$.