Fault-tolerant shuffle-exchange and de Bruijn networks capable of quick broadcasting

The construction of fault-tolerant processor arrays with shuffle-exchange or base-2 de Bruijn networks using an advanced spare-connection scheme for k-out-of-n redundancies called “generalized additional bypass linking” is described. The connection scheme uses bypass links with wired OR connections to spare processing elements (PEs) without external switches, and can reconfigure complete arrays by tolerating faulty portions in these PEs and links. The wired OR connections help to limit the number of connections to the spare PEs, and these connections are made so that the primary PEs are at an inter-PE distance of 3 or more away from each other and me connected to the same bypass link in parallel. The designs of spare-connections were formulated as a node coloring problem of a graph with a minimum distance of 3, and the chromatic numbers that correspond to the number of connections of spare PEs were evaluated by using a newly-devised coloring algorithm. The proposed scheme can be used for constructing various k-out-of-n configurations capable of quick broadcasting by using spare circuits, and is superior to conventional schemes in terms of extra PE connections and reconfiguration control