Skip to content
STIMSMITH

Multi-Class Randomization

Technique WIKI v1 · 5/26/2026

Multi-Class Randomization is a constrained-random instruction-generation technique that reduces solver complexity by splitting a large opcode class into multiple category-specific child classes. In the cited AMD microcode-stimulus case study, choosing the opcode category first reduced the active variables and constraints, producing faster runtime and lower memory use than a single-class architecture.

Overview

Multi-Class Randomization reduces the size of a constrained-random generation problem by splitting one large opcode class into multiple smaller classes. In the cited instruction-generator architecture, opcodes were divided into categories that matched the knobs or weights exposed by the test interface. [C1]

The technique uses a base instruction class for data members and methods common to all instruction types, while each opcode-category child class contains only the constraints specific to that category. [C2]

Motivation

The technique was introduced as an alternative to two less satisfactory approaches for x86 opcode generation. Serial randomization met speed and memory goals but produced skewed distributions because each opcode portion was generated sequentially, leaving no control over the overall distribution. A simple constrained-random approach fixed the distribution issue, but the complex x86 instruction set made the randomization problem too slow and memory-intensive. [C3]

Architecture

A Multi-Class Randomization architecture typically separates instruction generation into:

  • a base instruction class containing common data members, common constraints, and common methods such as setting, printing, and packing data; and
  • multiple opcode-category child classes containing constraints specific to each opcode set. [C2]

Within each child class, the cited implementation retained a structure similar to the original single-class code, using implication operators based on opcode type. [C4]

Generation flow

In the cited design, the upper-layer random sequence was controlled only by knobs or switches. It first chose the opcode category, then allocated the appropriate child-class object and added it into the sequence. This avoided direct test-layer constraints on child-class internals. [C5]

If the test layer directly controls lower-level subclass items, the cited source recommends making the subclass-selection decisions first. In that situation, a wrapper class may be needed to constrain all test-controlled variables, randomize those variables first, and then allocate and randomize the correct subclass object in a second generation phase. [C6]

Performance characteristics

The reported performance improvement came from reducing the number of variables and constraints seen by the solver. Compared with the original single-class implementation, the multi-class implementation had seven times fewer constraints, allowing the solver to calculate solutions more efficiently. [C7]

Runtime improved for both solvers evaluated in the case study. The default RACE solver showed a 4x speedup, while the BDD solver showed a 2x speedup for the measured opcode randomization workloads. [C8]

Memory use was also significantly better for the multi-class architecture. The cited study measured memory for the BDD solver because RACE memory consumption was typically smaller and not a limiting factor. [C9]

Solver and profiling considerations

The VCS constraint profiler was used to analyze runtime and memory behavior. It reported runtime data by cumulative randomize calls, individual randomize calls, and solver partitions. [C10]

For BDD solving, memory can be especially important because the solver elaborates the entire solution space before selecting a solution. That solution space can require substantial memory and time to elaborate, although it may be cached to speed later randomize calls. [C11]

Benefits

The main benefit of Multi-Class Randomization is that the solver only sees the constraints relevant to the selected opcode category. In the cited case study, this preserved distribution control and test-level control while improving speed and memory compared with the single-class constrained-random implementation. [C12]

CITATIONS

12 sources
12 citations
[1] Multi-Class Randomization reduces a constrained-random opcode-generation problem by splitting the opcode class into smaller category classes mapped to test-interface knobs or weights. Generating AMD microcode stimuli using VCS constraint solver
[2] The architecture uses a base instruction class for common data, common constraints, and common methods, with child classes holding category-specific constraints. Generating AMD microcode stimuli using VCS constraint solver
[3] Serial x86 opcode generation had acceptable speed and memory but caused skewed distributions, while a simple constrained-random approach solved distribution but reached speed and memory limits. Generating AMD microcode stimuli using VCS constraint solver
[4] Each opcode-category child class used constraints specific to that opcode set and retained a structure similar to the original single-class code, including implication operators based on opcode type. Generating AMD microcode stimuli using VCS constraint solver
[5] The upper-layer random sequence was controlled by knobs, chose the opcode category first, and then allocated the correct object type. Generating AMD microcode stimuli using VCS constraint solver
[6] If the test layer directly controls subclass items, a wrapper class may be required to randomize test-controlled variables before allocating and randomizing the correct subclass. Generating AMD microcode stimuli using VCS constraint solver
[7] The multi-class implementation had seven times fewer constraints than the original, enabling more efficient solving. Generating AMD microcode stimuli using VCS constraint solver
[8] Runtime for the multi-class architecture was faster with both solvers, with a 4x speedup for the default RACE solver and a 2x speedup for the BDD solver. Generating AMD microcode stimuli using VCS constraint solver
[9] Memory requirements were significantly better for the multi-class architecture; the study measured BDD memory because RACE memory was typically smaller and not limiting. Generating AMD microcode stimuli using VCS constraint solver
[10] The VCS constraint profiler provided runtime information for cumulative randomize calls, individual randomize calls, and partitions. Generating AMD microcode stimuli using VCS constraint solver
[11] The BDD solver elaborates the entire solution space before choosing a solution, which can consume substantial memory and time, with caching used to speed later randomizations. Generating AMD microcode stimuli using VCS constraint solver
[12] Choosing the opcode category first simplifies the randomization problem because only constraints specific to that category are present, improving memory and speed without sacrificing distribution or test-level control. Generating AMD microcode stimuli using VCS constraint solver