三維積體電路最小化時序差異繞線方法

A Bounded Minimal Skew Grid Router for 3 Dimensional Integrated Circuits

彭奎彰(Kuei-Chang Peng)

指導教授 ： 陳美麗

中原大學/工學院/資訊工程研究所/碩士(2009年)

https://doi.org/10.6840/cycu200900793

摘要

三維積體電路是將系統整合至一個單一晶片上，許多研究說明三
維積體電路可以大幅減少平均連線長度。
本篇論文即是在三維晶片架構下，提出最小時序差異繞線方法
(bounded minimal skew grid router)。我們由最上層開始對每層建立一
棵最小化時序差異子樹。這棵子樹會一層一層的往下成長，直到最底
層為止。藉由TSV 完成各層之間子樹的連接。在建樹的過程中，我
們都會試著最小化這棵子樹的時序差異。我們對每一層執行相同的繞
線程序，最後便可完成一棵最小化時序差異樹。
我們亦推演出skew upper bound 值，亦由實驗結果顯示我們繞線
結果的skew 均在此skew upper bound 之內。
本演算法的實驗結果可看出我們提供的繞線方法能夠很有效的
最小化時序差異。在所有的25 個測試電路中，我們的時序差異平均
為最大時序延遲(latency)的0.73%。在所有的測試電路中，時序差異
的值皆在9 單位以下。

關鍵字

零時序差異繞線 ； 演算法

並列摘要

3D IC integration of circuits is a promising approach to integrate a
large system on a single chip. The average global wire length is reduced
drastically. In this paper, we present a bounded minimal skew grid router
for Three Dimensional Integrated Circuits. We route a net layer by layer
starting from the top layer. All terminals on the layer are routed to form a
minimum skew subtree. The root of the subtree is projected to the layer
below. This projected point will be connected with the root of the subtree
of the projected layer. The connection between layers is implemented by
a TSV. This routing procedure is repeated for all layers. Finally, a
minimum skew routing tree is completed. The skew of the routing is
bounded by the height of the tree. Experimental results show that our
algorithm can generate routing with very small skew. In average, the
skew is 0.73% of the maximum latency in all 25 test cases. The skew is
smaller than 9 units in all cases. Experimental results have shown that our
algorithm is effective in skew minimization.

並列關鍵字

Minimum skew ； Routing ； Algorithm

參考文獻

[1] H. Kurino et. al., “Intelligent Image Sensor Chip with Three

Dimensional Structure,” in Proceedings of International Electron

Devices Meeting (IEDM), pp. 879–882, 1999.

“Three-Dimensional Cache Design Exploration Using 3DCacti,” in

Proceedings of the IEEE International Conference on Computer