Circuit-wise buffer insertion and gate sizing algorithm with scalability

Most existing buffer insertion algorithms, such as van Ginneken´s algorithm, consider individual nets and therefore often result in high buffer cost due to lack a global view. Thus, circuit-wise buffering is necessary to reduce buffer cost. Recently, some circuit-wise buffering algorithms are proposed. However, these algorithms are based on heuristics which are not scalable in handling large circuits. In this paper, we present a scalable circuit-wise algorithm with three novel features. (1) A linear modeling of nonlinear delay versus cost tradeoff. Due to the similar nature of buffer insertion and gate sizing, gate sizing is handled in such a manner. (2) A dynamic critical sink selection procedure to solve multiple-sink net. Multiple-sink nets have been problems for previous circuit-wise buffering algorithms. (3) A circuit partition technique to divide the circuit into sub-circuits and apply divide-and-conquer scheme. This technique provides high scalability for the algorithm. Experiments on ISCAS85 circuits show that the new algorithm achieves 17X speedup compared with Sze´s path based algorithm. In the meantime, it saves 16.0% buffer cost and 4.9% gate cost without increasing circuit delay. Furthermore, the running time of a testcase in ITC99 with approximate one hundred thousand gates is less than 11 minutes, which demonstrates the scalability of the new algorithm.