簡易檢索 / 詳目顯示

回結果列表
研究生： 洪忻煒
Hung, Shin-Wei
論文名稱： 考量多重設計參數限制之單晶片系統測試排程
Test Scheduling for Core-Based SOC Design Under Multiple Constraints
指導教授： 李昆忠
Lee, Kuen-Jong
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2002
畢業學年度： 90
語文別： 英文
論文頁數： 46
中文關鍵詞： 單晶片系統測試 、測試 、測試排程
外文關鍵詞： test scheduling, testing, SOC testing
相關次數： 點閱：94  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在以核心電路(Core)為基礎的單晶片系統上，可能包含了數十個或上百個核心電路，如何在符合諸多設計參數的限制下，以最短的時間完成所有核心電路的測試，是個很大的挑戰。本論文中，我們提出一個測試排程的解決方案，其目的是在符合所有設計參數限制下，有效率地決定所有測試集的時間順序，使得總測試時間為最小。
    我們考量的設計參數包括功率消耗、測試存取機制之寬度(TAM Width)、資源共享(Resource Sharing)、測試優先權(Precedence)以及多重測試集。我們也提出一個雙重二維裝箱模型(Dual Rectangle Bin-Packing Model)以及最佳位置(Best-Fit)演算法來解決這個問題。
    以下茲列舉本測試排程方案的特點：
    1. 第一個同時考量多重設計參數限制的測試排程方案。
    2. 可同時考量上千個核心電路。
    3. 可在數秒鐘之內得到排程結果。
    4. 在短時間內考量上千個核心電路，仍然可得到很好的排程效率。
    5. 與相關論文比較，在只有數十個核心電路以及考量較少的設計參數限制情況下，仍能得到不錯的結果。

    A test scheduling methodology for core-based SOC design is developed. The main objective of this methodology is to efficiently identify a test schedule that requires minimum test time under various constraints. These constraints include maximum power consumption, limited test access mechanism (TAM) width, resources shared by different cores, test precedence between test sets, and multiple test sets required by a single core. The efficiency of our method is due to a proposed dual rectangle bin-packing model and an efficient algorithm based on this model.
    The distinguishing features of our approach are listed below:
    l. It is the first one to consider multi factors including power consumption, TAM width, resource sharing, precedence and multiple test sets concurrently.
    2. The approach can deal with thousands of test sets simultaneously.
    3. The proposed algorithm can obtain the results in seconds for an SOC with thousands of cores.
    4. Though the program considers multiple constraints and a large number of test sets, its scheduling efficiency is still quite good.
    5. Though aiming at handling thousands of cores, while considering tens of cores with less constraints, we can get a comparable scheduling results with previous work in a much shorter time.

    CHAPTER 1 INTRODUCTION 1 1.1 THE IMPORTANCE OF TEST SCHEDULING 1 1.2 FEATURES OF PROPOSED SCHEDULING METHODOLOGY 2 1.3 ORGANIZATION OF THESIS 3 CHAPTER 2 PREVIOUS WORK 4 2.1 GRAPH BASED MODEL SCHEDULING 5 2.2 ILP BASED MODEL SCHEDULING 7 2.3 BIN-PACKING BASED MODEL SCHEDULING 8 CHAPTER 3 TEST SCHEDULING 10 3.1 TEST CONSTRAINT DEFINITION 10 3.1.1 TAM Width 11 3.1.2 Power Dissipation 12 3.1.3 Resource Sharing 14 3.1.4 Precedence 15 3.1.5 Multiple Test Sets 15 3.2 DUAL RECTANGLE BIN PACKING MODEL 16 3.2.1 One-dimensional Bin Packing 16 3.2.2 Two-dimensional Bin Packing 18 3.2.3 Dual Rectangle Bin Packing Model 19 3.3 TEST SCHEDULING ALGORITHM 21 3.3.1 The Scheduling Methodology 21 3.3.2 Multi_Factor_Scheduler Algorithm 23 3.3.3 Input / Output Files 29 CHAPTER 4 EXPERIMENTAL RESULTS 32 4.1 PLATFORM AND PROGRAMMING LANGUAGE 32 4.2 PARAMETERS OF TESTBENCH 32 4.3 EXPERIMENTS WITH 5 CONSTRAINTS 34 4.4 EXPERIMENTS WITH OPTIMAL TESTBENCH 38 4.5 COMPARISONS WITH OTHER WORK 41 CHAPTER 5 CONCLUSIONS 42 REFERENCES 43

    [1] C. R. Kime and K. K. Saluja, “Test scheduling in testable VLSI circuits”, Proc. Int. Symp. Fault-Tolerant Comput., pp. 406-412, June 1982.

    [2] G. L. Craig, C. R. Kime and K. K. Saluja, “Test scheduling and control for VLSI Built-In-Self-Test”, IEEE Transactions on Computers, Vol. 37, no. 9, pp. 1099-1109, 1988.

    [3] M. Garg, A. Basu, T. C. Wilson, D. K. Banerji and J. C. Majithia, “A new test scheduling algorithm for VLSI systems”, Proc. IEEE symposium on VLSI Design, pp. 148-153, Jan. 1991.

    [4] A. P. Stroele and H. -J. Wunderlich, “Signature analysis and test scheduling for self-testable curcuits”, Proc. Int. Symp. Fault-Tolerant Comput., pp. 96-103, 1991.

    [5] J. Sayah and C. R. Kime, “Test scheduling in high performance VLSI system implementations”, IEEE Transactions on Computers, Vol. 41, no. 1, pp. 52-66, 1992.

    [6] A. P. Stroele, “Self-test scheduling with bounded test execution time”, Proc. Int. Test Conf., pp. 130-139, 1992.

    [7] M. R. Garey and D. S. Johnson, “Computer and Intractability: A Guide to the Theory of NP-Completeness”, New York: Freeman, 1979.

    [8] R. M. Chou, K. K. Saluja and V. D. Agrawal, “Scheduling tests for VLSI systems under power constraints”, IEEE Transactions on VLSI. Vol. 5, no. 2, pp. 175-185, Jun 1997.

    [9] V. Muresan, X. Wang, V. Muresan and M. Vladutiu, “The left edge algorithm in block test scheduling under power constraints”, Proc. ISCAS, pp. 351-354, May 2000.

    [10] V. Muresan, X. Wang, V. Muresan and M. Vladutiu, “A comparison of classical scheduling approaches in power-constrained block-test scheduling”, Proc. International Test Conference, pp. 882-891, October 2000.

    [11] K. Chakrabarty, “Test scheduling for core-based systems using mixed-integer linear programming”, IEEE Trans. CAD, Vol. 19, no. 10, pp. 1163-1174, October 2000.

    [12] V. Iyengar and K. Chakrabarty, “Precedence-based, preemptive, and power-constrained test scheduling for system-on-a-chip”, Proc. IEEE VLSI Test Symposium, pp. 368-374, 2001.

    [13] K. Chakrabarty, “Design of system-on-a-chip test access architectures under place-and-route and power constraints”, Proc. Design Automation Conf., pp. 432-437, 2000.

    [14] K. Chakrabarty, “Design of system-on-a-chip test access architectures using integer linear programming,” Proc. IEEE VLSI Test Symposium, pp. 127 –134, 2000.

    [15] E.J. Marinissen, R. Arendsen, G. Bos, H. Dingemanse, M. Lousberg and C. Wouters, “A structured and scalable mechanism for test access to embedded reusable cores,” Proc. International Test Conference, pp. 284 –293, 1998.

    [16] M. Nourani and C. Papachristou, “An ILP formulation to optimize test access mechanism in system-on-chip testing,” Proc. International Test Conference, pp. 902 –910, 2000.

    [17] E. J. Marinissen, S. Goel and M. Lousberg, “Wrapper design for embedded core test,” Proc. International Test Conference, pp. 911 –920, 2000.

    [18] Y. Huang, W. T. Cheng, C. C. Tsai, N. Mukherjee, O. Samman, Y. Zaidan and S. M. Reddy, “Resource allocation and test scheduling for concurrent test of core-based SOC design”, Proc. Asian Test Symposium, 2001.

    [19] V. Iyengar, K. Chakrabarty and E. J. Marinissen, “Test wrapper and test access mechanism co-optimization for system-on-chip”, Proc. International Test Conference, pp. 1023-1032 –910, October 2001.

    [20] V. Iyengar, K. Chakrabarty and E. J. Marinissen, “On using rectangle packing for SOC wrapper/TAM co-optimization”, Proc. IEEE VLSI Test Symposium, pp. 253 –258, April 2002.

    [21] P. M. Rosinger, B. M. Al-Hashimi and N. Nicolici, “Power constrained test scheduling using power profile manipulation”, Proc. ISCAS, Vol. 5, pp. 251-254, 2001.

    [22] P. M. Rosinger, B. M. Al-Hashimi and N. Nicolici, “Power profile manipulation: a new approach for reducing test application time under power constraints”, IEEE Trans. CAD, 2002, to appear.

    [23] T. C. Huang, “Low power testing for CMOS logic circuits”, Ph.D thesis, Cheng Kung University, Taiwan, R.O.C. Jan. 2002.

    [24] A. L. Corcoran and R. L. Wainwright, “A genetic algorithm for packing in three dimensions”, Proc. ACM Symposium on Applied Computing, 1992.

    [25] “Dictionary of Algorithms, Data Structures, and Problems”, http://www.nist.gov/dads.

    [26] E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson, “Approximation algorithms for bin-packing – An updated survey”, Bell Laboratories, Murray Hill, New Jersey, Technical Report, 1988.

    [27] R. Fenrich, R. Miller and Q. F. Stout, “Multi-tiered algorithms for 2-dimensional bin packing”, Proc. Distributed Memory Computing Conference, 1990.

    [28] E. Larsson and Z. Peng, “An integrated system-on-chip test framework”, Proc. Design, Automation and Test in Europe, pp. 138-144, March 2001.

    下載圖示 校內：2005-07-11公開
    校外：2005-07-11公開
    QR CODE