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 ...

184 PARALLEL ALGORITHMS If we consider that the general model for the algorithms presented in Chap- ters 2 through 6 is a machin ...

7.3 SIMPLE PARALLEL OPERATIONS 185 a priority model, each processor has an assigned priority and the highest prior- ity processo ...

186 PARALLEL ALGORITHMS is one set of operations that are to be done in parallel and on their completion another set is to be pe ...

7.3 SIMPLE PARALLEL OPERATIONS 187 This algorithm will first write the data value to location M 1. On the first pass of the oute ...

188 PARALLEL ALGORITHMS single processor. If we have p < N / 2, we can perform a “preprocessing” step that reduces the number ...

7.4 PARALLEL SEARCHING 189 In this version, we have a preprocessing step that has each processor do a sequential algorithm on a ...

190 PARALLEL ALGORITHMS If we have the same number of processors as elements in the list (p = N), we can have each processor com ...

7.5 PARALLEL SORTING 191 had a cost of O(N) and a run time of O(1). At points in between, we will have p lists that each have N ...

192 PARALLEL ALGORITHMS each of the processors will keep the smaller value and then pass on the larger of the values to the next ...

7.5 PARALLEL SORTING 193 The outer for loop has the two parallel blocks nested inside it because at each pass of this loop, a ne ...

194 PARALLEL ALGORITHMS You can see in Fig. 7.4 that this process takes 16 parallel steps to sort these numbers and 1 step to wr ...

7.5 PARALLEL SORTING 195 ■ 7.5.2 Odd-Even Swap Sort In previous sections, we were able to reduce costs by reducing the number of ...

196 PARALLEL ALGORITHMS if they are out of order then swap them end if end for k Parallel End Parallel Start for k = 1 to N/2-1 ...

7.5 PARALLEL SORTING 197 There are parallel merge techniques that are beyond the level of this text that can merge two lists wit ...

198 PARALLEL ALGORITHMS Write a formal parallel algorithm that will divide a list into N / lg N pieces that are sorted using Qu ...

7.6 PARALLEL NUMERICAL ALGORITHMS 199 P 11 P 12 P 13 P 14 41 7 23 5 3 1 9 5 4 6 8 7 2 4 3 1 P 21 P 22 P 23 P 24 ■FIGURE 7.6A The ...

200 PARALLEL ALGORITHMS P 11 P 12 P 13 P 14 41 2 3 5 3548 763 30 1 9 6 4 8 7 2 4 3 1 P 21 P 22 P 23 P 24 ■FIGURE 7.6C P 11 multi ...

7.6 PARALLEL NUMERICAL ALGORITHMS 201 P 11 P 12 P 13 P 14 54 2 41776 46 14 52 34 2 9 16 5 35531 71 8 4 3 P 21 P 22 P 23 P 24 ■FI ...

202 PARALLEL ALGORITHMS P 11 P 12 P 13 P 14 54 76 66 4 53 1107 52 83 142 96 35 71 47 23522 4 P 21 P 22 P 23 P 24 ■FIGURE 7.6G P ...