We propose a model for fault tolerant 3D processor arrays using one-and-half track switches. Spare processors are laid on the two opposite surfaces of the 3D array. The fault compensation process is performed by shifting processors on a continuous straight line from a faulty processor to a spare on the surfaces. Two opposite directions are allowed for compensation paths only which they are not in the near-miss relation. Then, switches with only 4 states are needed to preserve the 3D mesh topology after compensating faults. We give an algorithm in a convenient form for reconfiguring by hardware the 3D mesh arrays with faults and show the survival rates and the probabilities of them by computer simulation. The probabilities are compared with those of the case using double tracks which have no restriction of the near-miss relation. The algorithm can reconfigure the 3D mesh arrays in polynomial time. Finally, we design a logical circuit for hardware realization of the algorithm. This will be able to make us build such a built-in self-reconfigurable 3D mesh array that the reconfiguration can be done very quickly.
展开▼