Design document: a compressed memory-access trace format for a RISC-V emulator

Nick Chaiyachakorn – 2026-10-14

1. The Problem

Context: I am implementing a RISC-V (64-bit) emulator, with an Sv39x4 paging scheme. One feature of this emulator is "meta-paging": not all emulated physical memory is resident in the emulator, but is split into "meta-pages" that are "meta-paged" to and from a larger backing store on disk.

Now let's say we have a resident memory budget -- say, 8MB. We need to determine, in an evidence-driven way:

  • The size of each metapage, assuming an integer multiple of base 4 KiB pages;
  • The number of metapages resident in memory.

I want to answer this question by simulating the costs of each scheme using recorded physical simulated memory access traces. (i.e. recordings of memory addresses accessed using a real workload!)

The problem we'll solve here: what is a good compressed format to store simulated memory access traces?

Let's now specify goals, non-goals, and hint at design choices:

2. Goals and Non-Goals

Non-goals:

  • No full address precision needed
    • This allows us to store only a subset of the bits of an accessed address.
  • No need for a constant address precision over time
    • This allows us to switch between "bursts" of high-precision address traces, sandwiched between longer spans of lower-precision address traces.

Goals:

  • Duration: Our traces should allow us to record access patterns over enough time for an emulated minimal Linux to boot to a shell -- say, ~100 seconds.
  • Small-ish memory trace recordings: The above recorded ~100-second trace should not exceed, say, 128MB!

3. Proposed Solution

The key idea: alternate between short "high-fidelity" bursts, sandwiched with long spans of "low-fidelity" recordings. These have different sampling rates, and compressed address storage formats.

High-fidelity bursts and low-fidelity spans over time Three short high-fidelity bursts alternate with three longer low-fidelity spans. The first burst is labeled as having compressed 48-bit addresses, and the first span as having compressed 32-bit addresses. Time increases to the right. High-Fidelity Burst Compressed 48-Bit Addresses Low-Fidelity Span Compressed 32-Bit Addresses High-Fidelity Burst Low-Fidelity Span High-Fidelity Burst Low-Fidelity Span Time

The upshot: reasonable trace sizes. Below, we show what parameters might allow us to record 30 seconds at 1GHz to produce a ~800MB trace.

Recording Section Type Sampling Rate (cycles/sample) Compressed Address Storage Format (see below) Duration (s)
High-Fidelity Burst 24 Compressed 48-bit 1
Low-Fidelity Span 2048 Compressed 32-bit 10

Then, for actual analysis, "guesstimate" high-fidelity reconstructions of low-fidelity spans, as described below.

3.1 What Is The Resulting Size of a Emulated Trace?

Assume we can't predict the actual clock speed of our emulator that's recording traces. However, we do know that we want to record the equivalent of t = 30\textrm{s} of a s_\textrm{ref} = 1 \textrm{GHz} processor, giving us a total target c = 30\textrm{Gcyc}.

Recording section type parameters. Additionally, define for each alternating recording section type, subscripted h and \ell respectively for high-fidelity bursts and low-fidelty spans:

  • A compressed address size in bytes, b_h = 6 \textrm{B}, b_\ell=4 (fixed forever unto eternity);
  • A sample rate in cycles-per-sample, r_h = 24\textrm{cyc/sample}, r_\ell = 2048\textrm{cyc/sample},
  • The lengths (in seconds recorded) of each section, s_h = 1{s}, , before we switch recording section types;

The below equation gives S, the resulting trace size in bytes:

S = \frac{s_{\mathrm{ref}}\,t}{s_h+s_\ell} \left( \frac{b_h s_h}{r_h} + \frac{b_\ell s_\ell}{r_\ell} \right).

Substituting these values in, S \approx 766\textrm{MiB}. Here's an interactive calculator for S that I generated using ChatGPT.

3.2 Compressed Sv39x4 Guest-Physical Address Formats

Recall that an Sv39x4 host-physical address has the following format:

Sv39x4 host-physical address (64 bits). From left to right, Unused: bits 63–56, PPN[2]: bits 55–30, PPN[1]: bits 29–21, PPN[0]: bits 20–12, Page offset: bits 11–0.

NB:

  1. PPN means Physical Page Number. The PPN fields collectively identify the physical page frame, while the page offset identifies a byte within that page.
  2. PPN[2] (bits 55:30) contains 26 bits; PPN[1] (bits 29:21) and PPN[0] (bits 20:12) contain 9 bits each.
  3. Together, the PPN fields contain 44 bits. With the 12-bit page offset, they form a 56-bit host-physical address.

We now define 48-bit compressed address formats, and 32-bit compressed address formats.

3.2.1 Compressed 48-Bit Address Format

From the original Sv39x4 host-physical address, retain only the PPN[2|1|0] portions, shift them to the lowest bits. Use the top 48th bit to denote whether the memory access was a read or write.

Compressed PPN[2:0] (48 bits). From left to right, R/W: bit 47, Unused: bits 46–44, PPN[2]: bits 43–32, PPN[2]: bits 31–18, PPN[1]: bits 17–16, PPN[1]: bits 15–9, PPN[0]: bits 8–0.

3.2.2 Compressed 32-Bit Address Format

From the original Sv39x4 host-physical address, retain only the PPN[2] portion, shifted to the lowest bits. Use the top 32th bit to denote whether the memory access was a read or write.

Compressed PPN[2] (32 bits). From left to right, R/W: bit 31, Unused: bits 30–26, PPN[2]: bits 25–16, PPN[2]: bits 15–0.

3.3 Guesstimating High-Fidelity Reconstructions of Low-Fidelity Spans

The key idea. Given a high-fidelity burst, and a low-fidelity span following it, we can "guesstimate" what a high-fidelity reconstruction of the low-fidelity span might look like. Specifically:

  1. Compute the 50th percentile 48-bit address (from low to high) of the high-fidelity burst. Call a "base address" a_b. Luckily enough, we don't need to hold the entire burst in memory: good enough streaming median (approximation) computation algorithms exist.
  2. Encode the high-fidelity with, with samples i = 1, ... , s_h as offsets off the base 48-bit address \{o_i + a_b\}_i. Retain the read-write indicator bits of the original ample.
  3. Then, take a low-fidelity address sample (recall -- 32-bits) as our new 48-bit base address a^{\prime}_b by filling in the lowest bits with 0s. Discard the read/write bit.
  4. The resulting high-fidelity reconstruction is given by adding these offsets (and read-write indicator bits) to the base address \{o_i + a^\prime_b\}_i.
    1. Of course, a low-fidelitysample may not expand to exactly one high-fidelity 48-bit burst. Repeat or truncate as needed.