Optimal placement by branch-and-price

ABSTRACT

Circuit placement has a large impact on all aspects of performance; speed, power consumption, reliability, and cost are all affected by the physical locations of interconnected transistors. The placement problem is NP-Complete for even simple metrics.In this paper, we apply techniques developed by the Operations Research (OR) community to the placement problem. Using an Integer Programming (IP) formulation and by applying a "branch-and-price" approach, we are able to optimally solve placement problems that are an order of magnitude larger than those addressed by traditional methods. Our results show that suboptimality is rampant on the small scale, and that there is merit in increasing the size of optimization windows used in detail placement.

REFERENCES

• 1: Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640022]
• 2: Ameya Agnihotri , Mehmet Can YILDIZ , Ateen Khatkhate , Ajita Mathur , Satoshi Ono , Patrick H. Madden, Fractional Cut: Improved Recursive Bisection Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.307, November 09-13, 2003 [doi>10.1109/ICCAD.2003.72]
• 3: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 4: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 5: Chin-Chih Chang , Jason Cong , Min Xie, Optimality and scalability study of existing placement algorithms, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119914]
• 6: Z. Chen and W. B. Powell. A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. European Journal of Operational Research, 116(1):220--232, 1999.
• 7: Martin Desrochers , Jacques Desrosiers , Marius Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, v.40 n.2, p.342-354, March–April 1992 [doi>10.1287/opre.40.2.342]
• 8: K. Doll, F. M. Johannes, and K. J. Antreich. Iterative placement improvement by network flow methods. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 13(10):1189--1200, 1994.
• 9: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 10: D. Hill. US patent 6,370,673: Method and system for high speed detailed placement of cells within an integrated circuit design, 2002.
• 11: Ateen Khatkhate , Chen Li , Ameya R. Agnihotri , Mehmet C. Yildiz , Satoshi Ono , Cheng-Kok Koh , Patrick H. Madden, Recursive bisection based mixed block placement, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981084]
• 12: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, May 1983.
• 13: J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 10(3):356--365, 1991.
• 14: Satoshi Ono , Patrick H. Madden, On structure and suboptimality in placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120864]
• 15: M. W. P. Savelsbergh. A branch-and-price algorithm for the generalized assignment problem. Operations Research, 6:831--841, 1997.
• 16: K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991 [doi>10.1145/103724.103725]
• 17: William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217531]
• 18: J.M. Van Den Akker , C.A.J. Hurkens , M.W.P. Savelsbergh, Time-Indexed Formulations for Machine Scheduling Problems: Column Generation, INFORMS Journal on Computing, v.12 n.2, p.111-124, April 2000 [doi>10.1287/ijoc.12.2.111.11896]
• 19: P. H. Vance, C. Barnhart, E. L. Johnson, and G. L. Nemhauser. Airline crew scheduling: A new formulation and decomposition algorithm. Operations Research, 45:188--200, 1997.
• 20: W. E. Wilhelm. A technical review of column generation in integer programming. Optimization and Engineering, 2:159--200, 2001.
• 21: 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]