運用限位緩衝之表現導向避開障礙繞線樹

Abstract

隨著製程技術迅速的演進，在晶片的表現上，連線延遲（Interconnect Delay）相較於電閘延遲（Gate Delay）的影響性越來越大如何。如何設計好的樹拓樸以配合限位緩衝（Fixed Buffers）將對降低樹延遲非常重要。本論文專注於如何利用預先分佈在繞線空間的限位緩衝，與樹拓樸配合以降低連線延遲在奈米級晶片設計帶來的衝擊。 本論文提出一個演算法建立以最小化樹延遲（Minimize Tree Delay）為目標的繞線樹，並在避開障礙物的條件下，同時考慮利用限位緩衝（Fixed Buffers）。此演算法以多源單靶繞線法（Multi-Source Single-Target A* Maze Routing）為基礎：以緩衝過濾器（Buffer Filter過濾掉對樹延遲較無幫助的緩衝，並留下較有利用價值的緩衝候選；以多重節點驅動幹道（Multi-Joint Driving Trunk）從緩衝候選中，確切評估出有降低樹延遲價值的緩衝；最後以主支（Stem） 與分支（Branch）連接未連結的受端（sinks），完成樹拓墣（Topology）的控制 實驗顯示在沒有限位緩衝可利用時，我們的演算法相較於關鍵幹道樹（Critical Trunk Tree）[8]多降低了10% 的延遲。在有限位緩衝可利用的情況下，也能調整樹拓樸配合有價值的限位緩衝，進一步降低約80%的延遲。

With the rapid evolution of manufacturing technology, interconnect delay has more impact than gate delay on chip performance. To design a good routing tree topology considering fixed buffers is important to improve timing. This paper focus on how to use pre-distributed buffers, i.e. Fixed Buffers, and tree topology to lower the impact interconnect delay brings on nanoscale IC design. In this paper, we proposed an algorithm to find a routing tree topology while avoiding obstacles and considering fixed buffers to minimizing tree delay. This algorithm based on Multi-Source Single-Target A* Maze Routing. With Buffer Filter, it filters out those buffers that are less useful on improving tree delay and determines relevant Fixed Buffers to be candidates. Then Multi-Joint Driving Trunk will accurately assess the Valued Buffers based on the ability to reduce tree delay. Finally, Stem and Branch will connect sinks that remains unconnected to complete topology control. Experimental results show that without using fixed buffer, the proposed algorithm can reduce about 10% delay than [8]. Furthermore, we can utilize fixed buffers efficiently to further reduce 80% delay than original tree.