Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents a fast and accurate routing demand estimation called RUDY and its efficient integration in a force-directed quadratic placer to optimize placements for routability.

RUDY is based on a Rectangular Uniform wire DensitY per net and accurately models the routing demand of a circuit as determined by the wire distribution after final routing. Unlike published routing demand estimation, RUDY depends neither on a bin structure nor on a certain routing model to estimate the behavior of a router. Therefore RUDY is independent of the router.

Our fast and robust force-directed quadratic placer is based on a generic demand-and-supply model and is guided by the routing demand estimation RUDY to optimize placements for routability. This yields a placer which simultaneously reduces the routing demand in congested regions and increases the routing supply there. Therefore our placer fully utilizes the potential to optimize the routability. This results in the best published routed wirelength of the IBMv2 benchmark suite until now. In detail, our approach outperforms mPL, ROOSTER, and APlace by 9%, 8%, and 5%, respectively. Compared by the CPU times, which ROOSTER needs to place this benchmark, our routability optimization placer is eight times faster.

REFERENCES

• 1: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• 2: Maogang Wang, Xiaojian Yang, and Majid Sarrafzadeh. Congestion minimization during placement. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 19(10):1140--1148, oct 2000.
• 3: Jinan Lou, Shankar Krishnamoorthy, and Henry S. Sheng. Estimating routing congestion using probablistic analysis. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 21(1):32--41, January 2002.
• 4: Andrew B. Kahng , Xu Xu, Accurate pseudo-constructive wirelength and congestion estimation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639942]
• 5: Mehdi Saeedi , Morteza Saheb Zamani , Ali Jahanian, Prediction and reduction of routing congestion, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123023]
• 6: Jurjen Westra , Chris Bartels , Patrick Groeneveld, Probabilistic congestion prediction, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981110]
• 7: Ulrich Brenner , André Rohe, An effective congestion driven placement framework, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505391]
• 8: Ke Zhong , Shantanu Dutt, Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion control, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514129]
• 9: Xiaojian Yang , Ryan Kastner , Majid Sarrafzadeh, Congestion estimation during top-down placement, Proceedings of the 2001 international symposium on Physical design, p.164-169, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369761]
• 10: Xiaojian Yang, Ryan Kastner, and Majid Sarrafzadeh. Congestion estimation during top-down placement. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 21(1):72--80, January 2002.
• 11: Bo Hu , Malgorzata Marek-Sadowska, Congestion minimization during placement without estimation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.739-745, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774681]
• 12: Maogang Wang , Xiaojian Yang , Kenneth Eguro , Majid Sarrafzadeh, Multi-center congestion estimation and minimization during placement, Proceedings of the 2000 international symposium on Physical design, p.147-152, May 2000, San Diego, California, United States [doi>10.1145/332357.332391]
• 13: Maogang Wang , Majid Sarrafzadeh, On the behavior of congestion minimization during placement, Proceedings of the 1999 international symposium on Physical design, p.145-150, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300044]
• 14: Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]
• 15: Zhuoyuan Li , Weimin Wu , Xianlong Hong, Congestion driven incremental placement algorithm for standard cell layout, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119934]
• 16: Wenting Hou , Hong Yu , Xianlong Hong , Yici Cai , Weimin Wu , Jun Gu , William H. Kao, A new congestion-driven placement algorithm based on cell inflation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.605-608, January 2001, Yokohama, Japan [doi>10.1145/370155.370560]
• 17: Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
• 18: Xiaojian Yang, Bo-Kyung Choi, and Majid Sarrafzadeh. Routability-driven white space allocation for fixed-die standard-cell placement. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 22(4):410--419, April 2003.
• 19: Chen Li , Min Xie , Cheng-Kok Koh , J. Cong , P. H. Madden, Routability-driven placement and white space allocation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.394-401, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382607]
• 20: Chin-Chih Chang , Jason Cong , Zhigang (David) Pan, Physical hierarchy generation with routing congestion control, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505399]
• 21: Jarrod A. Roy , James F. Lu , Igor L. Markov, Seeing the forest and the trees: Steiner wirelength optimization in placemen, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123024]
• 22: C. Chu, FLUTE: fast lookup table based wirelength estimation technique, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.696-701, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382665]
• 23: Qinke Wang Andrew B. Kahng. Implementation and extensibility of an analytic placer. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(05):734--747, May 2005.
• 24: Ucla/umich physical design tools. http://vlsicad.eecs.umich.edu/BK/PDtools.
• 25: Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Routability driven white space allocation for fixed-die standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505400]
• 26: Raia T. Hadsell , Patrick H. Madden, Improved global routing through congestion estimation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775842]
• 27: Peter Spindler , Frank M. Johannes, Fast and robust quadratic placement combined with an exact linear net model, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233537]
• 28: K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17(3):219--229, November 1970.
• 29: Standard Performance Evaluation Corporation. SPEC CPU 2000. http://www.spec.org/cpu2000.