近年來許多有關於測試處理機制(TAM)的最佳化已經廣泛的被討論，隨之而來的便是對於單晶片系統(System-on-Chip) 越來越嚴謹的環境限制，其中包括：內嵌電路(Embedded core)操作頻率的上限、測試處理機制的寬度(TAM Width)大小、整體功耗(Power consumption)的表現…等等，這些因素在在的影響了測試處理機制最佳化的結果，更進一步來說，也對於整體單晶片系統的測試時間(Test application time)與上市時間(Time-to-Market)有很大的影響。但往往這些研究所提出的方法都不能是一個完整符合現實的測試方案，而是只針對其中某一兩種的限制加以探討而已。
    隨著單晶片系統(SOC)的發展與製程上的進步，未來在測試上其複雜度是必定是難以估計的，所以如何提高其測試速度縮短測試時間，又能夠符合單晶片系統在實際生活上的表現，這才是我們所重視的。目前對於單晶片系統的測試主要可分成內部與外部的測試；內部來說，主要是在電路中加上內建自我測試(Built-in Self Test)電路，對於測試樣本(Test Pattern)的結果做壓縮、分析等工作，但由於面積成本需求，目前主要還是以外部測試為主，外部測試是以自動測試機台(Automatic Test Equipment，簡稱ATE)將所需的測試樣本灌入電路中，再由得到的測試結果輸出回ATE做分析。這樣的方法不僅在面積成本節省不少，也能更為精準的對單晶片系統作測試。
    由於目前自動測試機台的操作頻率(Angilent 93000: ~GHz)都高於SOC的操作頻率(~百MHz)，因此，如何充分的利用其頻率的關係，利用頻寬在測試寬度運用上加以考量，作一個有效的測試排程設計便是我們研究的重點。除此之外，單晶片系統上的階層關係(Hierarchy level)也限制著頻寬的使用。當然我們也知道，測試時的功耗遠大於一般模式下的操作，所以對於測試時的功耗問題，我們也一併納入考慮。如此考慮三重限制的條件下，我們制定出一套更有效率的測試排程演算法以縮短單晶片系統的整體測試時間。

Recent advance in TAM optimization has discussed broadly. The actual restrictions considered are more and more rigorous in their method. For example, they maybe think about the embedded core frequency or power consumption during TAM optimization. But some of the researches usually consider incomplete. It can not do the comprehensive doing in the test amount. Therefore, we take into account the optimization problem as below: first, as each core with different work frequency, we can roughly divide these cores into two sets; high and low frequency; second, each core has its own power consumption under test processes; third, the hierarchy relation does exist between each core.
In recent years the advance of CMOS technology has led to a great development, especially on the complexity of the system-on-chip (SOC). It not only increases the layout complexity but also increase the degree of difficulty. As the development of circuit with different technology, the embedded cores embedded into system-on-chips (SOCs) usually have multi-frequency to drive it. In other words, a core may work under different clock cycles. This ability was restricted by its frequency limitation. The total is come to say, all of the core’s working frequency can be divided roughly into two kinds: low-frequency and high-frequency. If we want to test a core at high-speed, we must to be transported the test data at high data rate. This work can be done by ATEs include the Agilent 93000 series tester [1]. But the speech in fact, the test channels with high data rate are constrained on the ATE resource limitations, power rating of the SOC, and scan frequency limit for the embedded cores. On these premise, optimization technique must ensure all of the constraint has already considered, such that high-frequency channels can be used reasonable during SOC test.
In this paper, we present a heuristic approach of TAM optimization according to the reality and reduce the test application time. Unlike prior methods that consider the incomplete situation, the proposed method is applicable to the real-world design model with hierarchy SOCs. We pay the price in hardware overhead in order to decrease test application time.

誌謝……………………………………………………………………	
中文摘要……………………………………………………………	I
英文摘要...……………………………………………………	III
Table of Contents ……………………………………………	V

List of Figures ……………………………………………	VII

List of Tables ……………………………………….	IX

	
Chapter 1 INTRODUCTION ………………………………	1
	
1.1  The overview of SOC deign………………………………	1
1.2  The development of design flow in SOC...........	3
1.3  Test challenge in SOC designs…………………………	5
1.4  Core test access…………………………………………	7
1.5  TAM architecture…………………………………………	8
1.5.1  Basic TAM architecture……………………………	9
1.5.2  Test Bus architecture……………………………	11
1.5.3  TestRail architecture...........................12
1.6  Wrapper architecture………………………..........	14

	
Chapter 2 THE PROBLEM OF TEST SCHEDULE................ 16
	
2.1  DFT……………………………………….…………………	16
2.1.1  Scan chain……………………………………………	16
2.1.2  Core test time……………………………………	17
2.2  The popular rectangle packing model…………………	19
2.3  The general test schedule………………………………	22
2.3.1  Serial test architecture……………………………	22
2.3.2  Parallel test schedule………………………………	23
2.3.3  Mixed test schedule…………………………………	24
2.4  Pareto-optimal point……………………………………	24

	
Chapter 3 THE MODEL FOR TEST SCHEDULING…….........	27
	
