ldes_cache.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_SOLVERS_LDES_LDES_CACHE_H
#define LINE_SOLVERS_LDES_LDES_CACHE_H
 
/**
 * @file
 * @ingroup line_solvers
 * The Cache node of the native LDES engine.
 *
 * A cache holds items in ORDERED LISTS, not one flat set. List l has its own
 * capacity, an item hit in list l may be PROMOTED to a higher list, and the
 * displaced occupant is DEMOTED back down. That structure is what distinguishes
 * the segmented policies (HLRU, CLIMB, SFIFO) from the flat ones (LRU, FIFO,
 * RR, QLRU), which are the same machinery with a single list.
 *
 * THE HIT IS AN EXACT SAMPLE-PATH EVENT, not a probability. The engine holds
 * the real list contents and looks the item up, so a hit is a hit; the
 * analytical solvers estimate a hit RATE instead. That is the whole reason a
 * simulator is asked about a cache at all.
 *
 * A COST CAP IS SERVED, NOT REFUSED. When an insertion or a promotion would
 * push a list past its storage-cost cap, the request is SERVED and the cache
 * state is left unchanged -- the "serve but do not swap" rule of RR-C(m)
 * (Casale-Gast, IEEE/ACM ToN 29(2), 2021, Sec. IX). Refusing the request
 * instead would drop a job the model never loses.
 */
 
#include <algorithm>
#include <cstddef>
#include <list>
#include <string>
#include <vector>
 
#include "line/lang/lang_types.h"
 
namespace line {
namespace ldes {
namespace engine {
 
/** Live state of one Cache node. */
struct CacheState {
    std::size_t node = 0;
    std::size_t nitems = 0;
    lang::ReplacementStrategy policy = lang::ReplacementStrategy::LRU;
    double qlru = 1.0;  ///< q-LRU admission probability on a miss
    std::vector<std::size_t> capacity;         ///< per list
    std::vector<std::list<std::size_t>> lists; ///< per list, most recent at the front
    std::vector<double> item_size;             ///< empty = unconstrained
    std::vector<double> cost_cap;              ///< empty = unconstrained
    /** Per access class: the item popularity, as a cumulative law. */
    std::vector<std::vector<double>> popularity;
    std::vector<int> hit_class, miss_class;    ///< 0-based destination class, -1 = unset
 
    // ---- statistics --------------------------------------------------------
    std::vector<double> hits, misses;  ///< per access class
 
    // ---- delayed-hit retrieval system --------------------------------------
    /**
     * `Cache.setRetrievalSystem`: a miss FETCHES the item through a sub-network
     * instead of being served at once, and a second request for an item already
     * in flight is parked rather than starting a fetch of its own. It is
     * released when the fetch returns, and counted as a DELAYED HIT: it neither
     * hit nor missed, and folding it into either loses the whole effect the
     * model exists to measure.
     */
    bool has_retrieval = false;
    /** (nitems x nclasses) the per-item retrieval class, 0 = none. 1-based. */
    std::vector<std::vector<std::size_t>> retrieval_class;
    /** Per class: the item it fetches, or -1 when it is not a retrieval class. */
    std::vector<int> retrieval_class_to_item;
    std::vector<char> in_flight;      ///< per item, a fetch is outstanding
    std::vector<double> fetch_start;  ///< per item, when that fetch began
 
    /** A request parked while its item was being fetched. */
    struct HeldRequest {
        std::size_t cls = 0;    ///< the ACCESS class that read the cache
        double hold_time = 0.0; ///< when it was parked
        double t_sys = 0.0;     ///< its system arrival time, for response time
    };
    std::vector<std::vector<HeldRequest>> held;  ///< per item
 
    std::vector<double> delayed;      ///< per access class, delayed-hit count
    double delayed_wait = 0.0;        ///< summed parked time over all releases
    double total_fetch_time = 0.0;    ///< summed fetch duration
    double completed_fetches = 0.0;
 
    /** The item `cls` fetches, or -1. */
    int fetches_item(std::size_t cls) const {
        return (cls < retrieval_class_to_item.size()) ? retrieval_class_to_item[cls] : -1;
    }
    /** The retrieval class of `item` for access class `cls`, or 0. */
    std::size_t retrieval_of(std::size_t item, std::size_t cls) const {
        if (item >= retrieval_class.size() || cls >= retrieval_class[item].size()) return 0;
        return retrieval_class[item][cls];
    }
 
    /** The list holding `item`, or -1. */
    int find(std::size_t item) const {
        for (std::size_t l = 0; l < lists.size(); ++l)
            for (std::size_t v : lists[l])
                if (v == item) return static_cast<int>(l);
        return -1;
    }
 
