Analysis of Algorithms : An Active Learning Approach

7.2 THE PRAM MODEL 183

The second issue that we must consider is the cost of the parallel algorithm,

which we will define as the time of the algorithm multiplied by the number of

processors used. In our example, if the parallel sorting algorithm of O(N)

required that the number of processors be the same as the number of data val-

ues, the cost would be O(N^2 ). This means that the parallel sorting algorithm

would be more expensive because the cost of a one-processor sequential sort-

ing algorithm is the same as its run time of O(N lg N).

A related issue is the scalability of the problem. If our only option for a par-

allel sort requires that we have the same number of processors as input values,

we will find that this algorithm is not usable for a list of any significant size.

This would be a problem, because our sequential sort algorithm has no such

size restrictions. In general, we will be interested in parallel solutions where the

number of processors is significantly less than the potential size of the input

and where the algorithm can handle an increase in the size of the input with-

out an increase in the number of processors.

7.1.4

1. A problem you are working on needs the series of numbers that are the
   summations of numbers from a set. More specifically, for the set {s 1 ,s 2 ,s 3 ,
   ... , sN} you need the sums s 1 + s 2 ,s 1 + s 2 + s 3 ,s 1 + s 2 + s 3 + s 4 ,... , s 1 +
   s 2 + s 3 + ... + sN. Design a method that you could use to solve this prob-
   lem using parallelism.


2. Another network configuration is a star network, where there is one central
   processor, and every other processor is just connected to this central one.
   Draw a picture of a star network that has seven processors. This section dis-
   cussed some advantages and disadvantages of a linear network. Using that
   discussion as the basis, what do you see as some of the advantages and disad-
   vantages of a star network?

7.2 The PRAM Model

In constructing parallel algorithms, we consider a set of four models of the actual

computer system on which our design will run. These models deal with the issue

of reading from and writing to memory, which can be a problem in parallel sys-

tems. For example, what if two of our processors want to write a value to the

same memory location at the same time—which one will succeed?

■7.1.4 EXERCISES