Analysis of Algorithms : An Active Learning Approach

7.4 PARALLEL SEARCHING 189

In this version, we have a preprocessing step that has each processor do a

sequential algorithm on a list of lg N elements, which you will recall will take

O(lgN) operations. The next part of this algorithm is our original attempt

with the number of processors now reduced to (N / lg N) / 2 (but the prepro-

cessing step still requires N / lg N processors). So, the total cost of this algo-

rithm is

This last parallel version has the same cost as the sequential version, but it runs

in a fraction of the time.

7.3.4

1. The median of a set of numbers is the value for which half of the numbers
   in the set are larger and half of the numbers are smaller. In other words, if
   the numbers were sorted, the median value would be in the exact center of
   this sorted list. Design a parallel algorithm to determine the median of a set
   of numbers using the CREW PRAM model. How efficient is your algo-
   rithm in terms of both run time and cost?


2. Design a parallel algorithm to determine the median of a set of numbers
   using the CRCW PRAM model, being very specific about your write con-
   flict resolution mechanism. (The median is described in question 1.) How
   efficient is your algorithm in terms of both run time and cost?

7.4 Parallel Searching

In investigating a parallel method for searching, we will begin with a naive

attempt with as many processors as elements of the list we are searching. Our

analysis will indicate to us how far away from optimal this solution’s cost is. We

will then attempt to reduce the costs by reducing the processors, like we did in

the case of finding the maximum value. We will assume that the list has no

duplicate elements.

Step Cost Time

Preprocessing (N / lg N)*O(lgN) = O(N) O(lgN)

Main Loop [(N / lg N) / 2] *O(lgN) = O(N) O(lgN)

Total O(N) O(lgN)

■7.3.4 EXERCISES