PaRS: fast and near-optimal grid-based cell sizing for library-based design

ABSTRACT

We propose PaRS, a parallel and randomized tool which solves the discrete gate sizing (cell sizing) problem on a grid. PaRS is formulated based on an optimization framework known as Nested Partitions which uses parallelism and randomization from a novel perspective to better identify the optimization direction. It achieves nearoptimal solutions for minimizing total power and area subject to meeting a delay constraint. The embarrassingly-parallel nature of PaRS makes it highly efficient. We show small algorithm run-times, in at most minutes for circuits with over 47,000 cells. We make comparison with the optimal solution generated by a custom and parallel branch-and-bound algorithm. Consequently, we are able to generate the optimal solution within hours. While the optimal algorithm uses up to 200 nodes in our grid, PaRS achieves its speedups and near-optimal solutions using only 20 nodes.

References

1. C-C.P. Chen, C. C. N. Chu, and D. F. Wong, "Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation," ICCAD, pp. 617--624, Nov 1998.
2. F. Beeftink, P. Kudva, D. Kung, and L. Stok, "Gate size selection for standard cell libraries," ICCAD, pp. 545--550, 1998.
3. H. Tennakoon, and C. Sechen, "Efficient and accurate gate sizing with piecewise convex delay models," DAC, pp. 807--812, Jun 2005.
4. J-P. Goux, S. Kulkarni, J. T. Linderoth, and M. E. Yoder, "Master-Worker: an enabling framework for applications on the computational grid," Cluster Computing, vol. 4, pp. 63--70, 2001.
5. J. P. Fishburn, and A. E. Dunlp, "TILOS: A posynomial programming approach to transistor sizing," TCAD, pp. 326--328, Nov 1985.
6. K. Kasamestty, M. Ketkar, and S. S. Sapatnekar, "A new class of convex functions for delay modeling and their application to the transistor sizing problem," TCAD, vol. 19, no. 7, pp. 779--788, Jul 2000.
7. L. Shi, and S. Ólafsson, "Nested partitions method for global optimization," Operations Research, vol. 48, no. 3, 2000.
8. O. Coudert, "Gate sizing for constrained delay/power/area optimization," TVLSI, vol. 5, no. 4, pp. 465--472, 1997.
9. S. Hu, M. Ketkar, and J. Hu, "Gate sizing for cell library-based designs," DAC, pp. 847--852, 2007.
10. S. S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang, "An exact solution to the transistor sizing problem for CMOS circuits using convex optimization," TCAD, vol. 12, no. 11, pp. 1621--1634, Nov 1993.
11. T. Tannenbaum, D. Wright, K. Miller, and M. Livny, "Condor -- A Distributed Job Scheduler," in Beowulf Cluster Computing with Linux, T. Sterling, Ed. MIT Press, October 2001.