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

research-article

Fault-Tolerant Processor Arrays Based on the 1$\frac{1}{2}$-Track Switches with Flexible Spare Distributions

Authors:

Tadayoshi Horita,

Itsuo TakanamiAuthors Info & Claims

IEEE Transactions on Computers, Volume 49, Issue 6

Pages 542 - 552

https://doi.org/10.1109/12.862214

Published: 01 June 2000 Publication History

Abstract

A mesh-connected processor array consists of many similar processing elements (PEs) which can be executed in both parallel and pipeline processing. For the implementation of an array of large numbers of processors, some fault-tolerant issues are necessary to enhance the (fabrication-time) yield and the (run-time) reliability. In this paper, we propose a fault-tolerant reconfigurable processor array using single-track switches like Kung et al.'s model in [1]. The reconfiguration process in our model is executed based on the concept of the compensation path like Kung et al.'s method, too. In our model, spare PEs are not necessarily put around the array, but are more flexibly put in the array by changing connections between spare PEs and nonspare PEs while retaining the connections among nonspare PEs in the same manner in Kung et al.'s model. The proposed model has such a desirable property that physical distances between logically adjacent PEs in the reconfigured array are within a constant, that is, independent of sizes of arrays. We show that the hardware overhead of the proposed model is a little greater than that of Kung et al.'s model, while the yield of the proposed model is much better than that of Kung et al.'s model.

References

[1]

S.Y. Kung S.N. Jean and C.W. Chang, “Fault-Tolerant Array Processors Using Single-Track Switches,” IEEE Trans. Computers, vol. 38, no. 4, pp. 501-514, Apr. 1989.

Digital Library

[2]

R.C. Aubusson and I. Catt, “Wafer-Scale Integration—A Fault-Tolerant Procedure,” IEEE J. Solid-State Circuits, vol. 13, no. 3, pp. 339-344, June 1978.

[3]

M.A. Fischetti, “Why Trilogy Dropped WSI,” IEEE Spectrum, p. 37, Oct. 1984.

[4]

J.R. Turnbull, “An Analysis of the Interconnection Problem for WSI,” Wafer Scale Integration, C. Jesshope and W. Moore., eds., pp. 24-30, Adam Hilger, 1986.

[5]

T.E. Mangir and A. Avizienis, “Fault-Tolerant Design for VLSI: Effect of Interconnection Requirements on Yield Improvement of VLSI Designs,” IEEE Trans. Computers, vol. 31, no. 7, pp. 609-615, July 1982.

Digital Library

[6]

A.L. Rosenberg, “The Diogenes Approach to Testable Fault-Tolerant Arrays of Processors,” IEEE Trans. Computers, vol. 32, no. 10, pp. 902-910, Oct. 1983.

Digital Library

[7]

T. Leighton and E. Leiserson, “Wafer-Scale Integration of Systoric Arrays,” IEEE Trans. Computers, vol. 34, no. 5, pp. 448-461, May 1985.

Digital Library

[8]

J.W. Greene and A.E. Gamal, “Configuration of VLSI Arrays in the Presence of Defects,” J. ACM, vol. 31, pp. 694-717, Oct. 1984.

Digital Library

[9]

M. Sami and R. Stefanelli, “Reconfigurable Architectures for VLSI Processing Arrays,” Proc. IEEE, pp. 712-722, May 1986.

[10]

M. Wang M. Cutler and S.Y.H. Su, “On-Line Error Detection and Reconfiguration of Array Processors with Two-Level Redundancy,” Proc. Compeuro '87, pp. 703-706, 1987.

[11]

S.Y. Kuo and W.K. Fuchs, “Efficient Spare Allocation for Reconfigurable Arrays,” IEEE Design and Test, pp. 24-31, Feb. 1987.

Digital Library

[12]

A.D. Singh, “Interstitial Redundancy: An Area Efficient Fault Tolerance Scheme for Large Area VLSI Processor Arrays,” IEEE Trans. Computers, vol. 37, no. 11, pp. 1,398-1,410, Nov. 1988.

Digital Library

[13]

F. Distante F. Lombardi and D. Sciuto, “Array Partitioning: A Methodology for Reconfigurability and Reconfiguration Problems,” Proc. Int'l Conf. Computer Design, pp. 564-567, 1988.

[14]

L. Jervis F. Lombardi and D. Sciuto, “Orthogonal Mapping: A Reconfiguration Strategy for Fault-Tolerant VLSI/WSI 2-D Arrays,” Proc. Int'l Workshop Defect Fault Tolerance VLSI Systems, vol. 7. 4, Oct. 1988.

[15]

C.W.H. Lam H.F. Li and R. Jakakumar, “A Study of Two Approaches for Reconfiguring Fault-Tolerant Systoric Arrays,” IEEE Trans. Computers, vol. 38, no. 6, pp. 833-844, June 1989.

Digital Library

[16]

J.H. Kim and S.M. Reddy, “On the Design of Fault-Tolerant Two-Dimensional Systoric Arrays for Yield Enhancement,” IEEE Trans. Computers, vol. 38, no. 4, pp. 515-525, Apr. 1989.

