Algorithms and Data Structures in C part 11

To illustrate message passing consider the case of determining the path to send a message from processor 0 to processor 7 in a 3-dimensional hypercube as shown
Nội dung trích xuất từ tài liệu:
Algorithms and Data Structures in C part 11To illustrate message passing consider the case of determining the path to send a message fromprocessor 0 to processor 7 in a 3-dimensional hypercube as shown in Figure 2.19. If the messageis to traverse a path which is of minimal length, that is d (0, 7), then it should travel over threeedges. For this case there are six possible paths:Figure 2.19 Hypercube ArchitectureIn general, in a hypercube of dimension d, a message travelling from processor x to processor yhas d (x, y) ! distinct paths (see Problem 2.11). One simple algorithm is to compute theexclusive-or of the source and destination processors and traverse the edge corresponding tocomplementing the first bit that is set. This is illustrated in Table 2.4 for left to rightcomplementing and in Table 2.5 for right to left complementing. Table2.4Calculating theMessagePath—LefttoRightProcessor ProcessorDestination Exclusive‐Or NextProcessor Source 000 111 111 100 100 111 011 110 110 111 001111Table2.5CalculatingtheMessagePath—Right toLeftProcessorSource Processor Exclusive‐ Next Destination Or Processor 000 111 111 001 001 111 110 011 011 111 100111The message passing algorithm still works under certain circumstances even when the hypercubehas nodes that are faulty. This is discussed in the next section.2.6.3EfficientHypercubesThis section presents the analysis of the class of hypercubes for which the message passingroutines of the previous section are valid. Examples are presented in detail for an 8-nodehypercube. 2.6.3.1TransitiveClosureDefinition 2.23The adjacency matrix, A, of a graph, G, is the matrix with elements aij such that aij = 1 impliesthere is an edge from i to j. If there is no edge then aij = 0. The adjacency matrix, A, of the transitive closure of the 8-node hypercube is simply the matrixFor a hypercube with all functional nodes every processor is reachable. Previous TableofContents Next Copyright © CRC Press LLC Algorithms and Data Structures in C++ by Alan Parker CRC Press, CRC Press LLC ISBN: 0849371716 Pub Date: 08/01/93 Previous TableofContents Next 2.6.3.2LeastWeightedPathLengthDefinition 2.24The least-weighted path-length graph is the directed graph where the weights of each edgecorrespond to the shortest path-length between the nodes. The associated weighted matrix consists of the path-length between the nodes. The path-lengthbetween a processor and itself is defined to be zero. The associated weighted matrix for an 8-node hypercube with all functional nodes isaij is the distance between nodes i and j. If nodes i and j are not connected via any path then aij =∞. 2.6.3.3HypercubeswithFailedNodesThis section introduces the scenario of failed processors. It is assumed if a processors or nodefails then all edges incident on the processor are removed from the graph. The remainingprocessors will attempt to function as a working subset while still using the message passingalgorithms of the previous sections. This will lead to a characterization of subcubes of ahypercube which support message passing. Consider the scenario illustrated in Figure 2.20. Inthe figure there are three scenarios with failed processors.In Figure 2.20b a single processor has failed. The remaining processors can communicate witheach other using a simple modification of the algorithm which traverses the first existing edgeencountered.Similarly, in Figure 2.20c communication is still supported via the modified algorithm. This isillustrated in Table 2.6. Notice that in Table 2.6 the next processor after 000 was 001. For thetopology in the figure the processor did not exist so the algorithm proceeded to the next bit fromright to left which gave 010. Since this processor existed the message was sent along the path.Figure 2.20 Hypercube with Failed Nodes Table2.6Calculating theMessagePath— ProcessorDestinationRighttoLeftforFigure Exclusive‐Or NextProcessor 2.20cProcessor Source 000 111 111 010 010 111 101 011 011 111 100111The scenario in Figure 2.20d is quite different. This is illustrated in Table 2.7.In this case, the first processor considered to is 001 but it is not functional. Processor 010 isconsidered next but it is not functional. For this case the modified algorithm has failed to routethe message from processor 000 to 011. There ...