高效率增量時態優化布局

On Efficient Incremental Placement for Timing Improvement

吳韋辰(Wei-Chen Wu)

指導教授 ： 陳宏明

國立交通大學/電機學院/電子工程系所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.01019

摘要

在晶片設計流程中的全域佈局步驟，時態問題可以粗略地被優化。然而，有許多的因素必須同時被考慮在全域步局步驟中，例如:繞線擁擠問題、功率問題、等，要在該階段將時態問題完全地解決是有相當的難度，因此在實體設計中步進時態優化佈局變得更加重要。透過將電路模塊重新擺放以解決有違反時態限制的邏輯路徑，本篇論文提出的演算法不同於傳統的步進時態優化步局，會考慮實際繞線後的時序延遲，而非只是連線兩點的最短路徑的時序延遲。為了得到精準的時序，需要先對所有電路模塊繞線，並從靜態時序分析獲取相關資訊。我們也解決另一個在優化過程中會出現的問題，即為了優化時態將電路模塊彼此拉近，進而造成佈局密度上升，更可能使得繞線空間不足，本篇論文的方法會盡量維持初始的佈局密度的條件下進行時態優化，並且透過控制非違反時態限制的路徑的時序擾動以達到最小化地改變電路模塊位置。本篇論文有兩點貢獻：(1)快速且有效率地對時序優化並維持初始的佈局密度，(2)移動電路模塊後能局部地對時序更新，不需要時態分析器對整體電路重新計算。任何已經過佈局合法化即無電路模塊重疊擺放的電路皆可當作此演算法的輸入。實驗結果的案例是由2014CAD競賽提供。

關鍵字

時態 ； 布局 ； 增量布局

並列摘要

In global placement step, the timing problem can be treated roughly. Nevertheless, many factors have to be included in this step (ex. routing congestion, power issue, ...), the circuit may have some negative slack paths. Incremental timing driven placement becomes more crucial step in physical design of integrated circuits. The step improves the timing for critical paths by relocating circuit modules to fix negative slack iterativly. Unlike conventional timing-driven placers which analyze timing without interconnect delay, to truly analyze timing path, the placer routes all modules and gets accurate timing from a static timer. Another critical problem is to optimize timing. The proposed approach can improve timing without degrading placement density. Furthermore, this approach tries to minimize modifications to the initial placement by controlling the timing perturbation on non-critical paths while optimizing critical path. Two contributions of this work are 1) fast and efficient data path timing optimization without increasing in placement density and 2) the placer can update timing quickly without calling timer and Our approach can take any initial legalized placement and improve timing or placement density. Experimental results on a set of CAD contest 2014 benchmarks for timing.

並列關鍵字

timing ； placement ； incremental placement

參考文獻

[1] B. Halpin, C. R. Chen, and N. Sehgal. Timing driven placement. In Proc. DAC, pp. 780-783, 2001.

[2] W. Hou, X. Hong, W. Wu, and Y. Cai. A path-based timingdriven quadratic placement algorithm. In Proc. ASPDAC, pp. 745-748, 2003

[3] T. Kong. A novel net weighting algorithm for timing-driven placement. In Proc. ICCAD, pp.172-176, 2002.

[4] T. Luo, D. Newmark, and D. Z. Pan. A new LP based incremental timing driven placement for high performance designs. In Proc. DAC, pp. 1115-1120, 2006.

[5] W. Choi and K. Bazargan. Incremental placement for timing optimization. In Proc. ICCAD, pp. 463-466, 2000.