Graph Algorithms

C HAPTER 10 Graph Algorithms 1 The parallel run time of Prim’s algorithm on a hypercube is   n2 + (n log p). (10.1) p If p = (n), the parallel run time is (n log n) and is determined by the second term of the above equation. The minimum parallel run time can be obtained by differentiating Equation 10.1 with respect to p, setting the derivative equal to zero, and solving for p as follows: TP =      n2 n = 0 ⇒ p = (n) + 2 p p Therefore, the minimum run time is obtained when p = (n) and is  −   n2 + (n log n) = (n) + (n log n) = (n log n). TP =  n However, if we use (n/ log n) processors, then the parallel run time is TP = (n log n) + (n log n − n log log n) = (n log n). (10.2) (10.3) From Equations 10.2 and Equation 10.3 we see that the parallel run times obtained using (n) and (n / log n ) processors are the same in asymptotic terms. However, the exact run time when (n/ log n) processors are used is larger than the one obtained when p = n, by a constant factor. 2 Dijkstra’s single-source shortest paths algorithm can record the shortest path by using an additional array path, such that path[v] stores the predecessor of v in the shortest path to v. This array can be updated by modifying Line 12 of Algorithm 10.2 (page 437). Whenever l[u] + w(u, v) is smaller than l[v ] in Line 12, path[v ] is set to u. This modification does not alter the performance of the algorithm. 3 Let G = (V , E ) be a graph. For each edge (u, v) ∈ E let w(u , v) = 1. The breadth-first ranking can be obtained by applying Dijkstra’s single-source shortest path algorithm starting at node u on graph G = (V, E, W ). The parallel formulation of this algorithm is similar to that of Dijkstra’s algorithm. 4 The solution is discussed by Bertsekas and Tsitsiklis [BT89]. 5 The sequential all-pairs shortest paths algorithm requires (n 2 ) memory. This memory is used to store the weighted adjacency matrix of G = (V , E ). The source-partitioning formulation of Dijkstra’s algorithm requires (n 2 ) memory on each processor, and the source-parallel formulation requires (n 3 / p ) memory on Memory per Processor Memory Overhead MatrixMultiplication Based Algorithm (n 2 / p) (1) Dijkstra’s Algorithm SourceSourcePartitioningParallelFormulation Formulation (n 2 ) (n 3 / p) ( p) (n) Floyd’s Algorithm BlockCheckerboard Pipelined Formulation Formulation 2 (n / p) (n 2 / p) (1) (1) Table 10.1 Memory overhead of the all-pairs shortest paths algorithm presented in Section 10.4 (page 437). Memory overhead is defined as the ratio of the memory required by all the p processors with the memory required by the sequential algorithm. each processor. The reason is that in the source-parallel formulation, there are n groups of p/n processors, each running a copy of Dijkstra’s single-source shortest path. For Floyd’s algorithm (both the 2D blockmapping and its pipelined variant) requires (n 2 / p) memory per processor. Table 10.1 summarizes the memory requirements, and the memory overhead factors of each formulation. For further details refer to Kumar and Singh [KS91]. 6 Replacing Line 7 of Algorithm 10.3 (page 440) by di, j := min{di, j , (di,k + dk, j )}, we perform the updates of the D matrix in place, without requiring any additional memory for the various (k−1) are D (k) matrices. The replacement is correct because during the kth iteration, the values of d (k−1) and d k, j i,k (k ) (k) the same as di,k and dk, j . This is because the operation performed at Line 7, does not change these values. 7 Recall from Section 10.4.2 (page 441) that in each iteration of Floyd’s algorithm, the algorithm performs two broadcasts, one along the rows and one along the columns. Each broadcast requires a message of size √ (n/ p) to be sent to all the processors in a row or column. On a mesh with store-and-forward routing, each broadcast operation takes (n) time, and on a mesh with cut√ √ through routing, it takes ((n log p)/ p + p) time. Since the algorithm requires n iterations, the parallel run time on a mesh with store-and-forward routing is  TP =  and on a mesh with cut-through routing is n3 p  + (n 2 ),     n2 n3 √ TP =  +  √ log p + n p . p p The efficiency of the formulation on a mesh with store-and-forward routing is E= 1 . 1 + ( p/n) Therefore, the isoefficiency function is ( p 3 ). The efficiency of the formulation on a mesh with cut-through routing is E= 1 . √ 1 + (( p log p)/n) + ( p1.5 /n 2 ) The isoefficiency function due to the first term is ( p1.5 log3 p) and the isoefficiency function due to the second term is ( p 2.25 ). Thus, the overall isoefficiency function is ( p 2.25). 8 (a) (k) (k ) and dk, j values to compute In each iteration of Floyd’s algorithm, each processor needs to know the di,k . di,(k+1) j By partitioning the D (k) matrix in a block-striped fashion, the d (k) k, j values are stored locally in each processor. However, the di(,kk) values needs to be obtained by the processor that stores the kth column of the D (k) matrix. Therefore, in each iteration of the block-striped formulation, the processor that has the kth column needs to broadcast it to all the other processors. Since each column contains n elements, this operation takes (n log p) time on a hypercube-connected parallel computer. Therefore, the parallel run time is (b)   n3 + (n 2 log p). TP = p is (( p log p)3 ), which is the overall isoefficiency The isoefficiency function due to communication function. The isoefficiency function of the block-striped formulation is worse than that of the 2D block formulation, which is ( p1.5 log3 p). Therefore, this formulation is less scalable, and has no advantages over the 2D block partitioning. √ On a mesh with store-and-forward routing, it takes (n p) time to broadcast a column. Therefore, the parallel run time is   n3 √ TP =  + (n 2 p). 4.5 Consequently, the isoefficiency function is ( p p ). √ On a mesh with cut-through routing, the column broadcast takes (n log p + p) time. Therefore, the parallel run time is   n3 √ TP =  + (n 2 log p) + (n p). The isoefficiency function due to the firstpcommunication term is (( p log p)3 ) and due to the second communication term is ( p2.25 ). Therefore, the overall isoefficiency function is (( p log p)3 ). On a ring with store-and-forward routing, the column broadcast takes (np) time. The parallel run time is   n3 TP =  + (n 2 p). p 6 The isoefficiency function is ( p ). The same column broadcast takes (n log p + p) time on a ring with cut-through routing. The parallel run time is   n3 + (n 2 log p) + (np). p The isoefficiency function is (( p log p)3 ). Thus block-striped partitioning has similar performance on a ring with CT routing and on a mesh with CT routing. TP =  9 The pipelined formulation of the block-striped partitioning proceeds along the same lines as that with the 2D block partitioning. As soon as the processor containing the kth column has finished the (k − 1)st iteration, it sends the (k − 1)st column to its two neighbor processors. When a processor receives elements of the (k − 1)st column it stores them locally and then forwards them to its other neighbor. A processor starts working on the kth iteration as soon as it has computed the (k − 1)st iteration and has received the (k − 1)st columns. It takes (np) time for the first column to reach processor Pp . After that each subsequent column follows after (n 2 / p) time in a pipelined mode. Hence, processor P p finishes its share of the shortest path computation in (n 3 / p) + (np) time. When processor P p has finished the (n − 1)st iteration, it sends the relevant values of the nth column to the other processors. These values reach processor P1 after (np) time. The overall parallel run time is  TP =  n3 p  + (np). Figure 10.1 Merging the spanning forests along a row of a mesh. Each arrow indicates the direction of data movement. In this example, each row has 16 processors. The efficiency is 1 . 1 + ( p 2 /n 2 ) E= Therefore, the isoefficiency function is ( p 3 ). 10 The analysis is presented by Kumar and Singh [KS91]. The exact parallel run time is TP = n3   n √ tc + 4( p − 1) ts + √ tw , (10.4) p p where tc is the time to perform the operation in Line 7 of Algorithm 10.3 (page 440), ts is the message startup time, and tw is the per-word transfer time. Note that Equation 10.4 is valid under the following two √ assumptions (a) n 2 tc / p ≈ ts + ntw / p and (b) when a processor transmits data it is blocked for ts time; after that it can proceed with its computations while the message is being transmitted. 11 The main step in deriving a parallel formulation of the connected components algorithm for a mesh-connected parallel computer is finding an efficient way to merge the spanning forests. One possible way is to first merge the spanning forests along each row of the mesh. At the end of this step, a column of mesh processors stores the merged spanning forests of each row. The global spanning forest is found by merging these spanning forests. This is accomplished by performing a merge along a single column of the mesh. One possible way of merging the spanning forests in each row is shown in Figure 10.1. Notice that in each but the last step, the distance among processors that need to communicate doubles. Recall that in order for a pair of processors to merge their spanning forests, one processor must send (n) edges to the other processor. In a mesh with store-and-forward routing in order to merge the spanning forests along a row, the total time spent in sending edges is ⎛ √ log( p/4)  (n) ⎝ 2i + 1 i =0 ⎞ ⎠ = (n √ p). √ Similarly, the time to perform the merge along the column is also (n p). Therefore, the parallel run time of the algorithm is  TP =  The speedup and efficiency are: S = E = Therefore, the isoefficiency function is ( p 3 ). n2 p  √ + (n p). (n 2 ) √ , (n 2 / p) + (n p) 1 . 1 + ( p 1.5 /n) In a mesh with cut-through routing, the time spent merging the spanning forests along each row is: √ log( p/4) (n log p) +  √ 2i = (n log p) + ( p). i =0 The parallel run time is  The speedup and efficiency are: TP =  S = E = n2 p  √ + (n log p) + ( p). (n 2 ) √ , (n 2 / p) + (n log p) + ( p) 1 . √ 1 + (( p log p)/n) + (( p p)/n 2 ) The isoefficiency function is ( p 2 log2 p). Note that the isoefficiency function for a mesh with cut-through routing is the same as that for a hypercube. 12 This formulation is analyzed by Woo and Sahni [WS89]. The performance of this formulation is similar to the block-striped partition. 13 Consider a sparse graph G = (V, E) with average out degree of m. That is, there is on the average m edges (u, v) for each vertex u. Recall that in each step of Johnson’s algorithm, a vertex with minimum l value is extracted from the priority queue and its adjacency list is traversed. The traversal of the adjacency list may require updating the priority queue. These updates correspond to Line 12 of Algorithm 10.5 (page 455). On an average, m priority queue updates are performed in each iteration. Therefore, during each iteration of Johnson’s algorithm, at most p2 = m processors can be used to compute new l values. The priority queue can be maintained using a scheme proposed by Kwan and Ruzzo [KR84]. According to this scheme, m updates are done in ((m log n )/ p) time on a CREW PRAM where p ≤ m ≤ n . Note that n is the number of elements in the priority queue and p is the number of processors used. Therefore, at most p1 = m processors can be used to maintain the priority queue. Note that computing updated values of l and updating the priority queue is done one after the other. Therefore, instead of using p1 and p2 processors, we can only use p = max{ p1 , p2 } processors. Since both p1 and p2 can be at most m, the maximum number of processors that can be used is m . The parallel run time of the formulation on a CREW PRAM is 14     nm nm log n + . TP =  p p Since the processor-time product is (nm log n) = (|E| log n), this formulation is cost-optimal. Recall that in each iteration of Dijkstra’s single-source shortest path, a vertex u with the smallest l-value is found, and its adjacency list is processed. Dijkstra’s algorithm is shown in Algorithm 10.2 (page 437). Furthermore, let m be the average out-degree of the vertices. First consider the case where n/ p vertices and their adjacency lists are assigned to each processor. Furthermore, assume that each processor also stores the l -values for its assigned vertices. In each iteration, the algorithm spends (n/ p) + (log p) time finding a vertex u with minimum l[u] value. Let Pi be the processor that has u. In order for Line 12 of Algorithm 10.2 (page 437) to be executed, processor Pi sends w(u, v) and l[u] to the processor that has v. Assuming that the destinations of the messages are distinct, this operation is similar to one-to-many personalized communication. The time required is (log p + m). Therefore, the parallel run time for n iterations is  TP =  n2 p  + (n log p) + (nm + n log p). Since the sequential complexity of Dijkstra’s algorithm is (n 2 ), the speedup and efficiency are as follows: S = E = (n 2 ) (n 2 / p) + (n log p) + (nm + n log p) 1 1 + (( p log p)/n) + (mp/n + ( p log p)/n) For a cost optimal formulation, ( p log p) = (n) and (mp) = (n). Therefore, this formulation can use min{(n/m), (n / log n )} processors. Now consider the case where each processor is assigned m/ p elements from each adjacency list. Assume that the l-values of the vertices are distributed among the p processors, so each processor has n/ p l-values. Finding the vertex u with the minimum value of l takes (n/ p) + (log p) time. In order for the l-values to be updated for each vertex v adjacent to u, the processor responsible for l[v] must know w(u, v). Each processor has m/ p elements of the adjacency list of u. These elements need to be send to different processors. Therefore each processor spends at least (m log p / p ) time. Thus, in the worse case the overall time spent in communication is (m log p). Therefore, the overall run time for n iterations is   n2 TP =  ( + (nm log p). p Since the sequential complexity is (n 2 ), this formulation is cost-optimal. However, this formulation can use only p = min{n/(m log n), m} processors. Note that Dijkstra’s algorithm has the same complexity for both sparse and dense graphs. The operation that determines the complexity is finding the vertex with the minimum value of l . 15 The solution to this problem is similar to Solution 14. 17 If we ignore overhead due to extra work, we essentially make the assumption that computation progresses in a wave fashion. That is, at any time, only the vertices belonging to a diagonal of the grid graph are performing computations. The average length of each diagonal is n/2 vertices, and there are a total of (2n − 1) diagonals. √ √ In the 2D cyclic mapping, each diagonal of vertices is mapped onto a diagonal of the p × p processor √ grid. This diagonal of processors is wrapped-around in such a way that at any time, at most p processors are performing computation. This can be verified by looking at Figure 10.2. √ Since there are an average of n/2 vertices in each diagonal and p processors assigned to it, the shortest path √ √ computation performed by these processors takes (n/(2 p)) = (n/ p) time. However, each shortest path computation requires sending the data to neighbor processors. Therefore, after computing each diagonal, √ the algorithm spends (n/ p) time sending path information. Therefore, the overall run time is    n2 n2 + √ . √ p p √ The processor-time product of this formulation is (n 2 p); therefore, this algorithm is not scalable. Let b be the block size of the 2D block-cyclic-mapping. As in Solution 17, each diagonal has n/2 vertices. √ √ Each diagonal now can intersect up to 2 p processors. Therefore, the algorithm spends (n/ p) time for √ √ each diagonal. Since the block size is b, each of the 2 p processors has approximately (n/(b p)) blocks assigned to it. Each processor needs to send path information for only the boundary vertices of each block, √ therefore the communication is (n/(b p)). The parallel run time of this formulation is  TP =  18     n2 n2 . + √ √ b p p √ 2 The processor-time product is (n p); thus, this formulation is not cost-optimal. TP =  (a) (b) (c) Figure 10.2 (a) A grid graph, (b) Mapping the grid graph onto a processor grid using 2D cyclic mapping. (c) The processors √ intersected by the diagonal in (a). Note that each diagonal intersects at most p processors. 19 The solution to this problem is along the lines of Solution 17. 20 The amount of extra computation performed depends on the grid graph. In particular, if the shortest paths from the source to any other vertex follow more or less a straight path then the amount of extra computation is minimal. However, if the shortest paths are snakelike, then the amount of extra computation is significant. Experimental results obtained by Wada and Ichiyoshi [WI89] suggest that the 2D block and the 1D block mappings perform less extra computation than the 2D cyclic and the 2D block-cyclic mappings. 21 The parallel formulation of Sollin’s algorithm is described by Leighton [Lei92b]. C HAPTER 11 Search Algorithms for Discrete Optimization Problems 1 The value of V ( p) for the GRR-M scheme is identical to that of the GRR scheme. However, the number of accesses to target are reduced drastically in this case. Each request now incurs a delay of time δ at each of the log p processors in the path. Therefore, there is a delay time of O(δ log p) associated with each request. This does not change the overall time, since the time to transfer work across the network is also (log p). The isoefficiency function due to communication overhead is given by O(V ( p) log p log W ), or O( p log p log W ). Equating this with the essential work W , we have the isoefficiency function of this scheme to be O( p log2 p). Since there is no contention in this load balancing scheme, the overall isoefficiency is given by O( p log2 p). Kumar, Ananth, and Rao [KGR91] discuss this scheme in detail and provide experimental evaluation. 2 This load balancing technique uses a distributed scheme for implementing the counter. The step in the counter is used to locate the processor to be requested for work. Each time a request is made, the step moves to the right. In this way, after p requests, the step returns to the processor it started at. The step in the value of counters can be detected in (log p) using the algorithm presented by Lin [Lin92]. This algorithm can be used in conjunction with the load balancing strategy described in the problem. V ( p) for this scheme is p. Therefore, the communication overhead is given by O( p log p log W ). Equating this with the essential work W , we can determine the isoefficiency of this scheme to be O( p log2 p). The isoefficiency term resulting from the number of messages required to balance load is the same as that of GRR (and GRR-M), which is O( p 2 log p). Therefore, the overall isoefficiency of this scheme on a network of workstations is O( p 2 log p). Lin [Lin92] discusses this result in detail. √ 3 Size of message grows as w: The contribution to the overall isoefficiency due to contention remains the same and can be obtained by equating W/ p = O(V ( p) log W ) O( p 2 log p). This yields an isoefficiency of There are a total of V ( p) log W messages. Of these, in the first V ( p) messages, the maximum work transferred is W . In the second V ( p) messages, the maximum work transferred is (1 − α)W . Each of these messages may potentially be communicated over a distance of log p . Therefore the total communication overhead is given by log W −1 Tcomm = O(  i =0 V ( p) (1 − α)i W log p) √ For GRR, V ( p ) = p . If (1 − α) = r, this expression reduces to Tcomm = √ O( p W log p log W −1  ri) i =0 Tcomm = √ (1 − r log W −1 ) ) O( p W log p 1−r Since r < 1, this expression reduces to √ Tcomm = O( p W log p) Equating this overhead with essential computation W , we get W = O( p2 log2 p) Therefore the overall isoefficiency is now O( p 2 log2 p). 4 The run time of a termination detection algorithm is considered as the time taken by an algorithm to signal termination after the last processor has finished its computation. Since the token may need to traverse the ring once after all processors have gone idle, in the worst case, the run time of the termination algorithm is ( p). Since all processors have to spend this time, the total overhead due to termination detection is ( p 2 ). The constant associated with this isoefficiency term is very small. Therefore, unless the value of p is very large, the contribution of termination detection to overall isoefficiency can be neglected. 6 The solution is discussed in detail by Mahapatra and Dutt [DM93]. 7 The solution is discussed in detail by Kimura and Nobuyuki [KI90]. Ignoring communication latency, they show that the isoefficiency function of the single level load balancing scheme is given by O( p 2 ). 8 The solution is discussed in detail by Kimura and Nobuyuki [KI90]. Ignoring communication latency, they show that the isoefficiency function of the multi-level load balancing scheme is given by O( p (l+1)/l (log p)(l+1)/l ), where l is the number of levels. 9 Ferguson and Korf [FK88] discuss this scheme in detail. 10 Let the total number of nodes to be expanded at a certain moment by the search algorithm be r and number of processors with at least one node in its local open list be X r . As shown by Manzini [MS90], E[X r ] = ( p) as r becomes ( p) (which is a reasonable assumption). In each iteration, ( p) nodes are expanded and the corresponding communication overhead is ( p). This corresponds to an isoefficiency function of ( p). Since there are no other overheads, the overall isoefficiency of this scheme is given by ( p). The analysis considers only the number of nodes and not the quality of nodes expanded. The quality of the nodes can be analyzed in a similar manner. Manzini [MS90] discusses these results in detail. Dutt and Mahapatra [MD93] experimentally evaluate this scheme and propose improved variants. 11 Each node in the parallel best-first search formulation is hashed to a random processor. The time taken to perform this communication is given by O(m + log p) for a message of size m. Since there are W/ p such hash operations, the total communication time is given by O(W m/ p + n / p log p). The total communication overhead is given by O(W m + W log p). Equating this with the total essential work, which is (W ), we can see that the formulation is unscalable. This is because no matter how fast the problem size W is increased, the efficiency cannot be held constant. The formulation is scalable only for architectures for which the cost of communicating a node across is O(1); e.g., on PRAMs.