# zbMATH — the first resource for mathematics

Testing and reconfiguration of VLSI linear arrays. (English) Zbl 0902.68007
Summary: Achieving fault tolerance through incorporation of redundancy and reconfiguration is quite common. In this paper we study the fault tolerance of linear arrays of $$N$$ processors with $$k$$ bypass links whose maximum length is $$g$$. We consider both arrays with bidirectional links and unidirectional links. We first consider the problem of testing whether a set of $$n$$ faulty processors is catastrophic, i.e., precludes reconfiguration. We provide new testing algorithms which improve and generalize known testing algorithms. For bidirectional arrays we provide an $$O(kn)$$ time testing algorithm and for unidirectional arrays we provide an $$O(n)$$ time algorithm for the case $$k=1$$, and an $$O(kn\log k)$$ time algorithm, for the case $$k>1$$. When the fault pattern is not catastrophic we study the problem of finding an optimal reconfiguration of the array. We consider optimality with respect to two parameters: the size of the reconfigured array and the number of redundant links to activate. Considering optimality with respect to the size of the reconfigured array, we prove that the problem is NP-hard in the strong sense if the bypass links are bidirectional, while it can be solved in $$O(kng)$$ time if the bypass links are unidirectional. Considering optimality with respect to the number of bypass links to activate, we prove that the problem can be solved in $$O(kn)$$ time if the bypass links are bidirectional, and in $$O(kng)$$ time if the bypass links are unidirectional.

##### MSC:
 68M07 Mathematical problems of computer architecture 68M99 Computer system organization
Full Text:
##### References:
 [1] Belkhale, K.P.; Banerjee, P., Reconfiguration strategies in VLSI processor arrays, (), 418-421 [2] Bruck, J.; Cypher, R.; Ho, C., Tolerating faults in a mesh with a row of spare nodes, (), 12-19 [3] Chean, M.; Fortes, J.A.B., A taxonomy of reconfiguration techniques for fault-tolerant processor arrays, IEEE comput., 23, 55-69, (1990) [4] De Prisco, R.; De Santis, A., Catastrophic faults in reconfigurable VLSI linear arrays, Discrete appl. math., 75, 105-123, (1997) · Zbl 0879.68037 [5] De Prisco, R.; Monti, A., On reconfiguration of VLSI linear arrays, (), 553-564 [6] Garey, M.; Johnson, D., Computers and intractability, (1979), Freeman New York [7] Greene, J.W.; Gamal, A.E., Configuration of VLSI arrays in presence of defects, J. ACM, 31, 694-717, (1984) · Zbl 0632.94033 [8] Horowitz, E.; Sahni, S., Fundamentals of computer algorithms, (1978), Computer Science Press Rockville, MD · Zbl 0442.68022 [9] Hosseini, S.H., On fault-tolerant structure, distributed fault-diagnosis, reconfiguration, and recovery of the array processors, IEEE trans. comput., 38, 932-942, (1989) · Zbl 0682.68009 [10] Kaklamanis, C.; Karlin, A.R.; Leighton, F.T.; Milenkovic, V.; Raghavan, P.; Rao, S.; Thomborson, C.; Tsantilas, A., Asymptotically tight bounds for computing with faulty arrays of processors, (), 285-296 [11] Kung, H.T., Why systolic architecture?, IEEE comput., 15, 37-46, (1982) [12] Liu, M.T., Distributed loop computer network, Adv. comput., 17, 163-221, (1978) [13] Nayak, A., On reconfigurability of some regular architectures, () [14] Nayak, A.; Pagli, L.; Santoro, N., Efficient construction for VLSI reconfigurable arrays, Integration VLSI J., 15, 133-150, (1993) · Zbl 0808.94033 [15] Nayak, A.; Santoro, N., Bounds on performance of VLSI processor arrays, () · Zbl 0681.68076 [16] Nayak, A.; Santoro, N.; Tan, R., Fault-intolerance of reconfigurable systolic arrays, (), 202-209 [17] Negrini, R.; Sami, M.G.; Stefanelli, R., Fault-tolerance techniques for array structures used in supercomputing, IEEE comput., 19, 78-87, (1986) [18] Pagli, L.; Pucci, G., Counting the number of fault pattern in redundant VLSI arrays, Inform. process. lett., 50, 337-342, (1994) · Zbl 0796.94022 [19] () [20] Raghavendra, C.S.; Avizienis, A.; Ercgovac, M.D., Fault tolerance in binary tree architectures, IEEE trans. comput., C-33, 568-572, (1984) [21] Rosemberg, A.L., The diogenes approach to testable fault-tolerant arrays of processors, IEEE trans. comput., 32, 902-910, (1983) [22] Roychowdhury, V.P.; Bruck, J.; Kailath, T., Efficient algorithms for reconfiguration in VLSI/WSI arrays, IEEE trans. comput., 39, 480-489, (1990) [23] Sami, M.; Stefanelli, R., Reconfigurable architectures for VLSI processing arrays, (), 712-722
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.