solver_mva_cache.h File Reference

The non-reentrant cache analyzer: a Source-Cache-Sink model. More...

#include <cmath>
#include <vector>
#include "line/api/cache/cache_mva.h"
#include "line/api/cache/cache_prob_fpi.h"
#include "line/api/cache/cache_ttl_hlru.h"
#include "line/api/cache/cache_ttl_lrua.h"
#include "line/api/da/da_cache_isolate.h"
#include "line/lang/qn/network_struct.h"
#include "line/solvers/mva/mva_types.h"

Include dependency graph for solver_mva_cache.h:

Go to the source code of this file.

Classes
struct	line::mva::CacheResult< T >
	What the cache analyzer reports beyond the [Q,U,R,T] block. More...

Namespaces
namespace	line
namespace	line::mva

Functions
template<class T>
CacheResult< T >	line::mva::solver_mva_cache_analyzer (const qn::NetworkStruct< T > &L, const MvaOptions &opt)
	Port of solver_mva_cache_analyzer.m for a Source-Cache-Sink model.

Detailed Description

The non-reentrant cache analyzer: a Source-Cache-Sink model.

Templated port of matlab/src/solvers/MVA/solver_mva_cache_analyzer.m.

A read of class r reaches the cache at the Source rate weighted by the class read distribution, and completes as a HIT (switching to hitclass(r)) or a MISS (switching to missclass(r)). The analyzer computes the per-item occupancy of the cache and from it the miss rate of each read class, then splits the Source throughput between the hit and the miss class.

The item occupancy comes from the cache algorithm family, keyed on the replacement policy:

RR, FIFO exact -> cache_mva (the exact product-form recursion) default -> cache_prob_fpi (the fixed-point approximation) LRU -> cache_ttl_lrua (the LRU-A characteristic-time approximation) HLRU -> cache_ttl_hlru (the h-LRU / LRU(m) characteristic time)

The RR/FIFO inputs – the access factors gamma – are built by da_cache_isolate, which spreads each class rate over the items through its read distribution and attaches the list-to-list access-cost matrices; qn::CacheParam carries pread and accost in exactly the shape it consumes.

THE TTL FAMILY IS SINGLE-STREAM. cache_ttl_lrua and cache_ttl_hlru read only the FIRST user stream in the reference (lambda(1,i,j), R{1,i}), so the port passes the first reading class's per-item rates and access graphs, which is what those two consume. A model with more than one reading class is therefore an LRU/h-LRU approximation over its first read law, matching the reference exactly rather than silently aggregating.

WHAT IS REFUSED BY NAME. The exact solution of any policy other than RR/FIFO, SFIFO, CLIMB and QLRU, and the marked-MAP LRU sub-branch, follow the reference's own line_errors. The marked-MAP branch needs an MMAP Source with per-item marks, which the builder cannot yet construct.

Arithmetic: RR/FIFO exact (cache_mva) is field arithmetic and runs at any T; the FPI approximation evaluates a fixed point on a tolerance and needs a transcendental T, so it refuses under Rational.

Definition in file solver_mva_cache.h.