3.1  Previous discussion………………………………………	27
3.2  Problem statement of bin packing……………………	28
3.3  Evaluation of the lower bound…………………………	33

	
Chapter 4  HEURISTIC OPTIMIATION ALGORITHM	.........35
	
4.1  Initialization……………………………………………	35
4.2  Part-scheduling……………………………………………	36
4.3  Optimized-scheduling for each level…………………	39
4.3.1  Minimize the idle space………………………	39
4.3.2  Redistribution of TAM lines….………………..	41
4.4  Finalized overall SOC scheduling……………………	44

	
Chapter 5 EXPERIMENTAL RESULTS…………………...	48
	
5.1  Comparison with previous work………………………….48

	
Chapter 6 CONCLUSION…………………...…………….	54
References ………………….………………………...	55

LIST OF FIGURES
Figure 1.1 An example of SOC………………………………………………….. 2
Figure 1.2 A simplified chip design flow and industry relationships……………. 3
Figure 1.3 System design flow using core cells…………………………………. 5
Figure 1.4 Overview of the test access in an embedded-core test……………….. 7
Figure 1.5 The test access architecture overview………………………………... 8
Figure 1.6 Multiplexing Architecture (a),Daisychain Architecture (b), and
Distribution Architecture (c)………………………………………… 11
Figure 1.7 Test Bus Architecture (a) and a possible corresponding serial test
schedule (b)………………………………………………………….. 12
Figure 1.8 TestRail Architecture (a) and possible corresponding serial (b) and
parallel (c) test schedules……………………………………………. 13
Figure 1.10 Core test wrapper…………………………………………………….. 15
Figure 2.1 An overview of scan chain…………………………………………… 17
Figure 2.2 An example of core test time………………………………………… 18
Figure 2.3 TAM design using TAM width partition……………………………... 19
Figure 2.4 The test schedule of Figure 2.3………………………………………. 20
Figure 2.5 The example rectangles for Core 6 in SOC p93791…………………. 20
Figure 2.6 TAM design using generalized rectangle packing…………………… 21
Figure 2.7 The test schedule of Figure 2.6………………………………………. 21
Figure 2.8 An example of the serial test schedules……………………………… 22
Figure 2.9 An example of the parallel test schedules……………………………. 23
Figure 2.10 An example of the mixed test schedules……………………………... 24
Figure 2.11 The pareto-optimal points for core 6 in SOC p93791………………... 26
Figure 3.1 2-D rectangle model………………………………………………….. 29
Figure 3.2 3-D rectangle model………………………………………………….. 30
Figure 3.3 Illustration of hierarchy circuit……………………………………….. 31
Figure 3.4 The example of virtual TAM…………………………………………. 32
Figure 4.1 Data structure………………………………………………………… 36
Figure 4.2 Core’s test scheduling………………………………………………... 37
Figure 4.3 3-D bin packing with hierarchy………………………………………. 38
Figure 4.4 Fill the idle time……………………………………………………… 40
Figure 4.4(a) Fill the idle time………………………………………………………40
Figure 4.4(b) Fill the idle time……………………………………………………... 41
VIII
Figure 4.5 Minimize the idle space further………………………………………. 42
Figure 4.5(a) Minimize the idle space further……………………………………… 43
Figure 4.5(b) Minimize the idle space further……………………………………… 43
Figure 4.6 The pseudo code for fill_idle…………………………………….…… 44
Figure 4.7 The result of test scheduling with hierarchy method………………… 45
Figure 4.8 The efficiency algorithm flow chart………………………………….. 46
Figure 4.9 The pseudo code of the algorithm………………………………….…. 47
Figure 5.1 Final bin-packing for p34392 (width = 40, single speed)…………… 52
Figure 5.2 Final bin-packing for p34392 (width = 40, dual speed)…………… 53

LIST OF TABLES
Table 5.1 The power information about h953……………48
Table 5.2 Test application time for benchmark h953….49
Table 5.3 Test application time for (a) p22810, (b) p34392, (c) p93791, compared the
method in [11]………………………………………………….50
Table 5.4 Test application time with dual-speed for p34392...............................................51

