We propose a timing-driven discrete cell-sizing algorithm that can address total cell size and/or leakage power constraints. We model cell sizing as a “discretized” mincost network flow problem, wherein available sizes of each cell are modeled as nodes. Flow passing through a node indicates the choice of the corresponding cell size, and the total flow cost reflects the timing objective function value corresponding to these choices. Compared to other discrete optimization methods for cell sizing, our method can obtain near-optimal solutions in a time-efficient manner. We tested our algorithm on ISCAS’85 benchmarks, and compared our results to those produced by an optimal dynamic programming- (DP-) based method. The results show that compared to the optimal method, the improvements to an initial sizing solution obtained by our method is only 1% (3%) worse when using a 180？nm (90？nm) library, while being 40–60 times faster. We also obtained results for ISPD’12 cell-sizing benchmarks, under leakage power constraint, and compared them to those of a state-of-the-art approximate DP method (optimal DP runs out of memory for the smallest of these circuits). Our results show that we are only 0.9% worse than the approximate DP method, while being more than twice as fast. 1. Introduction In order to achieve a balance between design quality and time-to-market, cell library-based design is becoming the dominant design methodology over the custom design method even for high-performance ICs. Usually in a cell library, several different cell implementations are available for the same function with different sizes, intrinsic delays, driving resistances, and input capacitances. Choosing the cell with an appropriate size, that is, cell sizing, is a very effective approach to improve timing. The cell-sizing problem has been studied for a long time. Many methods [1, 2] assume the availability of a continuous range of cell sizes; that is, the size of a cell can take any value in a range. Then, the obtained gate size is rounded to the nearest available size in the library. However, a large number of realistic cell libraries are “sparse,” for example, geometrically spaced instead of uniformly spaced [3]. Geometrically spaced gate sizes are desired in order to cover a large size range with a relatively small number of cell instances. Also it has been proved in [4] that, under certain conditions, the set of optimal gate sizes must satisfy the geometric progression. With a sparse library, the simple rounding scheme can introduce huge deterioration from the continuous solution,
References
[1]
C. P. Chen, C. C. N. Chu, and D. F. Wong, “Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, no. 7, pp. 1014–1025, 1999.
[2]
J. Fishburn and A. Dunlop, “Tilos: a posynomial programming approach to transistor sizing,” in Proceedings of International Conference on Computer-Aided Design, pp. 326–328, 1985.
[3]
S. Hu, M. Ketkar, and J. Hu, “Gate sizing for cell library-based designs,” in Proceedings of the 44th ACM/IEEE Design Automation Conference (DAC '07), pp. 847–852, June 2007.
[4]
F. Beeftink, P. Kudva, D. Kung, and L. Stok, “Gate-size selection for standard cell libraries,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '98), pp. 545–550, November 1998.
[5]
O. Coudert, “Gate sizing for constrained delay/power/area optimization,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 5, no. 4, pp. 465–472, 1997.
[6]
M. M. Ozdal, S. Burns, and J. Hu, “Gate sizing and device technology selection algorithms for high-performance industrial designs,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '11), pp. 724–731, November 2011.
[7]
S. Dutt and H. Ren, “Discretized network flow techniques for timing and wire-length driven incremental placement with white-space satisfaction,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 19, no. 7, pp. 1277–1290, 2011.
[8]
H. Ren and S. Dutt, “A provably high-probability white-space satisfaction algorithm with good performance for standard-cell detailed placement,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 19, no. 7, pp. 1291–1304, 2011.
[9]
S. Dutt, H. Ren, F. Yuan, and V. Suthar, “A network-flow approach to timing-driven incremental placement for ASICs,” in Proceedings of the International Conference on Computer-Aided Design (ICCAD '06), pp. 375–382, November 2006.
[10]
U. Brenner, “VLSI legalization with minimum perturbation by iterative augmentation,” in Proceedings of Design, Automation & Test in Europe Conference & Exhibition (DATE '12), pp. 1385–1390, March 2012.
[11]
H. Ren and S. Dutt, “A network-flow based cell sizing algorithm,” in Proceedings of the 17th International Workshop on Logic & Synthesis, pp. 7–14, 2008.
[12]
S. Dutt and H. Ren, “Timing yield optimization via discrete gate sizing using globally-informed delay PDFs,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '10), pp. 570–577, November 2010.
[13]
H. Ren and S. Dutt, “Effective power optimization under timing and voltage-island constraints via simultaneous VDD, Vth assignments, gate sizing, and placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 5, pp. 746–759, 2011.
[14]
H. Ren and S. Dutt, “Algorithms for simultaneous consideration of multiple physical synthesis transforms for timing closure,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD '08), November 2008.
[15]
A. Nahapetyan and P. M. Pardalos, “A bilinear relaxation based algorithm for concave piecewise linear network flow problems,” Journal of Industrial and Management Optimization, vol. 3, no. 1, pp. 71–85, 2007.
[16]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, chapter 10-11, Prentice-Hall, Upper Saddle River, NJ, USA, 1993.
[17]
D. Kim and P. Pardalos, “Gate sizing in MOS digital circuits with linear programming,” in Proceedings of the Conference on European Design Automation (EURO-DAC '90), pp. 217–221, 1990.
[18]
R. K. Ahuja and J. B. Orlin, “Scaling network simplex algorithm,” Operations Research, vol. 40, supplement 1, pp. S5–S13, 1992.
[19]
I. Adler and N. Megiddo, “A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension,” Journal of the ACM, vol. 32, no. 4, pp. 871–895, 1985.
X. Yang, B. K. Choi, and M. Sarrafzadeh, “Timing-driven placement using design hierarchy guided constraint generation,” in Proceedings of the IEEE/ACM International Conference on Computer Aided Design (ICCAD '02), pp. 177–180, November 2002.
