More Web Proxy on the site http://driver.im/

research-article

A Study of Two Approaches for Reconfiguring Fault-Tolerant Systolic Arrays

Authors:

Clement W. Lam,

R. JayakumarAuthors Info & Claims

IEEE Transactions on Computers, Volume 38, Issue 6

Pages 833 - 844

https://doi.org/10.1109/12.24292

Published: 01 June 1989 Publication History

Abstract

Presents a critical study of two approaches, the classical RC-cut approach and H.T. Kung and M.S. Lam's (Proc. 1984 MIT Conf. Advanced Res. VLSI p.74-83, 1984) RCS-cut approach, for reconfiguring faulty systolic arrays. The amount of cell (processing element) redundancy needed to ensure successful reconfiguration into an n*n array is considered. It is shown that no polynomial bounded redundancy is sufficient for the classical approach, whereas O(n/sup 2/log n) redundancy is sufficient for the Kung and Lams approach. The number of faulty cells that can be tolerated in a given array regardless of their locations is characterized and derived. It is shown that, for both approaches, in almost all cases a square array has better fault tolerance than a rectangular array having the same number of cells. A minimal fault pattern in a 2n*2n array with 3n+1 faults that is not reconfigurable into an n*n array using either of the two approaches is established.

References

[1]

{1} B. Bollobas, Extremal Graph Theory. London, England: Academic, 1978, sect. VI.2, pp. 309-326.

[2]

{2} J. A. Fortes and C. S. Raghavendra, "Dynamically reconfigurable fault-tolerant processors," in Proc. 14th Int. Symp. Fault-Tolerant Comput., 1984, pp. 386-392.

[3]

{3} D. Fussell and P. Varman, "Fault-tolerant wafer-scale architectures for VLSI," in Proc. 9th Int. Symp. Comput. Architecture, Apr. 1982, pp. 190-198.

Digital Library

[4]

{4} J. W. Greene and A. El Gamal, "Area and delay penalties in restructurable wafer scale arrays," in Proc. 3rd Caltech Conf. VLSI, 1983, pp. 165-184.

[5]

{5} V. Gupta and A. Zorat, "On constructing a grid of processors for wafer scale integration," Tech. Rep. TR-83/061, Dep. Comput. Sci., S.U.N.Y., Stony Brook, New York, 1983.

[6]

{6} K. S. Hedlund, "Wafer scale integration of parallel processors," Tech. Rep. CSD-TR-422, Purdue Univ., 1982.

[7]

{7} I. Koren, "A reconfigurable and fault-tolerant VLSI multiprocessor array," in Proc. 8th Int. Symp. Comput. Architecture, May 1981, p. 442.

Digital Library

[8]

{8} K. H. K. Kuang and J. A. Abraham, "Low cost schemes for faulttolerance with processor arrays," in Proc. 9th Int. Symp. Comput. Architecture, 1982, pp. 330-337.

[9]

{9} H. T. Kung and M. S. Lam, "Fault-tolerance and two-level pipelining in VLSI systolic arrays, " in Proc. 1984 M. I. T. Conf. Advanced Res. VLSI, 1984, pp. 74-83.

[10]

{10} F. T. Leighton and C. E. Leiserson, "Wafer-scale integration of systolic arrays," IEEE Trans. Comput., vol. C-34, pp. 448-461, May 1985.

[11]

{11} H. F. Li, R. Jayakumar, and C. Lam, "Restructuring for fault-tolerant systolic arrays," IEEE Trans. Comput. vol. C-38, pp. 307-311, Feb. 1989. Also available as Tech. Rep. CCSD-VLSI-86-1, Dep. Comput. Sci., Concordia Univ., Montreal, Canada, 1986.

[12]

{12} T. E. Mangir and A. Avizienis, "Fault-tolerant designs for VLSI: Effect of interconnect requirements on yield improvement of VLSI designs," IEEE Trans. Comput., vol. C-31, pp. 609-615, July 1982.

[13]

{13} D. K. Pradhan and S. M. Reddy, "A fault-tolerant communication architecture for distributed systems," IEEE Trans. Comput., vol. C- 31, pp. 863-870, Sept. 1982.

[14]

{14} D. K. Pradhan, "Fault-tolerant architectures for multiprocessors and VLSI systems," in Proc. 13th Int. Symp. Fault-Tolerant Comput., 1983, pp. 436-441.

[15]

{15} D. K. Pradhan, "Dynamically restructurable fault-tolerant processor network architectures," IEEE Trans. Comput., vol. C-34, pp. 434-447, May 1985.

[16]

{16} A. L. Rosenberg, "The Diogenes approach to testable fault-tolerant array of processors," IEEE Trans. Comput., vol. C-32, pp. 902-910, Oct. 1983.

[17]

{17} M. Sami and R. Stefanelli, "Reconfigurable architectures for VLSI processing arrays," in Proc. Nat. Comput. Conf., 1983, pp. 565- 577.

