考慮效能及可製造性設計於X架構零時序差異時脈樹之建立

X-Architecture Zero-Skew Clock Tree Construction with Performance and DFM Considerations

郭仲傑(Chung-Chieh Kuo)

指導教授 ： 蔡加春 ； 李宗演

國立臺北科技大學/電資學院/電腦與通訊研究所/博士(2010年)

摘要

近年來，積體電路技術緊隨著摩爾定律發展至六十五奈米及更為精細的製程，並帶給電子業許多的產值。新世代的技術整合數十億的電晶體於單一晶片上，因而能夠使用矽智財達成各式各樣的功能需求。為了同步所有矽智財的動作，我們需要一個時脈樹來連接所有矽智財的時脈端點，並藉此傳送時脈信號到這些端點。因為時脈樹在延遲、線長、及功率消耗等方面漸漸主導系統效能，在時脈樹繞線問題上，X架構就被用來取代一般的曼哈頓架構。此外，由天線效應及導通孔開路缺陷所引起的良率問題，對考慮可製造性設計的時脈樹是很重要的。在本論文中，我們提出一個考慮效能及可製造性設計於X架構零時序差異時脈樹建立的系統。
對於時脈樹的建立，我們採用X架構的繞線方式，其原因是此架構能夠在直線與斜線方向完成金屬線的佈局，進而在時脈延遲、線長、及功率消耗上優於曼哈頓架構。接著，我們提出一個以圖樣配對為基礎，並搭配X-翻轉技術(X-Flip)的PMXF演算法。對有n個時脈端點的集合，此演算法能在O(nlogn)的時間複雜度下，建立其X架構零時序差異時脈樹。在這個演算法中，我們定義一個X圖樣庫用於簡化DME方法的合併程序，也提出X-翻轉技術用於縮短兩配對點之間的距離，而調整線段寬度方法則是用於修正時序差異。在使用標準測試例子的實驗裡，我們所提出的PMXF演算法相較於其他的曼哈頓與X架構時脈繞線演算法，均能獲得更多的改善結果。
為了更進一步改善時脈樹的效能，我們提出一個X架構零時序差異時脈樹並搭配加入緩衝器與調整其尺寸之技術的BIS-X演算法。相異於其他採用加入緩衝器方法的研究，我們在計算時脈延遲的同時，考量導通孔的自身延遲，並探討已加入緩衝器之時脈樹在動態與靜態的功率消耗。對有n個時脈端點的集合以及具有B種尺寸大小的緩衝器庫，首先使用PMXF演算法連接每個配對點。接著，分別加入兩個單尺寸(unit-size) 緩衝器到栓點(tapping point)的左右分枝。然後，調整已加入的緩衝器尺寸去改善左右分枝的時脈延遲。此外，X-翻轉技術和調整線段寬度方法分別用於減少線長與確保零時序差異。我們所提出的BIS-X演算法能在O(B2nlogn) 的時間複雜度下，建立一個有緩衝器的X架構零時序差異時脈樹。在使用標準測試例子的實驗裡，BIS-X演算法相較於其他研究在時脈延遲上有更好的表現。
對於X架構時脈樹的天線效應避免與修正問題，我們提出以放電路徑為基礎的天線效應檢測方法。然後，使用半導體製造廠所建議的加入跳線技術去修正天線效應，我們更整合配置金屬線佈局層的技術，藉以減少所加入的跳線與導通孔數量。不同於已發表的相關研究，我們在修正天線效應後，於計算時脈延遲的同時，也考量導通孔的自身延遲並調整線寬，確保零時序差異。在使用標準測試例子的實驗裡，我們所提出的PADJILA演算法能在O(n2) 的時間複雜度下，完成天線效應的修正，在加入的跳線數量、時脈延遲、功率消耗上均有較佳的成果。
對於X架構時脈樹的導通孔良率問題，我們在後繞線階段採用半導體製造廠所建議的加入雙導通孔技術去提升導通孔良率。我們所提出的DVI-X演算法對被分割的X架構時脈樹佈局，利用導通孔與其冗餘導通孔候選者建立其二分部圖形。然後，使用擴充路徑方法並配合最大群組的建立，從二分部圖形中獲得導通孔與其冗餘導通孔候選者的配對結果，進而在不違反設計規則下順利地加入雙導通孔。在使用標準測試例子的實驗裡，DVI-X演算法相較於其他研究在加入雙導通孔的比例上有較好的表現。

關鍵字

天線效應 ； 緩衝器 ； 時脈樹 ； 可製造性設計 ； 跳線 ； 冗餘導通孔 ； X架構 ； 零時序差異

