Lazy Merging of Directed Streams

Technique

Lazy Merging of Directed Streams is an algorithmic refactoring used in RISCV-DV to merge directed instruction streams into an initial randomized instruction dump without repeated queue insertions. The technique records intended injection locations first, chains multiple streams targeting the same location, and then builds the final merged instruction dump in one pass, reducing the merge process from O(n²) behavior to O(n) scaling.

First seen 5/25/2026

Last seen 5/25/2026

Evidence 2 chunks

Wiki v1

WIKI

Overview

Lazy Merging of Directed Streams is a technique for combining directed instruction streams with an initial randomized instruction dump in RISCV-DV. It was introduced as an algorithmic refactoring of a greedy merge process that did not scale well for large generated instruction counts. The refactored process avoids actual queue insertions during placement and instead delays materialization of the merged instruction list until all directed stream injection locations have been recorded.

Problem Addressed

READ FULL ARTICLE →

NEIGHBORHOOD

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

explore full graph →

RELATIONSHIPS

2 connections

riscv-dv ← uses 100% 2e

RISCV-DV uses lazy merging to reduce algorithmic complexity of directed stream insertion from O(n²) to O(n).

mixin_dir_instr_list function ← implements 100% 2e

The mixin_dir_instr_list function implements the lazy merging algorithm for directed streams.

CITATIONS

7 sources

7 citations — click to expand

[1] The original RISCV-DV merge process was greedy: it randomly selected a directed-stream injection location, retried up to ten times if the location was inside another directed sequence, and then advanced to a boundary if needed. [PDF] Crafting a Million Instructions/Sec RISCV-DV - DVCon Proceedings

[2] The greedy process involved inserting slices into a SystemVerilog queue, which required moving elements and led to O(n²) complexity as instruction counts and directed stream counts increased. [PDF] Crafting a Million Instructions/Sec RISCV-DV - DVCon Proceedings

[3] Lazy merging marks intended injection locations with a random index instead of immediately performing insertions. [PDF] Crafting a Million Instructions/Sec RISCV-DV - DVCon Proceedings

[4] When multiple directed streams target the same injection location, the method stores the information in a linked-list structure using an index embedded in the stream object. [PDF] Crafting a Million Instructions/Sec RISCV-DV - DVCon Proceedings

[5] After all injectable directed streams have been tabulated, the merged instruction dump is created in one pass by emitting directed stream instructions for each recorded position and then the original instruction. [PDF] Crafting a Million Instructions/Sec RISCV-DV - DVCon Proceedings

[6] The refactoring reduces the insertion process to O(n), and re-profiling found that the merge process scaled well and was no longer a bottleneck for large test-program generation. [PDF] Crafting a Million Instructions/Sec RISCV-DV - DVCon Proceedings

[7] The source notes that larger test programs can generate increasingly complex program flows that are more likely to uncover processor bugs. [PDF] Crafting a Million Instructions/Sec RISCV-DV - DVCon Proceedings