Scalable processor to processor and processor-to-I/O interconnection network and method for parallel processing arrays

Claim 2

A multi-stage interconnect network (MIN) for a parallel processor array comprising: first, second and third switching stages for forming routing paths between processor elements (PEs) of the parallel processor array, each stage resolving one or more bits of a data routing header; and address bit duplicating means for duplicating bits resolved in a first stage such that the same bits are again resolved in a later stage to balance data routing loading; wherein: each PE is identified as belonging to a cluster of a plurality of PEs; each cluster is identified as belonging to one of a plurality of PE circuit boards; and said multi-stage interconnect network is divided into first, second, third and fourth resolving stages for resolving a plurality of route-requesting bits identifying each target PE, the second resolving stage being implemented in said second switching stage for revolving route requests according to the PE board on which the target PE resides, the fourth resolving stage being implemented in said each cluster of PEs for resolving the bits of a route requesting signal according to the location of the target PE within a specified PE cluster, and the first and third resolving stages being implemented in said first and third switching stages respectively for resolving the cluster number of the target PE.

Claim 3

The network of claim 1 wherein resolution of bits of the data routing header involves a delay in said first and second switching stages, and said route-requesting signal includes first and second groups of rest bits respectively interposed after the stage-1 resolving bits and after the stage-2 resolving bits for allowing the network to stabilize from effects of the delay in resolving stage-1 and the stage-2 bits in said first and second switching stages.

Claim 4

A global router network for a massively parallel array of processing elements, the routing network comprising a plurality of data-routing stages, wherein each of said data-routing stages comprises: a route requesting input wire (RRW-x) for receiving a route-requesting header signal; a pipeline latch (612) having a data input terminal (D) and a data output terminal (Q); a first tristate buffer (611) for selectively coupling the route request input wire (RRW-x) to the data input terminal of the pipeline latch (612); a switching matrix (615) having a router header-in line (621x), horizontal data input lines (650x), vertical output lines (654Y) and switching cells (620) for selectively coupling any one of said horizontal input lines (650x) to one of the vertical output lines (654Y); a second tristate buffer (652) for selectively coupling the output terminal (Q) of the pipeline latch (612) to said horizontal input line (650x) of the switching matrix (615) during a forward messagingmode; a third tristate buffer (657) for selectively coupling said horizontal data line (650x) to the data input terminal (D) of the pipeline latch (612) during a reverse messaging mode; and a fourth tristate buffer (658) for selectively coupling the output terminal (Q) of the pipeline latch (612) to the route requesting wire (RRW-x) during the reverse messaging mode.

Claim 5

A global router network for a massively parallel array of processing elements, the routing network comprising a plurality of data-routing stages, wherein each of said data-routing stages comprises: a route requesting input wire (RRW-x) for receiving a route-requesting header signal; a pipeline latch (612) having a data input terminal (D) and a data output terminal (Q); a first tristate buffer (611) for selectively coupling the route request input wire (RRW-x) to the data input terminal of the pipeline latch (612); a switching matrix (615) having a router header-in line (621x), horizontal data input lines (650x), vertical output lines (654Y) and switching cells (620) for selectively coupling any one of said horizontal input lines (650x) to one of the vertical output lines (654Y); a second tristate buffer (652) for selectively coupling the output terminal (Q) of the pipeline latch (612) to said horizontal input line (650x) of the switching matrix (615) during a forward messagingmode; a third tristate buffer (657) for selectively coupling said horizontal data line (650x) to the data input terminal (D) of the pipeline latch (612) during a reverse messaging mode; and a fourth tristate buffer (658) for selectively coupling the output terminal (Q) of the pipeline latch (612) to the route requesting wire (RRW-x) during the reverse messaging mode.

Claim 6