    double list_cost(std::size_t l) const {
        if (item_size.empty()) return 0.0;
        double c = 0.0;
        for (std::size_t v : lists[l]) c += (v < item_size.size()) ? item_size[v] : 1.0;
        return c;
    }
    double cap_of(std::size_t l) const {
        return (l < cost_cap.size()) ? cost_cap[l] : -1.0;
    }
    bool capped() const { return !item_size.empty() && !cost_cap.empty(); }
    double size_of(std::size_t item) const {
        return (item < item_size.size()) ? item_size[item] : 1.0;
    }
};
 
/** True for the policies that refresh recency on a hit. */
inline bool cache_refreshes(lang::ReplacementStrategy p) {
    return p == lang::ReplacementStrategy::LRU || p == lang::ReplacementStrategy::HLRU ||
           p == lang::ReplacementStrategy::QLRU;
}
 
/**
 * Serve a HIT in list `at`.
 *
 * CLIMB promotes one list per hit; the flat policies keep the item where it is
 * and only refresh its recency. A promotion into a full list swaps: the item
 * goes to the head of the higher list and the displaced occupant returns to the
 * lower one.
 */
inline void cache_hit(CacheState& cs, std::size_t item, std::size_t at, double u_random) {
    const bool climb = (cs.policy == lang::ReplacementStrategy::CLIMB);
    const std::size_t up = (climb && at + 1 < cs.lists.size()) ? at + 1 : at;
    if (up == at) {
        if (cache_refreshes(cs.policy)) {
            cs.lists[at].remove(item);
            cs.lists[at].push_front(item);
        }
        return;
    }
    std::list<std::size_t>& lo = cs.lists[at];
    std::list<std::size_t>& hi = cs.lists[up];
    if (hi.size() < cs.capacity[up]) {
        // Warm-up move: the higher list has room, so nothing is demoted.
        if (cs.capped() && cs.list_cost(up) + cs.size_of(item) > cs.cap_of(up)) return;
        lo.remove(item);
        hi.push_front(item);
        return;
    }
    const std::size_t victim =
        (cs.policy == lang::ReplacementStrategy::RR)
            ? *std::next(hi.begin(), static_cast<std::ptrdiff_t>(
                                         std::min<std::size_t>(hi.size() - 1,
                                                               static_cast<std::size_t>(
                                                                   u_random * hi.size()))))
            : hi.back();
    if (cs.capped()) {
        const double hi_after = cs.list_cost(up) - cs.size_of(victim) + cs.size_of(item);
        const double lo_after = cs.list_cost(at) - cs.size_of(item) + cs.size_of(victim);
        // SERVED, NOT REFUSED: a swap that breaches either cap leaves the cache
        // untouched and the request goes through anyway.
        if (hi_after > cs.cap_of(up) || (cs.cap_of(at) >= 0.0 && lo_after > cs.cap_of(at))) return;
    }
    lo.remove(item);
    hi.remove(victim);
    hi.push_front(item);
    if (cache_refreshes(cs.policy) || cs.policy == lang::ReplacementStrategy::SFIFO)
        lo.push_front(victim);
    else
        lo.push_back(victim);
}
 
/** Serve a MISS: insert into the entry list, evicting if it is full. */
inline void cache_miss(CacheState& cs, std::size_t item, double u_admit, double u_random) {
    if (cs.lists.empty()) return;
    const std::size_t target = 0;  // the entry list
    std::list<std::size_t>& list = cs.lists[target];
    const std::size_t cap = cs.capacity[target];
    // q-LRU admits only a fraction of misses, which is the whole policy.
    if (cs.policy == lang::ReplacementStrategy::QLRU && u_admit > cs.qlru) return;
 
    if (cs.policy == lang::ReplacementStrategy::RR && list.size() >= cap && !list.empty()) {
        const std::size_t pos =
            std::min<std::size_t>(list.size() - 1, static_cast<std::size_t>(u_random * list.size()));
        auto it = std::next(list.begin(), static_cast<std::ptrdiff_t>(pos));
        if (cs.capped() &&
            cs.list_cost(target) - cs.size_of(*it) + cs.size_of(item) > cs.cap_of(target))
            return;
        *it = item;
        return;
    }
    if (cs.capped()) {
        double resulting = cs.list_cost(target) + cs.size_of(item);
        if (list.size() + 1 > cap && !list.empty()) resulting -= cs.size_of(list.back());
        if (resulting > cs.cap_of(target)) return;
    }
    list.push_front(item);
    if (list.size() > cap) list.pop_back();
}
 
}  // namespace engine
}  // namespace ldes
}  // namespace line
 
#endif  // LINE_SOLVERS_LDES_LDES_CACHE_H