Reconfiguration Classes and an Optimal Reconfiguration Method within a Reconfiguration Class

Noritaka SHIGEI  Hiromi MIYAJIMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E85-D   No.12   pp.1909-1917
Publication Date: 2002/12/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerance
processor array,  reconfiguration,  fault tolerant,  reconfiguration classes,  inclusion relation,  

Full Text: PDF(1.2MB)>>
Buy this Article

This paper considers a reconfiguration problem on a processor array model based on single-and-half-track switches, which is proposed for a fault tolerance technique at the fabrication time. The focus of this paper is to achieve the optimal reconfigurability, which means that whenever there exists a solution for successful reconfiguration, the designed method can find the solution. The paper consists of two parts. In the first part, we show two essential constraints that have been assumed in most of the previous studies, and make four reconfiguration classes that differ in the assumed essential constraints. Then, we present some inclusion relations among the four reconfiguration classes. As a result, it becomes clear that the most restrictive class including most of the previous methods never achieves the truly optimal reconfigurability. In the second part, we present a reconfiguration method based on sequential routing (RMSR). Although the worst-case time complexity of the RMSR is exponential in the number of processing elements, the reconfigurability of the RMSR is optimal within the most restrictive reconfiguration class. The effectiveness of the RMSR is shown by a computer simulation.