[1] International SEMATECH. The International Technology Roadmap for Semiconductors (ITRS): 2001 Edition. http://public.itrs.net/Files/2001ITRS/Home.htm, 2001. 
[2] R.K. Gupta, Y. Zorian, “Introducing Core-Based System Design,” In Proceedings IEEE Design & Test of Computers, Volume: 14, Issue: 4, pp. 15 - 25, Oct.-Dec. 1997. 
[3] M. Keating and P. Bricaud, “Reuse Methodology Manual For System-on-Chip Designs,” Kluwer Academic Publishers, 1998. 
[4] IEEE P1500 Web Site, http://grouper.ieee.org/groups/1500/.
[5] Y. Zorian, E.J. Marinissen, and S. Dey, “Test Requirements for Embedded Core- Based Systems and IEEE P1500,” In Proceedings IEEE International Test Conference, pp. 191-199, Nov. 1997.
[6] Y. Zorian, E.J. Marinissen, and S. Dey, “Testing Embedded-Core Based System Chips,” In proceedings IEEE International Test Conference, pp. 130-134, Oct. 1998.
[7] J. Aerts and E.J. Marinissen, “Scan Chain Design for Test Time Reduction in Core-Based ICs,” In Proceedings IEEE International Test Conference, pp. 448-457, Oct. 1998.
[8] V. Immaneni and S. Raman, “Direct Access Test Scheme-Design of Block and Core Cells for Embedded ASICS,” In Proceedings IEEE International Test Conference, pp. 488-492, Sep. 1990.
[9] P. Varma and S. Bhatia, “A Structured Test Re-Use Methodology for Core-Based System Chips,” In Proceedings IEEE International Test Conference, pp. 294-302, Washington, DC, Oct. 1998.
[10] 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,” In Proceedings IEEE International Test Conference, pp. 284-293, Oct. 1998.
[11] IEEE P1500 Web Site, http://grouper.ieee.org/groups/1500/.
[12] Y. Zorian, “A Distributed BIST Control Scheme for Complex VLSI Devices,” In Proceedings IEEE VLSI Test Symposium, pp. 6-11, April. 1993.
[14] Harry Bleeker, Peter van den Dijnden, and Frans de Jong, “BoundaryScan Test-A Practical Approach. Kluwer Academic Publishers,” Dordrecht, Netherlands, 1993.
[15] V. Iyengar, K. Chakrabarty and E.J. Marinissen, “On Using Rectangle Packing for SOC Wrapper/TAM Co-Optimization,” In Proceedings IEEE VLSI Test Symposium, pp. 253-258., April. 2002.
[16] V. Iyengar, K. Chakrabarty and E.J. Marinissen, “Test wrapper and test access mechanism co-optimization for system-on-chip,” In Proceedings IEEE Internal Test Conference, pp.1023-1032, Oct. 2002.
[17] V. Iyegnar, K. Chakrabarty and E. J. Marinissen, “Test Access Mechanism Optimization, Test Scheduling, and Tester Data Volume Reduction for System-on-Chip,” In Proceedings IEEE Transaction on Computers, pp. 1619-1631, Dec. 2003.
[18]	S. K. Goel and E. J. Marinissen, “Effective and Efficient Test Architecture Design for SOCs,” In Proceedings IEEE International Test Conference, pp. 529-538, Oct. 2002.
[19]Yu Huang and S.M. Reddy, Wu-Tung Cheng, P. Reuter, N. Mukherjee, Chien-Chung Tsai, O.Samman and Y. Zaidan, “Optimal Core Wrapper Width Selection and SOC Test Scheduling Based on 3-D Bin Packing Algorithm”, In Proceedings IEEE International Test Conference, pp. 74-82, Oct. 2002.
[20]	E. Larrson and Z. Peng, “An Integrated framework for the Design and Optimization of SOC Test Solution”, In Proceedings Date, Automation and Test in Europe Conference and Exhibition 2001, pp.138-144, March. 2001.
[21]	A. Sehgal and K. Chakrabarty, “Efficient Modular Testing of SOCs Using Dual-Speed TAM Architectures”, In Proceedings Date, Automation and Test in Europe Conference and Exhibition, pp. 422-427, Feb. 2004.
[22]	Qiang Xu and N. Nicolici, “Multi-frequency Test Access Mechanism design for Modular SOC Testing,” In Proceedings 13th Asian Test Symposium, pp. 2-7, Nov. 2004.
[23]	K. Chakrabarty, V. Iyengar and M.D. Krasniewski, “Test Planning for Modular Testing of Hierarchical SOCs,” In Proceedings IEEE Transactions on Computer-
Aided Design of integrated Circuits and Systems, pp. 435-448, March, 2005. 
[24] K. Chakrabarty, V. Iyengar, M.D. Krasniewski and G.N. Kumar, “Design and Optimization of Multi-level TAM Architectures for Hierarchical SOCs,” In Proceedings 21st VLSI Test Symposium, pp. 299-304, April. 2003.
[25] A. Sehgal, K. Chakrabarty and V. Iyengar, “SOC Test Planning Using Virtual Test Access Architectures,” In Proceedings IEEE Transactions on Very Large Scale Integration Systems, pp. 1263-1276, Dec. 2004.
[26] A. Sehgal, K. Chakrabarty, V. Iyengar and M.D. Krasniewski, “Test Cost Reduction for SOCs Using Virtual TAMs and Lagrange Multipliers”, In Proceedings Design Automation Conference, pp. 738-743, June. 2003.
[27]Agilent Technologies. Winning in the SOC market, available online at: http://cp.literature.agilient.com/litweb/pdf/5988-7344EN.pdf