Since components faults occurring at arbitrary places (primarily on the links) affect seriously network performance and reliability, the multicomputers operating in harsh environments should be designed to guarantee normal network-missions in presence of those faults. One solution to the end is a fault-tolerant routing scheme, which enables messages to safely reach their destinations avoiding failed links when transmission of messages is blocked by certain faults. In the paper, we develop a fault-tolerant routing algorithm with deadlock freedom in an n-dimensional meshed network, and validate its efficiency and effectiveness through proper simulations. The aspects of fault-tolerance is adopted by appending partial-adaptiveness and detouring to the e-cube algorithm, while using a wormhole routing for the backbone routing method. The phenomenon of deadlock incurred due to its adaptiveness is eliminated by classifying a physical channel into a couple of virtual channels.

The authors previously proposed a reconfigurable architecture called the "XL-scheme" in order to cope with processor element (PE) faults as well as link faults. However, they described an algorithm for compensating only for link faults. They determined the potential ability to tolerate faults of the XL-scheme for simultaneous faults of links and PEs, and left a reconstruction algorithm for simultaneous PE and link faults to be studied in the future. This paper briefly explains the XL-scheme and gives a reconstruction algorithm for simultaneous PE and link faults. The algorithm first replaces faulty PEs with healthy ones and then replaces faulty links with healthy ones. We then compute the reliabilities of the mesh-arrays with simultaneous PE and link faults by simulation. We compare the reliability of the XL-scheme with that of the one-and-half track switch model. It is seen that the former is much larger than the latter. Furthermore, we show the result for processing time.