電路分割方法相關研究與應用於電路擺置之電路分割演算法

Partitioning Related Research and Placement-Aware Partitioning Algorithm

薛祖雲(Tsu-Yun Hsueh)

指導教授 ： 陳美麗

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

https://doi.org/10.6840/cycu201100552

摘要

中文摘要

對積體電路做分割是實體設計(physical design)的第一階段，隨著積體電路製程的進步，使得晶片上的電晶體數目迅速增加，因此如何以有效率的方式對電路做分割，降低電路設計的複雜度是非常重要的。

本篇作者對partition做過許多相關研究，並發展可應用於3D IC架構下之partition演算法，且加入不同目標考量，同時使得所需要的矽穿孔(Through Silicon Via, TSV)數量及Area Overhead最小。此外，也分析以2-way與k-way兩種不同partition的方式，對相同電路做分割的影響，比較其效能差異與分割結果。經由實驗證明，以2-way partition的效能比k-way好很多，以2011 CAD Contest中[1]由工研院[2]所提供之8個netlist，平均而言2-way可比k-way少69%的TSV數以及4.35x快的Run Time。

而在placement階段時，partitioning-based的placement是一種常見的方法，由於晶片設計進入深次微米(Deep Submicron)世代，許多晶片上都具有超過數十或百萬個元件，因此在對電路做partition的同時，考慮當前partitioning區域與其外部連線的影響是非常重要的。因而本篇論文以2-way的方式發展出Placement-aware Partitioning演算法，使其能有效考慮外部連線的影響，並準確計算cut數變化量，達到最少cut數的目的。

於實驗結果中，我們使用2011 ISPD contest提供之Benchmarks[3]，並運用本論文提出之演算法與不投影及由Dunlop等人提出之投影方式[13]相比，平均而言，以半周長比各別少37%、10%，若以建立直角化史坦納樹估計的線長比，可少31%與9%，若以2011 ISPD contest提供之Golden Router去實際繞線的線長比，則可少55%及36%。

關鍵字

電路擺置 ； 電路分割

並列摘要

Abstract
As the process technology progress, there are more and more components on a chip. Therefore, how to partition the circuit effectively is a very important issue. Partitioning-based placement is a common placement method. A good partition method can get a good placement result.

In our study of previous research, we find the partitioning methods [13][18][19] can not effectively consider the connection of external nets in global view. Therefore, we propose a new partitioning method which can consider the connection of external nets and minimize the number of cuts in the partitioning area.

In the past, we have done partitioning research for 3D ICs. We implement two partitioning methods which are two-way partition and k-way partition under 3D ICs to compare the performance of the two methods. As shown in the experimental results, on average, the two-way partition is 69% less than k-way partition in terms of TSV number and 4.35x faster in terms of run time. According to the experimental results, the performance of two-way partition is better than k-way partition.

Therefore, we use the two-way partitioning method to develop a Placement-aware Partitioning algorithm. We use our algorithm to compare with two kinds of methods. The one of the methods is do partition with traditional terminal propagation, another one is without terminal propagation.

As shown in the experimental results, on average, the result of our algorithm is 10% and 37% shorter in terms of HPWL (Half-perimeter Wirelength), 9% and 31% shorter in terms of STWL (Steiner Tree Wirelength), respectively. And we use a Golden Router which is provide by 2011 ISPD contest to route the result, on average, our wirelength is shorter than those two methods 36% and 55%, respectively.

並列關鍵字

placement ； partitioning

參考文獻

[4] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar “Multilevel Hypergraph Partitioning: Application in VLSI Domain”, in Proc. ACM/IEEE Design Automation Conference, pp.526-529, 1997.

[5] G. Karypis, V. Kumar, “Multilevel k-way Hypergraph Partitioning*”, in Proc. ACM/IEEE Design Automation Conference, pp.343-348, 1999.

[6] G.. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar “Multilevel Hypergraph Partitioning:Applications in VLSI Domain”, IEEE Trans. VLSI Syst., vol. 7, no. 1, pp.69-79, Mar. 1999.

[7] C. M. Fiduccia and R. M. Mattheyses, “A Linear Time Heuristic for Improving Network Partitions”, in Proc. of the ACM/IEEE Design Automation Conf, pp.175-181,1982.

[8] Iris H. R. Jiang, “Generic Integer Linear Programming Formulation for 3D IC Partition”, SOCCON, pp.321-324, 2009.