Cited By

Qian JQiu KDing HZhang HZhai Z(2024)An Efficient Bottleneck Planes Exclusion Method for Reconfiguring 3D VLSI ArraysIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333996135:2(250-263)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TPDS.2023.3339961
Takanami IHorita TAkiba MTerauchi MKanno T(2016)A Built-in Self-repair Circuit for Restructuring Mesh-Connected Processor Arrays by Direct Spare ReplacementTransactions on Computational Science XXVII - Volume 957010.1007/978-3-662-50412-3_7(97-119)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/978-3-662-50412-3_7
Jigang WSrikanthan TWang X(2007)Integrated Row and Column Rerouting for Reconfiguration of VLSI Arrays with Four-Port SwitchesIEEE Transactions on Computers10.1109/TC.2007.108556:10(1387-1400)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1109/TC.2007.1085
Show More Cited By

Index Terms

A Study of Two Approaches for Reconfiguring Fault-Tolerant Systolic Arrays

Recommendations

A Fault-Tolerant Systolic Sorter

A fault-tolerant systolic sorter design is proposed. An algorithm-based fault tolerance is achieved by testing the invariants of a systolic sorter during normal operation. Transient and permanent computation errors can be detected by using error-...
Fault Tolerance in Linear Systolic Arrays Using Time Redundancy

A linear systolic array with fault-tolerant capabilities is described. Fault tolerance is achieved by using triple time redundancy. The array is capable of undergoing reconfiguration and can operate in a gracefully degradable mode. The concept of ...
Restructuring for Fault-Tolerant Systolic Arrays

The problem of restructuring systolic arrays with faulty cells is considered. An approach to derive the required data-flow paths and computational sites is proposed. The data skewing requirement, which must be satisfied to find an input schedule, is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 38, Issue 6

June 1989

170 pages

ISSN:0018-9340

Editor:
M. T. Liu
Ohio State Univ., Columbus

Issue’s Table of Contents

Copyright © Copyright © 1989 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 June 1989

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Qian JQiu KDing HZhang HZhai Z(2024)An Efficient Bottleneck Planes Exclusion Method for Reconfiguring 3D VLSI ArraysIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333996135:2(250-263)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TPDS.2023.3339961
Takanami IHorita TAkiba MTerauchi MKanno T(2016)A Built-in Self-repair Circuit for Restructuring Mesh-Connected Processor Arrays by Direct Spare ReplacementTransactions on Computational Science XXVII - Volume 957010.1007/978-3-662-50412-3_7(97-119)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/978-3-662-50412-3_7
Jigang WSrikanthan TWang X(2007)Integrated Row and Column Rerouting for Reconfiguration of VLSI Arrays with Four-Port SwitchesIEEE Transactions on Computers10.1109/TC.2007.108556:10(1387-1400)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1109/TC.2007.1085
Jigang WSrikanthan T(2006)Reconfiguration Algorithms for Power Efficient VLSI Subarrays with Four-Port SwitchesIEEE Transactions on Computers10.1109/TC.2006.4355:3(243-253)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1109/TC.2006.43
Jigang WThambipillai S(2003)A Run-time Reconfiguration Algorithm for VLSI ArraysProceedings of the 16th International Conference on VLSI Design10.5555/832285.835610Online publication date: 4-Jan-2003
https://dl.acm.org/doi/10.5555/832285.835610
Wu JThambipillai S(2003)On the reconfiguration algorithm for fault-tolerant VLSI arraysProceedings of the 2003 international conference on Computational science: PartIII10.5555/1762418.1762457(360-366)Online publication date: 2-Jun-2003
https://dl.acm.org/doi/10.5555/1762418.1762457
Jigang WSrikanthan T(2003)An improved reconfiguration algorithm for degradable VLSI/WSI arraysJournal of Systems Architecture: the EUROMICRO Journal10.1016/S1383-7621(03)00041-949:1-2(23-31)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1016/S1383-7621%2803%2900041-9
Jigang WSchröder HThambipillai S(2002)New Architecture and Algorithms for Degradable VLSI/WSI ArraysProceedings of the 8th Annual International Conference on Computing and Combinatorics10.5555/646720.702546(181-190)Online publication date: 15-Aug-2002
https://dl.acm.org/doi/10.5555/646720.702546
Horita TTakanami I(2000)Fault-Tolerant Processor Arrays Based on the 1$\frac{1}{2}$-Track Switches with Flexible Spare DistributionsIEEE Transactions on Computers10.1109/12.86221449:6(542-552)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1109/12.862214
Chang CMohapatra P(1998)An Efficient Method for Approximating Submesh Reliability of Two-Dimensional MeshesIEEE Transactions on Parallel and Distributed Systems10.1109/71.7359589:11(1115-1124)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1109/71.735958
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents