三維積體電路在通用圖形處理器裡基於力使量法的平行分割演算法

Abstract

本論文提出一個創新的平行演算法(稱為FDPrior)，利用力使量法(force-directed)解決在3DIC中的多層次分割問題(multilayer partitioning problem)，我們的研究主要提供一個全新的角度去思考如何解決分割問題；由於3DIC技術中層次架構及規模日益擴大，需要昂貴的計算過程才能達到優化目的，利用多核心架構的平行性將成為關鍵，並可縮短運行時間，我們研究目標是盡量減少TSV的總數量，且同時滿足每一層晶片的面積限制。藉由N-body simulation方案及新技術達到減少不必要的同步次數，FDPrior成功地在通用圖形處理器(GPGPU)架構裡開發出大量平行度；使用ISPD98當作輸入並做實驗測試，FDPrior平均上比傳統FM演算法獲得5.95倍更好的實驗結果，並加速高達303.66倍的運行時間；而跟PP3D相比，FDPrior平均仍然可達到7.71倍更好的結果，和增強3.35倍的運行時間。 近年來，多階層超圖(multilevel hypergraph)分割演算法比非多階層的方法可得到更好性能。因此，該論文也提出一個新的演算法稱為MFDPrior，它是使用之前所提的FDPrior當作基本分割演算法，採用多階層演算法作為骨架，跟之前所提的FDPrior演算法相比，MFDPrior平均可獲取1.46倍更好的實驗結果，和贏得1.44倍的時間加速。

This thesis proposes an innovative force-directed parallel algorithm, FDPrior, to solve the multilayer partitioning problem of 3DICs. The purpose of our research is providing a new field of vision in the partition problem of 3DICs. The growing scale and multi-layered structure of the 3DIC technology make it computationally expensive for EDA tools to achieve optimization goals. Exploiting the algorithmic parallelism on multi-core architectures becomes the key to attain scalable runtime. The objective is to minimize the total number of Through Silicon Vias (TSVs) while meeting the area constraint for each layer. By adopting the N-body simulation scheme and novel techniques to reduce synchronization overhead, FDPrior successfully exposes the massive parallelism on the multi-core GPGPU architecture. The experimental results on ISPD98 benchmark show that FDPrior outperforms the conventional FM algorithm by achieving in average 5.95X better TSVs and up to 303.66X runtime speedup. Compared with PP3D, a parallel 3DIC partitioning algorithm, FDPrior achieves 7.71X better TSVs with 3.35 X runtime enhancements. In recent years, the multilevel hypergraph partitioning algorithms could earn better performances than non-multilevel methods. This is why our thesis also proposes an algorithm, MFDPrior, which fulfills the multilevel framework. MFDPrior exercises the FDPrior as the essential partitioning part. When comparing with the single level FDPrior, MFDPrior demonstrates an average of 1.46X better solution quality and earns 1.44X speedup.