Overview

Pseudorandom biased generation is documented in the context of IBM random test-program generation for functional processor verification. IBM's first generation of test generators, developed in the mid-1980s, incorporated a biased, pseudorandom, dynamic generation scheme. In the same verification context, generated stimuli are usually test programs intended to trigger architecture and microarchitecture events defined by a verification plan.

Verification role

The surrounding methodology targets simulation-based functional verification of microprocessors. Test programs in this setting are expected to satisfy two requirements:

• Validity: embedded test behavior should conform to the target design specification.
• Quality: tests should expand coverage of the target design and increase the probability of discovering bugs.

A generator can produce many distinct, well-distributed test-program instances that comply with user requests. Variation among instances is achieved through numerous random selections made during generation.

Evolution toward model-based generation

The evidence places pseudorandom biased generation as an earlier IBM approach. The need for a generic solution applicable to any architecture led to a model-based test-generation scheme. That scheme partitions the generator into two main components:

1. a generic, architecture-independent engine; and
2. a model describing the targeted architecture.

In 1991, IBM developed Genesys, described as the first model-based pseudorandom test-program generator. Genesys was later followed by Genesys-Pro, a model-based random test generator for functional microprocessor verification.

Constraint-based successors

Genesys-Pro keeps the model-based separation between a generic generation engine and architecture-specific information. Its generation engine translates the test-generation problem into a constraint satisfaction problem (CSP) and uses a generic CSP solver customized for pseudorandom test generation. The stated goals of this solver customization are to increase the probability of generation success and improve test-program quality.

For single-instruction generation, Genesys-Pro formulates an instruction request as a CSP, solves it, and produces an instruction instance that satisfies the constraints. A CSP consists of variables, domains of possible values, and constraints describing valid combinations of values. The Genesys-Pro instruction solver uses a customized maintaining-arc-consistency algorithm to produce uniformly distributed random solutions that satisfy all mandatory constraints and as many nonmandatory constraints as possible.

Technical significance

Within the cited IBM history, pseudorandom biased generation is significant as an early random test-program generation scheme. Its successor approaches preserved pseudorandom generation but introduced model-based architecture separation and, in Genesys-Pro, CSP-based solving for constrained pseudorandom test generation.