A Survey of Methods and Tools for Test Program Generation for Microprocessors
https://doi.org/10.15514/ISPRAS-2017-29(1)-11
Abstract
This paper gives a survey of existing methods and tools for test program generation for microprocessors. Test program generation and analysis of their execution traces is the main approach to functional verification of microprocessors. This approach is also known as testing. Despite continuous progress in test program generation methods, testing remains an extremely laborious process. One of the main reasons is that test program generation tools are unable to quickly enough adapt to changes. In the majority of cases, they are created for specific microprocessor types and are designed to solve specific tasks. For this reason, support for new microprocessors types and generation methods requires a significant effort. Often, in such situations, tools have to be implemented from scratch. Inability to reuse existing implementations of generation methods complicates evolution of test generation tools and, consequently, prevents improvement of testing quality. The present situation creates motivation to search for solutions to developing more flexible tools which could be easily adapted to testing new microprocessor types and applying new generation methods. The goal of the present work is to summarize existing experience in test program generation, which could serve as a basis for creating such tools. The paper considers strengths and weaknesses of popular generation methods, their application domains and cases of their combined use. It also makes a comparative analysis of facilities of existing generation tools implementing these methods. Based on the analysis, it gives recommendations on creating a unified methodology to develop tools for test program generation for microprocessors.
About the Author
A. D. Tatarnikov
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
References
1. Grant McFarland. Microprocessor Design: A Practical Guide from Design Planning to Manufacturing Professional Engineering. McGraw Hill Professional, 2006, 408 p.
2. Transistor count in microprocessors - http://en.wikipedia.org/wiki/Transistor_count
3. Intel® Pentium® 4 Processor. Specification Update, August 2008 (http://download.intel.com/design/intarch/specupdt/24919969.pdf)
4. Intel® Core™ i7-900 Desktop Processor Extreme Edition Series and Intel® Core™ i7-900 Desktop Processor Series. Specification Update, February 2015. (http://www.intel.com/content/dam/www/public/us/en/documents/specification-updates/core-i7-900-ee-and-desktop-processor-series-spec-update.pdf)
5. Beizer B. The Pentium Bug - An Industry Watershed // Testing Techniques Newsletter, TTN Online Edition, September 1995.
6. A. Kamkin, A. Kotsynyak, S. Smolov, A. Sortov, A. Tatarnikov, M. Chupilko. Tools for Functional Verification of Microprocessors. Trudy ISP RАN / Proc. ISP RAS, vol. 26, issue. 1, 2014. pp. 149-200 (in Russian). DOI: 10.15514/ISPRAS-2014-26(1)-5.
7. W.K. Lam. Hardware Design Verification: Simulation and Formal Method-Based Approaches. Prentice Hall, 2005, 624 p.
8. A. Adir, E. Almog, L. Fournier, E. Marcus, M. Rimon, M. Vinov, A. Ziv. Genesys-Pro: Innovations in Test Program Generation for Functional Processor Verification. IEEE Design & Test of Computers, 21(2), 2004, pp. 84-93.
9. J. Bhadra, M. Abadir, S. Ray, L. Wang. A Survey of Hybrid Techniques for Functional Verification. IEEE Design & Test of Computers, 24(22), 2007, pp. 112-122.
10. A.S. Kamkin, T.I. Sergeeva, S.A. Smolov, A.D. Tatarnikov, M.M. Chupilko. Extensible Environment for Test Program Generation for Microprocessors. Programming and Computer Software, 40(1), 2014, pp. 1-9. DOI: 10.1134/S0361768814010046.
11. A.Kamkin, A.Protsenko, A.Tatarnikov. An Approach to Test Program Generation Based on Formal Specifications of Caching and Address Translation Mechanisms. Trudy ISP RAN / Proc. ISP RAS, vol. 27, issue 3, 2015, pp. 125-138. DOI: 10.15514/ISPRAS-2015-27(3)-9.
12. Bobkov S.G., Chibisov P.A. Improving of Quality of High-performance Microprocessors Testing by Counter-Testing Methods with Analysis of the Functional Coverage of the Selected User Control Tasks. Informacionnye tehnologii [Information Technology], No. 8, 2013, pp. 26-33 (in Russian)
13. Khisambeev I.Sh., Chibisov P.A. On one method of defining functional coverage metrics for microprocessor testing. Proceedings of the conference on Problems of Perspective Micro- and Nanoelectronic Systems Development (MES-2014), Part II, 2014, pp. 63-68 (in Russian).
14. Piziali A. Functional Verification Coverage Measurement and Analysis. New York: Kluwer Academic Publishers. 2004. 216 p.
15. P. Mishra, N. Dutt. Specification-Driven Directed Test Generation for Validation of Pipelined Processors. ACM Transactions on Design Automation of Electronic Systems, 13(3), 2008, pp. 1-36.
16. E.A. Poe. Introduction to random test generation for processor verification. Technical report. Obsidian Software, 2002, 7 p.
17. RISU test program generator for testing QEMU simulator - https://git.linaro.org/people/peter.maydell/risu.git/about/.
18. Gribkov I.V., Zaharov A.V., Kol'cov P.P., et al. Stochastic testing in the INTEG system. Programmnye Produkty i Sistemy [Programming Products and Systems], 2007, no. 2, pp. 22-26 (in Russian).
19. Kamkin A.S. Test Program Generation for Microprocessors. Trudy ISP RАN / Proc. ISP RAS, vol. 14, issue. 2, 200, pp. 23-63 (in Russian).
20. N. Sharma, B. Dickman, Verifying an ARM Core, EE Times, 2001, 7 p.
21. A. Kamkin. Some issues of automation of test program generation for branch processing units of microprocessors. Trudy ISP RАN / Proc. ISP RAS, vol. 18, 2010, pp. 129-149 (in Russian).
22. Y. Naveh, M. Rimon, I. Jaeger, Y. Katz, M. Vinov, E. Marcus, G. Shurek. Constraint-Based Random Stimuli Generation for Hardware Verification. AI Magazine, 28(3), 2007, pp. 13-30.
23. P. Mishra and N. Dutt. Specification-Driven Directed Test Generation for Validation of Pipelined Processors. ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 13, Issue 3, 2008, pp. 1-36.
24. Gribkov I.V., Zaharov A.V., Kol'cov P.P., et al. Evolution of stochastic testing system of microprocessors INTEG. Programmnye Produkty i Sistemy [Programming Products and Systems], 2010, no. 2, pp. 14-23 (in Russian).
25. MIPS64™ Architecture For Programmers. Volume 1: Introduction to the MIPS64™ Architecture. Revision 6.01. MIPS Technologies Inc. 2014, 148 p.
26. VMIPS virtual machine simulator - http://www.dgate.org/vmips/.
27. ARM web site - http://www.arm.com.
28. N. Sharma and B. Dickman. Verifying an ARM Core. EE Times. 2001, p. 7.
29. Hrishikesh M.S., Rajagopalan M., Sriram S., Mantri R. System Validation at ARM - Enabling our Partners to Build Better Systems. White Paper. April 2016 (http://www.arm.com/files/pdf/System_Validation_at_ARM_Enabling_our_partners_to_build_better_systems.pdf).
30. Venkatesan D., Nagarajan P. A Case Study of Multiprocessor Bugs Found Using RIS Generators and Memory Usage Techniques. Workshop on Microprocessor Test and Verification, 2014, pp. 4-9. DOI: 10.1109/MTV.2014.28.
31. Hudson J., Kurucheti G. A Configurable Random Instruction Sequence (RIS) Tool for Memory Coherence in Multi-processor Systems. Workshop on Microprocessor Test and Verification, 2014, pp. 98-101. DOI: 10.1109/MTV.2014.26.
32. RAVEN test program generatort -http://www.slideshare.net/DVClub/introducing-obsidian-software-andravengcs-for-powerpc.
33. Obsidian Software Inc. “Raven: Product datasheet”. 6 p.
34. R.N. Mahapatra, P. Bhojwani, J. Lee, and Y. Kim. Microprocessor Evaluations for Safety-Critical. Real-Time Applications: Authority for Expenditure, no.43, Phase 3 Report, 2009, 43 p.
35. PowerPC architecture - https://en.wikipedia.org/wiki/PowerPC
36. M. Behm, J. Ludden, Y. Lichtenstein, M. Rimon, M. Vinov. Industrial Experience with Test Generation Languages for Processor Verification. Proceedings of the Design Automation Conference, 2004, pp. 36-40.
37. M. Aharoni, S. Asaf, L. Fournier, A. Koifman and R. Nagel. FPgen - A Test Generation Framework for Datapath Floating-Point Verification. Proceedings of the Eighth IEEE International Workshop on High-Level Design Validation and Test Workshop (HLDVT'03), 2003, pp. 17-22.
38. M. Aharony, E. Gofman, E. Guralnik, A. Koyfman. Injecting floating-point testing knowledge into test generators. Proceedings of the 7th international Haifa Verification conference on Hardware and Software: Verification and Testing (HVC’11), 2011, pp. 234-241.
39. IEEE standard for binary FP arithmetic. An American National Standard, ANSI/IEEEE Std. 754-2008, 58 p.
40. IBM Floating-Point Test Suite for IEEE 754R Standard - https://www.research.ibm.com/haifa/projects/verification/fpgen/ieeets.html
41. Adir A., Fournier L., Katz Y., Koyfman A. DeepTrans - Extending the Model-based Approach to Functional Verification of Address Translation Mechanisms. High-Level Design Validation and Test Workshop, 2006, pp. 102-110.
42. Seonghun Jeong, Youngchul Cho, Daeyong Shin, Changyeon Jo, Yenjo Han, Soojung Ryu, Jeongwook Kim, and Bernhard Egger. Random Test Program Generation for Reconfigurable Architectures. Proceedings of 13th International Workshop on Microprocessor Test and Verification (MTV), 2012, 6 p.
43. T.Li, D.Zhu, Y.Guo, G.Liu, S.Li. MA2TG: A Functional Test Program Generator for Microprocessor Verification. Euromicro Conference on Digital System Design, 2005, pp.176-183.
44. P. Grun, A. Halambi, A. Khare, V. Ganesh, N. Dutt and A. Nicolau. EXPRESSION: An ADL for System Level Design Exploration. Technical Report 1998-29, University of California, Irvine, 1998, 26 p.
45. SMV model checker - http://www.cs.cmu.edu/~modelcheck/smv.html
46. F. Corno, G. Cumani, M. Sonza Reorda, G. Squillero. Efficient Machine-Code TestProgram Induction. CEC’2002: Congress on Evolutionary Computation, Honolulu, Hawaii, USA, 2002.
47. F. Corno et al., “Fully Automatic Test Program Generation for Microprocessor Cores,” Proc. IEEE Design, Automation and Test in Europe (DATE 03), IEEE CS Press, 2003, pp. 1006-1011.
48. F. Corno, E. Sanchez, M. Sonza Reorda, G. Squillero. Automatic Test Program Generation - A Case Study. IEEE Design and Test, Special Issue on Functional Verification and Testbench Generation, Volume 21, Issue 2, 2004, pp. 102-109.
Review
For citations:
Tatarnikov A.D. A Survey of Methods and Tools for Test Program Generation for Microprocessors. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(1):167-194. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(1)-11
Email this article 