A fast general slew constrained minimum cost buffering algorithm

Abstract

As VLSI technology moves to the nanoscale regime, ultra-fast slew buffering techniques considering buffer cost minimization are highly desirable. The existing technique proposed in [S. Hu, C. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi, C.-N. Sze, Fast algorithms for slew constrained minimum cost buffering, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26 (11) (2007) 2009-2022] is able to efficiently perform buffer insertion with a simplified assumption on buffer input slew. However, when handling more general cases without input slew assumptions, it becomes slow despite the significant buffer savings. In this paper, a fast buffering technique is proposed to handle the general slew buffering problem. Instead of building solutions from scratch, the new technique efficiently optimizes buffering solutions obtained with the fixed input slew assumption. Experiments on industrial nets demonstrate that our algorithm is highly efficient. Compared to the commonly used van Ginneken style buffering, up to 49 × speed up is obtained and often 10% buffer area is saved. Compared to the algorithm without input slew assumption proposed in [S. Hu, C. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi, C.-N. Sze, Fast algorithms for slew constrained minimum cost buffering, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26 (11) (2007) 2009-2022], up to 37 × speedup can be obtained with slight sacrifice in solution quality. © 2009 Elsevier Ltd. All rights reserved.