針對繞線導向藉由路徑群組輔助時序考量力引導之標準元件置放演算法

A Timing-Aware Force-Directed Algorithm for Wirelength-Driven Standard Cell Placement using Path Grouping

陳柏偉(Bo-Wei Chen)

指導教授 ： 王廷基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

置放問題的結果對於晶片的可繞線程度、晶片面積大小、耗能、效能皆有很大的影響， 所以其在IC後段設計的流程中佔有很重要的部分，並成為一個多年來的熱門研究領域。在本篇論文中，我們提出一個考慮時序，且以連線長度為考量的標準元件置放演算法，使用的技術為加入一個新的力(考慮時序的力)到一個以力導向為基礎的置放器，希望能同時對連線長度和時序做最佳化。我們將所提出的演算法結合到一個以連線長度為主要考量的置放器，希望能找到連線長度較小且時序較佳的置放結果。實驗結果顯示，我們的演算法在平均連線長度上，比起僅考慮連線長度的置放器和商業的置放器分別達到1.8%和7.8%的改善;同時，在時序表現的平均改善也分別達到2.2%和2.6%。

關鍵字

置放 ； 時序 ； 連線長度 ； 標準元件

並列摘要

Placement always plays an important part in a back-end design flow and is an active research area for many years, because it significantly affects the routability, chip size, chip power, and chip performance. In this thesis, we propose a timing-aware standard-cell placement algorithm, which introduces a new force (timing force) into a force directed based placer to optimize wirelength and timing concurrently. We combine our method with a wirelength-driven placer, and want to find smaller wirelength with better circuit performance. Experimental results show that our method achieves average routed wirelength reduction by 1.8% and 7.8% as compared to an existing wirelength-driven placer and to a commercial placer, respectively. At the same time, the critical path delays of five test cases are also averagely reduced by 2.2% and 2.6%, respectively.

並列關鍵字

placement ； timing ； wirelength ； standard cell

參考文獻

[1] P. Gopalakrishnan, A. Obasioglu, L. Pileggi, and S. Raje, “Overcoming Wireload Model Uncertainty During Physical Design,” in Proc. ACM/IEEE ISPD, 2001.

[2] H. Eisenmann and F. M. Johannes, “Generic Global Placement and Floorplanning,” in Proc. ACM/IEEE DAC, 1998.

[3] Y. C. Chou and Y. L. Lin, “A Performance-driven Standard-Cell Placer Based on a Modified Force-Directed Algorithm,” in Proc. ACM/IEEE ISPD, 2001.

[5] Z. Xiu and R. A. Rutenbar, “Timing-Driven Placement by Grid-Warping,” in Proc. ACM/IEEE DAC, 2005.

[6] A. B. Kahng, I. L. Markov and S. Reda, “Boosting: Min-Cut Placement with Improved Signal Delay,” in Proc. IEEE DATE, 2004.