Multistage interconnect network combines back channel replies received from destinations into a single result and transmits to the source
View Patent ↗A multistage interconnect network (MIN) capable of supporting massive parallel processing, including point-to-point and multicast communications between processor modules (PMs) which are connected to the input and output ports of the network. The network is built using interconnected switch nodes arranged in 2 ┌log b N┐ stages, wherein b is the number of switch node input/output ports, N is the number of network input/output ports and ┌log b N┐ indicates a ceiling function providing the smallest integer not less than log b N. The additional stages provide additional paths between network input ports and network output ports, thereby enhancing fault tolerance and lessening contention.
1. A multistage interconnect network comprising:
(a) a plurality of switch nodes connected together, each of the switch nodes comprising a first plurality of input ports selectively connectable to a second plurality of output ports, the multistage interconnect network comprising more than ┌log b N┐ stages of switch nodes, wherein b is a total number of switch node input/output port pairs, N is a total number of network input/output port pairs, and ┌log b N┐ indicates a ceiling function providing the smallest integer not less than log b N, the stages thereby providing a plurality of paths between any network input port and network output port to enhance fault tolerance and lessen contention;
(b) the multistage interconnect network including forward channel and back channel signal paths between the switch nodes;
(c) the multistage interconnect network capable of multicast transmitting forward channel messages from a source connected to the multistage interconnect network to one or more destinations connected to the multistage interconnect network;
(d) the multistage interconnect network capable of combining back channel replies received from the destinations into a single result, wherein the result is transmitted on the back channel to the source.
2. The system of claim 1 wherein the multistage interconnect network steers a multicast request for a supercluster to a bounce back point within the network, wherein all multicast requests to the supercluster use the same bounce back point.
3. The system of claim 2 wherein the multistage interconnect network steers a multicast request from one supercluster to a destination supercluster through a bounce back point for the destination supercluster.
4. The system of claim 1 wherein the multistage interconnect network permits only one multicast request at a time within a supercluster, thereby preventing deadlock between competing multicast requests.
5. A method of operating a multistage interconnect network comprising:
(a) multicast transmitting forward channel messages from a source connected to the multistage interconnect network to one or more destinations connected to the multistage interconnect network, wherein the multistage interconnect network comprises a plurality of switch nodes connected together, the multistage interconnect network including forward channel and back channel signal paths between the switch nodes, each of the switch nodes comprising a first plurality of input ports selectively connectable to a second plurality of output ports, the multistage interconnect network comprising more than ┌log b N┐ stages of switch nodes, wherein b is a total number of switch node input/output port pairs, N is a total number of network input/output port pairs, and ┌log b N┐ indicates a ceiling function providing the smallest integer not less than log b N the stages thereby providing a plurality of paths between any network input port and network output port to enhance fault tolerance and lessen contention; and
(b) combining back channel replies received from the destinations into a single result in the multistage interconnect network, wherein the result is transmitted on the back channel to the source.
6. The method of claim 5 further comprising steering a multicast request for a supercluster to a bounce back point within the multistage interconnect network, wherein all multicast requests to the supercluster use the same bounce back point.
7. The method of claim 6 further comprising steering a multicast request from one supercluster to a destination supercluster through a bounce back point for the destination supercluster within the multistage interconnect network.
8. The method of claim 6 further comprising permitting only one multicast request at a time within a supercluster, thereby preventing deadlock between competing multicast requests.
9. A system for transmitting messages, comprising:
(a) a plurality of switch nodes connected together in a multistage interconnect network using forward channel and back channel signal paths therebetween; and
(b) means for multicast transmitting forward channel messages from a source connected to the multistage interconnect network to one or more destinations connected to the multistage interconnect network; and
(c) means for combining back channel replies received from the destinations into a single result, wherein the result is transmitted on the back channel to the source.
10. The system of claim 9 further comprising means for steering a multicast request for a supercluster to a bounce back point within the network, wherein all multicast requests to the supercluster use the same bounce back point.
11. The system of claim 10 further comprising means for steering a multicast request from one supercluster to a destination supercluster through a bounce back point for the destination supercluster.
12. The system of claim 10 further comprising means for permitting only one multicast request at a time within a supercluster, thereby preventing deadlock between competing multicast requests.