並列摘要

The advancement of the integrated circuit (IC) technology has been following the Moore’s Law tightly to reach 65nm and beyond in the past decade and introduces a huge valuable electronic market. New generation of technology leads to billions of transistors can be integrated on a single chip for performing various functions with intellectual properties (IPs). To synchronize the actions of IPs, a clock tree is employed to connect their clock sinks and then delivers a clock signal to them. Because clock tree gradually dominates system performance indicated by delay, wirelength, and power consumption, the X-architecture is applied to replace the general Manhattan-architecture in clock routing. Moreover, the yield losses induced by antenna effect and via-open defect are critical to clock tree construction in design for manufacturability (DFM). In this dissertation, we present a system of X-architecture zero-skew clock tree construction with performance and DFM considerations.
To handle the clock tree construction, we take X-architecture for routing because this architecture can route metal wires in diagonal and rectilinear directions to perform better in delay, wirelength, and power consumption than Manhattan-architecture. Then, we present a pattern-matching-based clock routing algorithm with X-Flip technique, called PMXF, to construct an X-architecture zero-skew clock tree with a set of n clock sinks in O(nlogn). In the proposed algorithm, an X-pattern library is defined to simplify the merging procedure of the DME approach, an X-Flip technique is proposed to reduce the wirelength between the paired points, and a wire sizing technique is applied to achieve zero skew. Experimental results on benchmarks show that the proposed PMXF algorithm respectively achieves more reductions compared with other previous Manhattan- and X-architecture clock routing algorithms.
To further improve the performance of clock tree, we present an X-architecture zero-skew clock tree construction with buffer insertion and sizing algorithm, called BIS-X. Differing from other buffer insertion works, the delay of vias is considered in clock delay calculation, as well as, the switching and leakage powers of the buffered clock tree are discussed. Given a set of n clock sinks and a B-type buffer library, PMXF algorithm is first used for connecting the paired sinks. Next, two unit-size buffers are respectively inserted into the left and right branches of a tapping point. Then, the inserted buffers are sized to improve branch delays. Furthermore, X-Flip and wire sizing techniques are sequentially applied to reduce wirelength and keep zero skew. The proposed BIS-X algorithm can construct a buffered X-architecture zero-skew clock tree in O(B2nlogn). Experimental results on benchmarks show that the proposed BIS-X algorithm performs better in clock delay compared with other buffered clock routing algorithms.
To handle the antenna effect avoidance/fixing problem in a given X-architecture clock tree, we propose a discharge-path-based antenna effect detection method. Then, we use the jumper insertion technique recommended by semiconductor foundries to fix the antenna violations. Furthermore, we integrate the layer assignment technique to reduce the inserted jumper and via counts. Differing from the existing works, the delay of vias is considered in delay calculation, and a wire sizing technique is applied for clock skew compensation after fixing the antenna violations. Experimental results on benchmarks show that the proposed PADJILA algorithm runs in O(n2) to respectively achieve more improvements in the inserted jumper count, delay, power consumption, and via count than the existing works.
To handle the via yield problem in a given X-architecture clock tree, we apply the double-via insertion (DVI) technique recommended by semiconductor foundries in the post-routing stage. Our proposed DVI-X algorithm constructs the bipartite graphs of the partitioned clock routing layout with single vias and redundant-via candidates (RVCs). Then, DVI-X applies the augmenting path approach associated with the construction of the maximal cliques to obtain the matching solution from the bipartite graph. Experimental results on benchmarks show that the proposed DVI-X algorithm achieves higher double-via insertion rate and less runtime than the existing works.

並列關鍵字

Antenna effect ； buffer ； clock tree ； design for manufacturability (DFM) ； jumper ； redundant via ； X-architecture ； zero skew

參考文獻

[2] Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 1997 Edition. Available: www.itrs.net/links/2007itrs/2007_chapters/2007_Interconnect.pdf

[6] L. Yi, W. Zhang, J. Wu, and D. Mao, “Comparison of metal-organic chemical vapour deposition TiN thin films with different process cycles,” Journal of Semiconductor Science and Technology, vol. 21, no. 3, pp. 250-253, March 2006.

[12] J. Cong, “An interconnect-centric design flow for nanometer technologies,” in Proc. IEEE, vol. 89, pp. 505-527, April 2001.

[14] Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 2001 Edition. Available: http://www.itrs.net/links/2001itrs/Interconnect.pdf

[19] M. Edahiro, “A clustering-based optimization algorithm in zero-skew routing,” in Proc. ACM/IEEE Design Automation Conference, pp. 612-616, June 1993.