Lower Bound Estimation of Hardware Resources for Scheduling in High-Level Synthesis

In high-level synthesis of VLSI circuits, good lower bound prediction can efficiently narrow down the large space of possible designs. Previous approaches predict the lower bound by relaxing or even ignoring the precedence constraints of the data flow graph (DFG), and result in inaccuracy of the lower bound. The loop folding and conditional branch were also not considered. In this paper, a new stepwise refinement algorithm is proposed, which takes consideration of precedence constraints of the DFG to estimate the lower bound of hardware resources under time constraints. Processing techniques to handle multi-cycle, chaining, pipelining, as well as loop folding and mutual exclusion among conditional branches are also incorporated in the algorithm. Experimental results show that the algorithm can produce a very tight and close to optimal lower bound in reasonable computation time. Shen Zhaoxuan received the B.Sc. degree in computer science from Zhejiang University, China and the M.Eng. degree in electrical and electronic engineering from Nanyang Technological University, Singapore. From August 1987 to January 1994, he was a research associate at Laboratory of CAD & Graphics, Institute of Computing Technologies, Chinese Academy of Sciences, Beijing, China. During 1996–1999, he was a senior engineer at Institute of High Performance Computing Singapore, developing parallel optimization algorithm for VLSI floorplanning, placement and synthesis, etc. He was a senior software engineer at Arcadia Design Systems, Inc. San Jose, CA, USA from March. 1999 to November 2000 and a senior engineer at Synopsys Inc. Mountain View, CA, USA from December 2000 to January 2002. He is now with Cadence Design Systems Inc. San Jose, CA, USA, developing new generation of P&R tools for SOC VLSI design. Dr. Shen received the 1991 First Class Science & technology Progressing Award from Chinese Academy of Sciences for the contribution to the EDCADS tool development. He has been an IEEE member since 1996. Jong Ching Chuen received the BSc (Eng) degree in electronics with computer science and the PhD degree in electronic engineering from Queen Mary College, University of London, U.K., in 1983 and 1988 respectively. From July 1987 to October 1990, he worked in the area of high-level synthesis of digital systems first in University of Southampton, U.K. and then in Racal Research Limited, U.K. In 1991, he joined the Nanyang Technological University, Singapore, as a faculty member. He is now an associate professor in the Division of Circuits and Systems, School of Electrical and Electronic Engineering. Dr. Jong is a chartered engineer, a member of IEE and a member of BCS. His technical interests include high-level synthesis, ASIC design and fast-prototyping of digital designs.