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

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.

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. 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:

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. 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, 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, 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 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 demonstrates attaching OBL with custom parameters:

#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:

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:

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:

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) exposing create_myAlgo_prefetcher(const char *init_params, uint64_t cache_size)
2. Implement the creator in myAlgo.c to allocate private state, parse parameters, and assign callbacks
3. Add the dispatch case in libCacheSim/include/libCacheSim/prefetchAlgo.h inside create_prefetcher()
4. Write unit tests in test/test_prefetchAlgo.c following the existing validation patterns

Summary

• The prefetcher_t structure in 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, Mithril.c, and 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 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 to inspect the prefetch table contents. The test suite in test/test_prefetchAlgo.c provides reference implementations that validate correct prefetch behavior against known access patterns.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}