三維積體電路（3D IC）被視為是有發展潛力的設計方式去應付積體電路日漸增加的效能與功能需求。然而，重新設計矽智財模組為三維整合使用必須耗費大量成本，也由於相關的電子設計自動化（EDA）工具尚未成熟，三維積體電路的成功案例依然有限。為了促進業界採納三維整合設計方式，模組化層級三維積體電路設計是低成本與快速的方案，模組化層級整合帶來最大的好處就是可以使用已經高度最佳化的二維矽智財模組而不需要作大量的修改動作。在三維積體電路中，不同晶粒層的訊號必須透過矽晶穿孔（through-silicon via, TSV）連結，因此矽晶穿孔規劃是三維積體電路設計中重要的議題之一，不適當的矽晶穿孔規劃將導致繞線線長增加、晶片面積上升，甚至使得三維積體電路效能低於二維積體電路。在本篇論文中，我們提出以全域的觀點去考量矽晶穿孔規劃及縮短繞線線長。首先建立與整合未使用空間格子（whitespace gird）去得到精確的未使用空間位置與容量。而為了避免障礙物與建立鄰層間的垂直連結，我們必須搜索與產生候選矽晶穿孔（TSV candidates）。接著我們提出了一個修正的掃描線演算法去建立生成圖（spanning graph）完成各晶粒層上的水平連結。最後透過整數線性規劃（integer linear programming）去選擇每個連線所使用的矽晶穿孔，在完成所有訊號連結與滿足所有未使用空間的容量限制下達到線長的最小化。實驗結果顯示，我們提出的方法不僅減少了繞線線長也有彈性地去規劃矽晶穿孔擺置。Three-dimensional integration circuit (3D IC) is a promising design option to cope with the increasing demands on performance and functionality of integrated circuit design. However, re-designing IP blocks in the 3D integrated type is very costly and the related electronic design automation tools are not mature yet, the success of 3D IC remains limited. In order to accelerate industry adoption of 3D IC integration, block-level 3D IC design is a low-cost and fast option. The primary advantage of the block-level integration is that we can reuse highly-optimization 2D IP blocks without considerable modifications.Because through-silicon via (TSV) is the connection of different dies, TSV planning is one of the most important issues in 3D IC design. The inappropriate planning of TSVs causes long routing path, increase chip area, or even makes the performance of 3D ICs worse than that of 2D ICs.In this thesis, we consider TSV planning and reduce routing wirelength for block-level 3D IC designs in global view. At first, we construct and integrate the whitespace grid to get the exact location and the capacity of each whitespace. Then, to avoid obstacles and construct vertical connections for adjacent dies, we search and generate TSV candidates. Besides, we propose a modified sweeping line algorithm to construct the horizontal connections of each die based on the spanning graph. Finally, integer linear programming is used to choose TSV candidates for each net, and the TSV planning result is satisfied the whitespace capacity constraints with minimum wirelength. Experimental results show that the proposed method not only reduces the routing wirelength, but also plans TSVs flexibly.
