在現今超大型積體電路設計中，由於製程技術進步和三維技術引進，藉由直通矽晶穿孔的堆疊結構發展，來達到三維空間的垂直整合。直通矽晶穿孔取代了二維空間中過長的繞線，如何有效適當的擺置區塊和直通矽晶穿孔來改善時序問題。在此篇論文，我們將電路分層，逐一對每層執行切割擺置演算法的標準元件擺置，同時考量到擺置直通矽晶穿孔的對準條件限制，接著使用模擬退火法來減少繞線長度和優化時序，最後處理擺置的重疊問題。實驗結果顯示，三維積體電路較二維積體電路提升與改善整體效能。

The semiconductor technology has been advanced in modern VLSI design. Three-dimension (3D) concept imports an additional dimension for circuit design by using stack structures with through-silicon via (TSV). 3D ICs replace longer interconnect in 2D ICs with TSV cells. However, there are problems how to place cells and TSV cells to improve timing. In this thesis, we perform standard cell placement by min-cut partitioning for one layer after layer assignment and address alignment constraint at the same time. Then use simulated-annealing to optimize timing and reduces wirelength of interconnect. In the last, a legal placement by a greedy method removes operlap between cells and TSV cells. The experimental results show that 3D ICs improve wirelength and delay of critical path than 2D ICs.

1 Introduction 1
1.1 Review of PreviousWork 1
1.2 Thesis Organization 3
2 Preliminaries 4
2.1 Partitioning-Based Placement 4
2.2 TimingModel 5
2.3 Problem Formulation 8
3 Placement Methodology 10
3.1 Flow of Our Methodology 10
3.2 Partition-Based 3D IC Placement 11
3.3 Alignment Constraint 15
3.4 Simulated-Annealing Timing Driven Placement16
3.5 Legalization 18
4 Experimental Results 20
5 Conclusion and Future Work 24

