A multilevel analytical placement for 3D ICs

ABSTRACT

In this paper we propose a multilevel non-linear programming based 3D placement approach that minimizes a weighted sum of total wirelength and TS via number subject to area density constraints. This approach relaxes the discrete layer assignments so that they are continuous in the z-direction and the problem can be solved by an analytical global placer. A key idea is to do the overlap removal and device layer assignment simultaneously by adding a density penalty function for both area & TS via density constraints. Experimental results show that this analytical placer in a multilevel framework is effective to achieve trade-offs between wirelength and TS via number. Compared to the recently published transformation-based 3D placement method [1], we are able to achieve on average 12% shorter wirelength and 29% fewer TS via compared to their cases with best wirelength; we are also able to achieve on average 20% shorter wirelength and 50% fewer TS via number compared to their cases with best TS via numbers.

REFERENCES

• 1: Jason Cong , Guojie Luo , Jie Wei , Yan Zhang, Thermal-Aware 3D IC Placement Via Transformation, Proceedings of the 2007 conference on Asia South Pacific design automation, p.780-785, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.358084]
• 2: Brent Goplen , Sachin Sapatnekar, Efficient Thermal Placement of Standard Cells in 3D ICs using a Force Directed Approach, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.86, November 09-13, 2003 [doi>10.1109/ICCAD.2003.60]
• 3: Brent Goplen , Sachin Spatnekar, Placement of 3D ICs with thermal and interlayer via considerations, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278637]
• 4: Gi-Joon Nam, ISPD 2006 Placement Contest: Benchmark Suite and Results, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123042]
• 5: Haixia Yan , Qiang Zhou , Xianlong Hong, Efficient Thermal Aware Placement Approach Integrated with 3D DCT Placement Algorithm, Proceedings of the 9th international symposium on Quality Electronic Design, p.289-292, March 17-19, 2008
• 6: G.-J. Nam and J. Cong, "Modern Circuit Placement: Best Practices and Results," Springer, New York, 2007.
• 7: J. Cong and J. Shinnerl, "Multilevel Optimization in VLSICAD," Kluwer Academic Publishers, Boston, 2003.
• 8: J. Cong and M. Xie, "A Robust Mixed-Size Legalization and Detailed Placement Algorithm," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 8, pp. 1349--1362, August 2008.
• 9: J. Nocedal and S. J. Wright, "Numerical Optimization 2nd ed.," Springer, 2006.
• 10: W. C. Naylor, R. Donelly, and L. Sha, "Non-linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer," US Patent 6301693, October, 2001.
• 11: Tony Chan , Jason Cong , Kenton Sze, Multilevel generalized force-directed method for circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055177]
• 12: A. B. Kahng , S. Reda , Qinke Wang, Architecture and details of a high quality, large-scale analytical placer, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.891-898, November 06-10, 2005, San Jose, CA
• 13: Tung-Chieh Chen , Zhe-Wei Jiang , Tien-Chang Hsu , Hsin-Chen Chen , Yao-Wen Chang, A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233538]
• 14: Jason Cong , Guojie Luo, Highly efficient gradient computation for density-constrained analytical placement methods, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA [doi>10.1145/1353629.1353639]
• 15: Charles Alpert , Andrew Kahng , Gi-Joon Nam , Sherief Reda , Paul Villarrubia, A semi-persistent clustering technique for VLSI circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055179]
• 16: http://er.cs.ucla.edu/benchmarks/ibm-place/
• 17: George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309954]