Multistage network with distributed pipelined control
First Claim
1. A multistage communication network with distributed pipeline control comprising:
- a first network comprising a first array of N×
M nodes jT, j=1 to N×
M, said first array having a topology defining N input ports and M output ports, said output ports being connected to corresponding output buses and each of said input ports being selectively connectable to any one of said output buses via said output ports;
each of said nodes jT comprising a transport node of one or more crossbar switches having input lines, output lines and at least one enable line, said input and output lines being connected to adjacent nodes in said first array;
a second network comprising a plurality of subnetworks or arrays Vi, i=(n) modulo Q, said second subnetworks or arrays having N×
M nodes jCi, said second subnetworks or arrays having the same topology as said first network; and
said nodes Jci comprising at least two control nodes V0 and V1 connected to said enable line and controlling transmission of a packet of data through said nodes jT during at least two different time slots, said control nodes each having input and output disable lines and input and output control lines connected to adjacent nodes in said network, whereby a collision occurring in one of said nodes jT during one time slot will not affect a message packet at said node during another time slot.
1 Assignment
0 Petitions
Accused Products
Abstract
A multistage network having a combination of low latency and probability of blockage has particular application in the interconnection of parallel computers. A technique minimizes the blockage of the multistage network, thereby minimizing the number of times that a message requires retransmission. The technique also permits higher utilization of data transport paths in the multistage network. The network has no buffers, so a message either succeeds in getting through, or, if blocked, leads to the notification of the originator that transmission was unsuccessful and that another attempt is required. Multiple return paths, used for example in a time-division-multiplexed (TDM) fashion, are provided in the network. This substantially reduces the amount of blocking in the network, and thus the number of times that a message requires retransmission. In addition, networks associated with the backward paths are used as a means of controlling the data transport. This permits the data transport function to be substantially simplified. It also permits higher utilization of the data transport paths, as the control function can be pipelined.
33 Citations
9 Claims
-
1. A multistage communication network with distributed pipeline control comprising:
-
a first network comprising a first array of N×
M nodes jT, j=1 to N×
M, said first array having a topology defining N input ports and M output ports, said output ports being connected to corresponding output buses and each of said input ports being selectively connectable to any one of said output buses via said output ports;each of said nodes jT comprising a transport node of one or more crossbar switches having input lines, output lines and at least one enable line, said input and output lines being connected to adjacent nodes in said first array; a second network comprising a plurality of subnetworks or arrays Vi, i=(n) modulo Q, said second subnetworks or arrays having N×
M nodes jCi, said second subnetworks or arrays having the same topology as said first network; andsaid nodes Jci comprising at least two control nodes V0 and V1 connected to said enable line and controlling transmission of a packet of data through said nodes jT during at least two different time slots, said control nodes each having input and output disable lines and input and output control lines connected to adjacent nodes in said network, whereby a collision occurring in one of said nodes jT during one time slot will not affect a message packet at said node during another time slot. - View Dependent Claims (2, 3)
-
- 4. In a multistage communication network comprising a bufferless delta transport network having a plurality of nodes, said network selectively connecting a plurality of originating input ports to a plurality of output ports, the improvement of the provision of multiple backward paths from each intermediate node in said delta network, said backward paths defining paths from a blocked node to an originating input port whereby blocking in said communication network is reduced due to the use of said multiple backward paths.
-
8. A method of connecting a plurality of inputs to a plurality of outputs in a multistage communication network comprising the steps of:
-
providing a first bufferless transport network for making selective connections between said input and said outputs; providing a second control network having a topology identical to said first network; and establishing multiple backward paths between selective connections of said outputs and said inputs whereby blocking in said communication network is reduced due to said multiple backward paths. - View Dependent Claims (9)
-
Specification