Patent Publication Number: US-8990616-B2

Title: Final faulty core recovery mechanisms for a two-dimensional network on a processor array

Description:
This invention was made with Government support under HR0011-09-C-0002 awarded by Defense Advanced Research Projects Agency (DARPA). The Government has certain rights in this invention. 
    
    
     BACKGROUND 
     Embodiments of the invention relate to redundant routing systems, and in particular, faulty recovery mechanisms for a two-dimensional (2-D) network on a processor array. 
     A processor array contains and manages multiple processing elements. There are different types of processing elements, such as microprocessors, microcontrollers, digital signal processors, graphics processors, reconfigurable processors, fixed function units, hardware accelerators, neurosynaptic neural core circuits, etc. A processor array may include different types of processing elements. The processing elements may be arranged in a one-dimensional array, a two-dimensional array, or a three-dimensional array, or a ring or torus topology. The processing elements are interconnected by a routing system including buses and switches. Packets are communicated between processing elements using the routing system. 
     BRIEF SUMMARY 
     Embodiments of the invention relate to faulty recovery mechanisms for a two-dimensional (2-D) network on a processor array. One embodiment comprises a processor array including multiple processors core circuits, and a redundant routing system for routing packets between the core circuits. The redundant routing system comprises multiple switches, wherein each switch corresponds to one or more core circuits of the processor array. The redundant routing system further comprises multiple data paths interconnecting the switches, and a controller for selecting one or more data paths. Each selected data path is used to bypass at least one component failure of the processor array. 
     Another embodiment comprises routing packets between multiple processors core circuits of a processor array via a redundant routing system including multiple switches and multiple data paths, and selecting one or more data paths. The selected data paths are used to bypass at least one component failure of the processor array. 
     These and other features, aspects and advantages of the present invention will become understood with reference to the following description, appended claims and accompanying figures. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  illustrates a processor array, in accordance with an embodiment of the invention; 
         FIG. 2  illustrates an example configuration for a switch in  FIG. 1 , in accordance with an embodiment of the invention; 
         FIG. 3  illustrates example component failures of a processor array, in accordance with an embodiment of the invention; 
         FIG. 4  illustrates an example redundant routing system for a processor array, wherein the routing system includes redundant data paths and a redundant column of redundant core circuits, in accordance with an embodiment of the invention; 
         FIG. 5  illustrates an example configuration for a switch in  FIG. 4 , in accordance with an embodiment of the invention; 
         FIG. 6  illustrates a static multiplexer, in accordance with an embodiment of the invention; 
         FIG. 7  illustrates an example redundant routing system for a processor array, wherein the routing system includes diagonal data paths and a redundant column of redundant core circuits, in accordance with an embodiment of the invention; 
         FIG. 8  illustrates an example configuration of a switch in  FIG. 7 , in accordance with an embodiment of the invention; 
         FIG. 9  illustrates another example configuration of a switch in  FIG. 7 , in accordance with an embodiment of the invention; 
         FIG. 10  illustrates an example redundant routing system for a processor array, wherein the routing system includes diagonal data paths and a redundant router column of redundant routers, in accordance with an embodiment of the invention; 
         FIG. 11  illustrates an example redundant routing system for a processor array, wherein the routing system is organized into blocks, in accordance with an embodiment of the invention; 
         FIG. 12A  illustrates an example redundant routing system for a processor array, wherein the routing system includes redundant data paths and a redundant row of redundant core circuits, in accordance with an embodiment of the invention; 
         FIG. 12B  illustrates an example configuration of a switch in  FIG. 12A , in accordance with an embodiment of the invention; 
         FIG. 13  illustrates an example redundant routing system for a processor array, wherein the routing system includes diagonal data paths and a redundant row of redundant core circuits  10 R, in accordance with an embodiment of the invention; 
         FIG. 14  illustrates an example configuration of a switch in  FIG. 13 , in accordance with an embodiment of the invention; 
         FIG. 15  illustrates an example redundant routing system for a processor array, wherein the routing system includes a redundant column of redundant core circuits and a redundant row of redundant core circuits, in accordance with an embodiment of the invention; 
         FIG. 16  illustrates an example configuration of a switch  20  in  FIG. 15 , in accordance with an embodiment of the invention; 
         FIG. 17A  illustrates an example redundant routing system for a processor array, wherein the routing system includes diagonal data paths, a redundant column of redundant core circuits, and a redundant row of redundant core circuits, in accordance with an embodiment of the invention; 
         FIG. 17B  illustrates an example configuration of a switch in  FIG. 17A , in accordance with an embodiment of the invention; 
         FIG. 18  illustrates an example redundant routing system for a processor array, wherein the redundant routing system bypasses a component failure using redundant data paths, in accordance with an embodiment of the invention; 
         FIG. 19  illustrates a routing system for a three-dimensional (3-D) processor array, wherein the routing system includes 3-D switches, in accordance with an embodiment of the invention; 
         FIG. 20  illustrates an example configuration of a 3-D switch in  FIG. 19 , in accordance with an embodiment of the invention; 
         FIG. 21A  illustrates an example redundant routing system for a 3-D processor array, wherein the routing system includes redundant data paths and a redundant plane, in accordance with an embodiment of the invention; 
         FIG. 21B  illustrates an example redundant routing system for a 3-D processor array, wherein the routing system includes diagonal data paths and a redundant plane, in accordance with an embodiment of the invention; 
         FIG. 22  illustrates an example redundant routing system for a 3-D processor array, wherein the routing system includes only redundant data paths, in accordance with an embodiment of the invention; 
         FIG. 23  illustrates an example processor array including multiple switches, wherein each switch is a communication interface to one or more core circuits, in accordance with an embodiment of the invention; 
         FIG. 24  illustrates an example processor array including multiple switches, wherein each switch has multiple sets of Local router channels, in accordance with an embodiment of the invention; 
         FIG. 25  illustrates an example configuration of a switch in  FIG. 24 , in accordance with an embodiment of the invention; and 
         FIG. 26  is a high level block diagram showing an information processing circuit useful for implementing one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     Embodiments of the invention relate to faulty recovery mechanisms for a two-dimensional (2-D) network on a processor array. One embodiment comprises a processor array including multiple processors core circuits, and a redundant routing system for routing packets between the core circuits. The redundant routing system comprises multiple switches, wherein each switch corresponds to a core circuit of the processor array. The redundant routing system further comprises multiple data paths interconnecting the switches, and a controller for selecting one or more data paths. Each selected data path is used to bypass at least one component failure of the processor array to facilitate full operation of the processor array. 
     Another embodiment comprises routing packets between multiple processors core circuits of a processor array via a redundant routing system including multiple switches and multiple data paths, and selecting one or more data paths. The selected data paths are used to bypass at least one component failure of the processor array. 
       FIG. 1  illustrates a processor array  50 , in accordance with an embodiment of the invention. The array  50  comprises multiple processor core circuits  10 . Each processor core circuit  10  is a processing element for executing and generating data (e.g., instructions). Each processor core circuit  10  has a corresponding physical label. For example, as shown in  FIG. 1 , some of the core circuits  10  of the array  50  have physical labels that identify said core circuits  10  as core circuits C 00 , C 01 , C 02 , C 03 , C 10 , C 11 , C 12 , C 13 , C 20 , C 21 , C 22 , C 23 , C 30 , C 31 , C 32 , and C 33 . 
     The core circuits  10  may be organized into a one-dimensional (1-D) array, a two-dimensional (2-D) array, a three-dimensional (3-D) array, or a ring or torus topology. In one embodiment, the core circuits  10  are arranged into a two-dimensional array including multiple rows  40  and multiple columns  45  ( FIG. 3 ). For example, the array  50  may be an M×N array, wherein M and N are integers greater than zero. 
     The array  50  further comprises a routing system  15  for routing packets between the core circuits  10 . The routing system  15  includes multiple switches (i.e., routers)  20  and multiple data paths (i.e., buses)  30 . Each switch  20  corresponds to one or more core circuits  10 . 
     For example, as shown in  FIG. 1 , the routing system  15  includes switches S 00 , S 01 , S 02 , S 03 , S 10 , S 11 , S 12 , S 13 , S 20 , S 21 , S 22 , S 23 , S 30 , S 31 , S 32 , and S 33 . Each switch  20  in  FIG. 1  corresponds to one core circuit  10 . Switches S 00 , S 01 , S 02 , S 03 , S 10 , S 11 , S 12 , S 13 , S 20 , S 21 , S 22 , S 23 , S 30 , S 31 , S 32 , and S 33  correspond to core circuits C 00 , C 01 , C 02 , C 03 , C 10 , C 11 , C 12 , C 13 , C 20 , C 21 , C 22 , C 23 , C 30 , C 31 , C 32 , and C 33 , respectively. 
     Each switch  20  is interconnected with a corresponding core circuit  10  via at least one data path  30 . Each switch  20  is further interconnected with at least one adjacent neighboring switch  20  via at least one data path  30 . For example, as shown in  FIG. 1 , switch S 00  is interconnected with corresponding core circuit C 00 , and adjacent neighboring switches S 01  and S 10 . As another example, switch S 21  is interconnected with corresponding core circuit C 21 , and adjacent neighboring switches S 11 , S 20 , S 22 , and S 31 . 
     Each core circuit  10  utilizes a corresponding switch  20  to pass along packets including information in the eastbound, westbound, northbound, or southbound direction. For example, a packet generated by core circuit C 00  and targeting core circuit C 33  may traverse switches S 00 , S 01 , S 02 , and S 03  n the eastbound direction, and switches S 13 , S 23 , and S 33  in the southbound direction to reach core circuit C 33 . 
       FIG. 2  illustrates an example configuration for a switch  20  in  FIG. 1 , in accordance with an embodiment of the invention. In one embodiment, multiple data paths  30  ( FIG. 1 ) interconnect the switch  20  with neighboring components (i.e., a corresponding core circuit  10 , neighboring switches  20 ). 
     Relative to a switch  20 , each data path  30  is either an incoming router channel  30 F or an outgoing router channel  30 B. The switch  20  receives packets from a neighboring component via an incoming router channel  30 F. The switch  20  sends packets to a neighboring component via an outgoing router channel  30 B. Each incoming router channel  30 F has a reciprocal outgoing router channel  30 B. An incoming router channel  30 F may have a buffer  30 Q for maintaining incoming packets. In one embodiment, the incoming packets are maintained in a buffer  30 Q in a First In, First Out (FIFO) fashion. 
     In one embodiment, the switch  20  exchanges packets with neighboring components via multiple sets of router channels, wherein each set of router channels has at least one incoming router channel  30 F and at least one reciprocal router channel  30 B. As shown in  FIG. 2 , a first set  25 L of router channels (“Local router channels”) interconnects the switch  20  with a corresponding core circuit  10 . The switch  20  receives packets generated by the corresponding core circuit  10  via an incoming router channel  30 F of the set  25 L, and sends packets targeting the corresponding core circuit  10  via an outgoing router channel  30 B of the set  25 L. 
     A second set  25 N of router channels (“North router channels”) interconnects the switch  20  with an adjacent neighboring switch  20  to the north of the switch  20  (“north neighboring switch”). The switch  20  receives packets from the north neighboring switch  20  via an incoming router channel  30 F of the set  25 N, and sends packets to the north neighboring switch  20  via an outgoing router channel  30 B of the set  25 N. 
     A third set  25 S of router channels (“South router channels”) interconnects the switch  20  with an adjacent neighboring switch  20  to the south of the switch  20  (“south neighboring switch”). The switch  20  receives packets from the south neighboring switch  20  via an incoming router channel  30 F of the set  25 S, and sends packets to the south neighboring switch  20  via an outgoing router channel  30 B of the set  25 S. 
     A fourth set  25 E of router channels (“East router channels”) interconnects the switch  20  with an adjacent neighboring switch  20  to the east of the switch  20  (“east neighboring switch”). The switch  20  receives packets from the east neighboring switch  20  via an incoming router channel  30 F of the set  25 E, and sends packets to the east neighboring switch  20  via an outgoing router channel  30 B of the set  25 E. 
     A fifth set  25 W of router channels (“West router channels”) interconnects the switch  20  with an adjacent neighboring switch  20  to the west of the switch  20  (“west neighboring switch”). The switch  20  receives packets from the west neighboring switch  20  via an incoming router channel  30 F of the set  25 W, and sends packets to the west neighboring switch  20  via an outgoing router channel  30 B of the set  25 W. 
     For example, referring back to  FIG. 1 , switch S 21  is interconnected with corresponding core circuit C 21 , and adjacent neighboring switches S 11 , S 20 , S 22 , and S 31 . Switch  21  exchanges packets with core circuit C 21 , north neighboring switch S 11 , south neighboring switch S 31 , east neighboring switch S 22 , and west neighboring switch S 20  via a set  25 L of router channels, a set  25 N of router channels, a set  25 S of router channels, a set  25 E of router channels, and a set  25 W of router channels, respectively. 
       FIG. 3  illustrates example component failures of a processor array  50 , in accordance with an embodiment of the invention. A component failure occurs when the component is faulty. In the case of the array  50 , a component failure may be any one of the following: a failed core circuit  10 , a failed data path  30 , or a failed switch  20 . For example, in  FIG. 3 , core circuit C 11  is a failed core circuit  10 , switch S 31  is a failed switch  20 , and a data path  30  interconnecting switches S 20  and S 30  is a failed data path  30 . 
     In this specification, a column  45  including at least one failed core circuit  10  is generally referred to as a failed column. As shown in  FIG. 3 , col1 is a failed column  45 . 
     Embodiments of the invention provide a redundant routing system for a processor array. The different redundancy granularities disclosed herein include the ability to bypass a single failed core circuit  10 , a block of one or more failed core circuits  10 , a row of one or more failed core circuits  10 , a column of one or more failed core circuits  10 , or a plane of one or more failed core circuits  10 . 
       FIG. 4  illustrates an example redundant routing system  100  for a processor array  50 , wherein the routing system  100  includes redundant data paths  30 R and a redundant column  45 R of redundant core circuits  10 R, in accordance with an embodiment of the invention. In one embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  100  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  100  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  100  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  100 , a data path  30  that interconnects switches  20  is either a normal data path  30 N or a redundant data path  30 R. A normal data path  30 N interconnects adjacent neighboring switches  20  (e.g., a data path  30 N interconnecting switch S 01  with adjacent neighboring switch S 02 ). By comparison, a redundant data path  30 R interconnects non-neighboring switches  20 . Each redundant data path  30 R provides an alternate pathway for routing around a component failure. 
     Redundant data paths  30 R are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R (i.e., redundant data paths  30 R that are enabled/selected for routing around a component failure) are shown in  FIG. 4 . As shown in  FIG. 4 , at least one redundant data path  30 R interconnects switch S 00  with switch S 02 , at least one redundant data path  30 R interconnects switch S 10  with switch S 12 , at least one redundant data path  30 R interconnects switch S 20  with switch S 22 , and at least one redundant data path  30 R interconnects switch S 30  with switch S 32 . 
     A switch  20  exchanges packets with adjacent neighboring switches  20  via normal data paths  30 N. A switch  20  may also exchange packets with non-neighboring switches  20  via redundant data paths  30 R. As shown in  FIG. 4 , each switch S 00 , S 10 , S 20 , and S 30  may exchange packets with non-neighboring switch S 02 , S 12 , S 22 , and S 32 , respectively, via at least one redundant data path  30 R. 
     The redundant routing system  100  further comprises additional core circuits  10 , such as core circuits  10  having physical labels  0 R,  1 R,  2 R, and  3 R. These additional core circuits  10  are redundant core circuits  10 R. The redundant routing system  100  further comprises additional switches  20 , such as switches S 0 R, S 1 R, S 2 R, and S 3 R. These additional switches  20  are redundant switches  20 R. Redundant switches S 0 R, S 1 R, S 2 R, and S 3 R correspond to redundant core circuits  0 R,  1 R,  2 R, and  3 R, respectively. 
     In one embodiment, the redundant core circuits  10 R are organized into at least one redundant column  45 R. A redundant column  45 R may be disposed anywhere in the array  50 . Each redundant column  45 R is used to recover a failed column  45 . The redundant routing system  100  recovers one failed column  45  per redundant column  45 R. 
     In one embodiment, the maximum number of failed core circuits  10  that a redundant column  45 R can recover is equal to M, where M is the number of rows  40  ( FIG. 1 ) of array  50  ( FIG. 1 ), provided that the failed core circuits  10  are in the same column. For example, if array  50  has only four rows  40 , the maximum number of failed circuits  10  that a redundant column  45 R may recover is four, provided that the failed core circuits  10  are in the same column. 
     As shown in  FIG. 4 , colR is a redundant column  45 R, and col1 is a failed column  45  that includes a component failure. In one example, the component failure of col1 is the failed core circuit C 11 . In another example, the component failure of col1 is the failed switch S 11 . In yet another example, the component failure of col1 is a failed data path  30  interconnecting the switch S 11  with a neighboring component. To facilitate full operation of the array  50 , col1 is bypassed entirely using redundant data paths  30 R. Each switch S 00 , S 10 , S 20 , and S 30  of col0 exchanges packets with non-neighboring switch S 02 , S 12 , S 22 , and S 32  of col2 instead of adjacent neighboring switch S 01 , S 11 , S 21 , and S 31  of col1, respectively. Similarly, each switch S 02 , S 12 , S 22 , and S 32  of col2 exchanges packets with non-neighboring switch S 00 , S 10 , S 20 , and S 30  of col0 instead of adjacent neighboring switch S 01 , S 11 , S 21 , and S 31  of col1, respectively. As such, switches S 01 , S 11 , S 21  and S 31  of col1 are not used to propagate packets. 
     Even though col1 is bypassed entirely, the redundant routing system  100  enables the array  50  to logically look like a complete M×N array. Specifically, colR provides a redundant column  45 R that makes the array  50  a complete M×N array. In one example, the columns  45  with physical labels col0, col2, col3, and colR are logically mapped as columns  45  with logical labels col0, col1, col2, and col3, respectively. 
       FIG. 5  illustrates an example configuration for a switch  20  in  FIG. 4 , in accordance with an embodiment of the invention. As described above and illustrated in  FIG. 2 , each switch  20  is connected to multiple sets of router channels, such as Local router channels  25 L, North router channels  25 N, South router channels  25 S, East router channels  25 E, and West router channels  25 W. 
     Multiple static multiplexers  26  are used to select the switches  20  that the switch  20  exchanges packets with. Specifically, each static multiplexer  26  corresponds to only one set of router channels (e.g., Local router channels  25 L, North router channels  25 N, South router channels  25 S, East router channels  25 E, or West router channels  25 W). Each static multiplexer  26  is used to select the type of data path  30  that a corresponding set of router channels should receive packets from/send packets to. 
     In one embodiment, a static multiplexer  26  is used to select either normal data paths  30 N (that interconnect the switch  20  to an adjacent neighboring switch  20 ) or redundant data paths  30 R (that interconnect the switch  20  with a non-neighboring switch  20 ). Relative to a switch  20 , each normal data path  30 N is either an incoming normal data path  30 NF or an outgoing normal data path  30 NB, and each redundant data path  30 R is either an incoming redundant data path  30 RF or an outgoing redundant data path  30 RB. 
     As shown in  FIG. 5 , a first static multiplexer  26  is used to select the type of data paths  30  that East router channels  25 E should receive packets from/send packets to. Specifically, the first static multiplexer  26  is used to select either normal data paths  30 N that interconnect the switch  20  to an east neighboring switch  20 , or redundant data paths  30 R that interconnect the switch  20  to an east non-neighboring switch  20 . For example, referring back to  FIG. 4 , switch S 30  exchanges packets with either east neighboring switch S 31  via normal data paths  30 N, or east non-neighboring switch S 32  via redundant data paths  30 R. 
     Also shown in  FIG. 5 , a second static multiplexer  26  is used to select the type of data paths  30  that West router channels  25 W should receive packets from/send packets to. Specifically, the second static multiplexer  26  is used to select either normal data paths  30 N that interconnect the switch  20  to a west neighboring switch  20 , or redundant data paths  30 R that interconnect the switch  20  to a west non-neighboring switch  20 . For example, referring back to  FIG. 4 , switch S 32  exchanges packets with either west neighboring switch S 31  via normal data paths  30 N, or west non-neighboring switch S 30  via redundant data paths  30 R. 
       FIG. 6  illustrates a static multiplexer  26 , in accordance with an embodiment of the invention. The static multiplexer  26  is used to select the type of data path  30  that a corresponding set of router channels should receive packets from/send packets to. As shown in  FIG. 6 , the static multiplexer  26  selects between two different types of data paths, that is a first set of data paths A (e.g., normal data paths  30 N) or a second set of data path B (e.g., redundant data paths  30 R). A corresponding set of router channels C receives packets from/sends packets to the selected set of data paths  30 . 
     A controller  60  is used to select the data paths  30 . Specifically, a controller  60  provides a configuration bit to each static multiplexer  26 . The configuration bit indicates whether redundancy mode for the array  50  is enabled or disabled. Each static multiplexer  26  selects the type of data path  30  based on the configuration bit received. For example, when the redundancy mode is enabled, redundant data paths ( 30 R) are selected. When the redundancy mode is disabled, normal data paths ( 30 N) are selected instead. 
     The controller  60  maintains a control register file. In one embodiment, one controller  60  is used for the entire array  50 . In another embodiment, each switch  20  or each core circuit  10  has its own controller  60 . 
     In one embodiment, the controller  60  sends a control packet including a configuration bit in-band to each static multiplexer  26 . In another embodiment, the controller  60  sends a configuration bit out-of-band (e.g., via a separate communication channel, such as a scan chain or a dedicated bus) to each static multiplexer  26 . 
     Component failures are detected by presenting test vectors. There may be a test vector for each core circuit  10 , a test vector for each switch  20 , and a test vector for each data path  30 . For each test vector, the output generated based on said test vector is compared with expected output. A core circuit  10 , a switch  20 , or a data path  30  for a test vector is a component failure if the output generated based on the test vector does not equal the expected output. The controller  60  sets configuration bits that result in the bypass of the detected component failures. 
     Each data path  30  may include one signal wire or multiple signal wires (i.e., a bus of wires). A logic pass-gate may be used in the switching of a single signal wire. In one example implementation, each static multiplexer  26  is implemented using two logic pass-gates (i.e., four transistors  27 ) per signal wire of a data path  30 . Other types of logic can also be used to implement the multiplexers  26 . 
     More than one configuration bit is required for a multiplexer  26  that is configured to select from more than two data paths  30  (see, for example,  FIG. 8 ). In one example implementation, the number of configuration bits for a multiplexer  26  is equal to ceiling (log 2 p), wherein p is the total number of data paths  30  that said multiplexer  26  is configured to select from. 
       FIG. 7  illustrates an example redundant routing system  150  for a processor array  50 , wherein the routing system  150  includes diagonal data paths  30 D and a redundant column  45 R of redundant core circuits  10 R, in accordance with an embodiment of the invention. In another embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  150  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  150  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  150  further comprises redundant core circuits  10 R, such as core circuits  0 R,  1 R,  2 R, and  3 R. The redundant routing system  150  further comprises redundant switches  20 R, such as switches S 0 R, S 1 R, S 2 R, and S 3 R. Redundant switches S 0 R, S 1 R, S 2 R, and S 3 R correspond to redundant core circuits  0 R,  1 R,  2 R, and  3 R, respectively. In one embodiment, the redundant core circuits  10 R are organized into at least one redundant column  45 R. 
     The redundant routing system  150  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  150 , a data path  30  is a normal data path  30 N, a redundant data path  30 R, or a diagonal data path  30 D. A diagonal data path  30 D interconnects diagonally adjacent switches  20 . Each diagonal data path  30 D provides an alternate pathway for routing around a component failure. 
     Redundant data paths  30 R and diagonal data paths  30 D are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R and enabled diagonal data paths  30 D (i.e., diagonal data paths  30 D that are enabled/selected for routing around a component failure) are shown in  FIG. 7 . As shown in  FIG. 7 , diagonal data paths  30 D interconnect switch S 12  with switches S 01  and S 21 , switch S 13  with switches S 02  and S 22 , and redundant switch S 1 R with switches S 03  and S 23 . Further, at least one redundant data path  30 R interconnects switch S 10  with switch S 12 . 
     Each switch  20  exchanges packets with adjacent neighboring switches  20  via normal data paths  30 N. Some switches  20  may also exchange packets with non-neighboring switches  20  via redundant data paths  30 R. Some switches  20  may also exchange packets with diagonally adjacent switches  20  via diagonal data paths  30 D. As shown in  FIG. 7 , each switch S 12 , S 13 , and S 1 R may exchange packets with diagonally adjacent switches S 01  and S 21 , S 02  and S 22 , and S 03  and S 23 , respectively, via diagonal data paths  30 D. For example, switch S 12  may exchange packets with adjacent neighboring switches S 02 , S 11 , S 13 , and S 22 , non-neighboring switch S 10 , and diagonally adjacent switches S 01  and S 21 . 
     The redundant routing system  150  recovers M failed core circuits  10  per redundant column  45 R, wherein M is the number of rows  40  ( FIG. 1 ) of array  50  ( FIG. 1 ), and each failed core circuit  10  is in a different row  40 , even if the failed core circuits  10  are in different columns. For example, if array  50  has only four rows  40 , the maximum number of failed core circuits  10  that the array  50  can recover is four provided that the failed core circuits  10  are in different rows  40 . 
     As shown in  FIG. 7 , colR is a redundant column  45 R and col1 includes the failed core circuit C 11 . Even though failed core circuit C 11  and corresponding switch S 11  are bypassed entirely, the redundant routing system  150  enables the array  50  to logically look like a complete M×N array. For example, to facilitate full operation of the array  50 , the core circuits  10  with physical labels C 10 , C 12 , C 13 , and C 1 R are logically mapped as core circuits  10  with logical labels C 10 , C 11 , C 12 , and C 13 , respectively. Switches S 21 , S 22 , and S 23  exchange packets with switches S 12 , S 13 , and SIR, respectively using at least one diagonal data path  30 D. Thus packets may arrive at the core circuits  10  with logical labels C 11 , C 12 , and C 13  (i.e., physical labels C 12 , C 13 , and C 1 R) via diagonal data paths  30 D. 
     One redundant core circuit  10 R of colR, such as redundant core circuit  1 R, is used to recover one failed core circuit C 11 . The remaining core circuits  10 R of colR may be used to recover up to three additional failed core circuits  10  as long as the failed core circuits  10  are in different rows  40 . 
       FIG. 8  illustrates an example configuration of a switch  20  in  FIG. 7 , in accordance with an embodiment of the invention. The switch  20  is connected to multiple sets of router channels, such as Local router channels  25 L, North router channels  25 N, South router channels  25 S, East router channels  25 E, and West router channels  25 W. A first static multiplexer  26  is used to select the type of data paths  30  that East router channels  25 E should receive packets from/send packets to. A second static multiplexer  26  is used to select the type of data paths  30  that West router channels  25 W should receive packets from/send packets to. 
     As shown in  FIG. 8 , additional static multiplexers  26  are also used. In one embodiment, each additional static multiplexer  26  is used to select one of the following types of data paths: a set of normal data paths  30 N that interconnect the switch  20  with an adjacent neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  with a diagonally adjacent switch  20  to the east of the switch  20 , or a different set of diagonal data paths  30 D that interconnect the switch  20  with a diagonally adjacent switch  20  to the west of the switch  20 . Each set of diagonal data paths  30 D includes an incoming diagonal data path  30 DF and an outgoing diagonal data path  30 DB. 
     As shown in  FIG. 8 , a third static multiplexer  26  is used to select the type of data paths  30  that North router channels  25 N should receive packets from/send packets to. Specifically, the third static multiplexer  26  is used to select one of the following: a set of normal data paths  30 N that interconnect the switch  20  to a north neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a north-east diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a north-west diagonally adjacent switch  20 . For example, referring back to  FIG. 7 , switch S 12  exchanges packets with either north-west diagonally adjacent switch S 01  via a set of diagonal data paths  30 D, or north neighboring switch S 02  via a set of normal data paths  30 N. Switch S 12  may also exchange packets with north-east diagonally adjacent switch S 03  via a set of diagonal data paths  30 D that interconnects switch S 12  with S 03 . 
     Also shown in  FIG. 8 , a fourth static multiplexer  26  is used to select the type of data paths  30  that South router channels  25 S should receive packets from/send packets to. Specifically, the fourth static multiplexer  26  is used to select one of the following: a set of normal data paths  30 N that interconnect the switch  20  to a south neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a south-east diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a south-west diagonally adjacent switch  20 . For example, referring back to  FIG. 8 , switch S 12  exchanges packets with either south-west diagonally adjacent switch S 21  via a set of diagonal data paths  30 D, or south neighboring switch S 22  via a set of normal data paths  30 N. Switch S 12  may also exchange packets with south-east diagonally adjacent switch S 23  via a set of diagonal data paths  30 D that interconnect switch S 12  with S 23 . 
       FIG. 9  illustrates another example configuration of a switch in  FIG. 7 , in accordance with an embodiment of the invention. The switch  20  is connected to multiple sets of router channels, such as Local router channels  25 L, North router channels  25 N, South router channels  25 S, East router channels  25 E, and West router channels  25 W. 
     In another embodiment, multiple sets of redundant router channels (i.e., spare router channels) are used instead of static multiplexers  26 . As shown in  FIG. 9 , a first set  25 Nr 1  interconnects the switch  20  with a north-west diagonally adjacent switch  20 , a second set  25 Nr 2  interconnects the switch  20  with a north-east diagonally adjacent switch  20 , a third set  25 Sr 1  interconnects the switch  20  with a south-west diagonally adjacent switch  20 , a fourth set  25 Sr 2  interconnects the switch  20  with a south-east diagonally adjacent switch  20 , a fifth set  25 Er interconnects the switch  20  with an east non-neighboring switch  20 , and a sixth set  25 Wr interconnects the switch  20  with an west non-neighboring switch  20 . 
     The controller  60  ( FIG. 6 ) provides configuration bits to the switch  20 . The switch  20  only uses router channels that are enabled. For each direction (i.e., North, South, East, and West), only one set of router channels is enabled. For example, in the South direction, only one set of router channels from the three sets  25 Sr 1 ,  25 S, and  25 Sr 2  is enables, and the switch  20  exchanges packets using only the enabled set of router channels. 
       FIG. 10  illustrates an example redundant routing system  200  for a processor array  50 , wherein the routing system  200  includes diagonal data paths  30 D and a redundant router column  45 RR of redundant routers  20 R, in accordance with an embodiment of the invention. In another embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  200  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  200  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  150  further comprises redundant switches  20 R, such as switches S 0 R, S 1 R, S 2 R, and S 3 R. In one embodiment, the redundant switches  20 R are organized into at least one redundant router column  45 RR. Redundant router columns  45 RR are positioned at an end of the array  50 . 
     The redundant routing system  150  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  200 , a data path  30  is a normal data path  30 N, a redundant data path  30 R, or a diagonal data path  30 D. Redundant data paths  30 R and diagonal data paths  30 D are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R and enabled diagonal data paths  30 D are shown in  FIG. 10 . As shown in  FIG. 10 , diagonal data paths  30 D interconnect switch S 12  with switches S 01  and S 21 , switch S 13  with switches S 02  and S 22 , and redundant switch S 1 R with switches S 03  and S 23 . Further, at least one redundant data path  30 R interconnects switch S 10  with switch S 12 . 
     As shown in  FIG. 10 , colRR is a redundant router column  45 RR. col1 includes at least one component failure. The component failure may be a failed core circuit C 11 , a failed switch S 11 , or a failed data path  30  interconnecting the switch S 11  with a neighboring component. To facilitate full operation of the array  50 , failed core circuit C 11  and corresponding switch S 11  are bypassed using diagonal data paths  30 D and redundant data paths  30 R. 
     Even though coil includes at least one component failure, the redundant routing system  200  allows the array  50  to logically operate as a fully functionally M×N network array of switches  20 . The redundant routing system  200  uses less area than the redundant routing system  150  of  FIG. 7  because the redundant routing system  200  does not include redundant core circuits  10 R. The redundant routing system  200  does not recover a failed core circuit  10 . Software is used to migrate functionality from a failed core circuit  10  to another core circuit  10  of the array  50 . 
       FIG. 11  illustrates an example redundant routing system  250  for a processor array  50 , wherein the routing system  250  is organized into blocks, in accordance with an embodiment of the invention. In another embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  250  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  250  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  250  operates using a block-based approach. Components of the array  50  are organized into multiple blocks  270 . The redundant routing system  250  further comprises redundant core circuits  10 R, such as core circuits  0 R,  1 R,  2 R, and  3 R. The redundant routing system  250  further comprises redundant switches  20 R, such as switches S 0 R, S 1 R, S 2 R, and S 3 R. Redundant switches S 0 R, S 1 R, S 2 R, and S 3 R correspond to redundant core circuits  0 R,  1 R,  2 R, and  3 R, respectively. In one embodiment, the redundant core circuits  10 R are organized into at least one redundant column  45 R. 
     The redundant routing system  250  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  250 , a data path  30  is a normal data path  30 N, a redundant data path  30 R, or a diagonal data path  30 D. Redundant data paths  30 R and diagonal data paths  30 D are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R and enabled diagonal data paths  30 D are shown in  FIG. 11 . 
     The redundant routing system  250  operates using a block-based approach. Components of the array  50  are organized into multiple blocks  270 . The redundant routing system  250  recovers one failed core circuit  10  per block  270 , per redundant column  45 R. For each block  270  including a failed core circuit  10 , redundant data paths  30 R within said block  270  are used to bypass components of a column  45  within said block  270 , wherein the column  45  includes the failed core circuit  10 , and wherein the bypassed components are recovered used components of a redundant column  45 R within said block  270 . Packets are propagated between blocks  270  using diagonal data paths  30 D. 
     As shown in  FIG. 11 , components of the array  50  are organized into multiple blocks  270 , such as Block  0  and Block  1 . Diagonal data paths  30 D interconnect switches S 12  and S 13  with switches S 21  and S 22 , respectively. Redundant data paths  30 R interconnect switches S 00  and S 10  with switches S 02  and S 12 , respectively. colR is a redundant column  45 R and col1 includes the failed core circuit C 11 . 
     Components of col1 within Block  0  (i.e., core circuits C 01  and C 11 , and switches S 01  and S 11 ) are entirely bypassed using redundant data paths  30 R. Components of redundant column  45 R within Block  0  (i.e., redundant core circuits  0 R and  1 R, and redundant switches S 0 R and S 1 R) are used to recover the bypassed components. Diagonal data paths  30 D at the edges of Block  0  are used to propagate packets to components of the Block  1 . 
       FIG. 12A  illustrates an example redundant routing system  325  for a processor array  50 , wherein the routing system  325  includes redundant data paths  30 R and a redundant row  40 R of redundant core circuits  10 R, in accordance with an embodiment of the invention. In one embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  325  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  325  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  325  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  325 , a data path  30  is either a normal data path  30 N or a redundant data path  30 R. Redundant data paths  30 R are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R are shown in  FIG. 12A . As shown in  FIG. 12A , at least one redundant data path  30 R interconnects switch S 00  with switch S 20 , at least one redundant data path  30 R interconnects switch S 01  with switch S 21 , at least one redundant data path  30 R interconnects switch S 02  with switch S 22 , and at least one redundant data path  30 R interconnects switch S 03  with switch S 23 . 
     The redundant routing system  325  further comprises additional core circuits  10 , such as core circuits R 0 , R 1 , R 2 , and R 3 . These additional core circuits  10  are redundant core circuits  10 R. The redundant routing system  325  further comprises additional switches  20 , such as switches SR 0 , SR 1 , SR 2 , and SR 3 . These additional switches  20  are redundant switches  20 R. Redundant switches SR 0 , SR 1 , SR 2 , and SR 3  correspond to redundant core circuits R 0 , R 1 , R 2 , and R 3 , respectively. 
     In one embodiment, the redundant core circuits  10 R are organized into at least one redundant row  40 R. Redundant rows  40 R are disposed anywhere in the array  50 . In this specification, a row  40  including at least one failed core circuit  10  is generally referred to as a failed row. Each redundant row  40 R is used to recover a failed row  40 . The redundant routing system  325  recovers one failed row  40  per redundant row  40 R. 
     In one embodiment, the maximum number of failed core circuits  10  that a redundant row  40 R may recover is equal to N, wherein N is the number of columns  45  ( FIG. 1 ) of array  50  ( FIG. 1 ), provided that the failed core circuits  10  are in the same row. For example, if array  50  has only four columns  45 , the maximum number of failed core circuits  10  that a redundant row  40 R can recover is four, provided that the failed core circuits  10  are in the same row. 
     As shown in  FIG. 12A , rowR is a redundant row  40 R, and row1 is a failed row  40  that includes the failed core circuit C 11 . To facilitate full operation of the array  50 , row1 is bypassed entirely using redundant data paths  30 R. Each switch S 00 , S 01 , S 02 , and S 03  of row0 exchanges packets with non-neighboring switch S 20 , S 21 , S 22 , and S 23  of row2 instead of adjacent neighboring switch S 10 , S 11 , S 12 , and S 13  of row1, respectively. Similarly, each switch S 20 , S 21 , S 22 , and S 23  of row2 exchanges packets with non-neighboring switch S 00 , S 01 , S 02 , and S 03  of row0 instead of adjacent neighboring switch S 10 , S 11 , S 12 , and S 13  of row1, respectively. As such, switches S 10 , S 11 , S 12 , and S 13  of row1 are not used to propagate packets. 
     Even though row1 is bypassed entirely, the redundant routing system  325  enables the array  50  to logically operate as an M×N array. Specifically, rowR provides a redundant row  30 R that enables the full operation of the array  50 . In one example, the rows  40  with physical labels row0, row2, row3, and rowR are logically mapped as rows  40  with logical labels row0, row1, row2, and row3, respectively. 
       FIG. 12B  illustrates an example configuration of a switch  20  in  FIG. 12A , in accordance with an embodiment of the invention. As described above and illustrated in  FIG. 2 , each switch  20  is connected to multiple sets of router channels, such as Local router channels  25 L, North router channels  25 N, South router channels  25 S, East router channels  25 E, and West router channels  25 W. 
     As shown in  FIG. 12B , a first static multiplexer  26  is used to select the type of data paths  30  that North router channels  25 N should receive packets from/send packets to. Specifically, the first static multiplexer  26  is used to select either normal data paths  30 N that interconnect the switch  20  to a north neighboring switch  20 , or redundant data paths  30 R that interconnect the switch  20  to a north non-neighboring switch  20 . For example, referring back to  FIG. 12A , switch S 22  exchanges packets with either north neighboring switch S 12  via normal data paths  30 N, or north non-neighboring switch S 03  via redundant data paths  30 R. 
     Also shown in  FIG. 12B , a second static multiplexer  26  is used to select the type of data paths  30  that South router channels  25 S should receive packets from/send packets to. Specifically, the second static multiplexer  26  is used to select either normal data paths  30 N that interconnect the switch  20  to a south neighboring switch  20 , or redundant data paths  30 R that interconnect the switch  20  to a south non-neighboring switch  20 . For example, referring back to  FIG. 12A , switch S 02  exchanges packets with either south neighboring switch S 12  via normal data paths  30 N, or south non-neighboring switch S 22  via redundant data paths  30 R. 
       FIG. 13  illustrates an example redundant routing system  350  for a processor array  50 , wherein the routing system  350  includes diagonal data paths  30 D and a redundant row  40 R of redundant core circuits  10 R, in accordance with an embodiment of the invention. In another embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  350  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  350  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  350  further comprises redundant core circuits  10 R, such as core circuits R 0 , R 1 , R 2 , and R 3 . The redundant routing system  350  further comprises redundant switches  20 R, such as switches SR 0 , SR 1 , SR 2 , and SR 3 . Redundant switches SR 0 , SR 1 , SR 2 , and SR 3  correspond to redundant core circuits R 0 , R 1 , R 2 , and R 3 , respectively. In one embodiment, the redundant core circuits  10 R are organized into at least one redundant row  40 R. 
     The redundant routing system  350  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  350 , a data path  30  is a normal data path  30 N, a redundant data path  30 R, or a diagonal data path  30 D. Redundant data paths  30 R and diagonal data paths  30 D are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R and enabled diagonal data paths  30 D are shown in  FIG. 13 . 
     As shown in  FIG. 13 , diagonal data paths  30 D interconnect switch S 21  with switches S 10  and S 12 , switch S 31  with switches S 20  and S 22 , and redundant switch SR 1  with switches S 30  and S 32 . Further, at least one redundant data path  30 R interconnects switch S 01  with switch S 21 . Each switch S 21 , S 31 , and SR 1  may exchange packets with diagonally adjacent switches S 10  and S 12 , S 20  and S 22 , and S 30  and S 32 , respectively, via diagonal data paths  30 D. For example, switch S 21  may exchange packets with adjacent neighboring switches S 20 , S 11 , S 31 , and S 22 , non-neighboring switch S 01 , and diagonally adjacent switches S 10  and S 12 . 
     The redundant routing system  350  recovers N failed core circuits  10  per redundant row  40 R, wherein N is the number of rows  40  ( FIG. 1 ) of array  50  ( FIG. 1 ), and each failed core circuit  10  is in a different column  45 , even if the failed core circuits  10  are in different rows. For example, if array  50  has only four columns  45 , the maximum number of failed core circuits  10  that the array  50  can recover is four provided that the failed core circuits  10  are in different columns  45 . 
     As shown in  FIG. 13 , rowR is a redundant row  40 R and row1 includes the failed core circuit C 11 . To facilitate full operation of the array  50 , failed core circuit C 11  and corresponding switch S 11  are bypassed using diagonal data paths  30 D and redundant data paths  30 R. Switches S 01  and S 21  exchange packets via at least one redundant data path  30 R, switches S 10  and S 21  exchange packets via at least one diagonal data path  30 D, and switches S 12  and S 21  exchange packets via at least one diagonal data path  30 D. As such, switch S 11  is not used to propagate packets 
     One redundant core circuit  10 R of rowR, such as redundant core circuit R 1 , is used to recover failed core circuit C 11 . The remaining core circuits  10 R of rowR may be used to recover up to three additional failed core circuits  10  as long as the failed core circuits  10  are in different columns  45 . 
       FIG. 14  illustrates an example configuration of a switch  20  in  FIG. 13 , in accordance with an embodiment of the invention. The switch  20  is connected to multiple sets of router channels, such as Local router channels  25 L, North router channels  25 N, South router channels  25 S, East router channels  25 E, and West router channels  25 W. A first static multiplexer  26  is used to select the type of data paths  30  that North router channels  25 N should receive packets from/send packets to. A second static multiplexer  26  is used to select the type of data paths  30  that South router channels  25 S should receive packets from/send packets to. 
     As shown in  FIG. 14 , additional static multiplexers  26  are also used. In one embodiment, each additional static multiplexer  26  is used to select one of the following types of data paths: a set of normal data paths  30 N that interconnect the switch  20  with an adjacent neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  with a diagonally adjacent switch  20  to the north of the switch  20 , or a different set of diagonal data paths  30 D that interconnect the switch  20  with a diagonally adjacent switch  20  to the south of the switch  20 . 
     As shown in  FIG. 14 , a third static multiplexer  26  is used to select the type of data paths  30  that East router channels  25 E should receive packets from/send packets to. Specifically, the third static multiplexer  26  is used to select one of the following: a set of normal data paths  30 N that interconnect the switch  20  to an east neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a north-east diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a south-east diagonally adjacent switch  20 . For example, referring back to  FIG. 13 , switch S 21  exchanges packets with either north-east diagonally adjacent switch S 12  via a set of diagonal data paths  30 D, or east neighboring switch S 22  via a set of normal data paths  30 N. Switch S 21  may also exchange packets with south-east diagonally adjacent switch S 32  via a set of diagonal data paths  30 D that interconnects switch S 21  with S 32 . 
     Also shown in  FIG. 14 , a fourth static multiplexer  26  is used to select the type of data paths  30  that West router channels  25 W should receive packets from/send packets to. Specifically, the fourth static multiplexer  26  is used to select one of the following: a set of normal data paths  30 N that interconnect the switch  20  to a west neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a north-west diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a south-west diagonally adjacent switch  20 . For example, referring back to  FIG. 13 , switch S 21  exchanges packets with either north-west diagonally adjacent switch S 10  via a set of diagonal data paths  30 D, or west neighboring switch S 21  via a set of normal data paths  30 N. Switch S 21  may also exchange packets with south-west diagonally adjacent switch S 30  via a set of diagonal data paths  30 D that interconnects switch S 21  with S 30 . 
       FIG. 15  illustrates an example redundant routing system  400  for a processor array  50 , wherein the routing system  400  includes a redundant column  45 R of redundant core circuits  10 R and a redundant row  40 R of redundant core circuits  10 , in accordance with an embodiment of the invention. In one embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  400  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  400  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  400  further comprises multiple redundant core circuits  10 R, such as redundant core circuits  0 R,  1 R,  2 R,  3 R, R 0 , R 1 , R 2 , R 3 , and RR. The redundant routing system  400  further comprises multiple redundant switches  20 R, such as switches S 0 R, S 1 R, S 2 R, S 3 R, SR 0 , SR 1 , SR 2 , SR 3 , and SRR. Redundant switches S 0 R, S 1 R, S 2 R, S 3 R, SR 0 , SR 1 , SR 2 , SR 3 , and SRR correspond to redundant core circuits  0 R,  1 R,  2 R,  3 R, R 0 , R 1 , R 2 , R 3 , and RR, respectively. 
     In one embodiment, the redundant core circuits  10 R are organized into at least one redundant column  45 R and at least one redundant row  40 R. Each redundant column  45 R is used to bypass a failed column  45 . Each redundant row  40 R is used to bypass a failed row  40 . The redundant routing system  400  recovers one failed column  45  per redundant column  45 R, and one failed row  40  per redundant row  40 R. 
     In one embodiment, the maximum number of failed core circuits  10  that a failed column  45  may have is equal to M, wherein M is the number of rows  40  ( FIG. 1 ) of array  50  ( FIG. 1 ). For example, if array  50  has only four rows  40 , the maximum number of failed circuits  10  that a failed column  45  may have is four. The maximum number of failed core circuits  10  that a failed row  40  may have is equal to N, wherein N is the number of columns  45  ( FIG. 1 ) of array  50  ( FIG. 1 ). For example, if array  50  has only four columns  45 , the maximum number of failed circuits  10  that a failed row  40  may have is four. 
     The redundant routing system  400  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  400 , a data path  30  is either a normal data path  30 N or a redundant data path  30 R. Redundant data paths  30 R are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R are shown in  FIG. 15 . As shown in  FIG. 15 , redundant data paths  30 R interconnect switch S 00  with switch S 20 , switch S 01  with switch S 21 , switch S 03  with switch S 23 , redundant switch S 0 R with redundant switch S 2 R, switch S 01  with switch S 03 , switch S 21  with switch S 23 , switch S 31  with switch S 33 , and redundant switch SR 1  with redundant switch SR 3 . 
     As shown in  FIG. 15 , colR is a redundant column  45 R and rowR is a redundant row  40 R. The array  50  includes failed core circuit C 11  in row1, col1, and failed core circuit C 22  in row2, col2. col1 and col2 are failed columns  45 , and row1 and row2 are failed rows  40 . To facilitate full operation of the array  50 , col2 and row1 are bypassed entirely using redundant data paths  30 R. Each switch S 01 , S 21 , S 31 , and SR 1  of col1 exchanges packets with non-neighboring switch S 03 , S 23 , S 33 , and SR 3  of col3 instead of adjacent neighboring switch S 02 , S 22 , S 32 , and SR 2  of col2, respectively. Similarly, each switch S 03 , S 23 , S 33 , and SR 3  of col3 exchanges packets with non-neighboring switch S 01 , S 21 , S 31 , and SR 1  of col1 instead of adjacent neighboring switch S 02 , S 22 , S 32 , and SR 2  of col2, respectively. As such, switches S 02 , S 22 , S 32 , and SR 2  of col2 are not used to propagate packets. 
     As col2 is bypassed entirely, colR is used to recover col2. 
     Further, each switch S 00 , S 01 , S 03 , and S 0 R of row0 exchanges packets with non-neighboring switch S 20 , S 21 , S 23 , and S 2 R of row2 instead of adjacent neighboring switch S 10 , S 11 , S 13 , and S 1 R of row1, respectively. Similarly, each switch S 20 , S 21 , S 23 , and S 2 R of row2 exchanges packets with non-neighboring switch S 00 , S 01 , S 03 , and S 0 R of row0 instead of adjacent neighboring switch S 10 , S 11 , S 13 , and S 1 R of row1, respectively. As such, switches S 10 , S 11 , S 13 , and S 1 R of row1 are not used to propagate packets. Switch S 12  is also not used to propagate packets. 
     As row1 is bypassed entirely, rowR is used to recover row1. 
       FIG. 16  illustrates an example configuration of a switch  20  in  FIG. 15 , in accordance with an embodiment of the invention. The switch  20  is connected to multiple sets of router channels, such as a set  25 L of Local router channels, a set  25 N of North router channels, a set  25 S of South router channels, a set  25 E of East router channels  25 E, and a set  25 W of West router channels. 
     A first static multiplexer  26  is used to select one of the following sets of data paths  30  that North router channels  25 N should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to a north neighboring switch  20 , or a set of redundant data paths  30 R that interconnect the switch  20  to a north non-neighboring switch  20 . For example, referring back to  FIG. 15 , switch S 21  exchanges packets with either north neighboring switch S 11  via a set of normal data paths  30 N, or north non-neighboring switch S 01  via a set of redundant data paths  30 R. 
     A second static multiplexer  26  is used to select one of the following sets of data paths  30  that South router channels  25 S should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to a south neighboring switch  20 , or a set of redundant data paths  30 R that interconnect the switch  20  to a south non-neighboring switch  20 . For example, referring back to  FIG. 15 , switch S 01  exchanges packets with either south neighboring switch S 11  via a set of normal data paths  30 N, or south non-neighboring switch S 21  via a set of redundant data paths  30 R. 
     A third static multiplexer  26  is used to select one of the following sets of data paths  30  that East router channels  25 E should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to a east neighboring switch  20 , or a set of redundant data paths  30 R that interconnect the switch  20  to a east non-neighboring switch  20 . For example, referring back to  FIG. 15 , switch S 21  exchanges packets with either east neighboring switch S 22  via a set of normal data paths  30 N, or east non-neighboring switch S 23  via a set of redundant data paths  30 R. 
     A fourth static multiplexer  26  is used to select one of the following sets of data paths  30  that West router channels  25 W should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to a west neighboring switch  20 , or a set of redundant data paths  30 R that interconnect the switch  20  to a west non-neighboring switch  20 . For example, referring back to  FIG. 15 , switch S 23  exchanges packets with either west neighboring switch S 22  via a set of normal data paths  30 N, or west non-neighboring switch S 21  via a set of redundant data paths  30 R. 
       FIG. 17A  illustrates an example redundant routing system  450  for a processor array  50 , wherein the routing system  450  includes diagonal data paths  30 D, a redundant column  45 R of redundant core circuits  10 , and a redundant row  40 R of redundant core circuits  10 , in accordance with an embodiment of the invention. In one embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  450  for bypassing a component failure and facilitating full operation of the array  50 . The redundant routing system  450  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  450  further comprises multiple redundant core circuits  10 R, such as redundant core circuits  0 R,  1 R,  2 R,  3 R, R 0 , R 1 , R 2 , R 3 , and RR. The redundant routing system  450  further comprises multiple redundant switches  20 R, such as switches S 0 R, S 1 R, S 2 R, S 3 R, SR 0 , SR 1 , SR 2 , SR 3 , and SRR. Redundant switches S 0 R, S 1 R, S 2 R, S 3 R, SR 0 , SR 1 , SR 2 , SR 3 , and SRR correspond to redundant core circuits  0 R,  1 R,  2 R,  3 R, R 0 , R 1 , R 2 , R 3 , and RR, respectively. In one embodiment, the redundant core circuits  10 R are organized into at least one redundant column  45 R and at least one redundant row  40 R. 
     The redundant routing system  450  recovers N failed core circuits  10  per redundant row  40 R, and M failed core circuits  10  per redundant column  45 R, wherein M is the number of rows  40  ( FIG. 1 ) of array  50  ( FIG. 1 ), and N is the number of columns  45  ( FIG. 1 ) of array  50 . The redundant routing system  450  can tolerate more than one failed core circuit in a row  40  or a column  45 . 
     The redundant routing system  450  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  450 , a data path  30  is a normal data path  30 N, a redundant data path  30 R, or a diagonal data path  30 D. Redundant data paths  30 R and diagonal data paths  30 D are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R and enabled diagonal data paths  30 D are shown in  FIG. 17A . As shown in  FIG. 17A , redundant data paths  30 R interconnect switch S 01  with switch S 21 , switch S 12  with redundant switch SIR, and switch S 22  with redundant switch SR 2 . Diagonal data paths  30 D interconnect switch S 21  with switches S 10  and S 12 , switch S 31  with switches S 20  and S 22 , redundant switch SR 1  with switch S 30 , redundant switch SR 2  with switch S 33 , and redundant switch S 1 R with switch S 03 . 
     As shown in  FIG. 17A , colR is a redundant column  45 R and rowR is a redundant row  40 R. The array  50  includes a first failed core circuit C 11  in row1, col1, a second failed core circuit C 32  in row3, col2, and a third failed core circuit C 13  in row1, col3. col1, col2, and col3 are failed columns  45 , and row1 and row3 are failed rows  40 . row1 includes more than one failed core circuit  10 . 
     To facilitate full operation of the array  50 , core circuits C 11 , C 13 , and C 32  and corresponding switches S 11 , S 13 , and S 32 , respectively, are bypassed using redundant data paths  30 R and diagonal data paths  30 D. For example, to shift packets around the failed core circuit C 11 , switches S 01  and S 21  exchange packets via at least one redundant data path  30 R, switches S 10  and S 21  exchange packets via at least one diagonal data path  30 D, and switches S 12  and S 21  exchange packets via at least one diagonal data path  30 D. As such, switch S 11  is not used to propagate packets. 
     As shown in  FIG. 17A , two redundant core circuits  10 R of rowR, such as redundant core circuits R 1  and R 2 , are used to recover failed core circuits C 11  and C 32 . Further, one redundant core circuit  10 R of colR, such as redundant core circuit  1 R, is used to recover failed core circuit C 13 . Alternatively, two redundant core circuits  10 R of colR and one redundant core circuit  10 R of rowR are used to recover failed core circuits C 11 , C 32 , and C 13 . 
       FIG. 17B  illustrates an example configuration of a switch  20  in  FIG. 17A , in accordance with an embodiment of the invention. The switch  20  is connected to multiple sets of router channels, such as Local router channels  25 L, North router channels  25 N, South router channels  25 S, East router channels  25 E, and West router channels  25 W. 
     A first static multiplexer  26  is used to select one of the following sets of data paths  30  that North router channels  25 N should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to a north neighboring switch  20 , a set of redundant data paths  30 R that interconnect the switch  20  to a north non-neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a north-east diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a north-west diagonally adjacent switch  20 . 
     A second static multiplexer  26  is used to select one of the following sets of data paths  30  that South router channels  25 S should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to a south neighboring switch  20 , a set of redundant data paths  30 R that interconnect the switch  20  to a south non-neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a south-east diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a south-west diagonally adjacent switch  20 . 
     A third static multiplexer  26  is used to select one of the following sets of data paths  30  that East router channels  25 E should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to an east neighboring switch  20 , a set of redundant data paths  30 R that interconnect the switch  20  to an east non-neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a north-east diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a south-east diagonally adjacent switch  20 . 
     A fourth static multiplexer  26  is used to select one of the following sets of data paths  30  that West router channels  25 W should receive packets from/send packets to: a set of normal data paths  30 N that interconnect the switch  20  to a west neighboring switch  20 , a set of redundant data paths  30 R that interconnect the switch  20  to a west non-neighboring switch  20 , a set of diagonal data paths  30 D that interconnect the switch  20  to a north-west diagonally adjacent switch  20 , and a different set of diagonal data paths  30 D that interconnect the switch  20  to a south-west diagonally adjacent switch  20 . For example, referring back to  FIG. 17A , redundant switch S 1 R exchanges packets with one of the following: west neighboring switch S 13  via a set of normal data paths  30 N, west non-neighboring switch S 12  via a set of redundant data paths  30 R, north-west diagonally adjacent switch S 03  via a set of diagonal data paths  30 D, and south-west diagonally adjacent switch S 23  via a different set of diagonal data paths  30 D. 
       FIG. 18  illustrates an example redundant routing system  750  for a processor array  50 , wherein the redundant routing system  750  bypasses a component failure using redundant data paths  30 R, in accordance with an embodiment of the invention. In one embodiment, the array  50  ( FIG. 1 ) comprises a redundant routing system  750  for bypassing a component failure. The redundant routing system  750  includes all components of the routing system  15  as described above and illustrated in  FIG. 1 . 
     The redundant routing system  750  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  750 , each data path  30  is either a normal data path  30 N or a redundant data path  30 R. Redundant data paths  30 R are present throughout the array  50 . For ease of illustration, only enabled redundant data paths  30 R are shown in  FIG. 18 . 
     Each redundant data path  30 R interconnects non-neighboring switches  20  in different rows  40  ( FIG. 1 ) or different columns  45  ( FIG. 3 ). For example, as shown in  FIG. 18 , switch S 10  in col0 is interconnected with switch S 12  in col2 via at least one redundant data path  30 R, and switch S 01  in row0 is interconnected with switch S 21  in row2 via at least one redundant data path  30 R. 
     As shown in  FIG. 18 , col1 of the array  50  includes at least one of the following component failures: a failed core circuit C 11 , a failed switch S 11 , or a failed normal data path  30 N that interconnects switch S 11  to a neighboring switch  20 . The redundant routing system  750  bypasses the core circuit C 11  and the corresponding switch S 11  using redundant data paths  30 R that interconnect switches in different rows  40  or different columns  45 . 
     The number of component failures the redundant routing system  750  can bypass is up to one-half the size of the array  50 . The redundant routing system  750  does not utilize redundant core circuits  10 R or redundant routers  20 R. As such, the number of core circuits  10  that the array  50  logically represents is directly reduced by the number of bypassed core circuits  10 . 
     In one embodiment, each switch  20  of the redundant routing system  750  is implemented in the same manner as each switch  20  of the redundant routing system  400  ( FIG. 15 ). For example, each switch  20  of the redundant routing system  750  has a first static multiplexer  26  ( FIG. 16 ) for a set  25 N of North router channels, a second static multiplexer  26  ( FIG. 16 ) for a set  25 S of South router channels, a third static multiplexer  26  ( FIG. 16 ) for a set  25 E of East router channels, and a fourth static multiplexer  26  ( FIG. 16 ) for a set  25 W of West router channels. Each static multiplexer  26  is configured to select between a set of normal data paths  30 N or a set of redundant data paths  30 R. 
     As stated above, multiple core circuits  10  may be organized into a three-dimensional 3-D processor array. 
       FIG. 19  illustrates a routing system  500  for a 3-D processor array  625 , wherein the routing system  500  includes three-dimensional switches  520 , in accordance with an embodiment of the invention. A 3-D processor array  625  includes multiple core circuits  10 . 
     A routing system  500  for a 3-D array  625  comprises multiple 3-D switches  520  and multiple data paths  30 . The routing system  500  is a multidimensional switch network. Each 3-D switch  520  corresponds to a core circuit  10  of the array  625 . As described in detail later herein, each 3-D switch  520  is interconnected with a corresponding core circuit  10  via at least one data path  30 . Each 3-D switch  520  is further interconnected with at least one adjacent neighboring 3-D switch  520  via at least one data path  30 . 
     The processor array has multiple X-Y planes  540  (e.g., Tier 0, Tier 1, and Tier 2), multiple Y-Z planes  545 , and multiple X-Z planes  546 . As shown in  FIG. 19 , Tier 0 includes switches S 000 , S 010 , S 020 , S 100 , S 110 , S 120 , S 200 , S 210 , and S 220 . Tier 1 includes switches S 001 , S 011 , S 021 , S 101 , S 111 , S 121 , S 201 , S 211 , and S 221 . Tier 2 includes switches S 002 , S 012 , S 022 , S 102 , S 112 , S 122 , S 202 , S 212 , and S 222 . 
     For ease of illustration, only the corresponding core circuit  10  for switch S 220  is shown (i.e., C 220 ). 
     As described in detail later herein, Z routing interconnects the X-Y planes  540 , and X-Y routing interconnects the switches  520  within an X-Y plane  540 . 
       FIG. 20  illustrates an example configuration of a 3-D switch  520  in  FIG. 19 , in accordance with an embodiment of the invention. In one embodiment, multiple data paths  30  ( FIG. 19 ) interconnect the 3-D switch  520  with neighboring components of the 3-D switch  520  (e.g., a corresponding core circuit  10 , neighboring 3-D switches  520 ). 
     In one embodiment, the 3-D switch  520  exchanges packets with neighboring components via multiple sets of router channels, wherein each set of router channels has an incoming router channel  30 F and a reciprocal router channel  30 B. As shown in  FIG. 20 , a first set  25 L of router channels (“Local router channels”) interconnects the 3-D switch  520  with a corresponding core circuit  10  ( FIG. 19 ). The 3-D switch  520  receives packets generated by the corresponding core circuit  10  via an incoming router channel  30 F of the set  25 L, and sends packets targeting the corresponding core circuit  10  via an outgoing router channel  30 B of the set  25 L. 
     A second set  25 X 1  and a third set  25 X 2  of router channels (“X router channels”) interconnects the 3-D switch  520  with an adjacent neighboring 3-D switch  520  in a first X direction with increasing X coordinates (“X+ direction”), and a different adjacent neighboring 3-D switch  520  in a second X direction with decreasing X coordinates (“X− direction”), respectively. 
     A fourth set  25 Y 1  and a fifth set  25 Y 2  of router channels (“Y router channels”) interconnects the 3-D switch  520  with an adjacent neighboring 3-D switch  520  in a first Y direction with increasing Y coordinates (“Y+ direction”), and a different adjacent neighboring 3-D switch  520  in a second Y direction with decreasing Y coordinates (“Y− direction”), respectively. 
     A sixth set  25 Z 1  and a seventh set  25 Z 2  of router channels (“Z router channels”) interconnects the 3-D switch  520  with an adjacent neighboring 3-D switch  520  in a first Z direction with increasing Z coordinates (“Z+ direction”), and a different adjacent neighboring 3-D switch  520  in a second Z direction with decreasing Z coordinates (“Z− direction”), respectively. 
     For example, referring back to  FIG. 19 , switch S 111  is interconnected with adjacent neighboring switches S 211  in the X+ direction, S 011  in the X− direction, S 121  in the Y+ direction, S 101  in the Y− direction, S 112  in the Z+ direction, and S 110  in the Z− direction. 
       FIG. 21A  illustrates an example redundant routing system  550  for a 3-D processor array  625 , wherein the routing system  550  includes redundant data paths  30 R and a redundant plane  545 R, in accordance with an embodiment of the invention. In one embodiment, the array  625  ( FIG. 1 ) comprises a redundant routing system  550  for bypassing a component failure and facilitating full operation of the array  625 . The redundant routing system  550  is a multidimensional switch network that includes all components of the routing system  500  as described above and illustrated in  FIG. 19 . 
     The redundant routing system  550  further comprises additional 3-D switches  520 , such as 3-D switches R 00 , R 01 , R 02 , R 10 , R 11 , R 12 , R 20 , R 21 , and R 22 . These additional 3-D switches  520  are redundant 3-D switches  520 R. In one embodiment, the redundant 3-D switches  520  are organized into at least one redundant plane  545 R. A redundant plane  545 R may be an X-Y plane  540 , a Y-Z plane  545 , or a X-Z plane  546 . For example, the redundant plane  545 R shown in  FIG. 21A  is Y-Z plane  545 . A redundant plane  545 R may be disposed anywhere in the array  625 . In one embodiment, one component failure is bypassed using an entire redundant plane  545 R. 
     The redundant routing system  550  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  550 , a data path  30  is either a normal data path  30 N or a redundant data path  30 R. Redundant data paths  30 R are present throughout the array  625 . For ease of illustration, only enabled redundant data paths  30 R are shown in  FIG. 21A . A normal data path  30 N interconnects adjacent neighboring 3-D switches  520  (e.g., a data path  30 N interconnecting switch S 001  with adjacent neighboring switch S 101 ). By comparison, a redundant data path  30 R interconnects non-neighboring 3-D switches  520 . Each redundant data path  30 R provides an alternate pathway for routing around a component failure. 
     As shown in  FIG. 21A , redundant data paths  30 R interconnect 3-D switch S 100  with redundant 3-D switch R 00 , 3-D switch S 110  with redundant 3-D switch R 10 , 3-D switch S 120  with redundant 3-D switch R 20 , 3-D switch S 101  with redundant 3-D switch R 01 , 3-D switch S 111  with redundant 3-D switch R 11 , 3-D switch S 121  with redundant 3-D switch R 21 , 3-D switch S 102  with redundant 3-D switch R 02 , 3-D switch S 112  with redundant 3-D switch R 12 , and 3-D switch S 122  with redundant 3-D switch R 22 . 
     Each 3-D switch  520  exchanges packets with adjacent neighboring 3-D switches  520  via normal data paths  30 N. Some 3-D switches  520  may also exchange packets with non-neighboring 3-D switches  520  via redundant data paths  30 R. For example, as shown in  FIG. 21A , 3-D switch S 100  may exchange packets with non-neighboring redundant 3-D switch R 00  via at least one redundant data path  30 R. 
     As shown in  FIG. 21A , the third Y-Z plane  545  includes failed 3-D switch S 211 . To facilitate full operation of the array  625 , the third Y-Z plane  545  including failed 3-D switch S 211  is bypassed entirely using redundant data paths  30 R. As such, switches S 200 , S 201 , S 202 , S 210 , S 211 , S 212 , S 220 , S 221 , and S 222  of the third Y-Z plane  545  are not used to propagate packets. 
     As the third Y-Z plane  545  including failed 3-D switch S 211  is bypassed entirely, a redundant plane  545 R is used to recover the bypassed third Y-Z plane  545 . Even though only 3-D switch S 211  failed, each redundant 3-D switch  520 R of the redundant plane  545 R serves as a backup for a 3-D switch  520  of the bypassed third Y-Z plane  545 . For example, each redundant 3-D switch R 00 , R 01 , R 02 , R 10 , R 11 , R 12 , R 20 , R 21 , and R 22  of the redundant plane  545 R is used to recover 3-D switch S 200 , S 201 , S 202 , S 210 , S 211 , S 212 , S 220 , S 221 , and S 222  of the third Y-Z plane  545 , respectively. 
       FIG. 21B  illustrates an example redundant routing system  600  for a 3-D processor array  625 , wherein the routing system  600  includes diagonal data paths  30 D and a redundant plane  545 R, in accordance with an embodiment of the invention. In one embodiment, the array  625  ( FIG. 19 ) comprises a redundant routing system  600  for bypassing a component failure and facilitating full operation of the array  625 . The redundant routing system  600  is a multidimensional switch network. The redundant routing system  600  includes all components of the routing system  500  as described above and illustrated in  FIG. 19 . 
     The redundant routing system  600  further comprises additional 3-D switches  520 , such as 3-D switches R 00 , R 01 , R 02 , R 10 , R 11 , R 12 , R 20 , R 21 , and R 22 . These additional 3-D switches circuits  520  are redundant 3-D switches  520 R. In one embodiment, the redundant 3-D switches  520  are organized into at least one redundant plane  545 R. 
     The redundant routing system  600  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  600 , a data path  30  is a normal data path  30 N, a redundant data path  30 R, or a diagonal data path  30 D. Redundant data paths  30 R and diagonal data paths  30 D are present throughout the array  625 . For ease of illustration, only enabled redundant data paths  30 R and enabled diagonal data paths  30 D are shown in  FIG. 21B . A diagonal data path  30 D interconnects diagonally adjacent neighboring 3-D switches  520 . Each diagonal data path  30 D provides an alternate pathway for routing around a component failure. 
     As shown in  FIG. 21B , diagonal data paths  30 D interconnect redundant 3-D switch R 11  with 3-D switches S 201 , S 210 , S 212 , and S 221 . Further, a redundant data path  30 R interconnects 3-D switch S 111  with redundant 3-D switch R 11 . 
     As shown in  FIG. 21B , 3-D switch S 211  is a failed 3-D switch  520 . To facilitate full operation of the array  625 , failed 3-D switch S 211  is bypassed entirely using the diagonal data paths  30 D and the redundant data path  30 R. As such, 3-D switch S 211  is not used to propagate packets. A redundant 3-D switch  520 R of the redundant plane  545 R, such as redundant 3-D switch R 11 , serves as a backup for failed 3-D switch S 211 . 
       FIG. 22  illustrates an example redundant routing system  800  for a 3-D processor array  625 , wherein the routing system  800  includes only redundant data paths  30 R, in accordance with an embodiment of the invention. In one embodiment, the array  625  ( FIG. 1 ) comprises a redundant routing system  800  for bypassing a component failure. The redundant routing system  800  is a multidimensional switch network that includes all components of the routing system  500  as described above and illustrated in  FIG. 19 . 
     The redundant routing system  800  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  800 , each data path  30  is either a normal data path  30 N or a redundant data path  30 R. Redundant data paths  30 R are present throughout the array  625 . For ease of illustration, only enabled redundant data paths  30 R are shown in  FIG. 22 . 
     Each redundant data path  30 R interconnects non-neighboring switches  520  in different X-Y planes  540  ( FIG. 19 ), different Y-Z planes  545  ( FIG. 19 ), or different X-Z planes  546  ( FIG. 19 ). For example, as shown in  FIG. 22 , switches S 101  and S 121  in different X-Z planes  546  are interconnected via at least one redundant data path  30 R, switches S 011  and S 211  in different Y-Z planes  545  are interconnected via at least one redundant data path  30 R, and switches S 110  and S 112  in different X-Y planes  540  are interconnected via at least one redundant data path  30 R. 
     As shown in  FIG. 22 , switch S 111  is a failed switch. The redundant routing system  800  bypasses the switch S 111  and corresponding core circuit  10  using redundant data paths  30 R that interconnect switches in different X-Y planes  540 , different Y-Z planes  545 , or different X-Z planes  546 . 
     The number of component failures the redundant routing system  800  can bypass is up to one-half the size of the array  625 . The redundant routing system  800  does not utilize redundant core circuits  10 R or redundant routers  20 R. As such, the number of core circuits  10  that the array  625  logically represents is directly reduced by the number of bypassed core circuits  10 . 
     The redundant routing system  800  further comprises additional data paths  30  ( FIG. 1 ). In the redundant routing system  800 , a data path  30  is either a normal data path  30 N or a redundant data path  30 R. A normal data path  30 N interconnects adjacent neighboring 3-D switches  520  (e.g., a data path  30 N interconnecting switch S 001  with adjacent neighboring switch S 101 ). By comparison, a redundant data path  30 R interconnects non-neighboring 3-D switches  520 . Each redundant data path  30 R provides an alternate pathway for routing around a component failure. 
     As shown in  FIG. 22 , redundant data paths  30 R interconnect 3-D switch S 101  with 3-D switch S 121 , 3-D switch S 110  with 3-D switch S 112 , and 3-D switch S 011  with 3-D switch S 211 . 
     As shown in  FIG. 22 , the second Y-Z plane  545  includes failed 3-D switch S 111 . To facilitate operation of the array  625 , the failed 3-D switch S 111  is bypassed entirely using redundant data paths  30 R. As such, switch S 111  is not used to propagate packets. 
       FIG. 23  illustrates an example processor array  650  including multiple switches  20 , wherein each switch  20  is a communication interface to one or more core circuits  10 , in accordance with an embodiment of the invention. The array  650  comprises multiple processor core circuits  10 . As shown in  FIG. 23 , some of the core circuits  10  of the array  650  are physically labeled as core circuits C 00 , C 01 , C 02 , C 03 , C 04 , C 05 , C 06 , C 07 , C 10 , C 11 , C 12 , C 13 , C 14 , C 15 , C 16 , C 17 , C 20 , C 21 , C 22 , C 23 , C 24 , C 25 , C 26 , C 27 , C 30 , C 31 , C 32 , C 33 , C 34 , C 35 , C 36 , and C 37 . 
     The array  650  further comprises a routing system  665  for routing packets between the core circuits  10 . The routing system  665  includes multiple switches  20  and multiple data paths  30 . As shown in  FIG. 23 , the routing system  665  includes switches S 00 , S 01 , S 02 , S 03 , S 10 , S 11 , S 12 , S 13 , S 20 , S 21 , S 22 , S 23 , S 30 , S 31 , S 32 , and S 33 . As stated above, each switch  20  corresponds to one or more core circuits  10 . For example, as shown in  FIG. 23 , each switch  20  corresponds to two core circuits  10 . Switch S 00  in  FIG. 23 , for example, corresponds to core circuits C 00  and C 01 . 
     In one embodiment, for each switch  20 , the set  25 L of Local router channels ( FIG. 2 ) of said switch  20  is a communication interface to one or more corresponding core circuits  10 . For example, for each switch  20  in  FIG. 23 , the set  25 L of Local router channels  25 L of said switch  20  is a communication interface to two core circuits  10 . 
       FIG. 24  illustrates an example processor array  700  including multiple switches  20 , wherein each switch  20  has multiple sets  25 L of Local router channels, in accordance with an embodiment of the invention. The array  700  comprises multiple processor core circuits  10 . As shown in  FIG. 24 , some of the core circuits  10  of the array  700  are physically labeled as core circuits C 00 , C 01 , C 02 , C 03 , C 04 , C 05 , C 06 , C 07 , C 10 , C 11 , C 12 , C 13 , C 14 , C 15 , C 16 , C 17 , C 20 , C 21 , C 22 , C 23 , C 24 , C 25 , C 26 , C 27 , C 30 , C 31 , C 32 , C 33 , C 34 , C 35 , C 36 , C 37 , C 40 , C 41 , C 42 , C 43 , C 44 , C 45 , C 46 , C 47 , C 50 , C 51 , C 52 , C 53 , C 54 , C 55 , C 56 , and C 57 . 
     The array  700  further comprises a routing system  715  for routing packets between the core circuits  10 . The routing system  715  includes multiple switches  20  and multiple data paths  30 . As shown in  FIG. 24 , the routing system  715  includes switches S 00 , S 01 , S 02 , S 03 , S 10 , S 11 , S 12 , S 13 , S 20 , S 21 , S 22 , and S 23 . Each switch  20  corresponds to four core circuits  10 . Switch S 00  in  FIG. 24 , for example, corresponds to core circuits C 00 , C 01 , C 10 , and C 11 . 
       FIG. 25  illustrates an example configuration of a switch  20  in  FIG. 24 , in accordance with an embodiment of the invention. In one embodiment, for each switch  20 , said switch  20  is connected to each corresponding core circuit  10  via a set  25 L of Local router channels. 
     As stated above, each switch  20  in  FIG. 24  corresponds to four core circuits  10 . Accordingly, a first set  25 L 1  of Local router channels interconnects the switch  20  with a first corresponding core circuit  10 . A second set  25 L 2  of Local router channels interconnects the switch  20  with a second corresponding core circuit  10 . A third set  25 L 3  of Local router channels interconnects the switch  20  with a third corresponding core circuit  10 . A fourth set  25 L 4  of Local router channels interconnects the switch  20  with a fourth corresponding core circuit  10 . 
     Switch S 00  in  FIG. 24 , for example, is connected with core circuits C 00 , C 01 , C 10 , and C 11  via a first set  25 L 1 , a second set  25 L 2 , a third set  25 L 3 , and a fourth set  25 L 4  of Local router channels, respectively. 
     Also shown in  FIG. 25 , for each switch  20 , a set  25 N of North router channels interconnects said switch  20  with a north neighboring switch  20 , a set  25 S of South router channels interconnects said switch  20  with a south neighboring switch  20 , a set  25 E of East router channels interconnects said switch  20  with an east neighboring switch  20 , and a set  25 W of West router channels interconnects said switch  20  with a west neighboring switch  20 . 
       FIG. 26  is a high level block diagram showing an information processing system  300  useful for implementing one embodiment of the invention. The computer system includes one or more processors, such as processor  302 . The processor  302  is connected to a communication infrastructure  304  (e.g., a communications bus, cross-over bar, or network). 
     The computer system can include a display interface  306  that forwards graphics, text, and other data from the communication infrastructure  304  (or from a frame buffer not shown) for display on a display unit  308 . The computer system also includes a main memory  310 , preferably random access memory (RAM), and may also include a secondary memory  312 . The secondary memory  312  may include, for example, a hard disk drive  314  and/or a removable storage drive  316 , representing, for example, a floppy disk drive, a magnetic tape drive, or an optical disk drive. The removable storage drive  316  reads from and/or writes to a removable storage unit  318  in a manner well known to those having ordinary skill in the art. Removable storage unit  318  represents, for example, a floppy disk, a compact disc, a magnetic tape, or an optical disk, etc. which is read by and written to by removable storage drive  316 . As will be appreciated, the removable storage unit  318  includes a computer readable medium having stored therein computer software and/or data. 
     In alternative embodiments, the secondary memory  312  may include other similar means for allowing computer programs or other instructions to be loaded into the computer system. Such means may include, for example, a removable storage unit  320  and an interface  322 . Examples of such means may include a program package and package interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units  320  and interfaces  322 , which allows software and data to be transferred from the removable storage unit  320  to the computer system. 
     The computer system may also include a communication interface  324 . Communication interface  324  allows software and data to be transferred between the computer system and external devices. Examples of communication interface  324  may include a modem, a network interface (such as an Ethernet card), a communication port, or a PCMCIA slot and card, etc. Software and data transferred via communication interface  324  are in the form of signals which may be, for example, electronic, electromagnetic, optical, or other signals capable of being received by communication interface  324 . These signals are provided to communication interface  324  via a communication path (i.e., channel)  326 . This communication path  326  carries signals and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link, and/or other communication channels. 
     In this document, the terms “computer program medium,” “computer usable medium,” and “computer readable medium” are used to generally refer to media such as main memory  310  and secondary memory  312 , removable storage drive  316 , and a hard disk installed in hard disk drive  314 . 
     Computer programs (also called computer control logic) are stored in main memory  310  and/or secondary memory  312 . Computer programs may also be received via communication interface  324 . Such computer programs, when run, enable the computer system to perform the features of the present invention as discussed herein. In particular, the computer programs, when run, enable the processor  302  to perform the features of the computer system. Accordingly, such computer programs represent controllers of the computer system. 
     From the above description, it can be seen that the present invention provides a system, computer program product, non-transitory computer-useable storage medium, and method for implementing the embodiments of the invention. The non-transitory computer-useable storage medium has a computer-readable program, wherein the program upon being processed on a computer causes the computer to implement the steps of the present invention according to the embodiments described herein. References in the claims to an element in the singular is not intended to mean “one and only” unless explicitly so stated, but rather “one or more.” All structural and functional equivalents to the elements of the above-described exemplary embodiment that are currently known or later come to be known to those of ordinary skill in the art are intended to be encompassed by the present claims. No claim element herein is to be construed under the provisions of 35 U.S.C. section 112, sixth paragraph, unless the element is expressly recited using the phrase “means for” or “step for.” 
     The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. 
     The corresponding structures, materials, acts, and equivalents of all means or step plus function elements in the claims below are intended to include any structure, material, or act for performing the function in combination with other claimed elements as specifically claimed. The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the invention. The embodiment was chosen and described in order to best explain the principles of the invention and the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.