Clock Skew Optimization Using Linear Programming under Multi-Corner Multi-Mode Conditions

考慮多重操作模式與環境參數下利用線性規劃演算法之時鐘樹時脈偏移最佳化

蕭海騏(Hai-Chi Hsiao)

指導教授 ： 張世杰

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

摘要

先進的數位電路設計中，需要設計一個時鐘樹來同步時脈到達每一個儲存單元的時間，如果到達儲存單元的時間訊號無法同步，則會產生時脈偏移。時脈偏移是一個很嚴重的問題，因為時脈偏移將直接影響電路的效能及可靠度。數位電路可能會再不同的環境下運行，如不同的電源供應電壓、運行溫度…等等，或者被設計者設計成在不同的電壓模式下操作，這些多重操作模式或環境參數將影響電路的時間行為，不同的時間行為將導致不同的時脈偏移。所以要設計一個時鐘樹同時滿足每一個操作模式或環境參數下的時間行為限制是非常困難。
我們利用線性規劃演算法，針對每一個操作模式的時間行為，同時最佳化時脈偏移，得到一個最佳解。但是最佳解是線性的值，製程技術提供的電路元件可能無法達到最佳解，於是我們又提出一個演算法將電路元件的時間延遲對應到最佳解，以得到一個估計最佳的實際時鐘樹佈局。我們觀察時脈偏移其實和時間從時脈源頭到每一個儲存單元的相對差距有關，根據此特性，我們可以動態調整時脈源頭到儲存單元的時間，在對應無法到達最佳解而產生偏差時，利用之後的對應將偏差補回來，以降低因無法對應到最佳解時而產生的時脈偏移誤差。我們的方法和當今商業工具SOCEncouunter比較，達到34.34%的改進。

關鍵字

時鐘樹 ； 時脈偏移 ； 線性規劃

並列摘要

Clock skew optimization is a complicated problem in modern VLSI technologies because circuits often operate in many environments (corners) such as different power supply voltage and temperature or functional modes (modes) like voltage modes. While circuits operate in different corners or modes, cell delay varies a lot. It will lead to large skew variation. Therefore, to optimize clock skew in all corners or modes is very important. In this paper, we develop an approach to minimize clock skew considering multi-corner multi-mode conditions. We optimize the clock skew in all corners simultaneously by linear programming, and propose a delay mapping algorithm that maps the buffer delay of the clock tree into optimal solutions from linear programming. Our experimental results shows there are 34.34% improvement compared with the commercial tool SOC Encounter.

並列關鍵字

clock skew ； linear programming ； clock tree

參考文獻

[1]. K. Boese and A. Kahng. Zero-skew clock routing trees with minimum wire length. In ASIC Conf., pages 1.1.1–1.1.5, 1992.

[2]. T.-H. Chao, Y.-C. Hsu, and J. Ho. Zero skew clock net routing. In DAC, pages 518–523, 1992.

[3]. S. Pullela, N. Menezes, and L. T. Pillage, “Reliable nonzero skew clock trees using wire width optimization,” in Proc. 30th Design Automation Conf., 1993, pp. 165–170.

[4]. J. Cong and K. S. Leung, “Optimal wire sizing under the distributed elmore delay model,” in Proc. Int. Conf. Computer-Aided Design, 1993, pp. 634–639.

[5]. Q. Zhu and W. W. M. Dai, “High-speed clock network sizing optimization based on distributed RC and lossy RLC interconnect models,” IEEE Trans. Computer-Aided Design Integr. Circuits Syst., vol. 15, no. 9, pp. 1106–1118, Sep. 1996.