有效時鐘偏斜排程之偏斜最小化探討

Issues on Skew Minimization in Useful Clock Skew Scheduling

邱佳瑯(Chia-Lang Chiu)

指導教授 ： 林榮彬

元智大學/資訊學院/資訊工程學系/碩士(2004年)

摘要

時鐘網路是在晶片設計當中很重要的一環。它不僅決定了一個電路的執行速度，甚而影響到該電路是否可正常工作。大多數的時鐘樹設計均是運用零偏斜。但是這造成每段介於相鄰的兩個正反器間的資料路徑，均分享到同樣的時間來傳遞訊號，因此電路的執行速度會被限制住。透過有效時鐘偏斜排程，不但時鐘週期可被改善，且還可以有許多不同的應用。
有效的時鐘偏斜排程可以由各種不同的方式獲得。有一類是將該問題轉化成線性規劃，另有一類則是將該問題轉化以圖論來探討。以圖論為基礎的這個方法會產生大量的偏斜。雖然可透過另一個圖論的方式，來減少該偏斜的產生，但卻沒有一個有系統的方式，來進行所有的偏斜最小化。因此，我們提出一個反複式的方法來減少整體偏斜。實驗結果顯示，時鐘週期可被改善3% ~ 35%，同時由於排程造成的大量偏斜，也可被改善高達95%。我們也發現，當我們在進行偏斜最小化的同時，不同的起始選擇點，甚至會造成整體偏斜 -33% 到 +189% 的落差。同時經由這個反覆式的方法，我們可以了解時鐘週期和整體偏斜數量上的關係。

關鍵字

有效時鐘偏斜

並列摘要

Clock network design is one of the most important tasks in an IC design. It not only determines operating frequency, but also affects whether a design can function properly or not. Conventionally, the clock tree is designed with zero skew. Each data path between two adjacent flip-flops has the same amount of time to propagate its data signal. Therefore, clock period can be limited. Useful clock skew scheduling in addition to clock period improvement could also obtain various kinds of advantages. There are many approaches to obtaining a clock scheduling. One is to formulate the problem as a linear programming model. Yet another one is to formulate the problem as a graph model. The graph-based approach will produce large delays. A method has been proposed to further limit skew, but total skew has not been optimized. Consequently, we develop an iterative approach to reduce total skew. The experimental results show that the clock period is improved by 3% ~ 35% and some of the total skews can be reduced over 95%. We also discover that executing skew minimization with different starting nodes will result in different total skew that could vary from -33% to +189%. With the iterative approach, we find the clock period and total skew has an inverse proportion relationship.

並列關鍵字

Useful Clock Skew

參考文獻

[Deo95] R. B. Deokar and S. S. Sapatnekar, “A Fresh Look at Retiming via Clock Skew Optimization,” Proceedings of Design Automation Conference, pp. 310-315, Jan. 1995.

[Fish90] J. P. Fishburn, “Clock Skew Optimization,” IEEE Transactions on Computer, vol. 39, pp. 945-991, July 1990.

[Ger98] Sabinh H. Gerez, Algorithms for VLSI Design Automation, pp. 92-97, John Wiley & Sons, 1998.

[Kah91] A. Kahng, J. Cong, and G. Robins, “High-Performance Clock Routing Based on Recursive Geometric Matching,” Proceedings of Design Automation Conference, pp. 322-327, June 1991.

[Kou99a] I. S. Kourtev and E. G. Friedman, ”Clock skew Scheduling for Improved Reliability via Quadratic Programming,” IEEE International Conference on Computer-Aided Design, pp. 239-243, Nov. 1999.