# How to Implement Prefetching Algorithms (OBL, Mithril, PG) in libCacheSim

> Implement OBL, Mithril, and PG prefetching algorithms in libCacheSim. Learn how to attach prefetcher objects and invoke callbacks for predictive fetches in your cache simulation.

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

---

**To implement prefetching in libCacheSim, attach a `prefetcher_t` object to your cache via `create_prefetcher()`, which dispatches to algorithm-specific creators like `create_Mithril_prefetcher()` or `create_OBL_prefetcher()`, and the framework automatically invokes callbacks (`prefetch`, `handle_find`, `handle_evict`) during simulation to generate predictive fetches.**

libCacheSim treats prefetching as a modular plugin architecture that integrates with the core cache simulation engine. This guide explains how to implement and configure the three built-in prefetchers—**OBL**, **Mithril**, and **PG**—using the generic `prefetcher_t` interface defined in [`libCacheSim/include/libCacheSim/prefetchAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/include/libCacheSim/prefetchAlgo.h).

## Architecture of the Prefetching Subsystem

### The Core Interface (prefetcher_t)

The prefetching system revolves around the `prefetcher_t` structure defined in [`libCacheSim/include/libCacheSim/prefetchAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/include/libCacheSim/prefetchAlgo.h). This struct contains six function pointer callbacks that define the prefetching lifecycle:

- `prefetch`: Generates the list of object IDs to fetch
- `handle_find`: Records metadata on every cache lookup
- `handle_insert`: Reacts to new insertions into the cache
- `handle_evict`: Manages eviction of prefetched objects (often giving them second-chance priority)
- `free`: Releases algorithm-specific memory
- `clone`: Duplicates the prefetcher state

Each algorithm stores private state in an opaque **params** field (e.g., `obl_params_t`, `mithril_params_t`, `pg_params_t`). The `cache_t` structure maintains a pointer to the active prefetcher via `struct prefetcher *prefetcher`, allowing the simulation engine to invoke these callbacks during request processing.

### Factory Dispatch Pattern

Rather than calling algorithm-specific functions directly, use the generic factory `create_prefetcher()` which dispatches to the appropriate creator based on the algorithm name string:

```c
if (strcasecmp(prefetching_algo, "Mithril") == 0) {
    prefetcher = create_Mithril_prefetcher(prefetching_params, cache_size);
} else if (strcasecmp(prefetching_algo, "OBL") == 0) {
    prefetcher = create_OBL_prefetcher(prefetching_params, cache_size);
} else if (strcasecmp(prefetching_algo, "PG") == 0) {
    prefetcher = create_PG_prefetcher(prefetching_params, cache_size);
}

```

This dispatch logic resides in [`libCacheSim/include/libCacheSim/prefetchAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/include/libCacheSim/prefetchAlgo.h). Each creator allocates private state, parses initialization strings via `*_parse_init_params()`, and populates the callback pointers.

## Built-In Prefetching Algorithms

### OBL (Object-Based Look-ahead)

Implemented in [`libCacheSim/cache/prefetch/OBL.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/prefetch/OBL.c), OBL detects strictly sequential access patterns by maintaining a circular buffer of the last *k* object IDs. When OBL observes a consecutive run of *k* accesses (controlled by `sequential-confidence-k`), it prefetches the next sequential block (`obj_id + 1`).

Key parameters include:
- `sequential-confidence-k`: Number of consecutive accesses required to trigger prefetching
- `block-size`: Size of the prefetching unit in bytes

### Mithril

Located in [`libCacheSim/cache/prefetch/Mithril.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/prefetch/Mithril.c), Mithril implements association rule mining to predict non-sequential access patterns. It maintains three core structures:
1. A **recording table** of timestamped accesses
2. A **mining table** for discovering frequent sequential and associative patterns
3. A **prefetch table** mapping source blocks to likely successor blocks

Mithril supports optional **AMP** (Adaptive Multi-stream Prefetching) when `sequential-type=2` is configured. Critical parameters include `lookahead-range`, `max-support`, `min-support`, and `AMP-pthreshold`.

### Probabilistic Graph (PG)

The PG algorithm in [`libCacheSim/cache/prefetch/PG.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/prefetch/PG.c) constructs a directed graph where nodes represent blocks and edges represent observed transitions within a sliding window. Edge weights indicate transition probability. During prefetching, PG extracts all successor nodes whose probability exceeds `prefetch-threshold`.

Configuration options include:
- `lookahead-range`: Size of the observation window for graph construction
- `prefetch-threshold`: Probability cutoff (e.g., 0.02 for 2% threshold)
- `block-size`: Granularity of the address space

## Implementing Prefetching in Practice

### Attaching a Prefetcher to a Cache

