research-article

Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays

Authors:

V. P. Roychowdhury,

Jehoshua Bruck,

Thomas KailathAuthors Info & Claims

IEEE Transactions on Computers, Volume 39, Issue 4

Pages 480 - 489

https://doi.org/10.1109/12.54841

Published: 01 April 1990 Publication History

Publisher Site

Abstract

The issue of developing efficient algorithms for reconfiguring processor arrays in the presence of faulty processors and fixed hardware resources is discussed. The models discussed consist of a set of identical processors embedded in a flexible interconnection structure that is configured in the form of a rectangular grid. An array grid model based on single-track switches is considered. An efficient polynomial time algorithm is proposed for determining feasible reconfigurations for an array with a given distribution of faulty processors. In the process, it is shown that the set of conditions in the reconfigurability theorem is not necessary. A polynomial time algorithm is developed for finding feasible reconfigurations in an augmented single-track model and in array grid models with multiple-track switches.

References

[1]

{1} S. N. Jean and S. Y. Kung, "Necessary and sufficient conditions for reconfigurability in single-track switch WSI arrays," in Proc. Int. Conf. Wafer Scale Integration, Jan. 1989.

Google Scholar

[2]

{2} S. Y. Kung, VLSI Array Processors. Englewood Cliffs, NJ: Prentice-Hall, 1987.

Crossref

Google Scholar

[3]

{3} S. Y. Kung, S. N. Jean, and C. W. Chang, "Fault-tolerant array processors using single-track switches," IEEE Trans. Comput., vol. 38, no. 4, pp. 501-514, Apr. 1989.

Digital Library

Google Scholar

[4]

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

Google Scholar

[5]

{5} F. Lombardi, M. G. Sami, and R. Stefanelli, "Reconfiguration of VLSI arrays by covering," IEEE Trans. Comput.-Aided Design, 1989.

Digital Library

Google Scholar

[6]

{6} W. R. Moore, "A review of fault-tolerant techniques for the enhancement of integrated circuit yield," Proc. IEEE, pp. 684-698, May 1986.

Google Scholar

[7]

{7} C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982.

Digital Library

Google Scholar

[8]

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

Digital Library

Google Scholar

[9]

{9} M. Sami and R. Stefanelli, "Reconfigurable architectures for VLSI processing arrays," Proc. IEEE, pp. 712-722, May 1986.

Google Scholar

[10]

{10} D. P. Siewiorek and R. S. Swarz, The Theory and Practice of Reliable System Design. Bedford, MA: Digital, 1982.

Google Scholar

[11]

{11} L. Snyder, "Introduction to the configurable, highly parallel computer," IEEE Trans. Comput., vol. C-15, pp. 47-56, Jan. 1982.

Google Scholar

[12]

{12} S. K. Tewksbury, Wafer-Level Integrated Systems: Implementation Issues. New York: Kluwer Academic, 1989.

Google Scholar

[13]

{13} V. Roychowdhury, J. Bruck, and T. Kailath, "Efficient algorithms for reconfiguration in VLSI/WSI arrays," Tech. Rep., Stanfor Univ., Nov. 1989.

Google Scholar

[14]

{14} Y. Birk and J. B. Lotspiech, "On finding non-intersecting straight-line connections of grid points to the boundary," Tech. Rep. RJ 7217 (67984), IBM, Almaden Research Center, San Jose, CA, Dec. 1989.

Google Scholar

[15]

{15} J. W. Greene and A. El Gamal, "Configuration of VLSI arrays in the presence of defects," J. ACM, vol. 31, no. 4, pp. 694-717, Oct. 1984.

Digital Library

Google Scholar

Cited By

View all

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
Luo LWong MWakabayashi K(2009)On using SAT to ordered escape problemsProceedings of the 2009 Asia and South Pacific Design Automation Conference10.5555/1509633.1509771(594-599)Online publication date: 19-Jan-2009
https://dl.acm.org/doi/10.5555/1509633.1509771
Luo LWong MKyung CChoi KHa S(2008)Ordered escape routing based on Boolean satisfiabilityProceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356865(244-249)Online publication date: 21-Jan-2008
https://dl.acm.org/doi/10.5555/1356802.1356865
Show More Cited By

Index Terms

Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays
1. Hardware
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics

