Analytical Modeling of Parallel Programs

C HAPTER 5 Analytical Modeling of Parallel Programs 1 S = W W = TP W S + W −W p S As p increases, the fraction (W − W S )/ p approaches zero. However, no matter how large p is, S cannot exceed W/W S . 2 On a single processor, 11 arcs are traversed by DFS before the solution is found. On two processors, only four arcs are traversed by P1 before it finds the solution. Therefore, speedup on two processors is 11/4 = 2.75. The anomaly is due to the fact that in Figure 5.10 (page 228)(b), the algorithm being executed is not the same as in Figure 5.10 (page 228)(a). Tha parallel algorithm performs less overall work than the serial algorithm. The algorithm in Figure 5.10 (page 228)(b) is not true depth-first search; it is part depth-first and part breadthfirst. If a single processor alternates between the nodes of the left and right subtress (thereby emulating the two-processor algorithm of Figure 5.10 (page 228)(b)), then the serial algorithm traverses only eight arcs. 3 The degree of concurrency, the maximum speedup, and speedup when p = 1/2 × degree of concurrency for the graphs are given in the following table: (a) 2n−1 Degree of concurreny Maximum possible speedup Speedup when p = 1/2 × (degree of concurrency) 2n −1 log n 2n −1 log n+1 (b) 2 n −1 2n − 1 log n 2n −1 log n+1 (c) n n2 2n−1 n2 3n−2 (d) n n+1 2 n+1 3 The efficiency corresponding to various speedups can be computed by using E = S/ p, and the overhead function can be computed by using the following relations: E = pTP = To = = W pTP W E pTP − W 1 W ( − 1) E 250 Plot (c) 200 Plot (b) 150 100 S 50 Plot (a) 0 0 50 100 150 200 250 300 p Figure 5.1 Standard (Plot (a)), scaled (Plot (b)), and isoefficient (Plot (C)) speedup curves for Problems 5.5 (page 230) and 5.6 (page 230). 4 Let the isoefficiency function f ( p) be greater than ( p). If p = (W ), or W = ( p), then W < f ( p) because f ( p) > ( p). Now if W < f ( p), then E < (1), or pTP > (W ). The converse implies that pT P = (W ) only if p < (W ), or E = (1) only if p < (W ); that is, W > ( p). Thus, the isoefficiency function is greater than ( p). 5 Plots (a) and (b) in Figure 5.1 represent the standard and scaled speedup curves, respectively. 6 See Plot (c) in Figure 5.1. 7 Figure 5.2 plots the efficiency curves corresponding to the speedup curves in Figure 5.1. 8 Scaled speedup, in general, does not solve the problem of declining efficiency as the number of processors is increased. The scaled speedup curve is linear only if the isoefficiency function of a parallel system is linear (that is, ( p)). 9 512 (513 − 11 log p) × p ≥ TP = n p − 1 + 11 log p ≥ n The following table gives the largest n corresponding to a p . p n 1 513 4 1964 16 7504 64 28,608 256 108,800 1024 412,672 4096 1560,576 It is not possible to solve an arbitrarily large problem in a fixed amount of time, even if an unlimited number of processors are available. For any parallel system with an isoefficiency function greater than ( p) (such as, the one in Problem 5.5 (page 230)), a plot between p and the size of the largest problem that can be solved in a given time using p processors will reach a maximum. It can be shown that for cost-optimal algorithms, the problem size can be increased linearly with the number of processors while maintaining a fixed execution time if and only if the isoefficiency function is ( p). The proof is as follows. Let C(W ) be the degree of concurrency of the algorithm. As p is increased, W has to be increased at least as ( p), or else p will eventually exceed C(W ). Note that C(W ) is upper-bounded by (W ) and p is upper-bounded by C(W ). T P is given by W/ p + To (W, p )/ p . Now consider the following Plot (c) 1 0.9 Plot (b) 0.8 0.7 0.6 0.5 0.4 E 0.3 0.2 0.1 0 Plot (a) 0 50 100 150 200 250 300 p Figure 5.2 Efficiencies corresponding to the speedups in Figure 5.1. two cases. In the first case C(W ) is smaller than (W ). In this case, even if as many as C(W ) processors are used, the term W/C(W ) of the expression for T P will diverge with increasing W , and hence, it is not possible to continue to increase the problem size and maintain a fixed parallel execution time. At the same time, the overall isoefficiency function grows faster than ( p) because the isoefficiency due to concurrency exceeds ( p). In the second case in which C(W ) = (W ), as many as (W ) processors can be used. If (W ) processors are used, then the first term in T P can be maintained at a constant value irrespective of W . The second term in TP will remain constant if and only if To (W, p) remains constant when p = (W ) (in p other words, To /W remains constant while p and W are of the same order). This condition is necessary and sufficient for linear isoefficiency. For further details, see paper by Kumar and Gupta [KG91]. 11 See solution to Problem 4.10 (page 191). TP = S = 2 n p Isoefficiency function = − 1 + 10 log p n/ p − 1 2 n − 1 + 10 log p p ( p log p) 12 The algorithm is a single-node accumulation in which the associative operation is a comparison that chooses the greater of the two numbers. The algorithm is not cost-optimal for finding the maximum of n numbers on an n-processor mesh. 13 Refer to the paper by Gupta and Kumar [GK93]. 14 10n log p n log n + p p dTP −n log n − 10n log p + 10n = = 0 p2 p2 dp p2 10 log p = 10 − log n log p = 1 − log n 1/10 2 p = n 1/10 Equation 5.21, inthiscase, leadstothe f ollowing : TP = This is actually a condition for a maximum, rather than a minimum (this can be verified by a taking a second derivative). Since To < ( p) in this case, the minimum parallel run time is obtained when as many processors as possible are used to solve the problem [GK93]. Hence, the actual value of T Pmi n should be derived by putting 15 p = n in the expression for TP . This leads to T min = 11 log n . P Refer to the paper by Gupta and Kumar [GK93]. C HAPTER Programming Using the Message-Passing Paradigm The solutions for this chapter will be provided at a later time. 6 C HAPTER 7 Programming Shared Address Space Platforms Since all of the questions in this chapter are implementation based and implementations (and their performance) differ markedly, we only give outlines of solutions. 1 • To time thread creation, create a large number of threads in a for loop and time this loop. • To time thread join, time the corresponding join functions executed in a for loop. • To time successful locks, create a large array of locks and lock all of these in a for loop. • To time successful unlocks, time corresponding unlocks in a for loop. • To time successful trylock, repeat the process above for successful locks. • To time unsuccessful trylocks, first lock a mutex and repeatedly try to lock it using trylock in a for loop. • To time a condition wait, set up two threads, one that waits and another that signals. Execute a large number of wait-signal pairs. The smallest of these times, with high probability, gives the condition-wait time. • To time a condition signal, time the function with various number of waiting threads. • The condition broadcast case is similar to the condition signal case, above. 2 The queue is implemented as a heap. The heap is protected by a single lock. Each insertion/extraction is protected by a lock associated with the heap. At 64 threads, in most thread systems, students should observe considerable contention. 3 The condition wait case is similar to the one above, except, instead of locking, a thread executes a condition wait and instead of unlocking, a thread does a condition signal. The performance of this formulation should be marginally better but will saturate as well. 4 This is a simple extension of a producer-consumer paradigm in which the network thread is the producer for the decompressor thread, which in turn is the producer for the render thread. The code can be implemented starting from the code in Example 7.6. 7 The read-write locks are illustrated in 7.8.1. These functions can be easily adapted to the problem of binary tree search. Only insertions require write locks. All other threads only need read locks. 8 The performance saturates as the number of threads increases because of contention on the global lock. 9 The saturation point is pushed back because of the use of read-write locks since reads can be concurrently executed. 10 There are several strategies for implementing a Sieve. As the numbers pass through, the first number installs itself as a thread. The thread is responsible for filtering all multiples of the associated number. The key programming task is to ensure coordination between threads eliminating different multiples (i.e., the thread eliminating multiples of 3 must be able to filter a block before the thread responsible for eliminating multiples of 5). An alternate strategy is to determine all the primes whose multiples need to be eliminated first and them to instantiate them as threads. This algorithm has a significant serial component and does extra work. 11 The implementation described saturates because of contention on the open list. 12 The saturation point is pushed back (depending on the choice of k). Also, as the number of heaps is increased, excess work increases, causing a reduction in the speedup. 14 When the function becomes computationally expensive, all of the formulations can be expected to perform similarly. 16 The implementation is very similar to the pthreads version, except the task of creation and joining is accomplished using sections, and explicit locks can be used in OpenMP, much the same way as in pthreads.