Maximum reconfiguration of 2-D mesh systems with faults
Nian-Feng Tzeng, Guanghua Lin · 2002
It is desirable to reconfigure a faulty system in a way that the system size after reconfiguration is maximized while reconfiguration hardware overhead is kept low. This paper proposes a maximum reconfiguration scheme for 2-D mesh systems by retaining as many fault-free nodes in reconfigured subsystems as possible. The basic idea is to reconfigure a faulty mesh system into a maximum convex subsystem, using the fault-free upper or lower boundary nodes to compensate for the internal (i.e., non-boundary) faulty nodes. To this end, our reconfiguration problem is transformed into the well-known min-cost flow problem, for which an efficient polynomial algorithm is introduced. Our reconfiguration requires a channel width of two only and is shown by simulation to exhibit much better utilization of fault-free nodes than other schemes.