A polynomial time algorithm for reconfiguring the 1 1/2 track-switch model with PE and bus faults

As VLSI technology has developed, the interest in implementing an entire or significant part of a parallel computer system using wafer scale integration is growing. The major problem for the case is the possibility of drastically low yield and/or reliability of the system if there is no strategy for coping with such situations. Various strategies to restructure the faulty physical system into the fault-free target logical system are described in the literature. These restructures are performed using interconnection networks consisting of links and switches. Then the reliabilities of the systems depend on those of PEs and the interconnection networks. However, as far as we know, there are few studies considering the simultaneous faults of PEs and interconnection links. In this paper, by extending the Roychowdhury´s (1989) algorithm, we propose a polynomial time algorithm for reconfiguring the 1 1/2 track-switch model compensating for simultaneous PE and bus faults.