基于非线性规划的三维集成电路布局算法研究
|
摘要
当今，集成电路迅猛发展，其芯片的集成度和规模都急剧地增加。为了能进一步降低芯片的互连延迟，提高芯片的电路性能，在电路设计与制造工艺中，出现了“三维集成电路”的概念。三维集成电路给集成电路的发展带来了动力，但是同时也给集成电路物理设计及其设计工具的开发带来了巨大的挑战。
本文在调研现有总体布局算法的基础上，着重对基于非线性规划的布局技术进行了研究和分析。同时结合三维集成电路的结构特点提出了一种线长驱动的三维集成电路非线性布局算法，得到三维集成电路上合法的单元分布。其中包括三项新技术：一种层次式的二元结群算法；一种线长驱动的合法化算法；一种使用最小代价流的层分配方法。实验结果证明本文的三维集成电路非线性规划布局算法可以稳定有效地解决大规模三维集成电路的布局问题。
The rapid development of the integrated circuits makes the increasement of chip intergrationand scale sharply. In order to reduce interconnect delay and improve the performance of the circuitfurther, the concept of the “Three-dimensional Integrated Circuits(3D ICs)” has been presented inintegrated circuit design and manufacturing process.3D ICs not only bring momentum to thedevelopment of the integrated circuits, but also bring huge challenges to the integrated circuitphysical design and design tools.
This paper has taken research on global placement algorithms, especially on nonlinearprogramming methods. Based on the3D ICs structural features, a new wirelength-diven3Dplacement algorithm is proposed in this paper, which resulted in a close-to-legal3D globalplacement. It composes of a series of new techniques includeing a new dyadic cluster approach; awire-length driven legalization algorithm; a layer assignment method using the minimum costflow. Experiments showed that the algorithm could effectively solve the issues of large-scale3DICs placement problems.
本文在调研现有总体布局算法的基础上，着重对基于非线性规划的布局技术进行了研究和分析。同时结合三维集成电路的结构特点提出了一种线长驱动的三维集成电路非线性布局算法，得到三维集成电路上合法的单元分布。其中包括三项新技术：一种层次式的二元结群算法；一种线长驱动的合法化算法；一种使用最小代价流的层分配方法。实验结果证明本文的三维集成电路非线性规划布局算法可以稳定有效地解决大规模三维集成电路的布局问题。
The rapid development of the integrated circuits makes the increasement of chip intergrationand scale sharply. In order to reduce interconnect delay and improve the performance of the circuitfurther, the concept of the “Three-dimensional Integrated Circuits(3D ICs)” has been presented inintegrated circuit design and manufacturing process.3D ICs not only bring momentum to thedevelopment of the integrated circuits, but also bring huge challenges to the integrated circuitphysical design and design tools.
This paper has taken research on global placement algorithms, especially on nonlinearprogramming methods. Based on the3D ICs structural features, a new wirelength-diven3Dplacement algorithm is proposed in this paper, which resulted in a close-to-legal3D globalplacement. It composes of a series of new techniques includeing a new dyadic cluster approach; awire-length driven legalization algorithm; a layer assignment method using the minimum costflow. Experiments showed that the algorithm could effectively solve the issues of large-scale3DICs placement problems.
引文
1. G. Moore. VLSI: Some fundamental challenges. IEEE Spectrum1979,16:30
2. Semiconductor Industry Association. International Technology Roadmap forSemiconducotrs.2005.[Online]: http://public.itrs.net/
3.程平阶.集成电路层次式热驱动布图布局算法研究:[硕士学位论文].武汉：武汉理工大学,2009
4.黄锋.面向微处理器系统结构的布图规划算法研究:[硕士学位论文].武汉：武汉理工大学,2008
5. NASA. Technology Readinesss Overview-Low-k Interlevel Dielectrics Technology–Brief description of low-k technology. http://nepp.nasa.gov/index_nasa.cfm/934/
6.夏艳.3D集成的发展现状与趋势.中国集成电路CIC.2011.7:23-28
7. S.F. Al-Sarawi, D. Abbott, P.D. Franzon. A Review of3-D Packaging Technology. IEEETransactions on Components, Packaging, and Manufacturing technology Part B, Vol.21,No.1,1998:2-14
8.徐宁，洪先龙.超大规模集成电路物理设计理论与算法.清华大学出版社,2009.1
9. J. W. Joyner, R. Venkatesan, P. Zarkesh-Ha, J. A. Davis, and J. D. Meindl. Impact ofThree-Dimensional Architectures on Interconnects in Gigascale Integration. In: IEEETransactions on Very Large Scale Integration Systems. Dec2001, Vol.9No.6:922-928
10. Tezzaron Company.3D IC Industry Summary.[Online]:http://www.tezzaron.com/technology/3D%20IC%20Summary.html
11. K. Banerjee, S.J. Souri, P. Kapur, K.C. Saraswat.3D-ICs: A Novel Chip Design forImproving Deep-Submicrometer Interconnect Performance and Systems on ChipIntegration. In: Proceedings of the IEEE.2001, Vol.89No.5:602-633
12. T. Kunio, K. Oyama, Y. Hayashi, and M. Morimoto. Three Dimensional ICs, Having FourStacked Active Device Layers. In: Proceedings of IEEE International Electron DevicesMeeting.1989:837-870
13. H. Huebner et al. Face-to-face chip integration with full mental interface. In: Proceedings ofAdvanced Metallization Conference.2002:1-4
14. J. Kalyanasundharam et al. Application of a global-local random-walk algorithm for thermalanalysis of3D integration circuits. In: Proceedings of Advanced Metallization Conference.2002:5-8
15. http://www.istis.sh.cn/list/list.aspx?id=6381
16. W.J. Sun and C. Sechen. Efficient and effective placement for very large circuits. InIEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages170–177,1993
17. Cadence. LEF/DEF Language Reference Product Version5.4.2003.1,http://openeda.org/download_lefdef.html
18.刘毅.超大规模集成电路时钟网络设计与优化算法研究：[清华大学博士论文].北京：清华大学,2003
19. Ted Manikas. YAL Language Specification for Netlists.1998.9,http://www.ee.utulsa.edu/~tmanikas/VLSI/yal-language.pdf
20. D.E.Thomas, P.R.Moorby. The Verilog Hardware Description Language (Fourth Edition).刘明业，蒋敬旗，刁岚松等译.硬件描述语言Verilog（第四版）.清华大学出版社,2001.8
21.乔长阁，边计年，薛宏熙等译. VHDL简明教程.北京：清华大学出版社，1997
22.洪先龙，严晓浪，乔长阁.超大规模集成电路布图理论与算法.北京：科学出版社,1998
23.隋文涛. FPGA布局算法研究:[博士学位论文].北京：清华大学计算机系,2011
24. T. Taghavi, X. Yang, and B.-K. Choi. Dragon2005: Large-scale mixed-size placement tool.In ACM/SIGDA International Symposium on Physical Design (ISPD), pages245–247,2005
25. R.S. Tsay, E.S. Kuh, and C.P. Hsu. PROUD: A sea-of-gates placement algorithm.ieeedesigntest, pages44–56, December1988
26. J.A. Roy, D.A. Papa, S.N. Adya, H.H. Chan, A.N. Ng, J.F. Lu, and I.L. Markov.Capo:Robust and scalable open-source min-cut floorplacer. In ACM/SIGDA InternationalSymposium on Physical Design (ISPD), pages224–226,2005
27. A.R. Agnihorti, S. Ono, C. Li, M.C. Yildiz, A. Khathate, C.-K. Koh, and P.H.Madden.Mixed block placement via fractional cut recursive bisection. IEEE Transactionson Computer-Aided Design of Circuits and Systems,24(5):748–761, May2005
28. B.W.Kernighan,S.Lin,“An Efficient Heuristic Procedure for Partitioning Graphs”，B.S.T.J.Vol.49, P.291,1970
29. C.M.Fiduccia and R.M.Mattheyses,“A linear-time heuristic for improving networkpartitions”, In proceedings of19th International Design and Automation Conference, pp.175-181,1982
30. A. E. Caldwell, A. B. Kahng and I. L. Markov,“Design and Implementation of theFiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning”, Lecture Notes in ComputerScience, vol.1619, Springer,1999
31. G. Karypis, R. Aggarwal, V. Kumar and S. Shekhar. Multilevel Hypergraph Partitioning:Application in VLSI Domain In proceedings of International Design and AutomationConference1997
32. A. E. Caldwell, A. B. Kahng and I. L. Markov,“Can Recursive Bisection Alone ProduceRoutable Placements?”, in Proceedings of International Design and Automation Conference2000, pp.477-482
33. J. Kleinhands, G. Sigl, F. Johannes and K. Antreich. GORDIAN: VLSI Placement byQuadratic Programming and Slicing Optimization. IEEE Transactions on Computer-AidedDesign. March1991,10(3):356~365
34. A. Srinivasan, K. Chaudhary and E. S. Kuh. RITUAL: A Performance-Driven PlacementAlgorithm. IEEE Trans. On CAS-II: Analog and Digital Processing.1992, Vol.39,No11:825~840
35.孔天明.高性能、高可靠性地超大规模集成电路物理布图算法研究：[博士学位论文].北京：清华大学计算机系，1999
36. H. Yu, X.L. Hong, et al. CASH: A Novel Quadratic Placement Algorithm for Very LargeStandard Cell Layout Design Based on Clustering. In: Proceedings of the5th InternationalConference on Solid-State and Integrated Circuit Technology.1998.496~501
37. W. Hou, X.L. Hong, et al. FaSa: A Fast and Stable Quadratic Placement Algorithm. Journalof Computer Science and Technology. May,2003, Vol.18, Issue3:318~324
38. H.Eisenmann and F.M.Johannes.Generic global placement and floorplanning.In ACM/IEEEDesign Automation Conference(DAC),pages269–274,June1998
39. B. Hu and M. Marek-Sadowska,“FAR: Fixed Point Addition and Relaxation basedPlacement”, Proc. Intl. Symp. on Physical Design,2002
40. N.Viswanathan and C.C.N.Chu,“FastPlace:Efficient Analytical Placement Using CellShifting,Iterative Local Refinement and a Hybrid Net Model”, Proc.Int.Symp.PhysicalDesign,2004, pp.26-33
41. B. Hu, Y. Zeng and M. Marek-Sadowska,“mFAR: Fixed-Points-Addtion-Based VLSIPlacement Algorithm,” Proc. ACM/IEEE International Symposium on Physical Design,2005, pp.239–241
42.侯文婷. VLSI电路性能驱动的快速布局算法研究：[博士学位论文].北京：清华大学计算机系，1999
43. I.I.Mahmoud, K.Asakura, T.Nishibu and T.Ohtsuki,“Experimental Appraisal of Linear andQuadratic Objective Functions Effect on Force Directed Method for Analog Placement”,IEICE Transactions on Fundamentals of Electronics, Communications and ComputerSciences, E77-A(4), April1994, pp.719-725
44. G.Sigl, K.Doll anda F.Johannes,“Partitioning Very Large Circuits Using AnalyticalPlacement Techniques”, In proceeding of31th ACM/IEEE Design Automation Conference,1991, pp.427-432
45. A. Kennings and I. Markov,“Analytical Minimum of Half-Perimeter Wirelength”, Inproceeding of the2000Asia and South Pacific Design Automation Conference, pp.179-184
46. W. Naylor,“Non-Linear Optimization System and Method for Wire Length and DelayOptimization for anAutomatic Electric Circuit Placer,” US Patent6301693,2001
47. A.B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEETransactions on Computer-Aided Design of Circuits and Systems,24(05):734–747,May2005
48. T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuitplacement. In ACM/SIGDA International Symposium on Physical Design (ISPD),pages185–192,2005
49. T.C. Chen, Z.W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang. A high-quality mixed-sizeanalytical placer considering preplaced blocks and density constraints. In IEEE/ACMInternational Conference on Computer-Aided Design (ICCAD), pages187–192,2006
50. A.R.Agnihotri, P.H.Madden. Fast Analytic Placement using Minimum Cost Flow.ASP-DAC2007:128-134
51. B.Landman and R.Russo. On a Pin Versus Block Relationship for Partitions of LogicGraphs. IEEE Transactions on Computers.1971, Vol. c-20:1469-1479
52. H. B. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Reading, MA:Addison-Wesley,1990
53. R. Zhang, K. Roy, C.K. Koh, D.B. Janes. Stochastic Interconnect Modeling, Power Trends,and Performance Characterization of3-D Circuits. IEEE Transactions on Electron Devices,2001, Vol.48No.4:638-652
54. J. A. Davis, V. K. De, and J. Meindl. A stochastic wire-length distribution for gigascaleintegration (GSI)—Part I: Derivation and validation. IEEE Transactions on ElectronDevices.1998, Vol.45No.3:580–589
55. A. Rahman, A. Fan, J. Chung, R.Reif. Wire-Length Distribution of Three-DimensionalIntegrated Circuits. In: Proceedings of IEEE International Interconnect TechnologyConference.1999:233-235
56. K. Banerjee, S.J. Souri, P. Kapur, K.C. Saraswat.3D-ICs: A Novel Chip Design forImproving Deep-Submicrometer Interconnect Performance and Systems on ChipIntegration. Proceedings of the IEEE,2001Vol.89No.5:602-633
57. A.B. Kahng, S. Reda,and Q. Wang. Architecture and details of a high quality,large-scaleanalytical placer.In Proc.of ICCAD,pages890–897,2005
58. S.J. Souri, K. Banerjee, A. Mehrotra, K.C. Saraswat. Multiple Si Layer ICs: Motivation,Performance Analysis, and Design Implications. In: Proceedings of ACM/IEEE DesignAutomation Conference.2000:213-220
59. K. Bazargan, R. Kastner, and M. Sarrafzadeh.3D Floorplanning: Simulated Annealing andGreedy Placement Methods for Reconfigurable Computing Systems. In: Proceedings ofInternational Workshop on Rapid System Prototyping.2000:38-43
60. L. Cheng, L. Deng, D.F. Wong. Floorplanning for3D VLSI Design. In: Proceedings ofACM/IEEE Asia South Pacific Design Automation Conference.2005:405-411
61. H. Yamazaki, K. Sakanushi, S. Nakatake, Y. Kajitani. The3D-packing by Meta DataStructure and Packing heuristics. In: IEICE Transactions on Fundamentals.2000,Vol.E38-A:639-645
62. Y. Ma, Z. Li, X. Hong, S. Dong. Cubic Packing with Various Candidates for3D IC Design.In: Proceedings of8th International Conference on Solid-State and Integrated-CircuitTechnology.2006
63. Y. Deng and W. P. Maly. Interconnect Characteristics of2.5-D System Integration Scheme.In: Proceedings of ACM International Symposium on Physical Design.2001:341-345
64. P. H. Shiu, R. Ravichandran, S. Easwar, and S. K. Lim, Multi-layer Floorplanning forReliable System-on-Package, In: Proceedings of International Symposium on Circuits AndSystems.2004: Vol.5V-69–V-72
65. J. Cong, J. Wei, and Y. Zhang. A Thermal-Driven Floorplanning Algorithm for3D ICs. In:Proceedings of International Conference on Computer Aided Design.2004:306-313
66.李卓远.三维芯片布图算法研究：[博士学位论文].北京：清华大学计算机系,2006
67. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel Hypergraph Partitioning:Application in VLSI Domain. In Proc.34th ACM/IEEE Design Automation Conference,pages526-529,1997
68. T.C. Chen, T.C. Hsu, Z.W. Jiang and Y-W Chang, NTUplace: a ratio partitioning basedplacement algorithm for large-scale mixed-size designs, Proceedings of the2005international symposium on Physical design, April03-06,2005, San Francisco, California,USA
69. C. Alpert, A. Kahng, G-J Nam, S. Reda and P. Villarrubia, A semi-persistent clusteringtechnique for VLSI circuit placement, Proceedings of the2005international symposium onPhysical design, April03-06,2005, San Francisco, California, USA
70. A.B. Kahng and Q. Wang. A faster implementation of APlace. in Proc. ISPD,2006, pp.218–220
71. N. Viswanathan, M. Pan, and C. Chu. Fastplace3.0:A fast multilevel quadratic placementalgorithm with placement congestion control. In Proc. ASP-DAC, pages135–140,2007
72. T. Chan, J. Cong, J. Shinnerl, K. Sze and M. Xie. mPL6: Enhanced multilevel mixed-sizeplacement. In Proc. of ISPD, pages212–214,2006
73. http://www.public.iastate.edu/~nataraj/ISPD04_Bench.html#The_Benchmarks
74. W.C. Gao, Y.Q. Lv, X. Qian, Q. Zhou, H.X. Yan and X. Wu. A Nonlinear PlacementTechnique for FPGA-Like Uniform Granularity Problem. In Pro. of ICCDA, V3pages441-444, June,2010
75. M. C. Yildiz and P. H. Madden. Improved Cut Sequences for Partitioning Based Placement.In Proc. of ACM/IEE Design Automation Conf.,2001, pp.776-779
76. D. Hill, Method and System for High Speed Detailed Placement of Cells within anIntegrated Circuit Design, US Patent6370673, April2002
77. A.B. Kahng, S. Reda, and Q. Wang. APlace: A General Analytic Placement Framework. inProc. ACM/IEEE International Symposium on Physical Design,2005.233~235
78. J. Cong and M. Xie. A robust detailed placement for mixed-size IC designs. In Proc. AsiaSouth Pacific Design Automation Conf.2006.188~194
79. N.Viswanathan, M. Pan and C. Chu, FastPlace2.0: An efficient analytical placer formixed-mode designs. In Proc. Asia South Pacific Design Automation Conf,2006.195~200
80. M. Pan, N. Viswanathan, and C. Chu. An efficient and effective detailed placementalgorithm. In Proc. IEEE/ACM International Conf. on Computer-Aided Design,2005.48~55
81. T.F. Chan, J. Cong, M. Romesis, J.R. Shinnerl, K. Sze and M. Xie. mPL6: A RobustMultilevel Mixed-Size Placement Engine. in Proc. ACM/IEEE International Symposium onPhysical Design,2005.227~229
82. http://www.ispd.cc/contests/11/ispd2011_contest.html#head-designs
83. N. Viswanathan, C. Alpert C, C. Sze et al. The DAC2012Routability-driven PlacementContest and Benchmark Suite [C].//Proc. Design Automation Conference. California, USA.2012:774-782
84. http://archive.sigda.org/dac2012/contest/other_files/dac2012_check_legality.gz
85. http://www.gnuplot.info/download.html
86. http://archive.sigda.org/dac2012/contest/other_files/BFG-R.tar.gz
87. M. K. Hsu, Y.W. Chang, and V. Balabanov. TSV-aware analytical placement for3-D ICdesigns. Proceedings of the Design automation conference, pages664–669,2011
88. J. Cong, G. Luo, J. Wei, and Y. Zhang. Thermal-aware3D IC placement via transformation.In Proc. of ASPDAC,2007
89. B. Goplen and S. Sapatnekar. Placement of3D ICs with thermal and interlayer viaconsiderations. In Proc. of DAC,2007
90. B. Goplen and S. Sapatnekar, Efficient Thermal Placement of Standard Cells in3D ICsusing a Force Directed Approach, Proceedings of the2003IEEE/ACM InternationalConference on Computer-Aided Design, pp.86,2003
91. H. Yan, Q. Zhou, and X. Hong,"Efficient Thermal Aware Placement Approach Integratedwith3D DCT Placement Algorithm," Proceedings of the9th International Symposium onQuality Electronic Design, pp.289-292,2008
92. J. Cong and G. Luo. A multilevel analytical placement for3D ICs. In Proc. of ASPDAC,2009
93.高文超，周强，吕勇强，闫海霞，钱旭.《计算机辅助设计与图形学学报》，2011年11期，1944-1948
94. T.C. Chen, Z.W. Jiang, T.C. Hsu, H.C. Chen, and Y.W. Chang. NTUplace3: An analyticalplacer for large-scale mixed-size designs with preplaced blocks and density constraints.IEEE Trans. on CAD,27(7),2008
95. IBM-PLACE Benchmarks. http://er.cs.ucla.edu/benchmarks/ibm-place
96. Wenchao Gao,Qiang Zhou,Xu Qian,Yici Cai.A DyadicCluster method used for nonlinearplacement. Proceedings of13th International Symposium on Quality Electronic Design(ISQED),2012, P418-423
2. Semiconductor Industry Association. International Technology Roadmap forSemiconducotrs.2005.[Online]: http://public.itrs.net/
3.程平阶.集成电路层次式热驱动布图布局算法研究:[硕士学位论文].武汉：武汉理工大学,2009
4.黄锋.面向微处理器系统结构的布图规划算法研究:[硕士学位论文].武汉：武汉理工大学,2008
5. NASA. Technology Readinesss Overview-Low-k Interlevel Dielectrics Technology–Brief description of low-k technology. http://nepp.nasa.gov/index_nasa.cfm/934/
6.夏艳.3D集成的发展现状与趋势.中国集成电路CIC.2011.7:23-28
7. S.F. Al-Sarawi, D. Abbott, P.D. Franzon. A Review of3-D Packaging Technology. IEEETransactions on Components, Packaging, and Manufacturing technology Part B, Vol.21,No.1,1998:2-14
8.徐宁，洪先龙.超大规模集成电路物理设计理论与算法.清华大学出版社,2009.1
9. J. W. Joyner, R. Venkatesan, P. Zarkesh-Ha, J. A. Davis, and J. D. Meindl. Impact ofThree-Dimensional Architectures on Interconnects in Gigascale Integration. In: IEEETransactions on Very Large Scale Integration Systems. Dec2001, Vol.9No.6:922-928
10. Tezzaron Company.3D IC Industry Summary.[Online]:http://www.tezzaron.com/technology/3D%20IC%20Summary.html
11. K. Banerjee, S.J. Souri, P. Kapur, K.C. Saraswat.3D-ICs: A Novel Chip Design forImproving Deep-Submicrometer Interconnect Performance and Systems on ChipIntegration. In: Proceedings of the IEEE.2001, Vol.89No.5:602-633
12. T. Kunio, K. Oyama, Y. Hayashi, and M. Morimoto. Three Dimensional ICs, Having FourStacked Active Device Layers. In: Proceedings of IEEE International Electron DevicesMeeting.1989:837-870
13. H. Huebner et al. Face-to-face chip integration with full mental interface. In: Proceedings ofAdvanced Metallization Conference.2002:1-4
14. J. Kalyanasundharam et al. Application of a global-local random-walk algorithm for thermalanalysis of3D integration circuits. In: Proceedings of Advanced Metallization Conference.2002:5-8
15. http://www.istis.sh.cn/list/list.aspx?id=6381
16. W.J. Sun and C. Sechen. Efficient and effective placement for very large circuits. InIEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages170–177,1993
17. Cadence. LEF/DEF Language Reference Product Version5.4.2003.1,http://openeda.org/download_lefdef.html
18.刘毅.超大规模集成电路时钟网络设计与优化算法研究：[清华大学博士论文].北京：清华大学,2003
19. Ted Manikas. YAL Language Specification for Netlists.1998.9,http://www.ee.utulsa.edu/~tmanikas/VLSI/yal-language.pdf
20. D.E.Thomas, P.R.Moorby. The Verilog Hardware Description Language (Fourth Edition).刘明业，蒋敬旗，刁岚松等译.硬件描述语言Verilog（第四版）.清华大学出版社,2001.8
21.乔长阁，边计年，薛宏熙等译. VHDL简明教程.北京：清华大学出版社，1997
22.洪先龙，严晓浪，乔长阁.超大规模集成电路布图理论与算法.北京：科学出版社,1998
23.隋文涛. FPGA布局算法研究:[博士学位论文].北京：清华大学计算机系,2011
24. T. Taghavi, X. Yang, and B.-K. Choi. Dragon2005: Large-scale mixed-size placement tool.In ACM/SIGDA International Symposium on Physical Design (ISPD), pages245–247,2005
25. R.S. Tsay, E.S. Kuh, and C.P. Hsu. PROUD: A sea-of-gates placement algorithm.ieeedesigntest, pages44–56, December1988
26. J.A. Roy, D.A. Papa, S.N. Adya, H.H. Chan, A.N. Ng, J.F. Lu, and I.L. Markov.Capo:Robust and scalable open-source min-cut floorplacer. In ACM/SIGDA InternationalSymposium on Physical Design (ISPD), pages224–226,2005
27. A.R. Agnihorti, S. Ono, C. Li, M.C. Yildiz, A. Khathate, C.-K. Koh, and P.H.Madden.Mixed block placement via fractional cut recursive bisection. IEEE Transactionson Computer-Aided Design of Circuits and Systems,24(5):748–761, May2005
28. B.W.Kernighan,S.Lin,“An Efficient Heuristic Procedure for Partitioning Graphs”，B.S.T.J.Vol.49, P.291,1970
29. C.M.Fiduccia and R.M.Mattheyses,“A linear-time heuristic for improving networkpartitions”, In proceedings of19th International Design and Automation Conference, pp.175-181,1982
30. A. E. Caldwell, A. B. Kahng and I. L. Markov,“Design and Implementation of theFiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning”, Lecture Notes in ComputerScience, vol.1619, Springer,1999
31. G. Karypis, R. Aggarwal, V. Kumar and S. Shekhar. Multilevel Hypergraph Partitioning:Application in VLSI Domain In proceedings of International Design and AutomationConference1997
32. A. E. Caldwell, A. B. Kahng and I. L. Markov,“Can Recursive Bisection Alone ProduceRoutable Placements?”, in Proceedings of International Design and Automation Conference2000, pp.477-482
33. J. Kleinhands, G. Sigl, F. Johannes and K. Antreich. GORDIAN: VLSI Placement byQuadratic Programming and Slicing Optimization. IEEE Transactions on Computer-AidedDesign. March1991,10(3):356~365
34. A. Srinivasan, K. Chaudhary and E. S. Kuh. RITUAL: A Performance-Driven PlacementAlgorithm. IEEE Trans. On CAS-II: Analog and Digital Processing.1992, Vol.39,No11:825~840
35.孔天明.高性能、高可靠性地超大规模集成电路物理布图算法研究：[博士学位论文].北京：清华大学计算机系，1999
36. H. Yu, X.L. Hong, et al. CASH: A Novel Quadratic Placement Algorithm for Very LargeStandard Cell Layout Design Based on Clustering. In: Proceedings of the5th InternationalConference on Solid-State and Integrated Circuit Technology.1998.496~501
37. W. Hou, X.L. Hong, et al. FaSa: A Fast and Stable Quadratic Placement Algorithm. Journalof Computer Science and Technology. May,2003, Vol.18, Issue3:318~324
38. H.Eisenmann and F.M.Johannes.Generic global placement and floorplanning.In ACM/IEEEDesign Automation Conference(DAC),pages269–274,June1998
39. B. Hu and M. Marek-Sadowska,“FAR: Fixed Point Addition and Relaxation basedPlacement”, Proc. Intl. Symp. on Physical Design,2002
40. N.Viswanathan and C.C.N.Chu,“FastPlace:Efficient Analytical Placement Using CellShifting,Iterative Local Refinement and a Hybrid Net Model”, Proc.Int.Symp.PhysicalDesign,2004, pp.26-33
41. B. Hu, Y. Zeng and M. Marek-Sadowska,“mFAR: Fixed-Points-Addtion-Based VLSIPlacement Algorithm,” Proc. ACM/IEEE International Symposium on Physical Design,2005, pp.239–241
42.侯文婷. VLSI电路性能驱动的快速布局算法研究：[博士学位论文].北京：清华大学计算机系，1999
43. I.I.Mahmoud, K.Asakura, T.Nishibu and T.Ohtsuki,“Experimental Appraisal of Linear andQuadratic Objective Functions Effect on Force Directed Method for Analog Placement”,IEICE Transactions on Fundamentals of Electronics, Communications and ComputerSciences, E77-A(4), April1994, pp.719-725
44. G.Sigl, K.Doll anda F.Johannes,“Partitioning Very Large Circuits Using AnalyticalPlacement Techniques”, In proceeding of31th ACM/IEEE Design Automation Conference,1991, pp.427-432
45. A. Kennings and I. Markov,“Analytical Minimum of Half-Perimeter Wirelength”, Inproceeding of the2000Asia and South Pacific Design Automation Conference, pp.179-184
46. W. Naylor,“Non-Linear Optimization System and Method for Wire Length and DelayOptimization for anAutomatic Electric Circuit Placer,” US Patent6301693,2001
47. A.B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEETransactions on Computer-Aided Design of Circuits and Systems,24(05):734–747,May2005
48. T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuitplacement. In ACM/SIGDA International Symposium on Physical Design (ISPD),pages185–192,2005
49. T.C. Chen, Z.W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang. A high-quality mixed-sizeanalytical placer considering preplaced blocks and density constraints. In IEEE/ACMInternational Conference on Computer-Aided Design (ICCAD), pages187–192,2006
50. A.R.Agnihotri, P.H.Madden. Fast Analytic Placement using Minimum Cost Flow.ASP-DAC2007:128-134
51. B.Landman and R.Russo. On a Pin Versus Block Relationship for Partitions of LogicGraphs. IEEE Transactions on Computers.1971, Vol. c-20:1469-1479
52. H. B. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Reading, MA:Addison-Wesley,1990
53. R. Zhang, K. Roy, C.K. Koh, D.B. Janes. Stochastic Interconnect Modeling, Power Trends,and Performance Characterization of3-D Circuits. IEEE Transactions on Electron Devices,2001, Vol.48No.4:638-652
54. J. A. Davis, V. K. De, and J. Meindl. A stochastic wire-length distribution for gigascaleintegration (GSI)—Part I: Derivation and validation. IEEE Transactions on ElectronDevices.1998, Vol.45No.3:580–589
55. A. Rahman, A. Fan, J. Chung, R.Reif. Wire-Length Distribution of Three-DimensionalIntegrated Circuits. In: Proceedings of IEEE International Interconnect TechnologyConference.1999:233-235
56. K. Banerjee, S.J. Souri, P. Kapur, K.C. Saraswat.3D-ICs: A Novel Chip Design forImproving Deep-Submicrometer Interconnect Performance and Systems on ChipIntegration. Proceedings of the IEEE,2001Vol.89No.5:602-633
57. A.B. Kahng, S. Reda,and Q. Wang. Architecture and details of a high quality,large-scaleanalytical placer.In Proc.of ICCAD,pages890–897,2005
58. S.J. Souri, K. Banerjee, A. Mehrotra, K.C. Saraswat. Multiple Si Layer ICs: Motivation,Performance Analysis, and Design Implications. In: Proceedings of ACM/IEEE DesignAutomation Conference.2000:213-220
59. K. Bazargan, R. Kastner, and M. Sarrafzadeh.3D Floorplanning: Simulated Annealing andGreedy Placement Methods for Reconfigurable Computing Systems. In: Proceedings ofInternational Workshop on Rapid System Prototyping.2000:38-43
60. L. Cheng, L. Deng, D.F. Wong. Floorplanning for3D VLSI Design. In: Proceedings ofACM/IEEE Asia South Pacific Design Automation Conference.2005:405-411
61. H. Yamazaki, K. Sakanushi, S. Nakatake, Y. Kajitani. The3D-packing by Meta DataStructure and Packing heuristics. In: IEICE Transactions on Fundamentals.2000,Vol.E38-A:639-645
62. Y. Ma, Z. Li, X. Hong, S. Dong. Cubic Packing with Various Candidates for3D IC Design.In: Proceedings of8th International Conference on Solid-State and Integrated-CircuitTechnology.2006
63. Y. Deng and W. P. Maly. Interconnect Characteristics of2.5-D System Integration Scheme.In: Proceedings of ACM International Symposium on Physical Design.2001:341-345
64. P. H. Shiu, R. Ravichandran, S. Easwar, and S. K. Lim, Multi-layer Floorplanning forReliable System-on-Package, In: Proceedings of International Symposium on Circuits AndSystems.2004: Vol.5V-69–V-72
65. J. Cong, J. Wei, and Y. Zhang. A Thermal-Driven Floorplanning Algorithm for3D ICs. In:Proceedings of International Conference on Computer Aided Design.2004:306-313
66.李卓远.三维芯片布图算法研究：[博士学位论文].北京：清华大学计算机系,2006
67. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel Hypergraph Partitioning:Application in VLSI Domain. In Proc.34th ACM/IEEE Design Automation Conference,pages526-529,1997
68. T.C. Chen, T.C. Hsu, Z.W. Jiang and Y-W Chang, NTUplace: a ratio partitioning basedplacement algorithm for large-scale mixed-size designs, Proceedings of the2005international symposium on Physical design, April03-06,2005, San Francisco, California,USA
69. C. Alpert, A. Kahng, G-J Nam, S. Reda and P. Villarrubia, A semi-persistent clusteringtechnique for VLSI circuit placement, Proceedings of the2005international symposium onPhysical design, April03-06,2005, San Francisco, California, USA
70. A.B. Kahng and Q. Wang. A faster implementation of APlace. in Proc. ISPD,2006, pp.218–220
71. N. Viswanathan, M. Pan, and C. Chu. Fastplace3.0:A fast multilevel quadratic placementalgorithm with placement congestion control. In Proc. ASP-DAC, pages135–140,2007
72. T. Chan, J. Cong, J. Shinnerl, K. Sze and M. Xie. mPL6: Enhanced multilevel mixed-sizeplacement. In Proc. of ISPD, pages212–214,2006
73. http://www.public.iastate.edu/~nataraj/ISPD04_Bench.html#The_Benchmarks
74. W.C. Gao, Y.Q. Lv, X. Qian, Q. Zhou, H.X. Yan and X. Wu. A Nonlinear PlacementTechnique for FPGA-Like Uniform Granularity Problem. In Pro. of ICCDA, V3pages441-444, June,2010
75. M. C. Yildiz and P. H. Madden. Improved Cut Sequences for Partitioning Based Placement.In Proc. of ACM/IEE Design Automation Conf.,2001, pp.776-779
76. D. Hill, Method and System for High Speed Detailed Placement of Cells within anIntegrated Circuit Design, US Patent6370673, April2002
77. A.B. Kahng, S. Reda, and Q. Wang. APlace: A General Analytic Placement Framework. inProc. ACM/IEEE International Symposium on Physical Design,2005.233~235
78. J. Cong and M. Xie. A robust detailed placement for mixed-size IC designs. In Proc. AsiaSouth Pacific Design Automation Conf.2006.188~194
79. N.Viswanathan, M. Pan and C. Chu, FastPlace2.0: An efficient analytical placer formixed-mode designs. In Proc. Asia South Pacific Design Automation Conf,2006.195~200
80. M. Pan, N. Viswanathan, and C. Chu. An efficient and effective detailed placementalgorithm. In Proc. IEEE/ACM International Conf. on Computer-Aided Design,2005.48~55
81. T.F. Chan, J. Cong, M. Romesis, J.R. Shinnerl, K. Sze and M. Xie. mPL6: A RobustMultilevel Mixed-Size Placement Engine. in Proc. ACM/IEEE International Symposium onPhysical Design,2005.227~229
82. http://www.ispd.cc/contests/11/ispd2011_contest.html#head-designs
83. N. Viswanathan, C. Alpert C, C. Sze et al. The DAC2012Routability-driven PlacementContest and Benchmark Suite [C].//Proc. Design Automation Conference. California, USA.2012:774-782
84. http://archive.sigda.org/dac2012/contest/other_files/dac2012_check_legality.gz
85. http://www.gnuplot.info/download.html
86. http://archive.sigda.org/dac2012/contest/other_files/BFG-R.tar.gz
87. M. K. Hsu, Y.W. Chang, and V. Balabanov. TSV-aware analytical placement for3-D ICdesigns. Proceedings of the Design automation conference, pages664–669,2011
88. J. Cong, G. Luo, J. Wei, and Y. Zhang. Thermal-aware3D IC placement via transformation.In Proc. of ASPDAC,2007
89. B. Goplen and S. Sapatnekar. Placement of3D ICs with thermal and interlayer viaconsiderations. In Proc. of DAC,2007
90. B. Goplen and S. Sapatnekar, Efficient Thermal Placement of Standard Cells in3D ICsusing a Force Directed Approach, Proceedings of the2003IEEE/ACM InternationalConference on Computer-Aided Design, pp.86,2003
91. H. Yan, Q. Zhou, and X. Hong,"Efficient Thermal Aware Placement Approach Integratedwith3D DCT Placement Algorithm," Proceedings of the9th International Symposium onQuality Electronic Design, pp.289-292,2008
92. J. Cong and G. Luo. A multilevel analytical placement for3D ICs. In Proc. of ASPDAC,2009
93.高文超，周强，吕勇强，闫海霞，钱旭.《计算机辅助设计与图形学学报》，2011年11期，1944-1948
94. T.C. Chen, Z.W. Jiang, T.C. Hsu, H.C. Chen, and Y.W. Chang. NTUplace3: An analyticalplacer for large-scale mixed-size designs with preplaced blocks and density constraints.IEEE Trans. on CAD,27(7),2008
95. IBM-PLACE Benchmarks. http://er.cs.ucla.edu/benchmarks/ibm-place
96. Wenchao Gao,Qiang Zhou,Xu Qian,Yici Cai.A DyadicCluster method used for nonlinearplacement. Proceedings of13th International Symposium on Quality Electronic Design(ISQED),2012, P418-423