Dynamic Programming

C HAPTER 12 Dynamic Programming 1 The parallel run time of the algorithm is given by TP = n(tc c p c + 2ts + tw p ) The corresponding speedup is given by S = = T1 nctc = n(tc pc + 2ts + tw c p ) TP 1 1 p + 2ts ctc + tw ptc The efficiency of the parallel formulation is given by E= 1 1+ 2 pts ctc + tw tc Now, as we increase the problem size (by increasing c), all terms in the denominator reduce except 1 + tw /tc . Therefore, 1 + tw /tc is the lower bound on the value of the denominator. Therefore, the efficiency is bounded from above by 1 E= 1 + twtc 2 The solution is discussed by Lee and Sahni in [LSS88]. 3 NOTE The hint in the problem should point to block-cyclic striped mapping and not cyclic striped mapping. In the cyclic striped mapping shown in Figure 12.1, in the computation of the first diagonal, one processor is busy; in the computation of the second diagonal, two processors are busy; and so on. This continues until diagonal p. The computation of each of these diagonals takes time tc + ts + tw . This is because a single word needs to be communicated from the processor on its left and a single entry needs to be computed. Therefore the total time for computing these p diagonals is p(tc + ts + tw ). The computation of each of the next p diagonals takes time 2(tc + ts + tw ) since some of the processors may be computing two entries in the table. The total time taken for these p diagonals is therefore 2 p(tc + ts + tw ). Similarly, the computation of the next p diagonals takes time 3(tc + ts + tw ) and the total time is 3 p(tc + ts + tw ). The time for the p diagonals leading up to the longest diagonal is given by n/ p(tc + ts + tw ). The total parallel run time of the algorithm is 0 1 2 3 0 3 Figure 12.1 Cyclic partitioning of the LSC problem for p = 4. twice the time taken to compute the first n diagonals. This is given by n/ p TP = 2 p(tc + ts + tw )  i i =1 n n ( = p(tc + ts + tw ) p p + 1) n = (tc + ts + tw )n( + 1) p n2 = (tc + ts + tw ) + (tc + ts + tw )n p The corresponding speedup and efficiency are given by S = E = n 2 tc (tc + ts + tw ) n2 t s +t w tc p 1 1+ + p + (tc + ts + tw )n n (tc + ts + tw ) We can see that on increasing the problem size (by increasing n), the efficiency increases. However, it is bounded from above by 1 E= 1 + ts +ttcw This upper bound can be removed by using block-cyclic striped mapping. In this case, processors are assigned √ √ √ p columns in a cyclic manner. Therefore, the first p columns are assigned to processor P0 , the next p 0 √ √ 1 p p √ √ Figure 12.2 Block cyclic partitioning of the LSC problem. The nodes are organized into blocks of size p × p and assigned to the processors in a cyclic fashion. columns to processor P1 and so on. The assignment wraps back to processor P0 after all processors have been √ √ √ assigned p columns. Computation is performed in blocks of size p × p as shown in Figure 12.2. The computation of the block at the top left corner is performed first. After this block has been processed, two blocks can be processed. One by processor P0 and the other by processor P1 . Using this mapping scheme, √ √ the computation of the first block is done by processor 0 in time ( p × p)tc . The next set of two blocks is √ computed by processors P0 and P1 in time (ts + tw p) + pt c . This continues until all processors become busy √ (that is, until diagonal p 1.5 ). For the next p1.5 diagonals, computing each block takes time 2((ts +tw p)+ pt c ). This continues and the longest diagonal. The total parallel run-time of the algorithm is twice the time for the computation of the first n diagonals. This is given by n/( p 1.5 ) TP = √ 2((ts + tw p) + ptc ) p i =1 = = i  n √ n ((ts + tw p) + ptc ) p p 1.5 ( 1.5 + 1) p n2 n2 n2 n √ ) + t ( + n) + tc ( ts ( √ + w + n p) p p2 p 1.5 p The corresponding speedup and efficiency are given by S E = = n 2 tc ts ( √np + 2 n2 ) + tw ( np1.5 p2 + n) + tc ( n 2 1 1+ p 1.5 n + tw ( √1 tc p + p n + √ ts p tc ( n + p √ + n p) 1) p From this expression, we can see that the efficiency does not have an upper bound. 4 The TSP can be solved by constructing a table which stores values of f (S, k) for increasingly larger sets S . Starting at city v1 , we can construct n − 1 sets of two cities with the second city being the terminating city. Each of these n − 1 sets now leads to n − 2 sets of 3 cities, with the added city being the terminating city. In general, at the k th level, there are (n − 1)n−2 C k nodes (since the initial and terminating cities are fixed). The total number of entires to be computed, N , is given by: n−2 n−2 n−2 N =  (n − 1) C k = (n − 1)2 k=0 Since computing an entry in the (n − 2)nd row takes time (n − 1)tc , the serial complexity of this algorithm is (n 2 2n ). The formulation is serial monadic, but is considerably harder to parallelize than the standard multistage graph procedure. This is because the average number of nodes at a level is O(2n ), but each node is connected to a small number of nodes (O(n)) at the next level. A simple parallel formulation of this algorithm is given below. The formulation uses only O(n) processors, but it uses them efficiently. The table can be constructed in parallel by assigning the responsibility of one terminating city to each processor. Therefore, using n − 1 processors, processor i in step k computes all paths through nodes in set k terminating at node i. After each step, an all-to-all broadcast is used to communicate all the results from the current step to all the processors. Therefore, in step k, an all to all broadcast of n−2 C k elements is required. The corresponding computation for the step is given by (k n−2 C k ). All-to-all broadcast takes time ts log p + tw m( p − 1). The first term is dominated by the second and can be ignored without significant loss in accuracy. The all-to-all broadcast operation can be performed in approximately tw mp time. Since m =n−2 C k and p = n − 1, the time taken is given by tw n n−2 C k . The total parallel time is therefore given by n−2 n−2 n−2 n−2 T P =  k C k tc +  tw n C k k=0 k=0 and the speedup is given by k=0 n−2 (n − 1)k n−2 C k t n n−2 C k S = n−2 n−2k=0 w k n−2processors C k tc + This corresponds to TP = (n2n ). Sincek=0(n) are used, the formulation is cost optimal. The same formulation gives identical performance on the mesh connected computer because the dominant term in all-to-all broadcast is the same for the mesh. 5 Let c(k) be the number of records in file k and f (S) be the cost of merging the set of files S. Furthermore, let u v represent the file of length c(u ) + c(v) resulting from the merger of files u and v. The recursive equation for solving the optimal merge problem is given by  min 0 { f (S − {u} − {v} + {u v}) + c(u ) + c(v)} S = {} or |S| = 1 u,v∈S f (S) = However, a better greedy formulation of the algorithm is represented by the following recursive equation  0f (S − {u} − {v} + {uv}) + min c(u) + v∈S−{u} min c(v) S = {} or |S| = 1 u∈S f (S) = The serial algorithm requires the two smallest files to be determined at each step. This is based on the heap data structure or on explicit determination of the smallest files. Parallel formulations of the algorithm can be derived based on the technique used to determine the smallest files. 7 Given a polygon v0 , v1 , . . . , v n−1 , the optimal triangulation problem can be solved using the following DP formulation: define C[i, j] as the weight of an optimal triangulation of vertices vi −1 , . . . , v j . The objective is to determine C[1, n − 1]. The following recursive equation can be used to determine C[i, j]: {C [i, k] + C [k + 1, j] + f (vi −1 , v k , v j )} i < j (12.1) min 0 i= j C[i, j] = Here, f (vi −1 , v k , v j ) is a weight function corresponding to the triangle formed by vertices vi −1 , vk , and v j . Using the perimeter of the triangle as the weight function,  i ≤k≤ j f (vi −1 , v , v ) = |v v | + |v v | + |v v | k j i −1 k k j j i −1 Comparing this with the recursive DP formulation for the matrix parenthesization problem, we can see that the two are identical. It is a nonserial polyadic DP formulation and parallel formulations identical to the optimal matrix parenthesization problem can be used here. Cormen [CLR90] provides details of the DP formulation to solve this problem. C HAPTER 13 Fast Fourier Transform 1 (a) (b) This problem assumes a hypothetical parallel computer with a hypercube interconnection network, in which there is no message startup time and a message contains only one word. The parallel run time of the binary exchange algorithm is TP = S = E = tw log p tc log n 1+ 1 p 1 + 1.2 log log n For maintaining a fixed efficiency E , log p log n = log n = n = n log n = 1.2 For E = 0.6, (c) tc n log n tw n log p + p p p 1 −1 E 1.2E log p 1−E p 1.2E/(1−E) 1.2E p 1.2E/(1−E) log p 1−E n log n = 1.8 p1.8 log p For E = 0.4, n log n = 0.8 p0.8 log p Since the lower bound on the isoefficiency function due to concurrency is p log p, the actual isoefficiency (d) function for E = 0.4 is p log p . E = 1 p 1 + 2 log log n For maintaining a fixed efficiency E , n log n = 2E 1− E p 2E/(1−E) log p Table 13.1 The binary representation of the various powers of ω calculated in different iterations of an 16-point FFT (also see Figure 13.1 (page 539)). The value of m refers to the iteration number of the outer loop, and i is the index of the inner loop of Program 13.2 (page 540). m m m m =0 =1 =2 =3 0 1 2 3 4 5 6 7 i 8 9 10 11 12 13 14 15 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 1000 0100 0000 0000 1000 1100 0000 1000 0100 0010 0000 1000 0100 1010 0000 1000 1100 0110 0000 1000 1100 1110 1000 0100 0010 0001 1000 0100 0010 1001 1000 0100 1010 0101 1000 0100 1010 1101 1000 1100 0110 0011 1000 1100 0110 1011 1000 1100 1110 0111 1000 1100 1110 1111 For E = 0.6, n log n = 3 p3 log p For E = 0.4, 4 4/3 p log p 3 n log n = 2 Refer to the paper by Thompson [Tho83]. 3 On a linear array of p processors, the distance between the communicating processors in the i th iteration (of the log p iterations that require interprocessor communication) is 2i (0 ≤ i < log p ). TP = ≈ tc n log n p tc n log n p log p−1 +  i =0 n i (ts + tw p 2 ) + ts log p + tw n The isoefficiency function due to the tw term is ( p2tw E p/(tc (1−E)) ). 4 If ts = 0, the expression for efficiency is as follows: 1 E = 1+ √ 2tw p tc log n In order to maintain a fixed efficiency E , tc n log n = 2 E 1− E √ tw p Let E/(1 − E) = K . √ tc n log n = 2K t w p √ n = 22K t w p/tc tw √ √ 2K t w p/tc n log n = W = 2K tc p2 5 The first equation of the recurrence follows from the fact that there are only n unique twiddle factors that a single processor needs to compute. When n = p, all but the first p/4 processors compute a different twiddle factor in each of the log n = log p iterations. This verifies the second equation of the recurrence. Table 13.1 shows the binary representation of the powers of ω required for all values of i (inner loop index) and m (outer loop index) for a 16-point FFT. Table 13.2 shows the values of h(16, p) for p = 1, 2, 4, 8, and 16. The table also shows the maximum number of new twiddle factors that any single processor computes in each iteration. Disregarding the case in which p = 1, notice from Tables 13.2 and 13.2 (page 552) that when the number of processors is reduced by a factor of two, an entry (m, 2 p) in the tables occupies the position (m − 1, p). The Table 13.2 The maximum number of new powers of ω used by any processor in each iteration of an 8-point FFT computation. p = 1 p = 2 p = 4 p = 8 p = 16 m =0 m =1 m =2 m =3 Total = h(16, p) 2 2 4 8 16 1 2 4 8 15 1 1 2 4 8 1 1 1 2 5 1 1 1 1 4 value of the entry (log n − 1, p) is n/ p ; that is, except for p = 1, all entries in the last row of the tables are n/ p . Thus, if the number of processors is changed from 2 p to p , all but the first entry of column 2 p are present in column p, but these entries are offset by one row. An entry n/ p is added to the last row of column p and the original entry (0, 2 p) = 1 does not move from column 2 p to column p. Hence, h (n, p) = h (n, 2 p)+n/ p − 1, which is the last equation of the recurrence. h (n, p) = h (n, 2 p) + = h(n, 4 p) + .. . .. . = h(n , n ) + n −1 p n n + 2p p − 2 n n n n − log( ) + + ···+ p n/2 n/4 p n = log n + 2 + 4 + · · · + − log n + log p p n = 2 − 2 + log p p 8 Since the computation time is the same in each case, we give the communication times in the following tables. A “—” indicates that the algorithm is not applicable for the given values of n and p. The least run time in each case is boldfaced, and hence, indicates the algorithm of choice. • n = 215, p = 212 : Communication constants ts = 250, tw = 1 ts = 50, tw = 1 ts = 10, tw = 1 ts = 2, tw = 1 ts = 0, tw = 1 2-D trans. — — — — — 3-D trans. 3.15E4 6316 1276 268 16 Runtimes 4-D trans. — — — — — 5-D trans. 8032 1632 352 96 32 Bin. ex. 3096 696 216 120 96 • n = 212, p = 26 : Communication constants 2-D trans. ts = 250, tw = 1 ts = 50, tw = 1 ts = 10, tw = 1 ts = 2, tw = 1 ts = 0, tw = 1 1.58E4 3214 694 190 64 3-D trans. 3628 828 268 156 128 Runtimes 4-D trans. 2442 642 282 210 192 5-D trans. — — — — — Bin. ex. 1884 684 444 396 384 • n = 220, p = 212 : Communication constants 2-D trans. ts = 250, tw = 1 ts = 50, tw = 1 ts = 10, tw = 1 ts = 2, tw = 1 ts = 0, tw = 1 1.04E6 2.05E5 4.12E4 8446 256 3-D trans. — — — — — Runtimes 4-D trans. 1.28E4 3168 1248 864 768 5-D trans. 9024 2624 1344 1088 1024 Bin. ex. 6072 3672 3192 3096 3072 9 With a constant tw , the parallel run time of the binary exchange algorithm on a two-dimensional mesh is √ approximately tc n log n/ p + ts log p + 2tw n/ p . If the per-word time is tw / p x for a p -processor mesh, then the parallel run time is tc n log n/ p + ts log p + 2tw n/ p 0.5+x . The isoefficiency function due to ts is ( p log p). To compute the isoefficiency function due to tw , tc n log n p ∝ log n ∝ 2tw n p 0.5+x tw 2 p 0.5−x tc 0.5−x /tc n ∝ 22tw p tw n log n = W ∝ 2 p 0.5−x 22tw p0.5−x /tc tc If the channel width is p x , then in each communication step, at least p x words must be transferred between any two communicating processors to utilize all links of a channel. Hence, n p n n log n = W ≥ px ≥ p 1+x ≥ (1 + x) p1+x log p 0.5−x ) and that due to Thus, the isoefficiency function due to communication overhead is ( p 0.5−x 22(tw /tc ) p concurrency is ( p 1+x log p). For x > 0.5, the isoefficiency function due to concurrency is greater than ( p 1.5 log p) and that due to communication is less than ( p 1.5 log p) if all channels are fully utilized. For x < 0.5, the isoefficiency function due to communication exceeds ( p 1.5 log p). The best isoefficiency function is therefore ( p1.5 log p) for x = 0.5. A higher rate of increase of channel width with respect to the number of processors does not improve the overall scalability because the size of data stored at each processor cannot be increased beyond (n/ p) without causing the scalability due to concurrency to deteriorate.