The interconnect network of claim 3 wherein each switching cell (620) comprises: a route selecting switch (623) for selectively connecting its router header input line (621) either through a single inverter (624) or through a noninverting circuit (622, 624) to a horizontal output wire (625); a wire-group request latch (630) having a request input terminal (D) and a request output terminal (Q); gating means (629) for coupling a route requesting bit on the horizontal output line (625) to the request input terminal of the wire-group request latch (630 if the wire-group request latch has not been activated by a previous request bit, and for preventing further bits from entering the wire-group request latch if it has already been activated; and request granting means (631, 632) for receiving a request input signal (631a) from the wire-group request latch and granting said request by connecting (631c) a horizontal data wire (650) to a corresponding vertical data wire (641) if a vertical messaging wire (641) has not already been granted to another route requesting signal.

Claim 9

A method as in claim 5, further comprising returning signals over said established data carrying routes rom the set of target PEs to the set of source PEs to indicate whether a correct set of routes is established in said interconnection network.

Claim 10

A method as in claim 6 wherein each of the returning signals indicating a correct route is included in a reverse acknowledge signal in accordance with a route close protocol.

Claim 11

A method as in claim 6 wherein each of the returning signals indicating a correct route is included in a reverse message body signal in accordance with a route reverse protocol.

Claim 12

A method as in claim 5, further comprising the steps of: generating toggle bits respectively associated with said route requesting signals for propagating through said interconnection network, said toggle bits having a particular value; and detecting the values of said toggle bits after propagation through said interconnection network, an error condition being indicated in the event that one or more of said toggle bits is not equal to said particular value.

Claim 13

A method as in claim 5, wherein said route requesting signals include respective PE numbers, further comprising, for each of said PEs receiving a PE number through a route requesting signal, in parallel, the steps of: comparing said received PE number with a PE identification number preassigned to said each PE to obtain a match signal indicative of whether said received PE number and said preassigned PE identification number match; and performing an AND operation with said match signal and the protocol bit received by said each PE to determine whether a valid data routing path is established.

Claim 14

In a parallel processor having an array of processor elements, an interconnection network for indirectly routing data from one set of the processor elements to another set of the processor elements comprising: a first bidirectional latch having a set of first ports and a set of second ports; first bidirectional routing path segments respectively connected to the first ports of the first latch, the first routing path segments including a first switch stage responsive to header data from the processor elements for configuring the first routing path segments; second bidirectional routing path segments respectively connected to the second ports of the first latch, the second routing path segments including a second switch stage responsive to header data from the first switch stage for configuring the second routing path segments; a second bidirectional latch having a set of first ports and a set of second ports, the first ports thereof being connected to the processor elements and the second ports thereof being respectively connected to the first routing path segments; a third bidirectional latch having a set of first ports and a set of second ports, the first ports thereof being respectively connected to the second routing path segments, and the second ports thereof being connected to the processor elements; third and fourth bidirectional routing path segments, wherein: the first ports of the second bidirectional latch are respectively connected to the processor elements by the third bidirectional routing path segments; and the second ports of the third bidirectional latch are respectively connected to the processor elements by the fourth bidirectional routing path segments; and means for operating the first, second and third latches and the processor elements to transfer data between one set of the processor elements and another set of the processor elements in either direction along routing paths comprising the configured first, second, third and fourth routing path segments.

Claim 15

In a parallel processor having an array of processor elements, an interconnection network for indirectly routing data from one set of the processor elements to another set of the processor elements comprising: a first bidirectional latch having a set of first ports and a set of second ports; first bidirectional routing path segments respectively connected to the first ports of the first latch, the first routing path segments including a first switch stage responsive to header data from the processor elements for configuring the first routing path segments; second bidirectional routing path segments respectively connected to the second ports of the first latch, the second routing path segments including a second switch stage responsive to header data from the first switch stage for configuring the second routing path segments; a second bidirectional latch having a set of first ports and a set of second ports, the first ports thereof being connected to the processor elements and the second ports thereof being respectively connected to the first routing path segments; a third bidirectional latch having a set of first ports and a set of second ports, the first ports thereof being respectively connected to the second routing path segments, and the second ports thereof being connected to the processor elements; third and fourth bidirectional routing path segments, wherein: the first ports of the second bidirectional latch are respectively connected to the processor elements by the third bidirectional routing path segments; and the second ports of the third bidirectional latch are respectively connected to the processor elements by the fourth bidirectional routing path segments; and means for operating the first, second and third latches and the processor elements to transfer data between one set of the processor elements and another set of the processor elements in either direction along routing paths comprising the configured first, second, third and fourth routing path segments.