skip to main content
10.1145/988952.988976acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

Evaluation of heuristic techniques for test vector ordering

Published: 26 April 2004 Publication History

Abstract

Vector reordering is an essential task in testing VLSI systems because it affects this process from two perspectives: power consumption and correlation among data. The former feature is crucial and if not properly controlled during testing, may result in permanent failure of the device-under-test (DUT). The atter feature is a so important because correlation is captured by coding schemes to efficiently compress test data and ease memory requirements of Automatic-Test-Equipment (ATE),while reducing the volume of data and lowering the test application time. Reordering however is NP-complete. This paper presents an evaluation of different heuristic techniques for vector reordering using ISCAS85 and ISCAS89 benchmark circuits in terms of time and quality. For this application, it is shown that the best heuristic technique is not the famous Christofides or Lin-Kernighan, but the Multi-Fragment technique.

References

[1]
R. K. Gupta and Y. Zorian., "Introducing Core-Based System Design," IEEE Design & Test, Vol. 14, No. 4, pp. 15--25, Oct-Dec 1997.
[2]
F. Corno, M. Rebaudengo, M. Reorda and M. Violante, "Optimal Vector Selection for Low Power BIST," Proc. IEEE Int. Symp. on Defect and Fault Tolerance in VLSI Systems, pp. 219--226, 1999.
[3]
S. Wang and S. K. Gupta, "ATPG for Heat Dissipation Minimization During Test Application," Proc. IEEE Int. Test Conf., pp. 250--258, 1994.
[4]
R. M. Chou, K. K. Saluja and V. D. Agrawal, "Power Constraint Scheduling of Tests," Proc. Int. Conf. on VLSI Design, pp. 271--274, 1994.
[5]
V. Dabholkar, S. Chakravarty, I. Pomeranz and S. Reddy, "Techniques for Minimizing Power Disspation in Scan and Combinational Circuits During Test Application," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 17, No. 12, pp 1325--1333, Dec. 1998.
[6]
P. Flores, J. Costa, H. Neto, J. Monteiro and J. M-Silva, "Assignment and Reordering of Incompletely Specified Pattern Sequences Targeting Minimum Power Dissipation," Proc. Int. Conf. on VLSI Design, pp. 37--41, 1999.
[7]
P. Girard, C. Landrault, S. Paravossoudovitch and D. Severac, "Reduction of Power Consumption During Test Application by Test Vector Ordering," IEE Electronics Letters, Vol. 33, No. 21, pp. 1752--1754, Oct. 1997.
[8]
A. Jasand N. A. Touba,"Test Vector Decompression via Cyclical Scan Chains and Its Application to Testing Core-Based Designs," Proc. IEEE Int. Test Conf., pp. 458--464, 1998.
[9]
A. Chandra and K. Chakrabarty, "Test Data Compression for System-on-a-Chip Using Golomb Codes," Proc. IEEE VLSI Test Symp., pp. 113--120, 2000.
[10]
S. Sahni and T. Gonzalez, "P-Complete Approximation Problems," Journal of ACM, Vol. 23, No. 3, pp. 555--565, July 1976.
[11]
E. Aarts and J. K. Lenstra, "Local Search In Combinatorial Optimization," John Wiley & Sons Pub., 1997.
[12]
E. L. Lawer, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, "The Traveling Salesman Problem," John Wiley & Sons Pub., 1985.
[13]
S. Arora, C, Lund, R. Motwani, M. Sudan and M. Szegedy, "Proof Verification and Hardness of Approximation Problems," Proc. IEEE Symp. on Foundations of Computer Science, pp. 14--23, 1992.
[14]
N. Christofides, "Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem," Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, 1976.
[15]
H. Hashempour and F. Lombardi, "ATE-Amenable Test Data Compression with no Cyclic Scan Register," Proc. IEEE Int. Conf. on Defect and Fault Tolerance in VLSI Systems, pp. 151--158, 2003.
[16]
T. Niermann and J. H. Patel, "HITEC: A Test Generation Package for Sequential Circuits," Proc. European Design Automation Conf., pp. 214--218, 1991.

Cited By

View all
  • (2023)Cluster-based test vector re-ordering for reduced power dissipation in digital circuitsAutomatika10.1080/00051144.2023.225123064:4(1141-1147)Online publication date: 29-Aug-2023
  • (2011)Weighted transition based reordering, columnwise bit filling, and difference vectorVLSI Design10.1155/2011/7565612011(9-9)Online publication date: 1-Jan-2011
  • (2011)Artificial intelligence based scan vector reordering for capture power minimization2011 Nirma University International Conference on Engineering10.1109/NUiConE.2011.6153270(1-6)Online publication date: Dec-2011
  • Show More Cited By

Index Terms

  1. Evaluation of heuristic techniques for test vector ordering

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI
    April 2004
    479 pages
    ISBN:1581138539
    DOI:10.1145/988952
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 26 April 2004

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. ATE
    2. SoC
    3. compression
    4. power consumption
    5. test data
    6. test vector ordering

    Qualifiers

    • Article

    Conference

    GLSVLSI04
    Sponsor:
    GLSVLSI04: Great Lakes Symposium on VLSI 2004
    April 26 - 28, 2004
    MA, Boston, USA

    Acceptance Rates

    Overall Acceptance Rate 312 of 1,156 submissions, 27%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 30 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Cluster-based test vector re-ordering for reduced power dissipation in digital circuitsAutomatika10.1080/00051144.2023.225123064:4(1141-1147)Online publication date: 29-Aug-2023
    • (2011)Weighted transition based reordering, columnwise bit filling, and difference vectorVLSI Design10.1155/2011/7565612011(9-9)Online publication date: 1-Jan-2011
    • (2011)Artificial intelligence based scan vector reordering for capture power minimization2011 Nirma University International Conference on Engineering10.1109/NUiConE.2011.6153270(1-6)Online publication date: Dec-2011
    • (2011)Survey on multimedia transmission using Network Coding over Wireless Networks2011 Nirma University International Conference on Engineering10.1109/NUiConE.2011.6153256(1-6)Online publication date: Dec-2011
    • (2010)Reordering of test vector using artificial intelligence approach for power reduction during VLSI testingProceedings of the 12th international conference on Networking, VLSI and signal processing10.5555/1820538.1820558(113-117)Online publication date: 20-Feb-2010
    • (2008)Evaluation and Analysis of Heuristic Techniques for Vector Ordering of VLSI Test SetsIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2008.91726157:9(1998-2004)Online publication date: Sep-2008
    • (2008)Artificial intelligence approach to test vector reordering for dynamic power reduction during VLSI testingTENCON 2008 - 2008 IEEE Region 10 Conference10.1109/TENCON.2008.4766747(1-6)Online publication date: Nov-2008

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media