Recommendations

Computational Arrays with Flexible Redundancy

Different multiple redundancy schemes for fault detection and correction in computational arrays are proposed and analyzed. The basic idea is to embed a logical array of nodes onto a processor/switch array such that d processors, 1/spl les/d/spl les/4, ...
The Full-Use-of-Suitable-Spares (FUSS) Approach to Hardware Reconfiguration for Fault-Tolerant Processor Arrays

A general approach to hardware recognition is proposed for VLSI/WSI fault-tolerant processor arrays. The technique, called full use of suitable spares (FUSS), uses an indicator vector, the surplus vector, to guide the replacement of faulty processors ...
Efficient reconfiguration algorithms for degradable VLSI/WSI arrays

The development of efficient algorithms for constructing a flawless subarray from a defective VLSI/WSI (wafer scale integration) array is discussed. The array consists of identical elements such as processors or memory cells embedded in a switch lattice ...

Reviews

Reviewer: Walter G. Rudd

In this research paper, the authors derive new algorithms for reconfiguring interprocessor connections in a rectangular array of processors when some of the processors in the array are faulty. The idea is to reconfigure the connections so that, in effect, spare processors on the borders of the array are incorporated into the array, while preserving the geometry and connectivity of the array. The authors derive an efficient constructive algorithm for determining feasible reconfigurations, if any, for an array with a given distribution of faulty processors for grids with single-track switch models. The time complexity of this algorithm is quadratic in the number of faulty processors. To solve the more general cases of augmented single-track switch models and multiple-track switch models in an n × n grid of processors, the authors convert the problem to one of finding the maximum flow in a network constructed from the grid including the faulty processors. They derive a constructive algorithm for determining the feasibility of reconfiguring the connections, which has time complexity O ( n 3 ). This well-written document has a few inconsistencies in terminology, but they are not serious enough to interfere with the reader's comprehension of the material. It should interest anyone who works in the area of fault-tolerant networks.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

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 39, Issue 4

April 1990

188 pages

ISSN:0018-9340

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

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 April 1990

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Luo LWong MWakabayashi K(2009)On using SAT to ordered escape problemsProceedings of the 2009 Asia and South Pacific Design Automation Conference10.5555/1509633.1509771(594-599)Online publication date: 19-Jan-2009
https://dl.acm.org/doi/10.5555/1509633.1509771
Luo LWong MKyung CChoi KHa S(2008)Ordered escape routing based on Boolean satisfiabilityProceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356865(244-249)Online publication date: 21-Jan-2008
https://dl.acm.org/doi/10.5555/1356802.1356865
Chan WChin FTing HShmoys D(2000)Escaping a grid by edge-disjoint pathsProceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms10.5555/338219.338632(726-734)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.5555/338219.338632
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
Chan WChin F(2000)Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in GridsJournal of Algorithms10.1006/jagm.1999.105434:2(337-369)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.1006/jagm.1999.1054
John LJohn E(1998)A dynamically reconfigurable interconnect for array processorsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/92.6612576:1(150-157)Online publication date: 1-Mar-1998
https://dl.acm.org/doi/10.1109/92.661257
Chan WChin FSaks M(1997)Efficient algorithms for finding disjoint paths in gridsProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms10.5555/314161.314342(454-463)Online publication date: 5-Jan-1997
https://dl.acm.org/doi/10.5555/314161.314342
Hershberger JSuri SBoissonnat J(1997)Efficient breakout routing in printed circuit boardsProceedings of the thirteenth annual symposium on Computational geometry10.1145/262839.263082(460-462)Online publication date: 1-Aug-1997
https://dl.acm.org/doi/10.1145/262839.263082
Dutt SMahapatra N(1997)Node-covering, Error-correcting Codes and Multiprocessors with Very High Average Fault ToleranceIEEE Transactions on Computers10.1109/12.62048146:9(997-1015)Online publication date: 1-Sep-1997
https://dl.acm.org/doi/10.1109/12.620481
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Computational Arrays with Flexible Redundancy

The Full-Use-of-Suitable-Spares (FUSS) Approach to Hardware Reconfiguration for Fault-Tolerant Processor Arrays

Efficient reconfiguration algorithms for degradable VLSI/WSI arrays

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations