延遲導向技術映射之動態準確度精進法

A Dynamic Accuracy-Refinement Approach to Timing-Driven Technology Mapping

黃思誠(Sz-Cheng Huang)

指導教授 ： 江介宏

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00548

摘要

技術映射的目的是尋找一種最佳的布林網路實作，而該實作是由一技術資料庫內的各種邏輯閘而組成。與複雜度為NP-complete的面積最佳化問題相比，有向非循環圖之技術映射使延遲最佳化是一更為複雜的問題，因為邏輯閘的匹配必須要在訊號真實的到達時間與輸出負載皆為未知的情況下做出選擇。傳統上解決這個問題的方法牽涉了太多的近似與簡化，因此而不夠準確。這些方法不外乎利用樹狀技術映射（而非有向非循環圖技術映射），或採用不涉及負載的延遲估計模型（而非涉及負載的延遲估計模型），來得到一個映射後的電路圖。

與傳統的方法不同的是，本論文直接在有向非循環圖上採用涉及負載的延遲估計模型來解決這個問題。能達到準確的估計是因為幾個其中的幾個重要技巧，包含即時負載估計精進法、鞏固負載的深先反向包覆，與利用分段線性函數來達到準確的時間計算。

這個新的技術映射演算法透過數種不同的實驗來評鑑。包括了電路延遲時間與面積的比較、執行時間的比較、不同估計負載方法的比較等等。實驗結果顯示對於大型電路，平均而言我們的方法能比已知最先進的映射工具減少百分之三十八點九的延遲、增加百分之十點八的電路面積。同時，即使是應用在大型電路上，我們的方法仍可以在幾秒鐘的時間內完成。因此總結而言，這個新的演算法不只能夠在準確的估計時有效地減少電路延遲，並且能夠有效率的得到一個映射電路。

關鍵字

最佳化 ； 演算法 ； 圖形覆蓋 ； 電子設計自動化 ； 邏輯合成 ； 技術映射

並列摘要

Technology mapping aims at searching an optimal implementation for a Boolean netlist using gates from a technology library. Compared with its $NP$-complete area minimization counterpart, DAG mapping for delay minimization is considered much sophisticated because matching choices must be made without knowing actual arrival times and output loads. Traditional approaches to this problem involve too many approximate simplifications, and are far from accurate. They either use tree mapping, but not DAG mapping, or apply a load-independent timing model, but not a load-dependent timing model to obtain a mapped netlist.

Unlike traditional approaches, this thesis tackles this problem directly under load-dependent DAG mapping. The enabling techniques for accurate optimization include on-the-fly load-estimation refinement, breadth-first backward covering for load consolidation, and use of a piecewise linear model for accurate timing calculation.
This new technology mapping algorithm is evaluated through several experiments. They include comparisons for delay and area, for run times, for load-estimation heuristics, etc. Experimental results show that our method outperforms the state-of-the-art mapper by 38.9\% in delay, with 10.8\% increase in area, on average for large benchmark circuits. Meanwhile, our method can be finished within few seconds, even for large circuits. Thus, our new algorithm can not only effectively reduce circuit delay with an accurate estimation, but also efficiently obtain a mapping solution.

並列關鍵字

Optimization ； Algorithm ； Graph Covering ； Electronic Design Automation ； Logic Synthesis ； Technology Mapping

參考文獻

[AJU77] A. V. Aho, S. C. Johnson, and J. D. Ullman. Code generation for expressions with common subexpressions. J. ACM, 24(1):146–160, 1977.

[CD93] Jason Cong and Yuzheng Ding. On area/depth trade-off in LUT-based FPGA technology mapping. In Proc. DAC, pages 213–218, New York, NY, USA, 1993.

[CD95] Jason Cong and Yuzheng Ding. On nominal delay minimization in LUT-based FPGA technology mapping. In Proc. FPGA, pages 82–88, 1995.

[CMB+05] S. Chatterjee, A. Mishchenko, R. Brayton, X. Wang, and T. Kam. Reducing structural bias in technology mapping. In Proc. ICCAD, pages 519–526, San Jose, CA, November 2005.

[CP92] K. Chaudhary and M. Pedram. A near optimal algorithm for technology mapping minimizing area under delay constraints. In Proc. DAC, pages 492–498, Los Alamitos, CA, USA, 1992. IEEE Computer Society Press.