Counting the number of fault patterns in redundant VLSI arrays. (English) Zbl 0796.94022

Pagli, Linda; Pucci, Geppino

Inf. Process. Lett. 50, No. 6, 337-342 (1994).

Summary: In VLSI technology, redundancy is a commonly adopted technique to provide reconfiguration capabilities to regular architectures. This paper proves upper and lower bounds on the number of minimal fault patterns (minimal set of faulty processors) which affect a link-redundant linear array in an unrepairable way, for both the cases of bidirectional and unidirectional links.

MSC:

94C12	Fault detection; testing in circuits and networks
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

distributed systems; fault tolerance; parallel processing; performance evaluation; VLSI circuits; upper and lower bounds; number of minimal fault patterns

References:

[1]	Brlkhale, K.P.; Banerjee, P., Reconfiguration strategies in VLSI processor arrays, Proc. internat. conf. on computer aided design, 418-421, (1988)
[2]	Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, (1989), Addison-Wesley Reading, MA · Zbl 0668.00003
[3]	Greene, J.W.; Gamal, A., Configuration of VLSI arrays in the presence of defects, J. ACM, 31, 4, 694-717, (1984) · Zbl 0632.94033
[4]	Nayak, A., On reconfigurability of some regular architectures, ()
[5]	A. Nayak, L. Pagli and N. Santoro, Testing for catastrophic fault patterns in reconfigurable arrays with arbitrary link redundancy, IEEE Trans. Comput. Aided Design, submitted. · Zbl 0875.68157
[6]	Nayak, A.; Santoro, N.; Tan, R., Fault-intolerance of reconfigurable systolic arrays, Proc. 20th internat. symp. on fault tolerant computing, 202-209, (1990)