Pyramids: an efficient computational geometry-based approach for timing-driven placement

ABSTRACT

The purpose of global placement is to find non-overlapping locations for cells, typically while minimizing a wirelength objective. Because of this objective, however, when more timing information about the design is known, some cells will inevitably be sub-optimally placed from a timing perspective. In this paper, we present two new techniques to incrementally improve placements by moving cells to their optimal timing locations. We call our approach Pyramids, since it uses pyramid-shaped delay surfaces to solve for the optimal location, rather than running a more expensive linear programming solver. We show how to apply these techniques to timing-driven detailed placement and also for more accurate latestage incremental timing correction. Experimental results validate the effectiveness of Pyramids by showing significantly improved timing after an industrial placement algorithm. Furthermore, compared to the linear programming solvers, the speedup of Pyramids solver is 373x vs. CLP and 448x vs. GLPK.

REFERENCES

• 1: Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, Timing driven placement using physical net constraints, Proceedings of the 38th conference on Design automation, p.780-783, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379065]
• 2: Tim (Tianming) Kong, A novel net weighting algorithm for timing-driven placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.172-176, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774597]
• 3: Haoxing Ren , David Z. Pan , David S. Kung, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981070]
• 4: Wonjoon Choi , Kia Bazargan, Incremental Placement for Timing Optimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.463, November 09-13, 2003 [doi>10.1109/ICCAD.2003.84]
• 5: Qingzhou (Ben) Wang , John Lillis , Shubhankar Sanyal, An LP-based methodology for improved timing-driven placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120925]
• 6: Amit Chowdhary , Karthik Rajagopal , Satish Venkatesan , Tung Cao , Vladimir Tiourin , Yegna Parasuram , Bill Halpin, How accurately can we model timing in a placement engine?, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065792]
• 7: Tao Luo , David Newmark , David Z. Pan, A new LP based incremental timing driven placement for high performance designs, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147190]
• 8: David A. Papa , Tao Luo , Michael D. Moffitt , C. N. Sze , Zhuo Li , Gi-Joon Nam , Charles J. Alpert , Igor L. Markov, RUMBLE: an incremental, timing-driven, physical-synthesis optimization algorithm, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA [doi>10.1145/1353629.1353633]
• 9: COIN-OR linear programming, "https://projects.coin-or.org/clp,"
• 10: GNU Linear Programming Kit, "http://www.gnu.org/software/glpk/,"
• 11: Ralph H. J. M. Otten, Global wires: harmful?, Proceedings of the 1998 international symposium on Physical design, p.104-109, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274550]
• 12: C. J. Alpert and et. al., "Accurate estimation of global buffer delay within a floorplan," in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2006.
• 13: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 14: P. C. P. Saxena, N. Menezes and D. A. Kirkpatrick, "Repeater scaling and its impact on cad," in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2004.
• 15: OpenAccess, "http://openeda.si2.org/,"
• 16: Zhong Xiu , David A. Papa , Philip Chong , Christoph Albrecht , Andreas Kuehlmann , Rob A. Rutenbar , Igor L. Markov, Early research experience with OpenAccess gear: an open source development environment for physical design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055156]
• 17: OAGear:, "http://openedatools.si2.org/oagear/,"
• 18: Charles J. Alpert , Miloš Hrkić , Jiang Hu , Stephen T. Quay, Fast and flexible buffer trees that navigate the physical layout environment, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996575]