TAILIEUCHUNG - 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 | 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 possible paths Figure Hypercube Architecture In general in a hypercube of dimension d a message travelling from processor x to processor y has d x y distinct paths see Problem . One simple algorithm is to compute the exclusive-or of the source and destination processors and traverse the edge corresponding to complementing the first bit that is set. This is illustrated in Table for left to right complementing and in Table for right to left complementing. Table Calculating the Message Path Left to Right Processor Source ProcessorDestination Exclusive-Or Next Processor 000 111 111 100 100 110 111 011 111 110 001 111 Table Calculating the Message Path Right to Left Processor Source Processor Destination Exclusive-Or Next Processor 000 111 111 001 001 111 110 011 011 111 100 111 The message passing algorithm still works under certain circumstances even when the hypercube has nodes that are faulty. This is discussed in the next section. Efficient Hypercubes This section presents the analysis of the class of hypercubes for which the message passing routines of the previous section are valid. Examples are presented in detail for an 8-node hypercube. Transitive Closure Definition The adjacency matrix A of a graph G is the matrix with elements aij such that aij 1 implies there 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 matrix For a hypercube with all functional nodes every processor is reachable. Previous Table of Contents Next Copyright CRC Press LLC Algorithms and Data Structures in C by Alan Parker CRC Press CRC .

• Kỹ thuật lập trình
• thủ thuật lập trình
• ngôn ngữ lập trình
• tài liệu lập trình
• hướng dẫn lập trình
• kĩ năng lập trình
• mẹo lập trình
• kỹ thuật lập trình
• kỹ năng lập trình
• bí quyết lập trình
• phương pháp lập trình
• tư liệu lập trình
• kĩ thuật lập trình
• AutoIT