實體設計系統之建構與演算法開發

Physical Design System Construction and Algorithms Development

紀俊呈(Jun-Cheng Chi)

指導教授 ： 陳美麗

中原大學/工學院/電子工程研究所/博士(2006年)

https://doi.org/10.6840/CYCU.2006.00446

摘要

中 文 摘 要

在本論文中，我們提出一個實體設計系統的架構。此架構包含一個共同的資料庫、一個LEF/DEF輸出及輸入的轉換程式、資料存取函式庫、最佳化程式集及一個使用者圖形介面。此架構具有容易擴充及容易維護的優點。在此架構之下，我們建構出一個整合時序導向的電路分割、平面規劃及元件擺置系統。在此系統的平面規劃及元件擺置階段，我們均提出新的時序導向最佳化演算法。在此系統的設計流程中，為了維持各個不同階段的成本函數的一致性，我們使用相同的Critical Path資訊，並使用相同的時序估算模型(delay model)來預估Critical Path的延遲時間。此時序導向系統已與商業CAD軟體的設計流程整合。並隨著VLSI設計的演進，持續加強其功能，以解決隨著製程的進步，所衍生出的問題。在此論文中，我們研究在平面規劃、元件擺置及低功率設計領域所衍生的問題，並提出最佳化演算法。
在平面規劃階段，我們提出一個可同時處理硬模組(hard module)及軟模組(soft module)的平面規劃演算法。此演算法採用序列對(sequence pair)的平面規劃表示法，並在模擬退火的過程中，對每個軟模組找出四個可供選擇的外形。這些候選的外形(candidate shape)提供了較佳的機會可以得到區域最佳解(local optimal solution)，進而有較大機會可以得到整體的最佳解(global optimal solution)。實驗結果顯示此演算法相當有效率。
在元件擺置階段，我們提出一個電壓降暨時序導向的元件擺置演算法，在元件擺置的過程中最佳化晶片的最大電壓降效應，並同時考量晶片的時序。實驗結果顯示，與商業的CAD工具軟體Cadence/QPlace相比， 本演算法可得到具有較低最大電壓降效應的元件擺置結果。較低的電壓降效應，將大大提升晶片的可靠度，並可減少電力線(power/ground nets)所佔用的空間成本。隨著製程的演進，較窄的金屬線將會導致較嚴重的電壓降效應。而在設計流程中若不考慮此電壓降效應，將可能導致晶片產生嚴重的電壓降，進而影響晶片的時序。
最後，我們研究應用於多重電壓源設計的電壓調整(voltage scaling)方法。在此論文中，我們提出一個整合greedy及反覆式最佳化(iterative optimization)方法的二階段電壓調整方法。此演算法可將具有高slack的標準元件，由較高的供應電壓調整(scale)為較低的供應電壓，以降低晶片的功率消耗。我們的研究結果顯示，在一個使用電壓調整技術的晶片上，其最低的電壓值，對於此晶片的功率消耗，具有決定性的影響。而我們知道使用較多的供應電壓，工程師必須花費較多的時間成本，配置較多的電壓島及規劃電力線的繞線。因此相較於使用多重電壓源的設計方法，使用雙重電壓源設計，將可同時兼顧改善功率消耗及減少時間成本。藉由使用此電壓調整的方式，將可大大降低晶片的功率消耗。

關鍵字

電壓降 ； 元件擺置 ； 計算機輔助設計 ； 平面規畫 ； 多重電壓源調整 ； 時序導向 ； 訊號完整度 ； 低功率 ； 實體設計系統

並列摘要

Abstract

In this thesis, we develop a physical design system. First, an architecture of the physical design system is proposed. This architecture consists of a central database, a LEF/DEF translator, a set of access utilities, a set of optimization processes, and a graphic user interface. The architecture is easy to be extended and maintained. Based on the architecture, an integrated timing-driven partitioning, floorplanning, and placement system has been constructed. In both floorplanning and placement stages, two novel timing-design methodologies are proposed to optimize the timing of the circuit. During the system flow, we use the same critical path information and the same models for delay estimation to increase the consistency of the cost functions in different stages. The timing-driven system is also integrated with a commercial CAD design flow. The system is continuously enhanced with the progress of the VLSI design. In this thesis, we also study the problems which are accompanied with the advancing of the VLSI process. We present the algorithms in the areas of the floorplan, placement, and low power design methodologies.
An effective hard/soft modules floorplanning algorithm is proposed. It uses simulated annealing framework based on the sequence pair representation. We proposed a method which finds four candidates of module shape to be chosen in a simulated annealing process for each module. These candidates provide a better choice toward local optimal packing. The proposed algorithm may be extended to handle the connectivity and different placement constraints. Experimental results show that the approach is very effective.
At placement stage, we proposed an IR drop-driven standard cell placement algorithm which simultaneously minimizes the maximum IR drop of a design and considers the critical path delay. The proposed algorithm can reduce the maximum value of IR drop among all rows at the placement stage. Experimental results show that the proposed algorithm may produce a placement with lower maximum IR drop value compared to the Cadence/QPlace. The placement with a lower maximum IR drop is more reliable and needs less power/ground straps or a coarser power grid in the design. Thus, more routing resources can be used for routing signal nets. With the advancement of technology, VLSI designs will become more complex with higher frequencies and lower supply voltages. It will cause more serious IR drop and timing closure problems.
Finally, we also study the multiple voltages scaling problem for low power designs. A two-phase voltage scaling algorithm for VLSI circuits is proposed. The proposed algorithm utilizes the slack of each gate to scale down the voltages of the gates. It combines a greedy approach and an iterative optimization method to scale the supply voltage of gates effectively. Our study also shows the lower bound value of the voltage domains is the main factor in determining power savings. If more voltage domains are used, more voltage islands will be needed and designers will be burdened with the chore of accommodating the extra voltage islands in their designs. Thus, using dual voltage domains is a good choice both for saving power and facilitating the design effort. By applying lower supply voltages on non-timing critical gates, we can greatly reduce the total power consumption.

並列關鍵字

Physical Design System ； Placement ； Floorplan ； CAD ； Voltage Drop ； Signal Integrity ； Timing-Driven ； Multiple Voltage Scaling

參考文獻

[1] X. Tang and D. F. Wang, “FAST-SP: A Fast Algorithm for Block Placement based on Sequence Pair,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 521-526, 2001.

[4] H. Murata, E. S. Kuh, “Sequence-Pair Based Placement Method for Hard/Soft/Pre-Placed Modules,” Proc. ISPD, pp.167-172, 2000.

[5] F. Y. Young; Chris C. N. Chu, W. S. Luk, Y. C. Wong, “Floorplan Area Minimization using Lagrangian Relaxation,” Proceedings of the international Symposium on Physical Design, pp. 174-179, 2000.

[6] P. Chen, E. S. Kuh, “Floorplan Sizing by Linear Programming Approximation,” on Proceedings of the 37th Design Automation Conference, pp. 468-471, 2000.

[9] Joon-Seo Yim, Seong-Ok Bae, and Chong-Min Kyung, “A floorplan-based planning methodology for power and clock distribution in ASICs [CMOS technology]”, Proceedings of 36th Design Automation Conference, 1999, pp. 766-771. (New Orleans, Louisiana,1999)