Principles of Parallel Algorithm Design

C HAPTER 3 Principles of Parallel Algorithm Design 2 We assume eacg node to be of unit weight. 1. (a) 8, (b) 8, (c) 8, (d) 8. 2. (a) 4, (b) 4, (c) 7, (d) 8. 3. (a) 15/4, (b) 15/4, (c) 2, (d) 15/8. 4. (a) 8, (b) 8, (c) 3, (d) 2. 5. Number of parallel processes limited to 2: (a) 15/8, (b) 15/8, (c) 7/4, (d) 15/8. Number of parallel processes limited to 4: (a) 3, (b) 3, (c) 2, (d) 15/8. Number of parallel processes limited to 8: (a) 15/4, (b) 15/4, (c) 2, (d) 15/8. 4 Since any path from a start to a finish cannot be longer than l, there must be at least ⌈t/l⌉ independent paths from start to finish nodes to accomodate all t nodes. Hence d must be ≥ ⌈t/l⌉. If d > t − l + 1, then it is impossible to have a critical path of length l or higher because because l − 1 more nodes are needed to construct this path. Hence ⌈t/l⌉d ≤ d ≤ t − l + 1. 5 See Figure 3.1. 6 1,2,6,10,11,13,14, 1,2,6,10,12,13,14, 1,4,6,10,11,13,14, 1,4,6,10,12,13,14. 7 See Figure 3.1. Using three processes achieves the maximum possible speedup of 2. 8 See Figure 3.1. 9 They both take the same amount of time. 12 max(2m − 2,(m − 1)2 ). 13 15 2m − 1. See Chapter 13. 16 See Chapter 13. 17 See Chapter 13. 19 See Chapter 9. 21 Best-case speedup = 2, worst-case sppedup = 1.5. Mapping I 2 P0 5 7 P0 P0 Mapping II (3 processes) 1 P0 3 P2 1 P1 P1 6 P1 11 12 P0 2 P0 1 2 P0 P3 3 P2 4 P1 P1 7 P2 8 P3 9 P2 3 6 P0 P1 10 4 10 P0 8 P2 9 4 5 (4 processes) P0 11 5 P1 12 13 P0 6 P0 13 14 P0 7 P0 14 Figure 3.1 Task-dependency graphs, critical-path lengths, and mappings onto 3 and 4 processes for 3×3 block LU factorization. C HAPTER 4 Basic Communication Operations 1 Add an extra iteration to the outer loop. Some processes in the first iteration in 4.1 and 4.2 and the last iteration in 4.3 (iteration d is all cases) will not participate in the communication. 2 Note: There is a typo in the problem statememt. Algorithm 3.1 should read Algorithm 4.1. 5 Refer to Figure 4.7 (page 155). In the first iteration, the following pairs of processors exchange their data of size m: (0,4), (1,5), (2,6), and (3,7). This step takes ts + 4tw m time because four messages of size m pass through the root of the tree. At the end of this step, each processor has data of size 2m. Now the following pairs of processors exchange their data: (0,2), (1,3), (4,6), and (5,7). In this step, the size of each message is 2m, and two messages traverse in each channel in the same direction. Thus, this step takes t s + 4tw m. In the final step, messages of size 4m are exchanged without channel contention between the following pairs of processors: (0,1), (2,3), (4,5), and (6,7). This step also takes ts + 4tw m time. In general, all-to-all broadcast can be performed on a p-processor tree of the type shown in Figure 4.7 (page 155) in (ts + tw mp/2) log p time. Note that if the order of the steps is changed, then the communication cost will increase. For example, if the pairs of processors that exchange data in the first step are (0,1), (2,3), (4,5), and (6,7), and the pairs that exchange data in the last step are (0,4), (1,5), (2,6), and (3,7), then the total communication time will be ts log p + tw m( p 2 − 1)/3. On the other hand, another scheme can perform all-to-all broadcast on a p-processor tree with CT routing in (ts + tw m)( p − 1) time. This can be done by embedding a logical ring onto the tree, as shown in Figure 4.1. Note that no two messages travelling in the same direction share a communication link. It is easy to verify that executing the algorithms of Figure 4.9 (page 159) of the text results in total communication time of (ts + tw m)( p − 1). This scheme leads to a higher ts term, but a lower tw term. 7 In the hypercube algorithm for all-to-all personalized communication described in Section 4.4 (page 167), the entire message received by a processor is not required by that processor. On a completely connected network, this operation can be performed in (ts + tw m)( p − 1) time. However, the best communication time for one-toall broadcast is (ts + tw m) log p (the same as in the case of a hypercube) if an entire message is routed along the same path. 8 The communication pattern for multinode accumulation on a hypercube is exactly the opposite of the pattern shown in Figure 4.11 (page 164) for all-to-all broadcast. Each processor has p messages to start with (as in Figure 4.11 (page 164)(d)), one for each processor (Figure 4.8 (page 157)). In the i th iteration (0 < i ≤ log p) of the multinode accumulation algorithm, processors communicate along the (log p − i + 1)th dimension 14 Basic Communication Operations 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Figure 4.1 All-to-all broadcast on an eight-processor tree by mapping a logical eight-processor ring onto it. of the hypercube so that processor j communicates with processor j ± 2log p−i . For example, in the first step, processor 0 sends the messages destined for processors 4, 5, 6, and 7 to processor 7, and processor 7 sends the messages destined for processors 0, 1, 2, and 3 to processor 0. After the first communication step, each processor adds the mp/2 numbers received to the mp/2 numbers already residing on them. The size of the data communicated and added in an iteration is half of that in the previous iteration. The total time is log p i i =1 (ts + (tw + tadd )mp/2 ), which is equal to ts log p + m(tw + tadd )( p − 1). 9 The shortest distance between processors i and j is their Hamming distance Hi, j (that is, the numbers of 1’s in bitwise exclusive-or of i and j). Let log p = d. The solution to this problem is the same as the number of d-bit numbers with exactly Hi, j 1’s in their binary representation. The solution is d!/(Hi, j !(d − Hi, j )!). 10 First, each processor performs a local prefix sum of its n/ p numbers in (n/ p − 1)tadd time. In the second step, the p processors compute prefix sums of p numbers by using the last prefix sum resulting from the local computation on each processor. This step takes (tadd + ts + tw ) log p time. Finally, the result of the parallel prefix sums operation of the second step is added to all the n/ p prefix sums of the first step at each processor in tadd n/ p time. Therefore, TP = (2 n − 1)tadd + (tadd + ts + tw ) log p. p 11 Consider a square mesh without wraparound connections. Number of words transmitted by a processor = Total number of processors = lav = Total traffic = Total number of links in the network = T lower bound all to all pers = = 13 m( p − 1) p √ p √ m( p − 1) p p 4p √ m( p − 1) p p 4p √ m( p − 1) p 4 The total number of links in a regular 3-D mesh of p processors is 3 p. Therefore, one-to-all broadcast and one-to-all personalized communication are more cost-effective on a sparse 3-D mesh (taking approximately 3tw mp1/3 and tw mp time, respectively) than on a regular 3-D mesh (on which they take the same amount of time as on the sparse 3-D mesh). On the other hand, a sparse 3-D mesh is less cost-effective for all-to-all broadcast (approximately 2tw mp time) than a regular 3-D mesh (approximately tw mp time). 14 In this communication model, one-to-all broadcast, all-to-all broadcast, and one-to-all personalized communication take approximately 3ts p 1/3 time on both the architectures. Thus, a sparse 3-D mesh is more costeffective. 15 In all-to-all broadcast on a hypercube, the message size doubles in each iteration. In k-to-all broadcast, in the worst case, the message size doubles in each of the first log k iterations, and then remains mk in the remaining 21 log( p/k) iterations. The total communication time of the first k iterations is ts log k + tw m(k − 1). The total communication time of the last log( p/k) iterations is (ts + tw mk) log( p/k). Thus, the entire operation is performed in ts log p + tw m(k log( p/k) + k − 1) time. As the base case of induction, it is easy to see that the statement is true for a 2-processor hypercube. Let all the p data paths be congestion-free in a p-processor hypercube for all q < p. In a 2 p-processor hypercube, if q-shifts for all q < p are congestion-free, then q-shifts for all q < 2 p are also congestion-free (Hint (1)). So the proof is complete if we show that q-shifts for all q < p are congestion-free in a 2 p-processor hypercube. Consider a circular q-shift for any q < p on a 2p-processor hypercube. All the p − q data paths leading from a processor i to a processor j such that i < j < p are the same as in a p-processor hypercube, and hence, by the induction hypothesis, do not conflict with each other. The remaining q data paths leading from a processor i to a processor j on the p-processor hypercube, such that j < i < p, lead to processor j + p on a 2 p-processor hypercube. Processor j + p is connected to processor j by a single link in the highest (that is, (log p + 1)th ) dimension of the 2 p-processor hypercube. Thus, following the E-cube routing, the data path from processor i to processor j + p in a circular q-shift on the 2 p-processor hypercube is the data path from processor i to processor j in a circular q-shift on a p-processor hypercube appended by a single link. The original path from processor i to j is congestion free (induction hypothesis) and the last link is not shared by any other message because it is unique for each message. Thus, q-shifts for all q < p are congestion-free in a 2 p-processor hypercube. 22 In a 1-shift on a 2-processor hypercube, the highest integer j such that 1 is divisible by 2 j is 0. Since log 2 = 1, the statement is true for p = 2 (because q = 1 is the only possible value of q for p = 2). Let the statement hold for a p-processor hypercube. As shown in the solution to Problem 4.22 (page 193), the length of a path between processors i and j, such that j < i < p, increases by a single link if the same shift operation is performed on a 2 p-processor hypercube. Thus, the length of the longest path increases from log p − γ (q) to log p − γ (q) + 1 (which is equal to log(2 p) + γ (q)) as the number of processors is increased from p to 2 p. Note that a circular q shift is equivalent to a (2 p − q)-shift on a 2 p-processor hypercube. So the result holds for all q such that 0 < q < 2 p. 24 Cost of Network ∝ Total Number of Links: No. of links in 2-D mesh with wraparound = 2p No. of links in a hypercube = s p log p 2 log p = 4 The communication times for various operations on a hypercube with cut-through routing can be found in Table 4.1 (page 187). For a 2-D wraparound mesh with CT routing and each link (log p/4)-channel wide, the communication times for various operations are as follows: Tone to all broadcast Tall = ts log p + 4tw m to all broadcast = √ 4tw m( p − 1) 2ts ( p − 1) + log p Tone to all per sonali zed Tall to all personali zed √ 4tw m( p − 1) 2ts ( p − 1) + log p √ 4tw mp( p − 1) √ = 2ts ( p − 1) + log p = If the cost of a network is proportional to the total number of links in it, then a mesh is asymptotically more cost-effective than a hypercube for all operations except all-to-all personalized communication. Cost of Network ∝ Bisection Width: √ Bisection width of 2-D mesh with wraparound = 2 p p Bisection width of hypercube = 2 √ p ′ s = 4 √ The following are the communication times on a 2-D wraparound mesh with CT routing and each link ( p/4)channel wide: Tone to all broadcast Tall to all broadcast Tone to all per sonali zed Tall to all personali zed 4tw m log p √ p √ √ = 2ts ( p − 1) + 4tw m p √ √ = 2ts ( p − 1) + 4tw m p √ = 2ts ( p − 1) + 4tw mp = ts log p + If the cost of a network is proportional to its bisection width, then a mesh is asymptotically more cost-effective than a hypercube for all operations except all-to-all personalized communication. For all-to-all personalized communication, both interconnection networks have the same asymptotic cost-performance characteristics. 25 Assuming the one-port communication model, one-to-all broadcast, all-to-all broadcast, and one-to-all personalized communication take the same amount of time on a completely connected network as on a hypercube. All-to-all personalized communication can be performed in (ts + tw m)( p − 1) time on a completely connected network.