臺灣博碩士論文加值系統

隨著超大型積體電路的設計應用到次微米技術(DSM)，設計者時常會發現所設計的電路不能達成時序的需求，而且甚至發現重複執行了幾次邏輯合成和實體合成之後，電路的時序無法收斂 (Timing closure problem)。導致問題的主要原因之一來自於邏輯合成和實體的佈局之間的微弱的相動關係。在傳統的設計流程中，邏輯合成使用簡單導線負載模型(wire load model)估量導線的遲延。另一方面，實體佈局合成後能獲得精確的導線時序資訊，但不能修改電路結構。在次微米技術中要完成高效設計，在邏輯和實體佈局合成工具之間要更緊密的整合是極重要的。
此論文有兩個主要的目標。首先、我們想建立一個整合商業CAD軟體及公用軟體之間的一個基本架構。在這個基本架構下，我們能安插和驗証新的演算法在目前的設計流程中。為了完成這個目標，我們打算在不同的工具之間，建構若干個語法分析器(parser)。這些語法分析器，盡管具有很少研究價值，但是對於將來在邏輯和實體合成之間的研究發展是很重要的。其次、我們提出佈局後繞線長度之最小化的演算法。在我們的設計流程，將以一個已完成邏輯合成與實體置放的設計開始。實體置放資訊使我們更精確地估計配線的時序。有了精確資訊，我們運用邏輯線路重新連接優化來達成目標。這個演算法將反覆用在邏輯及實體領域之間使得設計符合條件並且減少重複的步驟。

During high performance designs in deep sub-micro (DSM) technology, designers often find that their designs do not meet the timing constraints. And the timing of design does not converge after several iterations between logic and physical synthesis. One of the main causes concerning the timing converge problem is due to the weak interaction between the logic and physical layout optimization tools. In the current design flow, logic synthesis modifies the functionality of a circuit using simple wire load model. In difference, layout synthesis can obtain the accurate timing information but cannot modify the circuit structure. To achieve high performance design, it is imperative to have a much closer integration between logic and layout synthesis tools.
There are two objectives in this thesis. First, we would like to build a framework to link between commercial and public domain tool so that one can plug in their algorithms into the current design flow. To achieve this goal, we intend to construct several parsers to communicate between several different tools. Those ground works, though have little research value but can be very useful for the development of our new ideas between logic and physical synthesis. Secondly, we implement a post layout wire length minimization algorithms to obtain better total wire length and better timing results and to alleviate the timing closure problem. The optimization algorithm is to be iterated between logic and physical domain to meet the design constraint and to reduce the iterations.

Contents
1 Introduction -------------------------------------- 1
1.1 A framework to link between commercial tools with public domain synthesis tool. ------------------------------ 4
1.2 Links to layout and post layout logic and physical co-synthesis. ------------------------------------------------- 4
2 Tool parser and placement handler ------------------ 6
2.1 Gate level Verilog generator. --------------------- 8
2.2 Placement information parser. --------------------- 8
2.3 Library parser. ----------------------------------- 9
2.4 New-placement handler. --------------------------- 10
2.5 Static timing analysis tool. --------------------- 11
3 Review of Global Flow Optimization --------------- 13
4 Wire Length Minimization Using Global Flow Optimization ---------------------------------------------- 17
5 Experimental Results ----------------------------- 23
6 Conclusions -------------------------------------- 27
Reference ------------------------------------------------- 28

[1] P. Abouzeid and K. Sakouti and G. Saucier and F. Poirot, “Multilevel synthesis minimizing the routing factor,” Proc. 27th Design Automation Conf.., June 1990, pages 365-368.
[2] N. Bhat and D. Hill, “Routable technology mapping for LUT FPGA’s,” Proc. Int’l Conf. On Computer Design: VLSI in Computers and Processors, October 1992, pages 95-98.
[3] S.C. Chang, K.T. Cheng, N.S. Woo, and M. Marek-Sadowska, “Post Layout Logic Restructuring Using Alternative Wires“, IEEE Transaction on Computer Aided Design, Vol. 16, pp.587-596, June 1997.
[4] S.C. Chang, K-T. Cheng, N.S. Woo, and M. Marek-Sadoswka, “Layout-driven logic synthesis for FPGAs,” Proc. 31st Design Automation Conf., June 1994, pages 308-313.
[5] C.S. Chen, Y.W. Tsay, T.T Hwang, A.C. Hu, and Y.L. Lin, “Combining technology mapping and placement for delay optimization in FPGA designs,” Proc. Int’l Conf. On Computer Aided Design, November 1993, pages 123-127.
[6] O. Coudert, “Gate sizing: a general purpose optimization approach,” Proc. European Design and Test Conf., March 1996, pages.
[7] L. A. Entrena and K. T. Cheng, “Combinational and Sequential Logic Optimization by Redundancy Addition and Removal”, IEEE Transaction on Computer Aided Design, Vol. 16, pp.587-596, July 1995.
[8] U. Glaser and K. T. Cheng, “Logic Optimization by an Improved Sequential Redundancy Addition and Removal”, in Proc. of ASP-DAC, pp.235-240, Sept. 1995.
[9] L. N. Kannan, P. R. Suaris and H. Fang, “A methodology and algorithms for post-placement delay optimization,” Proc. 31st Design Automation Conf., June 1994, pages 327-332.
[10] K. Keutzer, “DAGON: technology mapping and local optimization,” Proc. 24th Design Automation Conf., June 1987, pages 341-347.
[11] S.M. Liu, K.R. Pan, M. Pedram and A. M. Despain, “Alleviating routing congestion by combining logic resynthesis and linear placement,” Proc. European Conf. on Design Automation, February 1993, pages 578-582.