Self-restructuring Mesh-connected Processor Arrays through Spares on Moved Diagonals, Direct Replacement and Built-in Circuits

Volume 8, Issue 3, June 2023     |     PP. 91-117      |     PDF (2323 K)    |     Pub. Date: October 30, 2023
DOI: 10.54647/computer520386    83 Downloads     171337 Views  

Author(s)

Itsuo Takanami, Department of Technology in the former times, Yamaguchi University, Ube, Japan
Masaru Fukushi, Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Ube, Japan

Abstract
We present a self-reconfiguring scheme for N × N mesh-connected processor arrays (PAs) with N spares where faulty PEs are directly replaced by spare PEs functionally located on the diagonals which may be moved. This replacement is formalized as a matching problem in graph theory. Then, the necessary and sufficient condition that all the faulty PEs in a PA are replaced (repaired) at the same time is given. Using the condition, a restructuring algorithm is given. By computer simulation, it is shown that the survival rates and the probabilities of the arrays increase so much, comparing with those of the existing network structures with the same number of spare PEs. The scheme is realized by digital circuits which can be built in a PA. The scheme may be useful in enhancing especially the run-time reliability and availability of PAs in mission critical applications where first self-reconfiguration is required without an external host computer and manual maintenance operations.

Keywords
fault-tolerance, mesh array, direct replacement, self-restructuring, built-in circuit

Cite this paper
Itsuo Takanami, Masaru Fukushi, Self-restructuring Mesh-connected Processor Arrays through Spares on Moved Diagonals, Direct Replacement and Built-in Circuits , SCIREA Journal of Computer. Volume 8, Issue 3, June 2023 | PP. 91-117. 10.54647/computer520386

References

