Algorithms and Data Structures in C part 9

A cube-connected cycles topology is shown in Figure 2.18. This topology is easily formed from the hypercube topology by replacing each hypercube node with a cycle of nodes. As a result, the new topology has nodes
Nội dung trích xuất từ tài liệu:
Algorithms and Data Structures in C part 9 2.5.3.4CubeConnectedCyclesA cube-connected cycles topology is shown in Figure 2.18. This topology is easily formed fromthe hypercube topology by replacing each hypercube node with a cycle of nodes. As a result, thenew topology has nodes, each of which, has degree 3. This has the look and feel of a hypercubeyet without the high degree. The cube-connected cycles topology has nlog n nodes.Figure 2.18 Cube-Connected Cycles2.6 The Hypercube TopologyThis section presents algorithms and issues related to the hypercube topology. The hypercube isimportant due to its flexibility to efficiently simulate topologies of a similar size.2.6.1DefinitionsProcessors in a hypercube are numbered 0, ..., n - 1. The dimension, d, of a hypercube, is givenaswhere at this point it is assumed that n is a power of 2. A processor, x, in a hypercube has arepresentation ofFor a simple example of the enumeration scheme see Section 2.5.3.3 on page 75. The distance, d(x, y), between two nodes x and y in a hypercube is given asThe distance between two nodes is the length of the shortest path connecting the nodes. Twoprocessors, x and y are neighbors if d (x, y) = 1. The hypercubes of dimension two and three areshown in Figure 2.19.2.6.2MessagePassingA common requirement of a parallel processing topology is the ability to support broadcast andmessage passing algorithms between processors. A broadcast operation is an operation whichsupports a single processor communicating information to all other processors. A messagepassing algorithm supports a single message transfer from one processor to the next. In all casesthe messages are required to traverse the edges of the topology.To 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 Definition 2.16A cycle is a path from a vertex to itself which does not repeat any vertices except the first and thelast. A graph containing no cycles is said to be acyclic. An example of cyclic and acyclic graphs isshown in Figure 2.9.Figure 2.9 Cyclic and Acyclic GraphsNotice for the directed cyclic graph in Figure 2.9 that the double arrow notations between nodesv2 and v4 indicate the presence of two edges (v2, v4) and (v4, v2). In this case it is these edges whichform the cycle.Definition 2.17A tree is an acyclic connected graph. Examples of trees are shown in Figure 2.10.Definition 2.18An edge, e, in a connected graph, G = (V, E), is a bridge if G′ = (V, E′) is disconnected whereFigure 2.10 TreesIf the edge, e, is removed, the graph, G, is divided into two separate connected graphs. Noticethat every edge in a ...