First initialize a core cache (such as LRU), then attach the prefetcher before running the simulation. This pattern from [`test/common.h`](https://github.com/1a1a11a/libcachesim/blob/main/test/common.h) demonstrates attaching OBL with custom parameters:

```c
#include "libCacheSim.h"
#include "libCacheSim/prefetchAlgo.h"

/* 1. Core cache parameters */
common_cache_params_t cc = {
    .cache_size = 1024 * MiB,   // 1 GiB cache
    .hashpower = 20,
    .default_ttl = 300 * 86400
};

/* 2. Initialize the LRU core */
cache_t *cache = LRU_init(cc, NULL);

/* 3. Attach a prefetcher – OBL with block size 4 KB and k=6 */
cache->prefetcher = create_prefetcher(
        "OBL",
        "block-size=4096,sequential-confidence-k=6",
        cc.cache_size);

/* 4. Run a trace */
reader_t *r = setup_oracleGeneralBin_reader();   // from test/common.h
cache_stat_t *stats = simulate_at_multi_sizes_with_step_size(
        r, cache, 128 * MiB, NULL, 0, 0, _n_cores(), false);

/* 5. Clean up */
cache->cache_free(cache);
close_reader(r);

```

### Configuring Algorithm Parameters

All three algorithms accept comma-separated configuration strings parsed by their respective `*_parse_init_params()` functions. For example, to configure PG with a 1% probability threshold:

```c
cache->prefetcher = create_prefetcher(
        "PG",
        "lookahead-range=15,block-size=1,prefetch-threshold=0.01",
        cc.cache_size);

```

For Mithril with AMP-enabled sequential prefetching:

```c
cache->prefetcher = create_prefetcher(
        "Mithril",
        "lookahead-range=30,max-support=10,min-support=2,confidence=2,"
        "pf-list-size=4,block-size=1,sequential-type=2,AMP-pthreshold=5",
        cc.cache_size);

```

### Running Simulations

Once attached, the prefetcher operates automatically during simulation. The function `simulate_at_multi_sizes_with_step_size()` invokes `cache->handle_find()` and `cache->prefetch()` on every request. You can also trigger prefetching manually in custom request loops:

```c
request_t *req = next_request(reader);
cache->handle_find(cache, req, cache->find(cache, req, false));   // update state
cache->prefetch(cache, req);                                    // issue prefetch

```

## Extending libCacheSim with Custom Prefetchers

To add a fourth prefetching algorithm, implement the six callbacks defined in `prefetcher_t` and provide a creator function following the existing pattern:

1. Define a header (e.g., [`myAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/myAlgo.h)) exposing `create_myAlgo_prefetcher(const char *init_params, uint64_t cache_size)`
2. Implement the creator in [`myAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/myAlgo.c) to allocate private state, parse parameters, and assign callbacks
3. Add the dispatch case in [`libCacheSim/include/libCacheSim/prefetchAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/include/libCacheSim/prefetchAlgo.h) inside `create_prefetcher()`
4. Write unit tests in [`test/test_prefetchAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_prefetchAlgo.c) following the existing validation patterns

## Summary

- The **`prefetcher_t`** structure in [`libCacheSim/include/libCacheSim/prefetchAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/include/libCacheSim/prefetchAlgo.h) defines the standard contract via six function pointer callbacks
- Use **`create_prefetcher()`** to instantiate OBL, Mithril, or PG, passing algorithm-specific parameters as comma-separated strings
- The simulation engine automatically invokes `handle_find` and `prefetch` on every request, while `handle_evict` provides second-chance protection for prefetched blocks
- Algorithm implementations reside in [`libCacheSim/cache/prefetch/OBL.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/prefetch/OBL.c), [`Mithril.c`](https://github.com/1a1a11a/libcachesim/blob/main/Mithril.c), and [`PG.c`](https://github.com/1a1a11a/libcachesim/blob/main/PG.c), each maintaining private state structures parsed from configuration strings

## Frequently Asked Questions

### How do I choose between OBL, Mithril, and PG for my workload?

**OBL** excels for strictly sequential workloads like video streaming or log processing. **Mithril** is optimal for workloads with complex associative patterns, such as database queries or graph traversals. **PG** suits workloads with probabilistic transition patterns where historical co-occurrence indicates future access likelihood. Test all three using the framework in [`test/test_prefetchAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_prefetchAlgo.c) to compare hit rate improvements.

### Can I use multiple prefetchers simultaneously on one cache?

No, the `cache_t` structure contains a single `prefetcher` pointer. To combine strategies, you must implement a composite prefetcher that internally instantiates multiple algorithms and merges their prefetch lists, or sequentially chain prefetchers by wrapping one within another's `prefetch` callback.

### What is the performance overhead of enabling prefetching?

Each request triggers `handle_find` and potentially `prefetch`, so computational complexity matters. OBL performs O(1) buffer operations, Mithril incurs higher overhead due to hash table updates and pattern mining, and PG requires graph traversal. The overhead is typically negligible for trace-driven simulation but becomes significant when simulating billions of requests with complex algorithms like Mithril.

### How do I verify that my prefetcher configuration is working correctly?

Check the `hit_on_prefetch` statistics in the `cache_stat_t` structure returned by the simulator. For Mithril, enable debug logging in [`libCacheSim/cache/prefetch/Mithril.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/prefetch/Mithril.c) to inspect the prefetch table contents. The test suite in [`test/test_prefetchAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_prefetchAlgo.c) provides reference implementations that validate correct prefetch behavior against known access patterns.