臺灣博碩士論文加值系統

標準元件的佈局因為合成方法(synthesis methodology)和自動佈局和繞線(APR)流程的成功而大受歡迎。然而隨著製程的演進，電路內部線路的時間延遲相對於閘的時間延遲是越來越重要。在這篇論文中我們提出一個階層式以模組(module)沿著最長路徑將最主要的模組建成硬巨集(Hard-macro)，再將其他的元件包含進來，如此對整個電路設計而言，們是分成階層式的二階段處理電路。在此論文中，第一章我們簡介了階層式以模組為主的佈局概念；第二章我們討論了過去的相關研究；第三章我們提出我們的設計流程；第四章我們針對這個問題提出整體的佈局演算法，決定模組的相關位址，以及細部的佈局演算法，決定模組的寬和高的比例；第五章是我們的實驗結果；第六章是結論和未來的方向。由實驗的結果可以發現我們的方法有效的縮短在最長路徑的線長度(wire length.)。標準元件的佈局因為合成方法(synthesis methodology)和自動佈局和繞線(APR)流程的成功而大受歡迎。然而隨著製程的演進，電路內部線路的時間延遲相對於閘的時間延遲是越來越重要。在這篇論文中我們提出一個階層式以模組為主的佈局方法，沿著最長路徑將最主要的元件建成硬巨集(Hard-macro)。再許多設計裡面，乘法器扮演一個舉足輕重的角色,尤其是在資料運算量大的設計中,乘法器通常都是位於最主要的部位,比如在DSP(Digital Signal Processing)。於是我們將一個乘法器建成硬巨集（Ｈard-macro）再將其他的元件包含進來，如此對整個電路設計而言，們是分成階層式的二階段處理電路。將給予RTL(Register Transfer Level)的程式碼,經由synopsys DA轉換成階層式的gate-level netlist，依照我們提出的方法：(1)初始階段，用來建立表示模組間關聯的階層式結構樹。(2)整體佈局階段，利用線連結數決定模組的相關位置。(3)細部佈局階段，利用調整寬高比消除模組間的重疊。沿著最長路徑將最主要的模組建成硬巨集以縮短最長路徑的線長度。

Layout optimization problem of integrated circuit design become more and more important. As the IC industry moves toward deep sub-micron era, interconnection delay will more important then gate delays. Therefore, the interconnection delay in deep sub-micro can no longer be neglected.
In this thesis, we present a structure-like method to perform performance-driven placement. Most electronic designs are described by hierarchical register-transfer schematics.
Today, most electronic designs are described by hierarchical register-transfer schematics. In addition to gates, latches, and flip-flops, schematics include register-transfer components, such as register, counters, ALU’s, shifters, multiplexers, and macro-cells. These designs are usually described as a mixed RTL/logic/gate-level description in HDLs such as Verilog and VHDL. Ideally, an HDL design description is represented as a set of interconnected modules in a hierarchical way so that the design hierarchy can be preserved. However, when designers use HDLs to describe their design specifications and behaviors, the HDL design description is predominately by designers’ coding styles.

ABSTRACT 1
CONTENTS 2
LIST OF FIGURES 3
LIST OF TABLES 4
CHAPTER 1 INTRODUCTION 5
CHAPTER 2 RELATED WORK 9
CHAPTER 3 THE DESIGN FLOW 14
CHAPTER 4 THE PLACEMENT ALGORITHM 17
4-1 PROBLEM FORMULATION 17
4.2 GLOBAL PLACEMENT 18
4-3 ALGORITHM OF DETAIL PLACEMENT 22
4-4 HARD MACRO FORMATION 26
4.5 A WALK THROUGH EXAMPLE 31
CHAPTER 5 EXPERIMENTAL RESULTS 38
CHAPTER 6 CONCLUSIONS 43
REFERENCE 44

[1] M. A. Breuer, “A class of min-cut placement algorithms,” Proceedings of Design Automation Conference, pp.284-290, 1977.
[2] M. A. Breuer, “Min-cut placement,” Journal of Design of Automation and Fault-Tolerant Computing, pp 343-382, Oct. 1977.
[3] K. M. Hall, “An r-dimensional quadratic placement algorithm,” Management Science, 17:219-229, November 1970.
[4] T. Gao, P. M. Vaidya, C. L. Liu, “A new performance driven placement algorithm,” International Confereence on Computer-Aided Design, pp.44-47,IEEE/ACM,1991.
[5] P.S Hauge, R. Nair, and E. J.Yoffa, “Circuit placement for pre dictable performance,” International Conference on Computer-Aided Design, pp.88-91, IEEE/ACM, 1987.
[6] W.E. Donath et.al, “Timing drived placement using complete path delays,” Proceedings of the 27th Design Automation Conference (DAC), pp.84-89,1990.
[7] M.A.B. Jackson, and E.S. Kuh, “Performance driven placement of cell based IC’s,” Proceeding of the 26th Design Automation Conference, pp.370-375, Jun.1990.
[8] S. Dey, F. Beglez and G. kedem, “Circuit partition for logic synthesis,” IEEE Journal of Solid-Stage Circuits, vol.26, pp.350-363, Mar. 1991.
[9] Gotaro Odawara, Takahisa Hiraide and Osamu Nishina, “Partitioning and placement technique for CMOS gate arrays,” IEEE Trans. On Computer-Aided Design, vol.CAD-6, pp.355-363, May 1987.
[10] Y. C. Wei and C.K. Cheng, “Ratio cut partitioning for hierarchical designs,” IEEE Trans. On Computer-Aided Design, vol. CAD-10, pp.911-921, Jul. 1991.
[11] H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, “VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair,” IEEE Trans. On Computer-Aided Design, vol.15, NO. 12, Dec 1996.
[12] H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, “Rectangle-packing-based module placement,” in IEEE Int. Conf. Computer-Aided Design, pp.472-479 1995.
[13] C-K Cheng and E. S. Kuh. “Module placement based on resistive network optimization,” IEEE Trans. On Computer-Aided Design, pp.218-225,3 1984.
[14] W. M. Dai and E. Kuh, “ Simaltaneous Floorplanning and Global Routing for Hierarchical Building Block Layout, “ IEEE Trans. on CAD, vol. CAD-6, no. 5, pp828-837, 1987.
[15] B. W. Kernighan and S.Lin, “An efficient heuristic procedure for partitioning graphs, “ Bell system Technical Journal, vol.49, pp.291-307, Feb. 1970.
[16] N. Sherwani, “Algorithms for VLSI physical design automation, “ Reading, Kluwer Academic Publishers Press, 1993.
[17] C. M. Fiduccia and R.M. Matteses, “A linear-time heuristic for improving network partitions,” Proceedings of the 19th Design Automation Conference (DAC), pp.241-247,1982.
[18] L.A. Sanchis, “Multi-way network partitioning,” IEEE Trans. On computer, vol. 38, pp.62-81, Jan. 1989.