1. Field of the Invention
The invention relates to data-processing systems, and more particularly, to a communication mechanism for use in a high-performance, parallel-processing system.
2. Description of the Prior Art
U.S. Pat. No. 5,113,523 describes a parallel processor comprised of a plurality of processing nodes, each node including a processor and a memory. Each processor includes means for executing instructions, logic connected to the memory for interfacing the processor with the memory and an internode communication mechanism. The internode communication mechanism connects the nodes to form a first array of order n having a hypercube topology. A second array of order n having nodes connected together in a hypercube topology is interconnected with the first array to form an order n+1 array. The order n+1 array is made up of the first and second arrays of order n, such that a parallel processor system may be structured with any number of processors that is a power of two. A set of I/O processors are connected to the nodes of the arrays by means of I/O channels. The internode communication comprises a serial data channel driven by a clock that is common to all of the nodes.
The above-referenced U.S. Pat. No. 5,367,636, describes a fixed-routing communication system in which each of the processors in the network described in U.S. Pat. No. 5,113,523 is assigned a unique processor identification (ID). The processor IDs of two processors connected to each other through port number n, vary only in the nth bit. A plurality of input ports and a plurality of output ports are provided at each node. Control means at one of the input ports of the node receives address packets related to a current message from an output port of another of the nodes. A data bus connects the input and output ports of the node together such that a message received on any one input port is routed to any other output port. A compare logic compares a node address in a first address packet with the processor ID of the node to determine the bit position of the first difference between the node address in the first address packet and the processor ID of the node. The compare logic includes means for activating for transmission of the message packet placed on the data bus by the input port, the one of the plurality of output ports whose port number corresponds to the bit position of the first difference, starting at bit n+1, where n is the number of the port on which the message was received.
In the fixed routing scheme described in the above-referenced U.S. Pat. No. 5,367,636, a message from a given source to a given destination can take exactly one routing path, unless it is forwarded, cutting through intermediate nodes and blocking on busy channels until the path is established. The path taken is the dimension-order minimum-length path. While this scheme is deadlock-free, it will not reroute messages around blocked or faulty nodes.
It is desirable to provide a new communication system using reliable messaging mechanisms, whereby both the sender and receiver of a message can know quickly whether the message was delivered reliably, and the receiver may deliver status information back to the sender before an established path is broken.
It is also desirable that the communication system be able to route messages around blocked or faulty nodes and hot spots in a parallel processor, by implementing unique adaptive routing methods that make use of the reliable messaging mechanisms.
It is also desirable that the communication mechanism provide a more efficient utilization of the bandwidth of a hypercube communication network, by duplicating (folding) network links or otherwise unused communications ports, and by avoiding extended network blockages through the adaptive routing methods.