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

Through-Silicon-Via(TSV)-constrained Scan Chain Reordering for Three-dimensional(3D) Circuits

陳韋廷(Wei-Ting Chen)

指導教授 ： 溫宏斌

國立交通大學/電機學院/電信工程系所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00608

摘要

本論文定義出在利用一定數量的矽穿孔的掃描鏈重排序問題，而且提出了一個有效率的兩階段演算法去解決該問題。在三維積體電路最佳化中，我們在第一階段使用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.

並列關鍵字

3D ICs ； Through-Silicon-Vias(TSV) ； Testing ； Scan Chain

參考文獻

[6] D. Eppstein. Fast hierarchical clustering and other applications of dynamic closest pairs. J. Exp. Algorithmics, 5:1, 2000.

[7] C. Giri, S.K. Roy, B. Banerjee, and H. Rahaman. Scan chain design targeting dual power and delay optimization for 3d integrated circuit. In Proc. Advances in Comput-ing, Control, Telecommunication Technologies Conf. (ACT), pages 845 –849, 2009.

[9] M. Hirech, J. Beausang, and X. Gu. A new approach to scan chain reordering using physical design information. In Proc. Int’l Test Conf. (ITC), pages 348 –355, 1998.

[10] X.-L. Huang and J.-l. Huang. A routability constrained scan chain ordering technique for test power reduction. In Proc. Asia and South Pacific Conf. on Design Automation (ASP-DAC), page 5 pp., 2006.

[12] J. W. Joyner, P. Zarkesh-Ha, J. A. Davis, and J. D. Meindl. A three-dimensional stochastic wire-length distribution for variable separation of strata. In Proc. Int’l Interconnect Technology Conf. (IITC), pages 126 –128, 2000.