針對時間自動測試向量產生器的有效布林特徵函式

Efficient Boolean Characteristic Function for Timed ATPG

張岳隆(Yue-Lung Chang)

指導教授 ： 張世杰

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

在各種電路最佳化裡電路時間分析扮演相當重要的角色，找出同時滿足功能需求與時間需求的輸入向量稱為時間自動測試向量產生器，一個時間自動測試向量產生器的演算法將會找出在模擬之後同時滿足功能需求與時間需求的輸入向量，先前許多與時間分析的相關研究都使用時間自動測試向量產生器當作解決問題核心的技術，像有串音干擾(crosstalk)、最大瞬間電流，但盡管時間自動測試向量產生器是這麼地有用，但是傳統上的時間自動測試向量產生器速度相當慢並且不能夠處理很大的電路，這我們的論文中，我們提出很有效的方法來建構出時間自動測試向量產生器，我們的所建構出的時間自動測試向量產生器平均來說比之前所提出的研究快了六倍，在某些例子裡我們的效能甚至快了三十二倍。

關鍵字

輸入向量稱為時間自動測試向量產生器 ； 串音干擾 ； 最大瞬間電流

並列摘要

Circuit timing analysis is important in various aspects of circuit optimization. The problem of finding input vectors achieving functional and temporal requirements is known as timed Automatic Test Pattern Generation (timed ATPG). A timed ATPG algorithm will return an input vector that satisfies functional and temporal requirements simultaneously when evaluated. Several previous works use timed ATPG as a core engine for solving problems related to timing analysis, such as crosstalk and maximum instantaneous current analysis. Despite the usefulness of timed ATPG, traditional timed ATPG is slow and unscalable for large circuits. In this thesis, we present a very effective way for timed ATPG. On average, our results are 6 times faster than the most recent work, and in some cases, up to 32 times faster.

並列關鍵字

timed ATPG ； crosstalk ； Maximum instantaneous current

參考文獻

[7]. H. Kriplani, F. Najm, and I. N. Hajj, “Pattern independent maximum current estimation in power and ground buses of CMOS VLSI circuits: algorithms, signal correlations, and their resolution,” IEEE Transactions on Computer-Aided Design, pp. 998-1012, Aug. 1995.

[8]. Y.-M. Jiang, A. Krstic, and K.-T. Cheng, “Estimation for Maximum Instantaneous Current Through Supply Lines for CMOS Circuits,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 8, no. 1, pp. 61-73, Feb. 2000.

[9]. Y.-M. Jiang, K.-T. Cheng, and A. Krstic, “Estimation of Maximum Power and Instantaneous Current Using a Genetic Algorithm,” IEEE Custom Integrated Circuits Conference, 1997.

[10]. R. Kundu, and R. D. Blanton, “Timed Test Generation for Crosstalk Switch Failure in Domino CMOS Circuits,” in Proceedings of the IEEE VLSI Test Symposium, pp. 379-385, Apr. 2002.

[16]. L. G. Silva, J. P. M. Silva, L. M. Silveira, and K. A. Sakallah, ”Satisfiability Models and Algorithms for Circuit Delay Computation,” ACM Transactions on Design Automation of Electronic Systems, vol. 7, no. 1, pp. 137-158, Jan. 2002.