Digital Library

[17]

R. Negrini M.G. Sami and R. Stefanelli, Fault-Tolerance through Reconfiguration of VLSI and WSI Arrays. MIT Press, 1989.

[18]

I. Koren and A.D. Singh, “Fault Tolerance in VLSI Circuits,” Computer, pp. 73-83, July 1990.

Digital Library

[19]

M. Chean and J.A.B. Fortes, “The Full-Use-of-Suitable Spares (FUSS) Approach to Hardware Reconfiguration for Fault-Tolerant Processor Arrays,” IEEE Trans. Computers, vol. 39, no. 4, pp. 564-571, Apr. 1990.

Digital Library

[20]

S. Dutt and J.P. Hayers, “Some Practical Issues in the Design of Fault-Tolerant Multiprocessors,” IEEE Trans. Computers, vol. 41, no. 5, pp. 588-598, May 1992.

Digital Library

[21]

P. Mazumder and Y.S. Jih, “Restructing of Square Processor Arrays by Built-In Self-Repair Circuit,” IEEE Trans. Computer-Aided Design, vol. 12, no. 9, pp. 1,255-1,265, Sept. 1993.

Digital Library

[22]

J.H. Kim and P.K. Rhee, “The Rule-Based Approach to Reconfiguration of 2-D Processor Arrays,” IEEE Trans. Computers, vol. 42, no. 11, pp. 1,403-1,408, Nov. 1993.

Digital Library

[23]

S.K. Lu S.Y. Kuo and C.W. Wu, “Fault-Tolerant Interleaved Memory Systems with Two-Level Redundancy,” IEEE Trans. Computers, vol. 46, no. 9, pp. 1,028-1,034, Sept. 1997.

Digital Library

[24]

R. Mazzaferri and T.M. Murray, “The Connection Network Class for Fault-Tolerant Meshes,” IEEE Trans. Computers, vol. 44, no. 1, pp. 131-138, Jan. 1995.

Digital Library

[25]

Y.Y. Chen S.J. Upadhyaya and C.H. Cheng, “A Comprehensive Reconfiguration Scheme for Fault-Tolerant VLSI/WSI Array Processors,” IEEE Trans. Computers, vol. 46, no. 12, pp. 1,363-1,371, Dec. 1997.

Digital Library

[26]

C.P. Low and H.W. Leong, “On the Reconfiguration of Degradable VLSI/WSI Arrays,” IEEE Trans. Computer-Aided Design, vol. 16, no. 10, pp. 1,213-1,221, Oct. 1997.

Digital Library

[27]

F. Distante M.G. Sami and R. Stefanelli, “Reconfiguration Techniques in the Presence of Faulty Interconnections,” Proc. Int'l Conf. WSI, pp. 379-388, 1989.

[28]

N. Lopez-Benitez and J.A.B. Fortes, “Detailed Modeling and Reliability Analysis of Fault-Tolerant Processor Arrays,” IEEE Trans. Computers, vol. 41, no. 9, pp. 1,193-1,200, Sept. 1992.

Digital Library

[29]

M.D. Smith and P. Mazumder, “Generation of Minimal Vertex Covers for Row/Column Allocation in Self-Repairable Arrays,” IEEE Trans. Computers, vol. 45, no. 1, pp. 109-115, Jan. 1996.

Digital Library

[30]

V.P. Roychowdhury J. Bruck and T. Kailath, “Efficient Algorithms for Reconstruction in VLSI/WSI Array,” IEEE Trans. Computers, vol. 39, no. 4, pp. 480-489, Apr. 1989.

Digital Library

[31]

T.A. Varvarigou V.P. Roychowdhury and T. Kailath, “A Polynomial Time Algorithm for Reconfiguring Multiple-Track Models,” IEEE Trans. Computers, vol. 42, no. 4, pp. 385-395, Apr. 1993.

Digital Library

[32]

T.A. Varvarigou V.P. Roychowdhury and T. Kailath, “Reconfiguring Processor Arrays Using Multiple-Track Models: The 3-Tracks-1-Spare-Approach,” IEEE Trans. Computers, vol. 42, no. 11, pp. 1,281-1,293, Nov. 1993.

Digital Library

[33]

J.S.N. Jean H.C. Fu and S.Y. Kung, “Yield Enhancement for WSI Array Processors Using Two-and-Half-Track Switches,” Proc. IEEE Int'l Conf. WSI, pp. 243-250, 1990.

[34]

I. Numata and S. Horiguchi, “Reconfigurable Architectures for Mesh-Interconnected Multiprocessor System,” IEICE Technical Report WSI92, no. 6, Aug. 1992.

[35]

I. Takanami K. Kurata and T. Watanabe, “A Neural Algorithm for Reconstructing Mesh-Connected Processor Arrays Using Single-Track Switches,” Proc. Int'l Conf. WSI, pp. 101-110, Jan. 1995.

[36]

T. Horita and I. Takanami, “A Built-In Self-Reconstruction Approach for Partitioned Mesh-Arrays Using Neural Algorithm,” IEICE Trans. Information and Systems, vol. E79-D, no. 8, pp. 1,160-1,167, Aug. 1996.

