臺灣博碩士論文加值系統

本篇論文我們提出一個新的設計方法來找到一個最佳的平面規劃，同時建立相對應的電源網格，並且考慮電壓降和電子遷移等的限制下最小化所使用的繞線資源。我們提出的方法藉由先決定好電源供應網路再來決定平面規劃，這打破了以往傳統的設計方式。同時藉由一個新的而且有效的電源供應網路表格來為快速的訊號完整性分析提供大量的資訊。我們使用基於基因演算法的固定外框導向平面規劃演算法來找平面規劃的解，並且確定符合訊號完整性。這個方法不只不需要因為分析電路而重複作龐大的反矩陣運算，因而明顯的加速最佳化的過程，也縮短了一個設計從平面規劃到電源分析的整個設計時間。

In this paper, we present a novel design methodology to find an optimized floorplan and simultaneously establish its corresponding mesh-based power network so that the used power routing resource is minimized with considering IR voltage drop and electromigration (EM). This proposed methodology breaks the traditional physical design procedure by building power network prior to deciding floorplanning. A novel and efficient regular power network table is created to provide gradient information for fast signal-integrity (SI) estimation, which results in efficient solution exploration. Based on the concept of genetic algorithm, a fixed-outline driven floorplanning algorithm is applied to explore floorplans to gradually satisfy the SI issues. The proposed flow not only significantly speeds up the optimization process, without repeatedly calculating complex matrix inverse, but also shortens the turn-around time from floorplanning to power analysis of a design.

致 謝 i
摘 要 ii
Abstract iii
目 錄 iv
圖目錄 v
表目錄 vii
第一章 簡介 1
1.1簡介 1
1.2動機與目的 1
1.3 論文架構 3
第二章 相關研究 5
2.1 Yim’s Method 5
2.2 Singh and Sapatnekar Method 7
2.3 Wu and Chang’s Work 9
2.4 Wang and Sadowska’s Method 12
2.5 Liu and Chang’s Method 14
第三章 問題描述 17
3.1 Block資訊 17
3.2 電源供應網路模型 17
3.3 電源限制 19
3.4 電源分析方式 21
第四章 演算法與程式流程 23
4.1固定外框導向平面規劃器(Fixed-outline Driven Floorplaner ) 24
4.1.1 波蘭表示法 ( Polish Expression) 24
4.1.2 固定外框導向基因平面規劃演算法 26
4.2 Power Mesh Table (PMT) 27
4.3 Regular Mesh Optimizing 29
4.4 IR Drop分析和調整 29
4.5 變換Power Table機制 32
4.6 完整流程 33
第五章 實驗結果 36
第六章 結論與未來研究方向 42
參考文獻 43

[1] H. Cai, “Multi-pads single layer power net routing in VLSI circuit,” Proc. DAC, pp. 183–188, 1988.
[2] K. H. Erhard, F. M. Johannes, R. Dachauer, “Topology optimization techniques for power/ground networks in VLSI,” Proc. EURO-DAC, pp. 362-367, 1992.
[3] T. Mitsuhashi and E. S. Kuh, “Power and ground network topology optimization for cell based VLSIs,” Proc. DAC, pp. 524-529, 1992.
[4] J. Oh and M. Pedram, “Multi-pad power/ground network design for uniform distribution of ground bounce,” Proc. DAC, pp. 287–290, 1998.
[5] J.-S. Yim, S.-O. Bae, and C.-M. Kyung, “A floorplan-based planning methodology for power and clock distribution in ASICs,” Proc. DAC, pp. 766-771, 1999.
[6] X. Wu, C. Qiao and X. Hong. “Design and optimization of power/ground network for cell-based VLSIs with macro cells,” Proc. ASP-DAC, pp. 21-24, 1999.
[7] J. Singh and S. S. Sapatnekar, “Topology optimization of structured power/ground networks,” Proc. ISPD, pp. 116-123, 2004.
[8] S.-W. Wu and Y.-W. Chang, “Efficient power/ground network analysis for power integrity-driven,” Proc. DAC, pp. 177–180, 2004.
[9] K. Wang and M.-S. Malgorzata, “On-chip power supply network optimization using multigrid-based technique,” IEEE Trans. of Computer-Aided Design, pp. 407-417, 2005.
[10] Chen-Wei Liu and Yao-Wen Chang, “Floorplan and Power/Ground Network Co-Synthesis for Fast Design Convergence,” Proc. ISPD, pp. 86-93, 2006.
[11] S. Chowdhury and M. A. Breuer, “Optimum design of IC power/ground nets subject to reliability constraints,” IEEE Trans. of Computer-Aided Design, pp. 787-796, 1988.
[12] R. Dutta and M. Marek-Sadowska, “Automatic sizing of power/ground (P/G) networks in VLSI,” Proc. DAC, pp.783–786, 1989.
[13] X. Tan, C.-J. R. Shi, D. Lungeanu, J.-C. Lee, and L.-P. Yuan, ”Reliability-constrained area optimization of VLSI power/ground networks via sequence of linear programming,” Proc. DAC, pp.78-83, 1999.
[14] X. Tan and C.-J. R. Shi, “Fast power/ground network optimization based on equivalent circuit modeling,” Proc. DAC, pp550-554, 2001.
[15] X. Wu, X. Hong, Y. Cai, Z. Luo, C.-K. Cheng, J. Gu, and W. Dai, “Area minimization of power distribution network using efficient nonlinear programming techniques,” Proc. ICCAD, pp. 153–157, 2001.
[16] T. Wang and C. C. Chen, “Optimization of the power/ground network wire-sizing and spacing based on sequential network simplex algorithm,” Proc. ISQED, pp. 157–162, 2002.
[17] H. H. Chen and D. D. Ling, “Power supply noise analysis methodology for deep-sub-micron VLSI chip design,” Proc. DAC, pp. 638–643, 1997.
[18] H. Su, K. H. Gala, and S. S. Sapatnekar, “Fast analysis and optimization of power/ground networks,” Proc. ICCAD, pp. 477–480, 2000.
[19] H. Su, S. S. Sapatnekar, and S. R. Nassif, “An algorithm for optimal decoupling capacitor sizing and placement for standard cell layouts," Proc. ISPD, pp. 68-73, 2002.
[20] S. Zhao, K. Roy, and C.-K. Koh, “Decoupling capacitance allocation for power supply noise suppression,” IEEE Trans. of Computer-Aided Design, pp. 81-92, 2002.
[21] A. Dharchoudhury, R. Panda, D. Blaauw, and R. Vaidyanathan, “Design and analysis of power distribution networks in PowerPC microprocessors,” Proc. DAC, pp.738-743, 1998.
[22] K. Gala, V. Zolotov, R. Panda, B. Young, J. Wang, and D. Blaauw, “On chip inductance modeling and analysis,”Proc. DAC, pp. 63–68, 2000.
[23] S. R. Nassif and O. Fakhouri, “Technology trends in power-grid-induced noise,” Proc. SLIP, pp. 55–59, 2002.
[24] C. Ho, A. Ruehli, and P. Brennan, “The modified nodal approach to network analysis,” IEEE Trans. Circuits and Systems, pp. 504–509, 1975.
[25] C.T. Lin, D.S. Chen and Y.W. Wang, "An Efficient Genetic Algorithm for Slicing Floorplan Area Optimization," Proc. of ISCAS, pp.II-879 -II-882, May 2002.