應用於三維積體電路在矽穿孔的限制下的掃描鏈重排序設計方法

Abstract

本論文定義出在利用一定數量的矽穿孔的掃描鏈重排序問題，而且提出了一個有效率的兩階段演算法去解決該問題。在三維積體電路最佳化中，我們在第一階段使用Multiple Fragment Heuristic 的貪婪演算法並且使用處理最靠近點對的資料結構FastPair去得到一個好的初始解，包括掃描鏈線長和測試時的功率消耗。而在演算法的第二階段，提出了三維平坦化(3D Planarization)去減少所使用的線長和功率消耗，也提出了三維釋放(3D Relaxation)去減少矽穿孔的使用量以符合數量限制。最後，實驗結果顯現出該演算法比以基因演算法為基礎的先前技術，在可以比較的效能下，提出的演算法比先前技術快上百倍以上。由此證明，該演算法可以實際應用在三維積體電路以矽穿孔數量為限制的掃描鏈重排序。

This thesis formulates the scan-chain reordering problem considering a limited number of through-silicon vias (TSVs), and further develops an efficient 2-stage algorithm. For three-dimensional optimization, a greedy algorithm named Multiple Fragment Heuristic combined with a dynamic closest-pair data structure FastPair is proposed to derive a good initial solution at stage 1. Later, stage 2 proceeds two local refinements 3D Planarization and 3D Relaxation to reduce the wire/power cost and the number of TSVs in use, respectively. Experiments show that the proposed algorithm can result in a comparable performance to a genetic-algorithm-based method but can run at least 2-order faster, which evidently makes it more practical for TSV-constrained scan-chain reordering for 3D ICs.