Analysis of Algorithms : An Active Learning Approach

198 PARALLEL ALGORITHMS

3. Write a formal parallel algorithm that will divide a list into N / lg N pieces
   that are sorted using Quicksort and then merged. In your algorithm, use
   the call Quicksort(M, j, k) to invoke Quicksort on the sublist in
   locationsMj through Mk. You should also use the call to ParallelMerge-
   Lists as described in question 2.

7.6 Parallel Numerical Algorithms

In this section, we will explore parallel algorithms to solve numerical prob-

lems. We will begin with two varieties of parallel matrix multiplication algo-

rithms and then we will look at the problem of finding the solution to a system

of linear equations.

■ 7.6.1 Matrix Multiplication on a Parallel Mesh

One method to achieve parallelism in matrix multiplication is to use a mesh

network related to the size of the matrices. To multiply an IJ matrix and a

JK matrix, you would use an IK mesh of processors, with a row of pro-

cessors for each row of the first matrix and a column of processors for each

column of the second matrix.

The numbers of the first matrix would be passed into the rows of the mesh

one per cycle. The first row would begin on the first cycle, the second row on

the second cycle, and so on. A similar process would be followed with the

numbers in the second matrix and the mesh columns, starting with the num-

bers in the first column. The delay in the later rows and columns is so that the

numbers that need to be multiplied by each processor arrive at the same time.

Each processor will then multiply the two numbers that arrive at it during each

cycle and add the result to its current total. At the end, each processor will hold

one value of the result. Figure 7.6(a) through (i) shows the steps to multiply

235

417

by

3584

1473

9621