[37]

I. Takanami T. Watanabe Y. Hisanaga and K. Inoue, “Fault Tolerant Mesh-Connected Parallel Computers with Spares on the Diagonal,” IEICE Technical Report CPSY-61, FTS91-60, pp. 69-76, Dec. 1991.

[38]

M.M. Bae and B. Bose, “Spare Processor Allocation for Fault Tolerance in Torus-Based Multicomputers,” Proc. IEEE Int'l Symp. Fault-Tolerant Computing (FTCS-26), pp. 282-291, June 1996.

Digital Library

[39]

T. Horita and I. Takanami, “A Note on Distributions of Spare Processors and Array Yields for the 11/2 Track-Switch Model,” IEICE Technical Report FIIS98, no. 39, pp. 1-8, Sept. 1998.

[40]

N. Shigei H. Miyajima and S. Murashima, “On Efficient Spare Arrangements and an Algorithm with Relocating Spares for Reconfiguring Processor Arrays,” IEICE Trans., vol. E80-A, no. 6, pp. 988-995, June 1997.

[41]

L.M. J and J. Grinberg, The 3-D Computer: An Integrated Stack of WSI Wafers, in Wafer Scale Integration, pp. 253-317. Kluwer Academic, 1989.

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
Liu CChu CXu DWang YWang QLi HLi XCheng K(2022)HyCA: A Hybrid Computing Architecture for Fault-Tolerant Deep LearningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.312476341:10(3400-3413)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TCAD.2021.3124763
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
Show More Cited By

Index Terms

Fault-Tolerant Processor Arrays Based on the 1$\frac{1}{2}$-Track Switches with Flexible Spare Distributions
1. Hardware

Recommendations

Fault Tolerant Processor Arrays Based on 1 1/2-Track Switch with Generalized Spare Distributions
ISPAN '99: Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks

As VLSI technology has developed, the interest in implementing an entire or significant part of a parallel computer system using wafer scale integration is growing. The major problem for the case is the possibility of drastically low yield and/or ...
An Analysis for Fault-Tolerant 3D Processor Arrays Using 1.5-Track Switches

This paper deals with redundant 3D mesh processor arrays using 1.5-track switches, considering track and switch faults together with processor faults. Four variants are defined based on the distributions of spare PEs, and arrays of three variants have ...
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, ...

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 49, Issue 6

June 2000

92 pages

ISSN:0018-9340

Editors:
Jean-Luc Gaudiot
Univ. of Southern California, Los Angeles
,
Fabrizio Lombardi
Northeastern Univ., Boston, MA
,
Mariagiovanna Sami
Politecnico Milano, Milan, Italy

Issue’s Table of Contents

Copyright © Copyright © 2000 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 June 2000

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 29 Jan 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
Liu CChu CXu DWang YWang QLi HLi XCheng K(2022)HyCA: A Hybrid Computing Architecture for Fault-Tolerant Deep LearningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.312476341:10(3400-3413)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TCAD.2021.3124763
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
Guiyuan Jiang Jigang Wu Yajun Ha Yi Wang Jizhou Sun (2015)Reconfiguring Three-Dimensional Processor Arrays for Fault-Tolerance: Hardness and Heuristic AlgorithmsIEEE Transactions on Computers10.1109/TC.2015.238984664:10(2926-2939)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TC.2015.2389846
Wu JJiang GShen YLam SSun JSrikanthan T(2014)Parallel reconfiguration algorithms for mesh-connected processor arraysThe Journal of Supercomputing10.1007/s11227-014-1096-y69:2(610-628)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/s11227-014-1096-y
Jiang GWu JSun J(2013)Efficiency of Flexible Rerouting Scheme for Maximizing Logical ArraysProceedings of the 10th IFIP International Conference on Network and Parallel Computing - Volume 814710.1007/978-3-642-40820-5_17(194-206)Online publication date: 19-Sep-2013
https://dl.acm.org/doi/10.1007/978-3-642-40820-5_17
Horita TTakanami I(2011)An FPGA-based fault-tolerant 2D systolic array for matrix multiplicationsTransactions on computational science XIII10.5555/2028176.2028183(108-124)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2028176.2028183
Pani DSecchi SRaffo LAmato NFranke HKelly P(2010)Self organization on a swarm computing fabricProceedings of the 7th ACM international conference on Computing frontiers10.1145/1787275.1787343(327-336)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1145/1787275.1787343
Horita TKatou YTakanami I(2008)An Analysis for Fault-Tolerant 3D Processor Arrays Using 1.5-Track SwitchesIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1093/ietfec/e91-a.2.623E91-A:2(623-632)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1093/ietfec/e91-a.2.623
Jalili SMovaghar ASadrmousavi MWainer G(2007)An improved replacement algorithm in fault-tolerant meshesProceedings of the 2007 Summer Computer Simulation Conference10.5555/1357910.1357980(443-448)Online publication date: 16-Jul-2007
https://dl.acm.org/doi/10.5555/1357910.1357980
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents