article

A Graph-Based Approach to Power-Constrained SOC Test Scheduling

Authors:

Cheng-Wen WuAuthors Info & Claims

Journal of Electronic Testing: Theory and Applications, Volume 20, Issue 1

Pages 45 - 60

https://doi.org/10.1023/B:JETT.0000009313.23362.fd

Published: 01 February 2004 Publication History

Abstract

The test scheduling problem is one of the major issues in the test integration of system-on-chip (SOC), and a test schedule is usually influenced by the test access mechanism (TAM). In this paper we propose a graph-based approach to power-constrained test scheduling, with TAM assignment and test conflicts also considered. By mapping a test schedule to a subgraph of the test compatibility graph, an interval graph recognition method can be used to determine the order of the core tests. We then present a heuristic algorithm that can effectively assign TAM wires to the cores, given the test order. With the help of the tabu search method and the test compatibility graph, the proposed algorithm allows rapid exploration of the solution space. Experimental results for the ITC02 benchmarks show that short test length is achieved within reasonable computation time.

References

[1]

1. J. Aerts and E.J. Marinissen, "Scan Chain Design for Test Time Reduction in Core-Based ICs," in Proc. Int. Test Conf. (ITC), 1998, pp. 448-457.

Digital Library

[2]

2. K. Chakrabarty, "Design of System-on-a-Chip Test Access Architecture Under Place-and-Route and Power Constraints," in Proc. IEEE/ACM Design Automation Conf. (DAC), 2000, pp. 432-437.

Digital Library

[3]

3. K. Chakrabarty, "Design of System-on-a-Chip Test Access Architecture Using Integer Linear Programming," in Proc. IEEE VLSI Test Symp. (VTS), 2000, pp. 127-134.

Digital Library

[4]

4. K. Chakrabarty, "Test Scheduling for Core-Based Systems Using Mixed-Integer Linear Programming," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 19, no. 10, pp. 1163-1174, 2000.

Digital Library

[5]

5. R.M. Chou, K.K. Saluja, and V.D. Agrawal, "Scheduling Tests for VLSI Systems Under Power Constraints," IEEE Trans. VLSI Systems, vol. 5, no. 2, pp. 175-185, 1997.

Digital Library

[6]

6. G.L. Craig, C.R. Kime, and K.K. Saluja, "Test Scheduling and Control for VLSI Built-in Self-Test," IEEE Trans. Computers, vol. 37, no. 9, pp. 1099-1109, 1988.

Digital Library

[7]

7. F. Glover, E. Taillard and D. de Werra, "A User's Guide to Tabu Search," Annals of Operations Research, vol. 41, pp. 3-28, 1993.

Digital Library

[8]

8. S.K. Goel and E.J. Marinissen, "Cluster-Based Test Architecture Design for System-on-Chip," in Proc. IEEE VLSI Test Symp. (VTS), Monterey, 2002, pp. 259-264.

Digital Library

[9]

9. S.K. Goel and E.J. Marinissen, "Effective and Efficient Test Architecture Design for SOCs," in Proc. Int. Test Conf. (ITC), Baltimore, 2002, pp. 529-538.

Digital Library

[10]

10. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press, 1980.

Digital Library

[11]

11. W.-L. Hsu and T.-H. Ma, "Fast and Simple Algorithm for Recognizing Chordal Comparability Graphs and Interval Graphs," SIAM J. Computing, vol. 28, no. 3, pp. 1004-1020, 1999.

Digital Library

[12]

12. 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," in Proc. Tenth IEEE Asian Test Symp. (ATS), Kyoto, pp. 265- 270, 2001.

Digital Library

[13]

13. Y. Huang, S.M. Reddy, W.-T. Cheng, and P. Reuter, "Optimal Core Wrapper Width Selection and SOC Test Scheduling Based on 3-D Bin Packing Algorithm," in Proc. Int. Test Conf. (ITC), Baltimore, 2002, pp. 74-82.

Digital Library

[14]

14. V. Iyengar and K. Chakrabarty, "Precedence-Based, Preemptive, and Power-Constrained Test Scheduling for System-on-a-Chip," in Proc. IEEE VLSI Test Symp. (VTS), 2001, pp. 368-374.

Digital Library

[15]

15. V. Iyengar and K. Chakrabarty, "Test Bus Sizing for System-ona-Chip," IEEE Trans. Computers, vol. 51, no. 5, pp. 449-459, 2002.

Digital Library

[16]

16. V. Iyengar, K. Chakrabarty, and E.J. Marinissen, "Test Wrapper and Test Access Mechanism Co-Optimzation for System-on-Chip," in Proc. Int. Test Conf. (ITC), Baltimore, 2001, pp. 1023- 1032.

Digital Library

[17]

17. V. Iyengar, K. Chakrabarty, and E.J. Marinissen, "Integrated Wrapper/TAM Co-Optimization, Constraint-Driven Test Scheduling, and Tester Data Volume Reduction for SOCs," in Proc. IEEE/ACM Design Automation Conf. (DAC), New Orleans, 2002, pp. 685-690.

Digital Library

[18]

18. V. Iyengar, K. Chakrabarty, and E.J. Marinissen, "On Using Rectangle Packing for SOC Wrapper/TAM Co-Optimization," in Proc. IEEE VLSI Test Symp. (VTS), Monterey, 2002, pp. 253- 258.

Digital Library

[19]

19. V. Iyengar, K. Chakrabary, and E. J. Marinissen, "Efficient Wrapper/TAM Co-Optimization for Large SOCs," in Proc. Design, Automation and Test in Europe (DATE), Paris, 2002, pp. 491- 498.

Digital Library

[20]

20. E. Larsson and Z. Peng, "An Integrated System-On-Chip Test Framework," in Proc. Design, Automation and Test in Europe (DATE), Munich, 2001, pp. 138-144.

Digital Library

[21]

21. E. Marinissen, R. Kapur, and Y. Zorian, "On Using IEEE P1500 SECT for Test Plug-n-Play," in Proc. Int. Test Conf. (ITC), 2000, pp. 770-777.

Digital Library

[22]

22. E.J. Marinissen, S. Goel, and M. Lousberg, "Wrapper Design for Embedded Core Test," in Proc. Int. Test Conf. (ITC), 2000, pp. 911-920.

Digital Library

[23]

23. E.J. Marinissen and S.K. Goel, "Analysis of Test Bandwidth Utilization in Test Bus and TestRail Architectures for SOCs," in Proc. IEEE Int. Workshop on Design and Diagnostics of Electronic Circuits and Systems (DDECS), 2002, pp. 52-60.

[24]

24. E.J. Marinissen, V. Iyengar, and K. Chakrabarty, "A Set of Benchmarks for Modular Testing of SOCs," in Proc. Int. Test Conf. (ITC), Baltimore, 2002, pp. 519-528.

Digital Library

[25]

25. V. Muresan, X. Wang, V. Muresan, and M. Vladutiu, "A Comparison of Classical Scheduling Approaches in Power-Constrained Block-Test Scheduling," in Proc. Int. Test Conf. (ITC), 2000, pp. 882-891.

Digital Library

[26]

26. C.-P. Su and C.-W. Wu, "Graph-Based Power-Constrained Test Scheduling for SOC," in Proc. IEEE Int. Workshop on Design and Diagnostics of Electronic Circuits and Systems (DDECS), Brno, Czech Republic, 2002, pp. 61-68.

[27]

27. Y. Zorian, E.J. Marinissen, and S. Dey, "Testing Embedded-Core Based System Chips," in Proc. Int. Test Conf. (ITC), 1998, pp. 130-143.

Digital Library

Cited By

Bahukudumbi SChakrabarty K(2019)Test-length and TAM optimization for wafer-level reduced pin-count testing of core-based SoCsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200915028:1(111-120)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1109/TCAD.2008.2009150
Giri CTipparthi DChattopadhyay S(2018)A genetic algorithm based approach for system-on-chip test scheduling using dual speed TAM with power constraintWSEAS Transactions on Circuits and Systems10.5555/1482066.14820777:5(416-427)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.5555/1482066.1482077
Bahukudumbi SChakrabarty K(2018)Wafer-level modular testing of core-based SoCsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.5555/1376110.137611915:10(1144-1154)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.5555/1376110.1376119
Show More Cited By

Index Terms

A Graph-Based Approach to Power-Constrained SOC Test Scheduling

Recommendations

Cycle-Accurate Test Power Modeling and Its Application to SoC Test Architecture Design and Scheduling

Concurrent testing of the cores in a core-based system- on-chip reduces the test application time but increases the test power consumption. Power models, test architecture design, and scheduling algorithms have been proposed to schedule the tests as ...
Abort-on-fail based test scheduling

The long and increasing test application time for modular core-based system-on-chips is a major problem, and many approaches have been developed to deal with the problem. Different from previous approaches, where it is assumed that all tests will be ...
System-on-chip test scheduling with reconfigurable core wrappers

The problem with increasing test application time for testing core-based system-on-chip (SOC) designs is addressed with test architecture design and test scheduling. The scan-chains at each core are configured into a set of wrapper-chains, which by a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Electronic Testing: Theory and Applications

Journal of Electronic Testing: Theory and Applications Volume 20, Issue 1

February 2004

115 pages

ISSN:0923-8174

Issue’s Table of Contents

Copyright © Copyright © 2004 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bahukudumbi SChakrabarty K(2019)Test-length and TAM optimization for wafer-level reduced pin-count testing of core-based SoCsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200915028:1(111-120)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1109/TCAD.2008.2009150
Giri CTipparthi DChattopadhyay S(2018)A genetic algorithm based approach for system-on-chip test scheduling using dual speed TAM with power constraintWSEAS Transactions on Circuits and Systems10.5555/1482066.14820777:5(416-427)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.5555/1482066.1482077
Bahukudumbi SChakrabarty K(2018)Wafer-level modular testing of core-based SoCsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.5555/1376110.137611915:10(1144-1154)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.5555/1376110.1376119
Xu QNicolici N(2018)Modular and rapid testing of SOCs with unwrapped logic blocksIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2005.85958513:11(1275-1285)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1109/TVLSI.2005.859585
Hussin FYoneda TOrailoĞLu AFujiwara H(2018)Scheduling Power-Constrained Tests through the SoC Functional BusIEICE - Transactions on Information and Systems10.1093/ietisy/e91-d.3.736E91-D:3(736-746)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.1093/ietisy/e91-d.3.736
Hu CLi ZXu CJia M(2018)Test Scheduling for Network-on-Chip Using XY-Direction Connected Subgraph Partition and Multiple Test ClocksJournal of Electronic Testing: Theory and Applications10.1007/s10836-016-5565-532:1(31-42)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s10836-016-5565-5
Giri CSarkar SChattopadhyay S(2009)Test Scheduling for Core-Based SOCs Using Genetic Algorithm Based Heuristic ApproachProceedings of the 3rd International Conference on Intelligent Computing: Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence10.1007/978-3-540-74205-0_107(1032-1041)Online publication date: 17-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-540-74205-0_107
Sehgal ABahukudumbi SChakrabarty K(2008)Power-aware SoC test planning for effective utilization of port-scalable testersACM Transactions on Design Automation of Electronic Systems (TODAES)10.1145/1367045.136706213:3(1-19)Online publication date: 25-Jul-2008
https://dl.acm.org/doi/10.1145/1367045.1367062
Meena ABoulet P(2005)Model driven scheduling framework for multiprocessor soc designProceedings of the 6th international conference on Parallel Processing and Applied Mathematics10.1007/11752578_107(888-895)Online publication date: 11-Sep-2005
https://dl.acm.org/doi/10.1007/11752578_107

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents