Patent Publication Number: US-5255368-A

Title: Method for selecting data communications paths for routing messages between processors in a parallel processing computer system organized as a hypercube

Description:
FIELD OF THE INVENTION 
     This invention relates to computer systems and more particularly to parallel processors within a computer system. Even more particularly, the invention relates to routing messages between parallel processors within a hypercube parallel processor computer system. 
     BACKGROUND OF THE INVENTION 
     Parallel data connections between processors within a computer system can be accomplished in various ways. One such way is called a hypercube, and can have various dimensions. An n-cube network of processors or nodes, called an n-dimensional hypercube, consists of 2&#34; identical nodes that are interconnected to each other so that each node has n neighbors. The nodes are given a binary number address and they are connected in such a manner that the binary number addresses between connected nodes differs in one and only one bit. FIG. 1 shows an example of a prior art hypercube where n =3. As shown in FIG. 1, when n=3, an n-cube can be represented as an ordinary cube in three dimensions where the vertices are the 8 (2 3 ) nodes of the 3-cube and the edges represent data communication paths between the nodes. 
     Hypercubes have shown to be superior over simpler interconnects because of faster communication between the nodes. In a Hypercube data transfers are performed by passing messages between nearest neighbors. Thus a data packet which must travel between a starting node and a destination node may cross a sequence of nodes between the starting and destination nodes. 
     A key disadvantage of the hypercube topology is the growth rate of the data communication path count between neighbors as n increases. As n increases, each node becomes more difficult to design and fabricate due to this increasing number of connections. This growth rate, coupled with pin limitations on VLSI chips, continues to seriously limit the scalability of the hypercube topology to massively parallel systems. Additionally, the inherent bi-directional nature of the data communication paths within the hypercube prevents it from being readily used with naturally unidirectional media, such as fiber-optic media. Most of the existing hypercube connected multi-processor systems use two physical data communication paths, one for transmitting data in each direction, to allow parallel transmission between two adjacent nodes of the hypercube. 
     There is a need in the art then for a method of defining a hypercube using single unidirectional data communication paths. There is a further need for a method of determining the data communication paths that must be traversed when sending a message from one node of the hypercube to a second node. The present invention meets these needs. 
     SUMMARY OF THE INVENTION 
     It is an aspect of the present invention to provide a method of defining the direction of the data communication paths in a parallel processing computer system organized as a unidirectional hypercube. 
     It is another aspect of the invention to provide a method of determining which data communication paths to traverse when sending a message from a starting node of the hypercube computer system to a destination node within the system. 
     The above and other aspects of the invention are accomplished in a method of defining the direction for each data communication path that interconnect the processors, also called nodes, of a parallel processor computer system that is organized as a hypercube. The method computes a sum from the binary bits of the address of the node and if the sum is an odd number, the data communication path will be inbound. If the sum is an even number, the data communication path will be outbound. 
     The invention also defines a method of routing messages between any two arbitrary nodes within the hypercube. The routing method is performed in each node as the message passes through the node. The method forms a destination path by exclusive or-ing the starting node address with the destination node address. The method then analyzes the bits of the destination path to determine which data communication path to use when forwarding the message to the next node in the hypercube. The routing method is based on local information only, and does not query other nodes to determine how they might route the message. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above and other aspects, features, and advantages of the invention will be better understood by reading the following more particular description of the invention, presented in conjunction with the following drawings, wherein: 
     FIG. 1 shows a prior art bi-directional data path hypercube computer system; 
     FIGS. 2 and 3 shows a method for defining the direction of data paths within a unidirectional hypercube computer system; 
     FIG. 4 shows a hypercube having eight processors with directional data paths as defined by the method of FIGS. 2 and 3; 
     FIG. 5 shows a block diagram of one of the identical parallel processors within the hypercube of FIG. 4; 
     FIG. 6 shows a block diagram of the input/output (I/0) processor of the system of FIG. 4; and 
     FIGS. 7-14 show a flowchart of the routing method of the present invention for routing messages between the parallel processors of the system defined by FIGS. 2 and 3. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The following description is of the best presently contemplated mode of carrying out the present invention. This description is not to be taken in a limiting sense but is made merely for the purpose of describing the general principles of the invention. The scope of the invention should be determined by referencing the appended claims. 
     Appendix 1, attached hereto and incorporated herein by reference for all that is disclosed therein, describes the mathematical foundations for the invention. The mathematical foundations are also disclosed in a Masters Thesis entitled &#34;Optimal Diameter Unidirectional Hypercubes&#34; published Aug. 21, 1990 at the University of Minnesota by the inventor hereof, also incorporated herein by reference for all that is disclosed therein. 
     As discussed above a hypercube consists of 2&#34; identical nodes that are interconnected to each other so that each node has n neighbors and the node addresses for each of the neighbors differs from the address of the node by only one binary bit. Referring now to FIG. 1, a hypercube computer system 100 contains a node 102 which has a binary address of 000. The node 102 represents a processor within the hypercube, which typically includes a processing element and associated random access memory. Typically a hypercube will also contain an input output processor, not shown in FIG. 1, which performs communications with a user of the system and which also contains data storage devices such as disks or tapes. 
     The hypercube of FIG. 1 is a 3-cube, which contains 2 3  or 8 elements. Each node is connected to three other nodes using a bi-directional data communication path. For example, node 102 is connected to node 104 through a bi-directional data communications path 110, node 102 is also connected node 106 through a bi-directional data communication path 114, and node 102 is connected to node 108 through a bi-directional data communication path 112. Note that node 104 has a binary address of 001 which differs from the binary address 000 of node 102 by only 1 bit. Also, node 108 has a binary address 100 which also differs from the binary address 000 of node 102 by 1 bit. Likewise, node 106 has an address of 011, which differs from the address of node 104 by only one bit. 
     In a hypercube having bi-directional data communication paths, such as the hypercube of FIG. 1, the number of paths through which a message must pass when going from one of the nodes to another of the nodes, is at most n paths, in an n-cube. For example, to send a message from node 102 to node 122 in FIG. 1, the message must pass through data communication path 110 to node 104, then through data communication path 114 to node 106, and then through data communication path 118 through node 122. 
     The present invention will first define a method of constructing a hypercube having unidirectional data communication paths, and then define a method of determining which data communication paths must be traversed to send a message from one node to another within a hypercube, including the hypercube thus defined. 
     The key disadvantage of the hypercube topology is the growth rate of the data communication path count and node degree as n increases. This growth rate, coupled with pin limitations on VLSI chips, continues to seriously limit the scalability of the hypercube topology to massively parallel systems. Additionally, the inherent bi-directional nature of the hypercube prevents it from being readily used with naturally unidirectional media, such as fiber-optic media. Most of the existing hypercube connected multi-processor systems use two physical data communication paths, to allow parallel transmission between two adjacent nodes of the hypercube. FIGS. 2 and 3 show a flowchart of the method of the present invention for defining the direction of unidirectional data communication paths within a hypercube. This method can be used when designing a hypercube. FIG. 3 can also be used within a node of an existing hypercube to program the direction of the data communication paths when such data paths can be switched from one direction to the other. 
     Referring now to FIGS. 2 and 3, after entry, block 202 determines the first or next node address within the hypercube that needs to have its data communication paths defined. Block 204 determines if all nodes have been processed, and if not, transfers to block 206. Block 206 calls FIG. 3 to determine the directions of the data communication paths from the node address. 
     In FIG. 3, block 302 determines the first or next bit position that needs to be processed. In a hypercube, there is one data communication path corresponding to each binary bit position of the address of the node. For example, in a 3-cube, there are three data communication paths connected to each node, and each node has a three bit binary address. 
     After determining the next bit position to be processed, block 302 goes to block 304 which determines if all bit positions have been processed, and if not, control transfers to block 306 which computes a sum, s, using the following equation: ##EQU1## In the above equation, i represents the bit position, and a represents the address of the node, where a x  is the bit value of bit position x, counting from the right, within the address a. After block 306 determines the value of the variable s, block 308 determines whether s is an odd number. If s is an odd number, block 308 transfers to block 310 which defines the data communication path for the edge as an incoming data communication path before returning to block 302 to check the next bit position. If the method of FIG. 3 is being performed within a node of a hypercube, block 310 programs the direction of the data communication path before returning to block 302. 
     If s is an even number, block 308 transfers to block 312 which defines the data communication path as an outgoing data communication path and then returns to block 302 to determine the next bit position. If the method of FIG. 3 is being performed within a node of a hypercube, block 312 programs the direction of the data communication path before returning to block 302. 
     Those skilled in the art will recognize that either odd or even values for s could be used to define either inbound or outbound data paths. 
     After all bit positions have been determined within the address for this node, block 302 returns to FIG. 2, block 202 which gets the next node address and computes the data communication paths for that node. After all nodes have been processed, block 204 returns to the caller of FIG. 2. 
     FIG. 4 shows a hypercube system having eight nodes or processors with directional paths as defined by the method of FIGS. 2 and 3. Referring now to FIG. 4, a hypercube system 402 contains eight identical nodes, typically represented by node 404 which has an address 110. The system of FIG. 4 is a 3-cube, therefore, each nodes connects to three other nodes through three data communication paths or edges. For example, node 404 has data communication paths 406, 408, and 410. Also, each of the nodes of the hypercube has a bi-directional data communication path which connects to a cube interface module 414, which in turn connects to an I/0 system processor 416 to allow the hypercube to store data and communicate with users of the system. The following is an example of computing the directions of the data communication paths 406, 408, and 410 for the node 404 of FIG. 4 using the formula from block 306 of FIG. 3: 
     For data communication path 410 (bit zero of the node address): ##EQU2## 
     since s is even, communication path 410 is outgoing. 
     For data communication path 406 (bit one of the node address): ##EQU3## 
     since s is odd, communication path 406 is incoming. 
     For data communication path 408 (bit two of the node address): ##EQU4## 
     since s is communication path 408 is outgoing. 
     FIG. 5 shows a block diagram of the electronics of node 404 of FIG. 4. Referring now to FIG. 5, the processor 404 contains a processing element 502 which is connected to other parts of the system over a system bus 504. Connected to the system bus 504 are four network interface electronic modules 530, 532, 534, and 536, which provide the interface to the data communication paths 406, 408, 410, and 412 respectively. The interface between the system bus 504 and the network interfaces 530, 532, and 534 is bi-directional, to allow the system bus 504 to send and receive status information, even though the interfaces 406, 408, and 410 are uni-directional. Also connected to the system bus 504 is memory 516 which contains an operating system 526 routing system software 530 and background process software 528. 
     The routing system software 530 will be described below with respect to FIG. 7 through 14. When the routing system software 530 determines that a message addressed to this node has arrived, it passes that message to the background process 528 which processes the message and may or may not return a reply message to the routing system 530. 
     FIG. 6 shows a block diagram of the I/O system processor 416 of FIG. 4. Referring now to FIG. 6, the I/O system processor 416 contains a processing element 602 which is connected to other elements of the system through a system bus 604. Also attached to the system bus 604 is a keyboard 606, a graphics display 60B, and a mouse interface 610 whioh are used to allow the I/0 system 416 to interface to a user of the computer system. A disk 612 is used to store software and data for the entire system. A network interface 614 is used to interface to the cube interface 414 which in turn interfaces to all of the processors within the hypercube. A memory 616 contains an operating system 626 and user interface software 628. The user interface software 628 is used to allow a user of the system to interact with the processors of the hypercube. 
     FIGS. 7-14 show a flowchart of the routing system software 530 (FIG. 5) which is used for routing messages between the processors of the hypercube shown in FIG. 4. This software runs in each processor to route a message from a processor to the next processor that the software determines is closer to the message destination. The software relies on information local to the processor. That is, it does not query other processors about possible routes, instead it determines the best route and sends the message along that route. As the message travels along the route to a destination, the message encounters the same software in each processor. This software uses the source and destination addresses of the processors and the distance pattern formed at each subsequent processor along the route to find the next data communication path necessary to reach the destination. 
     Referring now to FIGS. 7-14, block 702 determines whether a message has been received from one of the network interfaces 530, 532, or 534. If a message has not been received, block 702 loops back on itself until such time as a message is received. Block 702 also determines whether a message has been received from the background process to send to some other node within the hypercube. When a message is received, block 702 transfers to block 704 which calls the route message software of FIG. 8. The route message software of FIG. 8 determines which node to send the message to next, and it also determines whether the message is intended for this node. After returning from the route message software of FIG. 8, block 706 determines whether the message received is intended for this node. If the message is not intended for this node, block 706 transfers back to block 702 since the message has already been sent on by the route message software of FIG. 8. If the message has been sent to this node, block 706 transfers to block 708 which sends the message to the background process 528 for processing before returning to block 702 to receive the next message. 
     When block 704 calls FIG. 8, FIG. 8 is entered at block 802. Block 802 computes the value of a variable DIST as the node address of the node where the software is running, exclusive or-ed with the destination node address. Therefore, DIST is the Hamming distance between this node and the destination node. After computing the value of DIST, block 802 transfers to block 804 which determines whether there are any one bits within the variable DIST. If there are no one bits in DIST, then the message is being sent to this node, so block 804 transfers to block 806 which returns a flag showing that the message has arrived at its destination. If there is at least one 1 bit in DIST, block 804 transfers to block 808 which determines whether there is exactly one binary 1 bit in DIST. If there is exactly one 1 bit within DIST, block 804 transfers to block 81 which determines the corresponding data communication path for the bit. As discussed above with respect to FIG. 4, each data communication path connected to the node corresponds to one of the bit positions within the address of the node. Block 810 determines which bit is a one in DIST, and checks the corresponding path to determine whether that path is an outbound path. If that data communication path is outbound, then the message should be routed on that path so block 810 transfers to block B12 whioh sends the message on the data communication path corresponding to the one bit within DIST before returning to FIG. 7. 
     If the data communication path for the bit is not outbound, or if there is more than one 1 bit in DIST, control goes to block 814 which determines whether there is an odd number of dimensions in the cube. If the cube does have an odd number of dimensions, such as, for example, the 3-cube of FIG. 4, block 814 transfers to block 816 which determines whether there is only one inbound 1 path to the node. This test only checks the data communication path to or from the other nodes within the hypercube, and ignores the data communication path that leads to the I/O system 416 within the hypercube. If there is only one inbound 1 data communication path to the node, block 816 transfers to block 818 which determines whether the inbound data communication path corresponds to the n-1 path, where n is the dimension of the cube. For example, in the hypercube of FIG. 4, node 404, this test would determine whether the inbound path corresponds to the second path. If the inbound path does correspond to the n-1 path, block 818 transfers to block 820 which randomly selects an outbound path corresponding to a zero bit within DIST. After randomly selecting an outbound path, block 820 transfers to block 822 which sends the message on the data communication path selected. 
     If there is more than one inbound data communication path to the node, or if the inbound path is not the n-1 path, control transfers to FIG. 9 block 902. Block 902 determines whether the number of one bits within DIST is less than or equal to n/2, where n is the dimension of the cube. If this is true, block 902 transfers to block 904 which determines whether the n-1 data communication path is outbound. If this is also true, block 904 transfers to block 906 which determines whether the n-1 data communication path corresponds to a one bit within DIST, and if so, block 906 transfers to block 908 which sends the message on the n-1 data communication path. If any of the above tests are false, FIG. 9 transfers to FIG. 10 block 1002. Also, if the dimension of the cube is an even number, control also transfers to FIG. 10 block 1002. 
     Block 1002 creates a list of all the outbound data communication paths from the node which have a corresponding one bit in DIST. Block 1004 then determines whether any were found and if not, transfers to FIG. 12 block 1202. If some outbound data communication paths with corresponding one bits in DIST were found, block 1004 transfers to block 1006 which removes from the list all data communication paths within a pair of one bits in DIST. Pairs are defined by taking the bits within the address starting at the right end of the address and grouping the bits into pairs. Control then transfers to block 1008 which determines whether any data communication paths remain in the list and if not, control is transferred to FIG. 12 block 1202. If at least one data communication path does remain in the list, block 1008 transfers to block 1010 which sets the value of a variable C to the first remaining data communication path in the list. Transfers back to this block from block 1? 17 will get the next remaining data communication path from the list. Block 1012 then determines whether all data communication paths have been processed, and if all data communication paths have been processed, block 1012 transfers to FIG. 11 block 1102. If at least one data communication path remains to be processed, block 1012 transfers to block 1014 which sets the value of a variable pcount[C] equal to zero. Block 1016 then sets the value of a variable B to the first data communication path within the list which corresponds to a one bit within DIST. Transfers back to this block will get the next remaining data communication path within the list which corresponds to a one bit within DIST. Block 1017 determines if all the data communication paths have been processed, and if so, transfers to block 1010. If at least one path remains to be processed, block 1017 transfers to block 1018. Block 1018 then determines if the variable B represents the same data communication path as the variable C, and if they are equal, control transfers back to block 1016 to ignore this data communication path. If B is not equal to C, block 1018 transfers to block 1020 which inverts bit C within the node address to create a new destination address DISTC. Block 1022 then calls FIG. 3 to determine the data communication paths that will exist from the node represented by DISTC. After returning from FIG. 3, block 1024 determines whether data communication path B at the node represented by the address DISTC will be an outgoing data communication path and also whether it corresponds to a one bit within DISTC. If neither of these is true, block 1024 transfers to block 1016 to ignore this data communication path. If data communication path B is outgoing and corresponds to a one bit in DISTC, block 1024 transfers to block 1026 which increments the value of pcount[C] before transferring back to block 1016 to process the next data communication path. 
     After all data communication paths have been processed, block 1012 transfers to FIG. 11 block 1102. Block 1102 sets the value of a variable MAX to zero and the variable MAXI to -1. Block 1104 then sets the value of the variable C to the first or next remaining data communication path within the list created by blocks 1002 and 1006. Block 1106 then determines if all data communication paths have been processed and if not, transfers to block 1108 which determines whether the value of the variable MAX is less than the value of the pcount[C]. If MAX is less than pcount[C], block 1108 transfers to block 1110 which sets MAX equal to the value of pcount[C], and also sets MAXI equal to C before returning to block 1104. After all data communication paths have been processed, block 1106 transfers to block 1112 which determines whether MAX is greater than zero, that is, did any of the data communication paths satisfy the tests of block 1010 through block 1026. If MAX is not greater than zero, block 1112 transfers to FIG. 12 block 1202. If MAX is greater than zero, block 1112 transfers to block 1114 which sends the message on the data communication path defined by the variable MAXI before returning. 
     Block 1202 creates a list of all the outbound data communication paths from the node which have a corresponding zero bit in DIST. Block 1204 then determines whether any were found and if not, transfers to FIG. 14 block 1402. If some outbound data communication paths with corresponding zero bits in DIST were found, block 1204 transfers to block 1206 which removes from the list all data communication paths within a pair of one bits in DIST. Pairs are defined by taking the bits within the address starting at the right end of the address and grouping the bits into pairs. Control then transfers to block 1208 which determines whether any data communication paths remain in the list and if not, control is transferred to FIG. 14 block 1402. If at least one data communication path does remain in the list, block 1208 transfers to block 121? which sets the value of a variable C to the first remaining data communication path in the list. Transfers back to this block will get the next remaining data communication path within the list which corresponds to a one bit within DIST. Block 1212 then determines whether all data communication paths have been processed, and if all data communication paths have been processed, block 1212 transfers to FIG. 13 block 1302. If at least one data communication path remains to be processed, block 1212 transfers to block 1214 which sets the value of a variable pcount[C] equal to zero. Block 1216 then sets the value of a variable B to the first data communication path within the list which corresponds to a one bit within DIST. Transfers back to this block will get the next remaining data communication path within the list which corresponds to a one bit within DIST. Block 1217 then determines if all the paths have been processed and, if so, transfers back to block 1210. If paths remain to be processed, block 1217 transfers to block 1218. Block 121 then determines if the variable B represents the same data communication path as the variable C, and if they are equal, control transfers back to block 1216 to ignore this data communication path. If B is not equal to C, block 1218 transfers to block 1220 which inverts bit C within the node address to create new destination address DISTC. Block 1222 then calls FIG. 3 to determine the data communication paths that will exist from the node represented by DISTC. After returning from FIG. 3, block 1224 determines whether data communication path B at the node represented by the address DISTC will be an outgoing data communication path and also whether it corresponds to a one bit within DISTC. If neither of these is true, block 1224 transfers to block 1216 to ignore this data communication path. If data communication path B is outgoing and corresponds to a one bit in DISTC, block 1224 transfers to block 1226 which increments the value of pcount[C] before transferring back to block 1210 to process the next data communication path. 
     After all data communication paths have been processed, block 212 transfers to FIG. 13 block 1302. Block 1302 sets the value of a variable MAX to zero and the variable MAXI to -1. Block 1304 then sets the value of the variable C to the first or next remaining data communication path within the list created by blocks 1202 and 1206. Block 1306 then determines if all data communication paths have been processed and if not, transfers to block 1308 which determines whether the value of the variable MAX is less than the value of pcount[C]. If MAX is less than pcount[C], block 1308 transfers to block 1310 which sets MAX equal to the value of pcount[C], and also sets MAXI equal to C before returning to block 1304. After all data communication paths have been processed, block 1306 transfers to block 1312 Which determines whether MAX is greater than zero, that is, did any of the data communication paths satisfy the tests of block 1210 through block 1226. If MAX is not greater than zero, block 1312 transfers to FIG. 14 block 1402. If MAX is greater than zero, block 1312 transfers to block 1314 which sends the message on the data communication path defined by the variable MAXI before returning. 
     If none of the other tests defined in FIGS. 8 through 12 were successful in selecting a data communication path, control goes to block 1402 which selects a random pair of one bits within DIST. Block 1404 then sends the message on the outbound path of the selected data communication pair of paths. 
     Having thus described a presently preferred embodiment of the present invention, it will now be appreciated that the aspects of the invention have been fully achieved, and it will be understood by those skilled in the art that many changes in construction and circuitry and widely differing embodiments and applications of the invention will suggest themselves without departing from the spirit and scope of the present invention. The disclosures and the description herein are intended to be illustrative and are not in any sense limiting of the invention, more preferably defined in scope by the following claims.