An Improved Reconfiguration Method for Degradable Processor Arrays Using Genetic Algorithm

摘要

This paper addresses the NP-complete problem of reconfiguring two-dimensional degradable processor arrays under the row and column rerouting constraint. One promising approach to this problem is to treat the reconfiguration problem as a combinatorial optimization problem of finding the set of rerouting rules for all rows/columns and employ a genetic algorithm (GA) to obtain an optimal solution [1]. However, major drawback of this method is poor utilization of processing elements (PEs) in the reconfiguration process. In this paper, we improve the previous method [1] for efficient reconfiguration. The key idea is to treat the reconfiguration problem as an optimization problem of determining routing directions for all faulty PEs. A new rerouting scheme is also proposed to reroute logical rows/columns efficiently. Experimental study shows that the proposed method produces good results in terms of the percentage of harvest and degradation.