Question

Give an O(lg n)-time EREW algorithm to perform the prefix computation on an array x[1. . n]. Do not use pointers, but perform index computations directly.

Answer 1

EREW:

It is Exclusive Read Exclusive Write (EREW) algorithm in which every memory cell can be read or written to by only one processor at a time.

A parallel random-access machine (PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM was intended as the parallel-computing analogy to the random-access machine .

PRAM Models:

1. Exclusive read exclusive write (EREW)—every memory cell can be read or written to by only one processor at a time
2. Concurrent read exclusive write (CREW)—multiple processors can read a memory cell but only one can write at a time
3. Exclusive read concurrent write (ERCW)—never considered
4. Concurrent read concurrent write (CRCW)—multiple processors can read and write. A CRCW PRAM is sometimes called a concurrent random-access machine.

EREW is a PRAM model.

We can perform prefix sum by using EREW algorithm in O(logn) complexity.

SIMPLIFIED ALGORITHM:

Definition (Prefix Problem)

Input: an array A of n elements a_i .

Output: All terms a₁ × a₂ × · · · × a_k for k = 1, . . . , n.

× may be any associative operation.

Straightforward serial implementation:

P r e f i x ( A: Array [ 1 . . n ] ) {

/ / in−pla ce computation :

for i from 2 to n do {

A[ i ] := A[ i −1]∗A[ i ] ;

}

This takes O(logn) time to perform prefix computation by using EREW algorithm.