[ 1 ] L.W. Schaper, "Design of Multichip Modules," Proc. IEEE, Vol. 80, Issue 12, pp. 1955-1964, 1992.
[ 2 ] K. Okamoto, "Importance of Wafer Bonding for The Future Hype-Miniaturized CMOS Devices," ECS Transactions, Vol. 16, No.8, pp. 15-29, 2008.
[ 3 ] W.J. Dally and B. Towles, "Route Packets, Not Wires: On-chip Interconnection Networks," Proc. of the 38th Design Automation Conference, pp. 684-689, 2001, March, 2001.
[ 4 ] 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, Jan., 1989.
[ 5 ] E. Mangir and A. Avizienis, "Fault-Tolerant Design for VLSI: Effect of Interconnection Requirements on Yield Improvement of VLSI Designs," IEEE Trans. Comput., Vol.c-31, No.7, pp.609-615, July, 1982.
[ 6 ] R. Negrini, M.G. Sami and R. Stefanelli, "Fault-tolerance through reconfiguration of VLSI and WSI arrays," MIT Press series in computer systems, MIT Press, 1989.
[ 7 ] V.P. Roychowdhury, J. Bruck and T. Kailath, "Efficient Algorithms for Reconstruction in VLSI/WSI Array," IEEE Trans. Comput., Vol.39, No.4, pp.480-489, April, 1989.
[ 8 ] I. Koren and A.D. Singh, "Fault Tolerance in VLSI Circuits," IEEE Computer, Vol. 23, No. 7, pp.73-83, July, 1990.
[ 9 ] T.A. Varvarigou, V.P. Roychowdhury and T. Kailath, "Reconfiguring processor arrays using multiple-track models: the 3-tracks-1-spare-approach," IEEE Trans. Comput., Vol.42, No.11, pp. 1281–1293, Nov, 1993.
[ 10 ] R. Negrinii, M. Sami and R. Stefanelli, "Fault Tolerance Techniques for Array Structures Used in Supercomputing," IEEE Computer, Vol.19, No.2, pp.78-87, Feb, 1986.
[ 11 ] M. Sami and R. Stefanelli, "Reconfigurable Architectures for VLSI Processing Arrays," Proc. IEEE, pp.712-722, May, 1986.
[ 12 ] P. Mazumder and Y.S. Jih, "Restructuring of square processor arrays by Built-in Self-Repair Circuit," IEEE Trans. Comput. Aided Des., Vol.12, No.9, pp.1255-1265, Sep, 1993.
[ 13 ] I. Takanami, K. Kurata and T. Watanabe, "A Neural Algorithm for Reconstructing Mesh-Connected Processor Arrays Using Single-Track Switches," Proc. of Int’l Conf. on WSI, pp. 101-110, Jan, 1995.
[ 14 ] T. Horita and I. Takanami, "An FPGA Implementation of a Self-Reconfigurable System for the 1 Track-Switch 2-D Mesh Array with PE Faults," IEICE Trans. Inf. & Syst., Vol.E83-D, No.8, pp.1701-1705, Aug, 2000.
[ 15 ] S.Y. Lin, W.C. Shen, C.C. Hsu and A.Y. Wu, "Fault-tolerant router with built-in self-test/self-diagnosis and fault-isolation circuits for 2D-mesh based chip multiprocessor systems," Int. Jour. of Electrical Engineering., Vol. 16, No. 3, pp. 213-222, 2009.
[ 16 ] J. H. Collet, P. Zajac, M. Psarakis and D. Gizopoulos, "Chip Self-Organization and Fault-Tolerance in Massively Defective Multicore Arrays", IEEE Trans. on Dependable and Secure Computing, Vol. 8, No. 2, pp. 207-217, March, 2011.
[ 17 ] I. Takanami, "Self-Reconfiguring of 1-Track-Switch Mesh Arrays with Spares on One Row and One Column by Simple Built-in Circuit," IEICE Trans. Inf. & Syst., Vol.E87-D, No.10, pp.2318-2328”, Oct, 2004.
[ 18 ] I. Takanami and T. Horita, "A Built-in Circuit for Self-Repairing Mesh-Connected Processor Arrays by Direct Spare Replacement," Proc. of IEEE 18th Pacific Rim International Symposium on Dependable Computing, pp. 96-104, Nov, 2012.
[ 19 ] I. Takanami, T. Horita, M. Akiba, M. Terauchi and T. Kanno, "A Built-in Self-repair Circuit for Restructuring Mesh-Connected Processor Arrays by Direct Spare Replacement," Trans. on Computational Science XXVII, LNCS 9570, pp. 97-119, April, 2016.
[ 20 ] I. Takanami and M. Fukushi, "Self-restructuring of Mesh-Connected Processor Arrays with Spares Assigned on Rotated Orthogonal Sides," Trans. on Computational Science XXXVIII, LNCS 12620, pp. 36-53, 2021.
[ 21 ] I. Takanami and M. Fukushi, "A Built-in Circuit for Self-restructuring Mesh-Connected Processor Arrays with Spares on Diagonal," Trans. on Computational Science XXXIV, LNCS 11820, pp. 109-135, 2019
[ 22 ] J. Wu, L. Zhu, P. He and G. Jiang, "Reconfigurations for Processor Arrays with Faulty Switches and Links," Proc. of 15th IEEE/ACM Int. Symp. on Cluster, Cloud and Grid Computing, pp. 141-148, 2015.
[ 23 ] J. Qian, Z. Zhou, T. Gu, L. Zhao and L. Chang, "Optimal Reconfiguration of High-Performance VLSI Subarrays with Network Flow," IEEE Trans. On Parallel and Distributed Systems, pp. 3575-3587, Dec., 2016.
[ 24 ] J. Qian, F. Mo, H. Ding, Z. Zhou, L. Zhao and Z. Zai, "An improved algorithm for accelerating reconfiguration of VLSI array," Integration, Vol. 79, pp. 124-132, 2021.
[ 25 ] H. Ding, J. Qian, B. Huang, L. Zhao and Z. Zai, "Flexible scheme for reconfiguring 2D mesh-connected VLSI subarrays under row and column rerouting," Journal of Parallel and Distributed Computing, Vol. 151, pp. 1-12, 2021.
[ 26 ] H. Ding, J. Qian, L. Zao and Z. Zhai, "A high-performance VSLI array reconfiguration scheme based on network flow under row and column rerouting," Journal of Parallel and Distributed Computing, Vol. 158, pp. 176-185, 2021.