Analysis of Algorithms : An Active Learning Approach

7.3 SIMPLE PARALLEL OPERATIONS 185

a priority model, each processor has an assigned priority and the highest prior-

ity processor attempting to write into a location will succeed. In a simple ver-

sion of this, the processor’s number is its priority, and the lower the number,

the higher the priority. For example, if processor 4 and processor 7 are both

trying to write to one location, processor 4 would succeed. In an arbitrary

model, one of the processors will succeed in writing to memory, but it is not

known which will succeed. In the common model, multiple writes are allowed

but only if all processors are attempting to write the same value. In the com-

bining model, the system will perform some sort of combination on all of the

values written. So, the system may sum the values, take their product, store

only the largest or smallest of the values, or perform a logical operation (and,

or, or exclusive or) on the values. Each of these options may be useful in vari-

ous circumstances.

We then have four combinations of these read and write options: Concur-

rent Read Concurrent Write (CRCW), Concurrent Read Exclusive Write

(CREW), Exclusive Read Concurrent Write (ERCW), and Exclusive Read

Exclusive Write (EREW).

7.2.1

1. Write an algorithm to compute the sum of N numbers using the CREW
   PRAM model. How efficient is your algorithm in terms of both run time
   and cost?


2. Write an algorithm to find the largest and second largest values in a set of
   numbers using the CRCW PRAM model, being specific about your write
   conflict resolution mechanism. How efficient is your algorithm in terms of
   both run time and cost?

7.3 Simple Parallel Operations

We now investigate two simple operations: broadcasting a data value to all pro-

cessors and finding the minimum or maximum value in a list. In the algorithms

in the rest of this chapter, we will use Pi to refer to the ith processor, p to refer

to the number of processors, N to refer to the number of input data items, and

Mj to refer to the jth memory location. Operations to be done in parallel will

be nested between Parallel Start and Parallel End keywords. If there

■7.2.1 EXERCISES