tailieunhanh - Algorithms and Data Structures in C part 9

A cube-connected cycles topology is shown in Figure . 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 | Cube-Connected Cycles A cube-connected cycles topology is shown in Figure . 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 each of which has degree 3. This has the look and feel of a hypercube yet without the high degree. The cube-connected cycles topology has nlog n nodes. Figure Cube-Connected Cycles The Hypercube Topology This section presents algorithms and issues related to the hypercube topology. The hypercube is important due to its flexibility to efficiently simulate topologies of a similar size. Definitions Processors in a hypercube are numbered 0 . n - 1. The dimension d of a hypercube is given as where at this point it is assumed that n is a power of 2. A processor x in a hypercube has a representation of For a simple example of the enumeration scheme see Section on page 75. The distance d x y between two nodes x and y in a hypercube is given as The distance between two nodes is the length of the shortest path connecting the nodes. Two processors x and y are neighbors if d x y 1. The hypercubes of dimension two and three are shown in Figure . Message Passing A common requirement of a parallel processing topology is the ability to support broadcast and message passing algorithms between processors. A broadcast operation is an operation which supports a single processor communicating information to all other processors. A message passing algorithm supports a single message transfer from one processor to the next. In all cases the 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 from processor 0 to processor 7 in a 3-dimensional hypercube as shown in Figure . If the message is to traverse a path which is of minimal length that is d 0 7 then it should travel over three edges. For this case there are six .