以結構最佳化為基礎之時鐘網路合成

高效能超大型積體電路設計需要小的時鐘歪斜以維持時脈速度。為減少時鐘歪斜，大多的早期技術通常根據時序模型對時鐘網路作最佳化，像是艾爾摩爾延遲模型（Elmore delay model）。然而文獻顯示，時序模型的精準度難以協助達成高速晶片所需的時鐘歪斜。因此近來的技術開始嵌入電路模擬到時鐘網路合成中，藉此改善精準度。儘管如此，以電路模擬為基礎的合成技術卻會使得執行時間過長。為突破這兩難的情況（即使用準度不足的時序模型或嵌入耗費時間的模擬），我們提出新的結構最佳化方式，透過建立對稱結構來最小化時鐘歪斜。此結構中，所有從時鐘訊號源到時鐘標的之路徑將被給與相似配置。由於這樣的結構最佳化不需要時序模型與電路模擬，我們能很有效率地得到很小的時鐘歪斜。在時鐘歪斜最小化之外，時鐘網路合成也面臨了當代高效能設計所帶來的關鍵挑戰；而挑戰尤以處理障礙物、電壓壓降、與製程變異最為重要。其一，許多晶片設計會採用巨集元件，而這些巨集元件會對時鐘網路形成障礙物。一個實際的時鐘合成方法不該因為障礙物的出現而不可行；否則，這樣的方法只能被少部分不包含障礙物的晶片設計所採用。其二，在高效能晶片設計中，電力議題往往優先被考量。因為時鐘網路是一個主要被電力網路時常驅動的元件，所以時鐘合成方法應仔細考慮電力網路上的效應，像是電壓壓降效應。其三，製程變異在晶片製造時會改變電路元件的大小，像是金屬線與閘極。高效能晶片設計對於製程變異的影響是非常敏感的，即使是很小的改變也會劇烈造成時鐘歪斜上升。因此，如何提升變異容忍度以在變異發生時維持小的時鐘歪斜是很重要的。我們提出數個結構最佳化方法以最小化時鐘歪斜並且處理上述的關鍵挑戰。在此論文中，方法的介紹可以分為四個部分。（1）我們呈現對稱樹與對應的合成演算法以證實對於時鐘歪斜最小化的有效性。（2）我們設計了迴避障礙物的機制，證實對稱樹不會受限於障礙物的出現而不可實行。由於迴避障礙物，繞線長度可能會被明顯地拉長，所以權重導向的演算法也被提出以改善繞線長度。（3）因為電壓壓降會改變緩衝器供應電壓，所以我們提出電壓對齊演算法，藉由減少供應電壓的差異來達到時鐘歪斜最小化。（4）為獲得好的製程變異容忍度，我們發展兩種非樹狀的時鐘網路。其一，單一全域網格提供了最高的製程變異容忍度；其二，相連網格島強調了耗電量與變異容忍度的交換關係。根據實驗結果，當先進技術受限於電路模擬所造成的過長執行時間，我們提出的結構最佳化演算法能有效並迅速降低時鐘歪斜與時鐘網路電容。

關鍵字

實體設計；時鐘；時鐘誤差；時鐘網路電容；障礙物；電壓壓降；緩衝器供應電壓；製程變異

並列摘要

High-performance VLSI designs need small clock skew to maintain clocking speed. To minimize the skew, most earlier techniques optimized clock networks based on analytical timing models like the Elmore delay model. However, the literature shows that the accuracy of timing models might be insufficient to assist in achieving small skew for the high-performance designs. As a result, recent techniques embed simulations into the clock network synthesis to improve the accuracy. Nevertheless, the running time of the simulation-based synthesis would be prohibitively long. It is evident that using insufficiently accurate timing models and embedding time-consuming simulations might not minimize the skew effectively and efficiently. Therefore, we propose new structural optimization methods that minimize the skew by constructing a symmetrical structure. In the structure, configurations of all paths from the clock source to sinks are similar. Since the structural optimization requires neither timing models nor simulations, we can obtain small skew efficiently. Moreover, in addition to the skew minimization, modern high-performance designs also bring critical challenges to the clock-network synthesis. Especially, the challenges of handling obstacles, IR-drops, and process variations are of particular importance. First, many designs introduce macros, which are obstacles for the clock network. A practical clock-synthesis approach must not fail with the presence of obstacles; otherwise, only a small number of designs without obstacles can adopt the approach. Second, power issues have high priority in high-performance designs. Since the clock network is a major device constantly triggered by the power network, a clock-synthesis approach should carefully consider effects on the power network, e.g., the IR-drop effect. Third, the process variations change the size of circuit elements (e.g., metal wires and poly gates) during chip fabrication. High-performance designs are highly sensitive to the process variations because even small changes could alter signal path timing and thus increase the skew drastically. Hence, it is desirable to enhance clock-network variation tolerance that maintains small skew when the process variations occur. We propose several structural-optimization approaches to minimize the skew and to handle the three mentioned challenges. In this dissertation, our proposed approaches are detailed in four parts. (1) We present a symmetrical tree and corresponding synthesis algorithms to show the effectiveness of the skew minimization. (2) We design obstacle-avoiding mechanisms to show that the proposed symmetrical tree does not fail in the presence of obstacles. As avoiding obstacles may significantly lengthen routing wirelength, a weighted matching algorithm is also proposed to further minimize the wirelength. (3) Since the IR-drop effects change the supply voltages of clock buffers, we propose a voltage alignment algorithm to minimize the supply-voltage difference for the skew minimization. (4) To obtain good process variation tolerance, we develop two non-tree networks. A global-mesh network is proposed for providing the highest tolerance to variations, while a connected-mesh-island network is proposed to address the trade-off between the power consumption and the variation tolerance. According to the experimental results, our proposed structural optimization can effectively and efficiently minimize the clock skew, while most state-of-the-art works suffer from long running time due to the requirement of simulation.

並列關鍵字

Physical Design ； Clock ； Clock Skew ； Clock Power Consumption ； Obstacle ； IR-Drop ； Buffer Supply Voltage ； Process Variation

參考文獻

[1] ISPD 2009 Clock Network Synthesis Contest. http://ispd.cc/contests/09/ispd09cts.html.

[2] ISPD 2010 High Performance Clock Network Synthesis Contest. http://archive.sigda.org/ispd/contests/10/ispd10cns.html.

Apr. 2001.

[6] C. Berge. Two theorems in graph theory. National Academy of Sciences U.S.A., 43(9):842-844, Sept. 1957.

[8] K. D. Boese and A. B. Kahng. Zero-skew clock routing trees with minimum wirelength. In IEEE International Conference on ASIC, pages 17-21, Sept. 1992.

國際替代計量

以結構最佳化為基礎之時鐘網路合成

全文下載

主題瀏覽