Dynamic Biased Pseudo-Random Test Program Generation

Overview

Dynamic Biased Pseudo-Random Test Program Generation is a functional verification technique used in processor design verification. Rather than relying solely on hand-written tests, the approach generates test programs dynamically, while applying biases that skew the random selection of instructions, operands, and program constructs toward situations that are unlikely to be covered by uniform random testing.

The technique was introduced in the context of verifying the IBM RISC System/6000 processor, as described by Aharon, Bar-David, Dorfman, Gofman, Leibowitz, and Shwartzbund in the IBM Systems Journal in April 1991 [1]. It is cited as part of a broader methodology for processor implementation verification, discussed in a Springer chapter that surveys processor verification approaches [source].

Motivation

Functional verification of complex processors requires exercising a vast instruction and state space. Uniform pseudo-random test program generation can leave significant portions of the design uncovered, particularly corner cases and rare interactions. Biased generation addresses this by directing the generator toward "interesting" regions of the design while retaining the scalability advantages of automated, random-style test synthesis.

The motivation for such techniques was reinforced in the mid-1990s by widely reported processor bugs such as the Pentium floating-point defect, which underscored the cost of inadequate functional verification [2].

Approach

The dynamic-biased pseudo-random approach combines several ideas reported in the related literature:

• Dynamic generation of test programs so that new stimuli are produced continuously during a verification run, enabling coverage of large spaces without storing large hand-curated suites [1].
• Biasing of the random distributions that select instructions, addressing modes, register and memory operands, and program control flow, so that rare but high-risk cases are exercised more frequently than a uniform distribution would allow [1].
• Model-based and coverage-driven extensions, in which the generator is steered by architectural models of the processor under test, and by feedback from coverage measures, as later described for PowerPC processor verification and related model-based generator work [3,4].

Subsequent work in the IBM lineage extended these ideas: Aharon et al. described test program generation for functional verification of PowerPC processors in IBM at the ACM/IEEE Design Automation Conference in 1995 [3], and Lichtenstein, Malka, and Aharon reported on model-based test generation for processor design verification at IAAI 1994 [4].

Relation to Broader Verification Practice

The technique is positioned within a wider ecosystem of pseudo-random and generator-based functional verification methods for processors:

• HP reported design verification of the HP 9000 Series 7000 PA-RISC workstations using comparable generator-driven techniques [5].
• AVPGEN was described as a test-case generator for architecture verification [6].
• Coverage-directed generation using symbolic techniques, as in FMCAD 96, further extended the biasing idea using symbolic analysis and coverage feedback [7].
• Foundational analyses of partition testing strategies provided theoretical context for biased selection from partitioned input domains [8,9].

Significance

Dynamic Biased Pseudo-Random Test Program Generation established a practical pattern for industrial-scale processor verification: combine automated, continuously produced test programs with principled biasing toward hard-to-reach design states. The pattern influenced subsequent generator-based and model-based verification tools used across the microprocessor industry.

References

1. A. Aharon, A. Bar-David, B. Dorfman, E. Gofman, M. Leibowitz, V. Shwartzbund, "Verification of the IBM RISC System/6000 by a Dynamic Biased Pseudo-Random Test Program Generator", IBM Systems Journal, April 1991.
2. B. Beizer, "The Pentium Bug, an Industry Watershed", Testing Techniques Newsletter On-Line Edition, September 1995.
3. A. Aharon, D. Goodman, M. Levinger, Y. Lichtenstein, Y. Malka, C. Metzger, M. Molco, G. Shurek, "Test Program Generation for Functional Verification of PowerPC Processors in IBM", ACM/IEEE Design Automation Conference, 1995.
4. Y. Lichtenstein, Y. Malka, A. Aharon, "Model Based Test Generation for Processor Design Verification", Innovative Applications of Artificial Intelligence (IAAI), AAAI Press, 1994.
5. A. M. Ahi, G. D. Burroughs, A. B. Gore, S. W. LaMar, C. R. Lin, A. L. Wieman, "Design Verification of the HP9000 Series 7000 PA-RISC Workstations", Hewlett-Packard Journal, num. 8 vol. 14, August 1992.
6. A. Chandra, V. Iyengar, D. Jameson, R. Jawalker, I. Nair, B. Rosen, M. Mullen, J. Yoor, R. Armoni, D. Geist, Y. Wolfstal, "AVPGEN — A Test Case Generator for Architecture Verification", IEEE Transactions on VLSI Systems, 6(6), June 1995.
7. D. Geist, M. Farkas, A. Landver, Y. Lichtenstein, S. Ur, Y. Wolfsthal, "Coverage Directed Generation Using Symbolic Techniques", FMCAD 96.
8. E. J. Weyuker, B. Jeng, "Analyzing Partition Testing Strategies", IEEE Transactions on Software Engineering, vol. 17 no. 7, July 1991.
9. E. J. Weyuker, T. J. Ostrand, "Theor..." (truncated in the evidence).