Speculative forwarding in a high-radix router

• US 7,830,905 B2
• Filed: 04/21/2008
• Issued: 11/09/2010
• Est. Priority Date: 04/20/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Marquardt, Kelly, Bethard, Roger A., Scott, Steven L., Hubbard, Gregory, Abts, Dennis C.
• Primary Examiner(s): Vu; Thong H
• Application Number:
  US12/107,036
• Publication Number:
  US 20090028172A1
• Time in Patent Office: 932 Days
• Field of Search: 370/386, 370/355, 370/535, 710/52
• US Class Current: 370/419
• CPC Class Codes: G06F 15/17362 hierarchical topologies
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/15 Interconnection of switching modules

Abstract

A system and method for speculative forwarding of packets received by a router, wherein each packet includes phits and wherein one or more phits include a cyclic redundancy code (CRC). A packet is received and phits of the packet are forwarded to router logic. A cyclic redundancy code for the packet is calculated and compared to the packet'"'"'s cyclic redundancy code. An error is generated if the cyclic redundancy codes don'"'"'t match. If the cyclic redundancy codes don'"'"'t match, a phit of the packet is modified to reflect the error, the CRC is corrected and the corrected CRC is forwarded to the router logic along with the phit reflecting the CRC error. At the router logic, a check is made to see if the packet is still within the router logic. If the packet is still within the router logic and there was a CRC error, the packet is discarded. If, however, the packet is no longer within the router logic and there was a CRC error, the packet is modified so that the next router discards the packet.

Claims

1. A router, comprising:

a plurality of subswitches arranged in a n×

p matrix, wherein each subswitch includes n inputs and p outputs, wherein both n and p are greater than one;

a plurality of input ports;

local control blocks connected to the plurality of input buffers, wherein the local control blocks include means for speculative forwarding of phits received by the router, wherein speculative forwarding comprises forwarding before a cyclic redundancy code has been verified;

a plurality of output ports, wherein each output port includes a multiplexer and an arbiter for selecting data to be switched onto the output port via the multiplexer;

a plurality of row busses, wherein each row bus receives data from one of the plurality of input ports and distributes the data to two or more of the plurality of subswitches; and

a plurality of column channels, wherein each column channel connects one of the outputs of one of the subswitches to an input of one of the multiplexers;

wherein each row bus includes a route selector, wherein the route selector includes a routing table which selects an output port for each packet and which routes the packet through one of the row busses to the selected output port.

2. The router of claim 1, wherein n equals p.

3. The router of claim 1, wherein the speculative forwarding means includes means for discarding packets with incorrect cyclic redundancy codes.

4. A router, comprising:

a plurality of subswitches arranged in a n×

p matrix, wherein each subswitch includes n inputs and p outputs, wherein both n and p are greater than one;

a plurality of input ports;

local control blocks connected to the plurality of input buffers, wherein the local control blocks include means for speculative forwarding of phits received by the router, wherein speculative forwarding comprises forwarding before a cyclic redundancy code has been verified;

a plurality of output ports, wherein each output port includes a multiplexer and an arbiter for selecting data to be switched onto the output port via the multiplexer;

distribution means, connected to the input ports and the subswitches, for receiving data from one of the plurality of input ports and for distributing the data to two or more of the plurality of subswitches; and

a plurality of column channels, wherein each column channel connects one of the outputs of one of the subswitches to an input of one of the multiplexers;

wherein the distribution means includes a route selector, wherein the route selector includes a routing table which selects an output port for each packet and which routes the packet to the selected output port.

5. The router of claim 4, wherein n equals p.

6. The router of claim 4, wherein the speculative forwarding means includes means for discarding packets with incorrect cyclic redundancy codes.

7. A computer system, comprising:

a plurality of processor nodes;

a plurality of first routers; and

a plurality of second routers;

wherein each first router is connected to a processor node and to two or more second routers and wherein each first router includes;

a plurality of subswitches arranged in a n×

p matrix, wherein each sub switch includes p inputs and p outputs;

a plurality of input ports;

local control blocks connected to the plurality of input buffers, wherein the local control blocks include means for speculative forwarding of phits received by the router, wherein speculative forwarding comprises forwarding before a cyclic redundancy code has been verified;

a plurality of output ports, wherein each output port includes a multiplexer and an arbiter for selecting data to be switched onto the output port via the multiplexer;

a plurality of row busses, wherein each row bus receives data from one of the plurality of input ports and distributes the data to two or more of the plurality of subswitches; and

a plurality of column channels, wherein each column channel connects one of the outputs of one of the subswitches to an input of one of the multiplexers;

wherein each row bus includes a route selector, wherein the route selector includes a routing table which selects an output port for each packet and which routes the packet through one of the row busses to the selected output port.

8. The computer system of claim 7, wherein n equals p.

9. The computer system of claim 7, wherein the speculative forwarding means includes means for discarding packets with incorrect cyclic redundancy codes.

10. A method of speculative forwarding of packets received by a router, wherein each packet includes phits and wherein one or more phits include a cyclic redundancy code (CRC), the method comprising:

receiving a packet and forwarding phits of the packet to router logic;

calculating a cyclic redundancy code;

comparing the calculated cyclic redundancy code to the packet'"'"'s cyclic redundancy code and generating an error if the cyclic redundancy codes don'"'"'t match;

if the cyclic redundancy codes don'"'"'t match, modifying a phit of the packet to reflect the error, correcting the CRC and forwarding the corrected CRC with the phit reflecting the error to the router logic;

at the router logic, determining if the packet is still within the router logic;

if the packet is still within the router logic and there was a CRC error, discarding the packet; and

if the packet is no longer within the router logic and there was a CRC error, modifying the packet so that the next router discards the packet.

11. The method of claim 10, wherein comparing the calculated cyclic redundancy code to the packet'"'"'s cyclic redundancy code includes determining if the packet has a length greater than the maximum packet length.

12. A method of speculative forwarding of packets received by a router, wherein each packet includes phits and wherein one or more phits include a cyclic redundancy code (CRC), the method comprising:

receiving a packet comprising a plurality of phits;

calculating a cyclic redundancy code for the packet;

comparing the calculated cyclic redundancy code to the packet'"'"'s cyclic redundancy code; and

if the cyclic redundancy codes don'"'"'t match, discarding the packet in either the receiving router or a subsequent router.

13. A router, comprising:

an input operable to receive a packet comprising a plurality of phits;

a routing element operable to forward a packet before checking a cyclic redundancy code for the packet; and

an error handler operable to;

calculate a cyclic redundancy code for the packet;

compare the calculated cyclic redundancy code to the packet'"'"'s cyclic redundancy code; and

if the cyclic redundancy codes don'"'"'t match, cause the packet to be discarded in either the receiving router or a subsequent router.