# How to Build a Multi-Layer Cache Hierarchy Simulator with libCacheSim

> Learn to build a multi-layer cache hierarchy simulator with libCacheSim. Explore parallel trace processing and YAML configuration for efficient cache simulation. GitHub repo available.

- Repository: [Juncheng Yang/libcachesim](https://github.com/1a1a11a/libcachesim)
- Tags: how-to-guide
- Published: 2026-02-23

---

**libCacheSim provides a ready-to-run cache hierarchy example that demonstrates how to simulate multiple L1 caches feeding their miss streams into a shared L2 cache using YAML configuration, parallel trace processing, and chronological merge utilities.**

Building a multi-layer cache hierarchy simulator with libCacheSim enables you to model complex storage systems where independent upper-level caches converge into shared lower-level pools. The `1a1a11a/libcachesim` repository includes a complete reference implementation in `example/cacheHierarchy/` that handles configuration parsing, parallel L1 simulation, trace merging, and miss-ratio curve generation for arbitrary depth hierarchies.

## Understanding the Cache Hierarchy Architecture

The libCacheSim hierarchy example consists of four modular components that separate configuration, simulation, trace manipulation, and orchestration concerns.

### Configuration Loader

The **`Myconfig`** class defined in [`example/cacheHierarchy/myconfig.hpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/myconfig.hpp) parses a YAML configuration file that specifies the number of L1 caches, their sizes, input trace paths, and the L2 cache sizes to evaluate. It exposes structured vectors such as `l1_sizes`, `l1_trace_path`, and `l2_sizes` that downstream components consume.

### Trace Utilities

The **`TraceUtils::merge_l1_trace`** function implemented in [`example/cacheHierarchy/utils.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/utils.cpp) handles the critical step of merging multiple binary miss trace files into a single chronologically ordered stream. It uses a min-heap (priority queue) to perform an O(N log K) merge where *K* is the number of L1 caches and *N* is the total number of miss requests.

### Simulator API

The **`Simulator`** class in [`example/cacheHierarchy/simulator.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/simulator.cpp) provides two primary methods:
- **`gen_miss_trace`** – Instantiates a cache instance (e.g., LRU), replays the supplied trace, and writes every cache miss as a binary record (timestamp, object ID, size) to a specified path.
- **`output_mrc`** – Replays a merged trace across multiple cache sizes to compute and output the miss-ratio curve (MRC).

### Orchestrator

The **[`main.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/main.cpp)** file in the same directory coordinates the workflow: it creates one thread per L1 cache to run `gen_miss_trace` in parallel, invokes `merge_l1_trace` after all threads complete, and finally calls `output_mrc` for the L2 evaluation.

## Step-by-Step Workflow to Build Your Simulator

Follow this four-stage pipeline to construct a functional two-level hierarchy.

### Step 1: Configure Your Hierarchy with YAML

Create a configuration file that defines your L1 instances and L2 evaluation parameters. The `Myconfig` parser expects keys such as `n_l1`, `l1_sizes`, `l1_trace_path`, and `l2_sizes`.

```yaml
L1:
  size: 1MB
  path:
    - ../../../data/traceA.bin
    - ../../../data/traceB.bin
    - ../../../data/traceC.bin

L2:
  size:
    - 4MB
    - 8MB
    - 16MB

output: result

```

This configuration instantiates three 1 MiB L1 caches that feed a shared L2 evaluated at 4 MiB, 8 MiB, and 16 MiB.

### Step 2: Generate L1 Miss Traces in Parallel

Instantiate the `Simulator` class and launch one thread per L1 cache. Each thread calls `gen_miss_trace` to run the specified eviction algorithm (e.g., **LRU** implemented in [`libCacheSim/cache/eviction/LRU.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/eviction/LRU.c)) against its assigned trace.

```cpp
std::vector<std::thread> workers;
for (int i = 0; i < cfg.n_l1; ++i) {
    workers.emplace_back(
        Simulator::gen_miss_trace,
        "LRU",                     // eviction algorithm name
        cfg.l1_sizes.at(i),
        cfg.l1_trace_path.at(i),
        cfg.l1_miss_output_path.at(i));
}
for (auto &t : workers) t.join();

```

Each L1 simulation outputs a binary miss trace containing timestamp, object ID, and size records for every cache miss.

### Step 3: Merge Miss Streams for L2 Input

After all L1 threads complete, use `TraceUtils::merge_l1_trace` to combine the individual miss files into a single chronologically ordered trace suitable for L2 simulation.

```cpp
uint64_t n_req = TraceUtils::merge_l1_trace(
                         cfg.l1_miss_output_path,
                         cfg.l2_trace_path);
std::cout << "Merged " << n_req << " requests for L2\n";

```

The merge utility uses a min-heap to maintain O(N log K) complexity, ensuring accurate temporal ordering even when L1 traces have different request rates.

### Step 4: Compute L2 Miss-Ratio Curves

Finally, invoke `Simulator::output_mrc` to evaluate the merged L2 trace across the configured cache sizes. This function leverages the core simulation engine in [`libCacheSim/profiler/simulator.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/profiler/simulator.c) to compute miss ratios efficiently.

```cpp
Simulator::output_mrc(
    cfg.l2_algo,
    cfg.l2_sizes,
    cfg.l2_trace_path,
    cfg.l2_mrc_output_path);

```

The output file contains the miss-ratio curve data that you can plot to analyze L2 behavior under varying capacity constraints.

## Extending to Three-Level Hierarchies (L1/L2/L3)

The modular design supports deeper hierarchies without structural changes. To add an **L3 cache**:

1. **Add L2 miss-output configuration** – Extend the YAML parser in [`myconfig.hpp`](https://github.com/1a1a11a/libcachesim/blob/main/myconfig.hpp) to accept `l2_miss_output_path` vectors.
2. **Generate L2 miss traces** – After the L2 MRC stage, call `Simulator::gen_miss_trace` for each L2 instance, writing to the new miss-output paths.
3. **Merge L2 streams** – Reuse `TraceUtils::merge_l1_trace` (or rename it generically) to merge the L2 miss files into a single L3 input trace.
4. **Evaluate L3** – Call `Simulator::output_mrc` with the L3 cache sizes and the merged L2 miss trace.

Because `libCacheSim/cache/eviction/*.c` already provides the eviction logic and [`libCacheSim/profiler/simulator.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/profiler/simulator.c) handles the simulation engine, you only need to orchestrate the data flow between levels.

## Key Source Files and APIs

| File | Purpose |
|------|---------|
| [`example/cacheHierarchy/main.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/main.cpp) | Orchestrates parallel L1 simulation, trace merging, and L2 MRC generation. |
| [`example/cacheHierarchy/myconfig.hpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/myconfig.hpp) | YAML configuration parser (`Myconfig` class) defining hierarchy parameters. |
| [`example/cacheHierarchy/utils.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/utils.cpp) | Implements `TraceUtils::merge_l1_trace` for chronological merging of binary miss streams. |
| [`example/cacheHierarchy/simulator.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/simulator.cpp) | Provides `Simulator::gen_miss_trace` and `Simulator::output_mrc` wrappers around the core engine. |
| [`libCacheSim/cache/eviction/LRU.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/eviction/LRU.c) | Core eviction algorithm implementation used by the simulator. |
| [`libCacheSim/profiler/simulator.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/profiler/simulator.c) | Core simulation engine that executes traces and collects statistics. |

## Summary

- **libCacheSim** provides a complete reference implementation for multi-layer cache hierarchy simulation in `example/cacheHierarchy/`.
- The architecture separates concerns into **configuration** (`Myconfig`), **simulation** (`Simulator`), **trace manipulation** (`TraceUtils`), and **orchestration** ([`main.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/main.cpp)).
- The workflow follows four stages: configure via YAML, generate L1 miss traces in parallel, merge streams chronologically, and compute L2 miss-ratio curves.
- You can extend the hierarchy to L3 or deeper by adding additional merge stages and reusing the same `Simulator` API methods.
- All eviction algorithms (LRU, LFU, etc.) reside in `libCacheSim/cache/eviction/` and are reusable across any hierarchy level.

## Frequently Asked Questions

### What trace format does libCacheSim use for miss streams?

libCacheSim uses a compact binary format for miss traces where each record contains a timestamp, object ID, and object size. The `TraceUtils::merge_l1_trace` function in [`example/cacheHierarchy/utils.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/example/cacheHierarchy/utils.cpp) expects this format when merging multiple L1 miss streams into a single L2 input trace.

### Can I use different eviction algorithms for each cache level?

Yes. The `Simulator::gen_miss_trace` and `Simulator::output_mrc` methods accept an algorithm name string (e.g., "LRU", "LFU", "ARC") as their first parameter. You can specify different algorithms for L1 and L2 by passing distinct strings to each simulation stage, leveraging the implementations found in `libCacheSim/cache/eviction/`.

### How does the merge utility handle chronological ordering?

The `TraceUtils::merge_l1_trace` function uses a min-heap (priority queue) to merge K sorted binary trace files in O(N log K) time, where N is the total number of requests. This ensures the resulting L2 trace maintains strict chronological order based on timestamps, even when individual L1 traces have different request rates.

### Is there a Python API for building multi-layer hierarchies?

While the primary hierarchy example is implemented in C++, libCacheSim provides Python bindings that expose the core simulation engine. You can construct equivalent multi-layer hierarchies in Python by using trace reader classes, running `process_trace` for L1 caches, merging miss outputs with trace utilities, and simulating L2 caches, though the exact helper method names may differ from the C++ implementation.