| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Simulation-Based Functional Test Generation for Embedded Processors
November 2006 (vol. 55 no. 11)
pp. 1335-1343
Deterministic functional test pattern generation has been a long-standing open problem, which is an important problem to be solved for both design verification and manufacturing testing. One key in developing a practical functional test pattern generation approach is to avoid the exponential growth of the test generation complexity in terms of the design size. This work proposes a novel functional test generation approach where simulation results are used to guide the generation of additional tests. Our methodology avoids the complexity growth issue by converting some modules in a design into simpler and more efficient models. Then, these models are used to facilitate the actual test generation process. We develop two sets of techniques to achieve these conversions: Boolean learning for random logic and arithmetic learning for datapath modules. We demonstrate the effectiveness and discuss the limitations of these techniques through experiments on benchmark circuits. Last, we validate the overall test generation methodology based on the OpenRISC 1200 microprocessor.
[1] M.J. Kearns and U.V. Vazirani, An Introduction to Computational Learning Theory. MIT Press, 1994.
[2] A. Aharon, A. Bar-David, B. Dorfman, E. Gofman, M. Leibowitz, and V. Schwatzburd, “Verification of the IBM RISC System/6000 by a Dynamic Biased Pseudo-Random Test Program Generation,” IBM Systems J., vol. 30, no. 4, pp. 527-538, 1991.
[3] A. Aharon, D. Goodman, M. Levinger, Y. Lichtenstein, Y. Malka, C. Metzger, M. Molcho, and G. Shurek, “Test Program Generation for Functional Verification of PowerPC Processors in IBM,” Proc. Design Automation Conf., pp. 279-285, 1995.
[4] Tutorial notes #9, “Verification and Validation for High-Performance Microprocessors and SOCs” Proc. Int'l Test Conf., 2003.
[5] P. Parvathala, K. Maneparambil, and W. Lindsay, “FRITS—A Microprocessor Functional BIST Method,” Proc. Int'l Test Conf., pp.590-598, 2002.
[6] R. Tupuri and J.A. Abraham, “A Novel Functional Test Generation Method for Processors Using Commercial ATPG,” Proc. Int'l Test Conf., pp. 743-752, 1997.
[7] J. Shen and J.A. Abraham, “Native Mode Functional Test Generation for Processors with Applications to Self-Test and Design Validation,” Proc. Int'l Test Conf., pp. 990-999, 1998.
[8] L. Chen, S. Ravi, and A. Raghunathan, “A Scalable Software-Based Self-Test Methodology for Programmable Processors,” Proc. Design Automation Conf., pp. 548-553, 2003.
[9] X. Bai, L. Chen, and S. Dey, “Software-Based Self-Test Methodology for Crosstalk Faults in Processors,” Proc. High-Level Design Validation and Test Workshop, pp. 11-16, Nov. 2003.
[10] V. Vedula and J.A. Abraham, “FACTOR: A Hierarchical Methodology for Functional Test Generation and Testability Analysis,” Proc. Design Automation and Test in Europe Conf., 2002.
[11] W.-C. Lai, A. Krstic, and K.-T. Cheng, “On Testing the Path Delay Faults of a Microprocessor Using Its Instruction Set,” Proc. VLSI Test Symp., pp. 15-20, 2000.
[12] C. Wen, L.-C. Wang, K.-T. Cheng, W.-T. Liu, and C.-C. Chen, “On A Software-Based Self-Test Methodology and Its Application,” Proc. VLSI Test Symp., pp. 107-113, 2005.
[13] M. Ben-Or and P. Tiwari, “A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation,” Proc. 20th Ann. ACM Symp. Theory Computing, pp. 301-309, 1988.
[14] E. Kaltofen and Y. Lakshman, “Improved Sparse Multivariate Polynomial Interpolation Algorithms,” Proc. Int'l Symp. Symbiotic and Algebraic Computing, pp. 467-474, 1988.
[15] R. Zippel, “Interpolating Polynomials from Their Values,” J. Symbiotic Computing, vol. 9, no. 3, pp. 375-403, 1990.
[16] J. Schwartz, “Fast Probabilistic Algorithms for Verification of Polynomial Identities,” J. ACM, vol. 27, no. 4, pp. 701-717, 1980.
[17] http://www.uweb.ucsb.edu/~opwenITC05_Appendix.pdf , 2006.
[18] L. Valiant, “A Theory of the Learnable,” Comm. ACM, vol. 27, no. 11, pp. 1134-1142, 1984.
[19] M. Kearns, M. Li, L. Pitt, and L. Valiant, “Recent Results on Boolean Concept Learning,” Proc. Fourth Int'l Workshop Machine Learning, pp. 337-352, 1987.
[20] M. Kearns, M. Li, L. Pitt, and L. Valiant, “On the Learnability of Boolean Formulae,” Proc. 19th Symp. Theory of Computing, pp. 285-295, 1987.
[21] O. Coudert and J. Madre, “A Unified Framework for the Formal Verification of Sequential Circuits,” Proc. Int'l Conf. Computer-Aided Design, pp. 126-129, 1990.
[22] Y. Hong, P.A. Beerel, J.R. Burch, and K.L. McMillan, “Sibling-Substitution Based BDD Minimization Using Don't Cares,” IEEE Trans. Computer-Aided Design, vol. 19, no. 1, 2000.
[23] S. Friedman and K. Supowit, “Finding the Optimal Variable Ordering for Binary Decision Diagrams,” IEEE Trans. Computers, vol. 39, no. 5, pp. 710-713, May 1990.
[24] D. Sieling and I. Wegener, “Reduction of OBDDs in Linear Time,” Information Processing Letters, vol. 48, pp. 139-144, 1993.
[25] B. Bollig and I. Wegener, “Improving the Variable Ordering of OBDDs Is NP-Complete,” IEEE Trans. Computers, vol. 45, no. 9, pp.993-1002, Sept. 1996.
[26] OpenRISC 1200 Specification, OPENCORES.ORG, http://www. opencores.org/projects.cgi/web/ or1kopenrisc_1200, 2006.
[27] Design Compiler, Synopsys Inc., http:/www.synopsys.com, 2006.
[28] Fastscan & Flextest, Mentor Graphics Corp., http:/www. mentor.com, 2006.
Index Terms:
Simulation, test generation, functional test, learning
Citation:
Charles H.-P. Wen, Li-C. Wang, Kwang-Ting Cheng, "Simulation-Based Functional Test Generation for Embedded Processors," IEEE Transactions on Computers, vol. 55, no. 11, pp. 1335-1343, Nov. 2006, doi:10.1109/TC.2006.186
