×

zbMATH — the first resource for mathematics

Catastrophic faults in reconfigurable systolic linear arrays. (English) Zbl 0879.68037
Summary: In regular architectures of identical processing elements, a widely used technique to improve the reconfigurability of the system consists of providing redundant processing elements and connections together with mechanisms of reconfiguration. In this paper we consider linear arrays of processing elements, with unidirectional bypass links of length \(g\). We study those sets of faulty processing elements, called catastrophic, which prevent the reconfiguration. We show that the number of catastrophic faults of \(g\) elements is equal to the \((g-1)\)th Catalan number. We also provide algorithms to rank and unrank all catastrophic sets of \(g\) faults. Finally, we describe a linear-time algorithm that generates all such sets of faults. Our results are useful to provide reliability estimates of linear arrays and for testing the behavior of reconfiguration strategies in the presence of catastrophic faults.

MSC:
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Abraham, J.A.; Fuchs, K., Fault and error models for VLSI, (), 639-654
[2] Balasubramanian, V.; Banerjee, P., A fault tolerant massively parallel processing architecture, J. parallel distributed comput., 4, 363-383, (1987)
[3] Barcucci, E.; Verri, M.C., Some more properties of Catalan numbers, Discrete math., 102, 229-237, (1992) · Zbl 0757.05005
[4] Belkhale, K.P.; Banerjee, P., Reconfiguration strategies in VLSI processor arrays, (), 418-421
[5] Brack, J.; Cypher, R.; Ho, C.-T., Fault-tolerant meshes with minimal number of spares, (), 288-295
[6] Chean, M.; Fortes, J.A.B., A taxonomy of reconfiguration techniques for fault-tolerant processor arrays, IEEE comput., 23, 55-69, (1990)
[7] Cole, R.; Maggs, B.; Sitaraman, R., A technique for reconfiguring arrays with faults, (), 561-572 · Zbl 1310.68045
[8] Reconfiguring arrays with faults, Part I: worst-case faults, SIAM J. Comput., to appear. · Zbl 0885.68011
[9] De Prisco, R.; Monti, A., Efficient testing and reconfiguration of catastrophic faults in linear arrays, (), 553-564
[10] Dutt, S.; Hayes, J.P., On designing and reconfiguring k-fault-tolerant tree architectures, IEEE trans. comput., C-39, 37-44, (1990)
[11] Dutt, S.; Hayes, J.P., Designing fault-tolerant systems using automorphisms, J. parallel distributed comput., 12, 249-268, (1991) · Zbl 0741.68018
[12] Fortes, J.A.B.; Raghavendra, C.S., Dynamically reconfigurable fault-tolerant array processors, (), 386-392
[13] Greene, J.W.; Gamal, A.E., Configuration of VLSI arrays in presence of defects, J. ACM, 31, 694-717, (1984) · Zbl 0632.94033
[14] Leighton, F.T.; Leiserson, C.E., Wafer scale integration of systolic arrays, IEEE trans. comput. C-34, 448-461, (1985) · Zbl 0558.94020
[15] Lin, Y.-C., New systolic arrays for the longest common subsequence problem, Parallel comput., 20, 1323-1334, (1994)
[16] Quinton, P.; Robert, Y., Systolic algorithms and architectures, (1991), Prentice-Hall Hertfordshire, UK
[17] Knuth, D.E., ()
[18] Kung, H.T., Why systolic architecture?, IEEE comput., 15, 37-46, (1982)
[19] Kung, H.T.; Lam, M., Fault-tolerant VLSI systolic arrays and two-level pipelining, J. parallel distributed processing, 32-63, (1984)
[20] Kuo, S.; Fuchs, W.K., Efficient spare allocation for reconfigurable arrays, IEEE design test, 24-31, (1987)
[21] Nayak, A., On reconfigurability of some regular architectures, ()
[22] Nayak, A.; Pagli, L.; Santoro, N., Recognition of catastrophic faults in reconfigurable arrays with arbitrary link redundancy, () · Zbl 0875.68157
[23] Nayak, A.; Santoro, N., Bounds on performance of VLSI processor arrays, () · Zbl 0681.68076
[24] Nayak, A.; Santoro, N.; Tan, R., Fault-intolerance of reconfigurable systolic arrays, (), 202-209
[25] Negrini, R.; Sami, M.G.; Stefanelli, R., Fault-tolerance techniques for array structures used in supercomputing, IEEE comput., 19, 78-87, (1986)
[26] Pagli, L.; Pucci, G., Reliability analysis of redundant VLSI arrays, Inform. process. lett., 50, 337-342, (1994) · Zbl 0796.94022
[27] ()
[28] Reingold, E.M.; Nievergelt, J.; Deo, N., Combinatorial algorithms: theory and practice, (1977), Prentice-Hall Englewood Cliffs, NJ · Zbl 0367.68032
[29] Robert, Y.; Tchuente, M., A systolic array for the longest common subsequence problem, Inform. process. lett., 21, 191-198, (1985) · Zbl 0578.68066
[30] Rogers, D.G., Pascal triangles, Catalan numbers and renewal arrays, Discrete math., 22, 301-310, (1278) · Zbl 0398.05007
[31] Rosenberg, A.L., The diogens approach to testable fault-tolerant arrays of processors, IEEE trans. comput., C-32, 902-910, (1983)
[32] Roychowdhury, V.P.; Brack, J.; Kailath, T., Efficient algorithms for reconfiguration in VLSI/WSI arrays, IEEE trans. comput., C-39, 480-489, (1990)
[33] Sami, M.; Stefanelli, R., Reconfigurable architectures for VLSI processing arrays, (), 712-722
[34] Shapiro, L.W., A Catalan triangle, Discrete math., 14, 83-90, (1976) · Zbl 0323.05004
[35] Youn, H.Y.; Singh, A.D., A highly efficient design for reconfiguring the processor array in VLSI, (), 375-382
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.