Bubble Sort Input Generation

Concept

A constrained-random stimulus generation scenario in which CRAVE produces randomized input arrays for a CPU testbench executing a bubble sort program. Inputs are shaped by constraints that keep the array within CPU memory, prevent collisions with the loaded program, and force nearly non-increasing (reverse-sorted) data to stress the bubble sort routine.

First seen 7/2/2026

Last seen 7/2/2026

Evidence 3 chunks

Wiki v1

WIKI

Overview

Bubble Sort Input Generation refers to the stimulus-generation step in the CRAVE verification flow in which randomized input arrays are produced for a CPU testbench running a bubble sort program. The arrays serve as stimuli for a CISC CPU (8 registers, 32-bit data width, IA-32 instruction subset with load/store, arithmetic, jump, and halt instructions) that is modeled at three levels of abstraction (C++ ISA, SystemC TLM with OSCI TLM-2.0, and a SystemC RTL five-stage pipeline). CRAVE generates both the programs (instruction sequences) and their inputs, which are reused as stimuli across all three models. The inputs then drive a simulation-based equivalence-checking flow applied to models at different abstraction levels.

Constraints Applied to the Input

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

CRAVE ← evaluates 100% 2e

CRAVE is evaluated for generating bubble sort inputs as a program input generation scenario.

LINKED ENTITIES

1 links

CRAVE EVALUATES Extracted graph relationship

CITATIONS

8 sources

8 citations — click to expand

[1] CRAVE generates programs and their inputs, used as stimuli for three CPU models (C++ ISA, SystemC TLM, SystemC RTL five-stage pipeline). CRAVE: An Advanced Constrained RAndom

[2] The first constraint ensures the array size is positive and less than 1024, fitting into CPU memory. CRAVE: An Advanced Constrained RAndom

[3] The second constraint start()+4*data().size() <= 1024 ensures the array fits into memory and does not collide with the loaded program. CRAVE: An Advanced Constrained RAndom

[4] Each element is bounded to <= 0x00FFFFFF via a foreach constraint. CRAVE: An Advanced Constrained RAndom

[5] The last constraint forces the array to be nearly non-increasing (and thus challenging for bubble sort). CRAVE: An Advanced Constrained RAndom

[6] Such a concise set of constraints would have not been possible with the SCV library due to the lack of support for dynamic data structures. CRAVE: An Advanced Constrained RAndom

[7] The average time for CRAVE to generate the first 1000 arrays is approximately 90s (0.09s per array). CRAVE: An Advanced Constrained RAndom

[8] The CPU being verified is a CISC CPU with 8 registers of 32-bit data width, implementing a subset of IA-32 instructions including load/store, arithmetic, jump, and halt. CRAVE: An Advanced Constrained RAndom