Core-Level Approach: Test Program Generation


This page describes our approach to test program generation for microprocessors. The approach is based on MicroTESK tool that automates creation of test program generators for microprocessors. The tool allow specifying microprocessor instruction sets, to define test coverage, and to configure test program generators for concrete testing goals.

Structure of Test Programs

The test program generator creates a set of test programs. Each test program begins with a prologue and ends with an epilogue. Inner part of the program comprises a number of test cases associated with particular testing goals. The main part of the test case is a test action, i.e. a specially prepared sequence of instructions targeted at creation of a certain situation in microprocessor behavior. Test action is forestalled by initializing instructions and is optionally followed by a test oracle, which checks correctness of the microprocessor state after execution of the test action.

So, the structure of test programs can be described by the following formula:

TEST = PROLOGUE * {(INIT[i], ACTION[i], POST[i])} * EPILOGUE,

where INIT[i] is a sequence of initializing instructions of the i-th test case, ACTION[i] is a test action of the i-th test case, and POST[i] is a test oracle of the i-th test case.

Test case example is shown below. The example uses MIPS instruction set.

The primary goal of MicroTESK is to automate construction of actions and corresponding INIT and POST components resting on high-level microprocessor model and test coverage.

Microprocessor Model and Test Coverage

Microprocessor model consists of two constituents: structural model and instruction set model. Structural description specifies microprocessor’s registers (GPR, FPR, etc.), subsystems (TLB, cache, etc.), and data types (word, single-precision floating-point number, etc.).

Specification of instructions rests on structural model and includes the following parts:

  • instruction interface, which describes instruction’s operands (name, type, data flow direction, etc.) and instruction’s precondition;
  • execution function, which calculates values of the output operands and updates the model state of the microprocessor;
  • assembler format, which specifies textual assembler representation of the instruction.

Basing on the microprocessor model one can define instruction-level test coverage (testing knowledge). We distinguish two types of such knowledge: test situations and dependencies. Test situations describe different events to be created in test programs (exceptions, cache hits/misses, etc.). Dependencies specify interrelations between instructions (usage of the same register, equality of cache rows, etc.). Test coverage is usually defined manually, but some kind of testing knowledge can be derived automatically from microprocessor model.

Microprocessor model and test coverage give a lot of information to be used in test program generation. Architectural knowledge allows controlling instructions’ preconditions (including hazards) and to automatically create test oracles (all instructions are co-simulated by MicroTESK with the help of execution functions). Testing knowledge defines instruction-level situations that might be created in test programs. However, it should be emphasized that there is a lack of information on how to combine instructions, test situations and dependencies into test templates. This is the main problem of instruction-level models.

We suggests using combinatorial techniques to solve this problem. Test templates are generated by systematic enumeration of all feasible combinations of the given instructions, test situations and dependencies. To reduce number of tests, one can use heuristics, like instruction factorization, limitation of the number of dependencies, etc. MicroTESK has a library of ready-to-use template iterators covering different verification tasks. Iterators can be divided into three types: universal iterators (random, combinatorial, etc.), specialized iterators (for testing branching issues, pipelining, etc.), and user-defined iterators.

Generator Development Process

We distinguish three roles in the process of generator development (see the figure below).

Basing on the analysis of the microprocessor documentation (instruction set manual, standards, implementation features, etc.) verification analyst creates a verification plan. The plan contains generalized goals and tasks of testing.

Architecture modeler (usually he or she is also a test developer) specifies microprocessor instruction set and defines instruction-level test coverage, which both form a primary configuration of MicroTESK generator. It is significant to note that some coverage information can be automatically obtained from the microprocessor model.

Verification engineer maps generalized goals of testing, which are stipulated in the verification plan, into concrete values of MicroTESK parameters and starts generation.