Power Efficient Sub-Array in Reconfigurable VLSI Meshes

Given an m × n mesh-connected VLSI array with some faulty elements, the reconfiguration problem is to find a maximum-sized fault-free sub-array under the row and column rerouting scheme. This problem has already been shown to be NP-complete. In this paper, new techniques are proposed, based on heuristic strategy, to minimize the number of switches required for the power efficient sub-array. Our algorithm shows that notable improvements in the reduction of the number of long interconnects could be realized in linear time and without sacrificing on the size of the sub-array. Simulations based on several random and clustered fault scenarios clearly reveal the superiority of the proposed techniques. Ji-Gang Wu has been with Nanyang Technological University (NTU), Singapore, since 2000. He is currently a research fellow in Centre for High Performance Embedded Systems. He received his B.S. degree in computational mathematics from Lanzhou University (China) in 1983 and his Ph.D. degree in computer software and theory from University of Science and Technology of China. He was an assistant professor and lecturer in Lanzhou University from 1983 to 1993. He was an associate professor in Yantai University (China) from 1993 to 2000. His research interests include VLSI design, hardware/software co-design and parallel computing. Thambipillai Srikanthan has been with Nanyang Technological University (NTU), Singapore, since 1991, where he holds a joint appointment as Professor and Director of the Centre for High Performance Embedded Systems. He received his B.Sc. degree (Hons) in computer and control systems and Ph.D. degree in system modelling and information systems engineering from Coventry University, United Kingdom. His research interests include system integration methodologies, architectural translations of compute intensive algorithms, high-speed techniques for image processing and dynamic routing. He is a corporate member of the IEE and a senior member of the IEEE.