[1] H. Hua, C. Mineo, K. Schoenfliess, A. Sule, S. Melamed, R. Jenkal, and W. R. Davis,
“Exploring compromises among timing, power and temperature in three-dimensional
integrated circuits,” In Proceedings of ACM/IEEE Design Automation Conference, pp.
997-1002, 2006.
[2] D. H. Kim, S. Mukhopadhyay, and S. K. Lim, “Through-Silicon-Via aware interconnect
prediction and optimization for 3D Stacked ICs,” In Proceedings of International
Workshop on System-Level Interconnect Prediction, pp. 85-92, 2009.
[3] S. K. Lim, “TSV-Aware 3D physical design tool needs for faster mainstream acceptance
of 3D ICs,” ACM DAC Knowledge Center (dac.com), 2010.
[4] G. Chen, and S. Sapatnekar, “Partition-Driven standard cell thermal placement,” In
Proceedings of International Symposium on Physical Design, pp. 75-80, 2003.
[5] W. Sui, S. Dong, J. Bian, and X. Hong, “Fast wirelength-driven partition-based placement
for island style FPGAs,” In Proceedings of Joint Conference on Information Sci-ences , 2008.
[6] Y. C. Chou, and Y. L. Lin, “A performance-driven standard-cell placer based on a modified
force-directed algorithm,” In Proceedings of International Symposium on Physical
Design, pp. 24-29, 2001.
[7] C. Hwang, and M. Pedram, “Timing-driven placement based on monotone cell ordering
constraints,” In Proceedings of the Asia and South Pacific Design Automation Conference,
pp. 201-206, 2006.
[8] S. Raman, C. L. Liu, and L. G. Jones, “Timing-constrained FPGA placement: A forcedirected
formulation and its performance evaluation,” VLSI Design, vol. 4, no.4 ,pp.
345-355, 1996.
[9] A. B. Kahng, and Q. Wang, “An analytic placer for mixed-size placement and timingdriven
placement,” In Proceedings of IEEE/ACM International Conference on Computer
Aided Design, pp. 565-572, 2004.
[10] X. Yang, B. Choi, and M. Sarrafzadeh “Timing-driven placement using design hierarchy
guided constraint generation,” In Proceedings of IEEE/ACM International Conference
on Computer Aided Design, pp. 177-180, 2002.
[11] C. Sechen, and W. Swartz, “Timing driven placement for large standard cell circuits,”
In Proceedings of ACM/IEEE Design Automation Conference, pp. 211-215, 1995.
[12] Z. Xiu, and R.A. Rutenbar, “Timing-driven placement by grid-warping,” In Proceedings
ACM/IEEE Design Automation Conference, pp. 585-591, 2005.
[13] P. Maidee, C. Ababei, and K. Bazargan, “Timing-driven partitioning-based placement
for island style FPGAs,” IEEE transaction on Computer-Aided Design of Integrated
Circuits and Systems, vol. 24, no. 3, pp. 395-406, March 2005.
[14] S. L. Ou, and M. Pedram, “Timing-driven placement based on partitioning with dynamic
cut-net control,” In Proceedings of ACM/IEEE Design Automation Conference,
pp. 472-476, 2000.
[15] D. Sinha, N. V. Shenoy, and H. Zhou, “Statistical Gate Sizing for Timing Yield Optimization,”
In Proceedings of IEEE/ACM International Conference on Computer Aided
Design , pp. 1037-1041, 2005.
[16] W. P. Lee, H. Y. Liu, and Y. W. Chang “Voltage island aware floorplanning for power
and timing optimization,” In Proceedings of IEEE/ACM International Conference on
Computer-Aided Design, pp. 389-394, 2006.
[17] H. Wu, M. D. R. Wona, and I. Liu, “Timing-constrained and voltage-island-aware voltage
assignment,” In Proceedings of ACM/IEEE Design Automation Conference, pp.
429-432, 2006.
[18] J. F. Lee, and D. T. Tang, “An algorithm for incremental timing analysis,” In Proceedings
of ACM/IEEE Design Automation Conference, pp. 696-701 ,1995.
[19] H. F. Jyu, S. Malik, S. Devadas, and K. W. Keutzer, “Statistical timing analysis of combinational
logic circuits,” IEEE Transactions on Very Large Scale Integration (VLSI)
Systems, vol. 1, no. 2, pp. 126-137 ,Jun 1993.
[20] M. C. Yildiz, and P. H. Madden, “Improved cut sequences for partitioning based placement,”
In Proceedings of ACM/IEEE Design Automation Conference, pp. 776-779, 2001.
[21] T. C. Chen, T. C. Hsu, Z. W. Jiang, and Y. W. Chang, “NTUplace: A ratio partitioning
based placement algorithm for large-scale mixed-size designs,” In Proceedings of
International Symposium on Physical Design, pp. 236-238, 2005.
[22] l. Savidis, S. M. Alam, A. Jain, S. Pozder, R. E. Jones, and R. Chatterjee “Electrical
modeling and characterization of through-silicon vias (TSVs) for 3-D integrated
circuits,” Microelectronics Journal, vol. 41, no. 1, pp. 9-16, 2010.
[23] J. Cong, and G. Luo, “Thermal-Aware 3D Placement,” Integrated Circuits and Systems,
pp. 103-144, 2010.
[24] http://dropzone.tamu.edu/˜xiang/iscas.html
[25] W. C. Elmore, “The transient response of damped linear networks with particular regard
to wideband amplifiers,” Journal of Applied Physics, vol. 19, no. 1, pp. 55-63, Jan 1948.
[26] H. Ren, D.Z. Pan, and D.S. Kung “Sensitivity guided net weighting for placement
driven synthesis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systemsn, vol. 24, no. 5, pp. 711- 721, May 2005.
[27] A. Y. Weldezion, R. Weerasekera, D. Pamunuwa, and L. R. Zheng, and H. Tenhunen
“Bandwidth optimization for through silicon via (TSV) bundles in 3D integrated circuits,”
In Proceedings Design, Automation and Test in Europe Conference, 2009.
[28] M. Grange, R. Weerasekera, D. Pamunuwa, H. Tenhunen, and L. R. Zheng, “Closedform
equations for through-silicon via(TSV) parasitics in 3-D integrated circuits,” In
Proceedings Design, Automation and Test in Europe Conference, 2009.
[29] R. Hentschke, and R. Reis, “A 3D-Via Legalization Algorithm for 3D VLSI Circuits
and its Impact on Wire Length,” In Proceedings of IEEE International Symposium on
Circuits and Systems, pp. 2036-2039, 2007.
[30] P. Spindler, U. Schlichtmann, and F. M. Johannes “Abacus: Fast Legalization of Standard
Cell Circuits with Minimal Movement,” In Proceedings of International Symposium
on Physical Design, pp. 47-53 , 2008.
[31] A. Khatkhate, C. Li, A. R. Agnihotri, M. C. Yildiz, S. Ono, C. Koh, and P. H. Madden
“Recursive bisection based mixed block placemen,” In Proceedings of International
Symposium on Physical Design, pp. 84-89 , 2004.
[32] C. T. Lin, D. M. Kwai, Y. Fa. Chou, T. S. Chen, and W. C. Wu “CAD Reference
Flow for 3D Via-Last Integrated Circuits,” In Proceedings of the Asia and South Pacific
Design Automation Conference, pp. 187-192 , 2010.
[33] A. Marquardt, V. Betz, and J. Rose “Timing-driven placement for FPGAs,” In Proceedings
of ACM/SIGDA eighth International Symposium on Field Programmable Gate
Arrays, pp. 203-213 , 2000.