以平行模擬退火法改善迭代式層級感知分割

Using Parallel Simulated Annealing to Improve Iterative Layer-Aware Partitioning

李懿庭(Yi-Ting Li)

指導教授 ： 方志鵬

共同指導教授 ： 張陽郎

國立臺北科技大學/電資學院/電機工程系研究所/碩士(2014年)

https://doi.org/10.6841/NTUT.2014.00294

摘要

隨著積體電路技術的演進與設計複雜度快速的成長，連線延遲已演變成傳統二維積體電路架構的瓶頸。因此近年來，三維積體電路技術逐漸成為可行的替代方案。此技術將晶粒相互堆疊，晶粒與晶粒間使用矽穿孔技術互相連接，使得電路連線密度提升，進而讓外觀尺寸縮小，並且降低功耗與減少連線延遲。
因為矽穿孔的電容較大，不必要的矽穿孔反而加劇連線延遲，這使得減少矽穿孔的數量成為一個重要的議題。因此本論文提出兩階段式的分層方法來減少矽穿孔的數量。第一階段：使用迭代式層級感知分割演算法進行分層，以求得初步的分層結果；第二階段：在GPU上進行平行模擬退火法，用以改善第一階段所產生的分層結果。過程中除了考量矽穿孔數量外，也考慮到每層之間的面積平衡問題，以避免減少矽穿孔數時，所導致的面積不平衡問題。
本研究以GSRC Benchmark做為測試電路，實驗結果顯示迭代式層級感知分割演算法搭配平行模擬退火法，能有效減少矽穿孔數，並且維持面積平衡。

關鍵字

三維積體電路 ； 矽穿孔 ； 模擬退火法 ； hMetis ； CUDA ； 面積平衡

並列摘要

With the evolution of integrated circuit technology and rapid growth of design complexity, the interconnection delay has become the bottleneck of traditional 2D architecture. Thus, the 3D integrated circuit technology has gradually become a viable solution in recent years. This emerging technology allows stacking multiple dies and resolves the vertical connection issue between each die by using through-silicon-via (TSV) technique, which raises the density of circuit connection and thereby reduces the size, power consumption, and interconnection delay of chip.
Since unnecessary TSVs would influence interconnection delay due to large capacitance of TSV, reducing the number of TSVs becomes a critical topic. In this thesis, we propose a two-phased layer-aware partitioning algorithm for minimizing the number of TSVs. In the first phase, we apply an iterative layer-aware partitioning (iLap) algorithm to assign circuit modules to different layers and derive the initial solution. In the second phase, we apply a parallel simulated annealing on GPU to further improve the result derived from the first phase. In the process of second phase, we not only consider the number of TSVs, but also take the area balance between each layer into account to avoid area imbalance during the process of TSV reduction.
In our experiments, we used GSRC benchmark as the test circuits. The results from our experiments show that our approach can effectively reduce the number of TSVs and maintain the area balance.

並列關鍵字

3D-VLSI ； TSV ； Simulated Annealing ； hMetis ； CUDA ； Area Balance

參考文獻

9.G. Karipis and V. Kumar “Multilevel k-way Hypergraph Partitioning” VLSI Des., vol. 11,no. 3, 2000, pp.285-300.

13.蘇哲彥，應用多層級平面規劃於三維超大型積體電路，碩士論文，國立台北科技大學電機工程研究所，台北，2013。

2.Johann Knechtel, Igor L. Markov and Jens Lienig, "Assembling 2-D Blocks Into 3-D Chips, "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, No. 2, February 2012, pp.228-241.

3.I. Loi et al. “A low-overhead fault tolerance scheme for TSV-based 3D network on chip links,” Proc. International Conference on Computer-Aided Design, pp.598- 602, 2008.

6.Cha-Ru Li, Wai-Kei Mak and Ting-Chi Wang, “Fast Fixed-Outline 3-D IC Floorplanning With TSV Co-Placement,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2013, pp.523-532.