cache_miss_pos_rmf.h File Reference

Position-resolved mean-field miss rates for FIFO(m) and strict FIFO(m). More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <numeric>
#include <string>
#include <vector>
#include "line/api/cache/cache_miss_rmf.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
#include "line/util/ode.h"

Include dependency graph for cache_miss_pos_rmf.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Typedefs
template<class T>
using	line::cache::CacheMissPosRmfResult = CacheMissRmfResult<T>
	Return value of the position-resolved routines, as CacheMissRmfResult.

Functions
template<class T>
CacheMissPosRmfResult< T >	line::cache::cache_miss_fifo_rmf (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	Port of cache_miss_fifo_rmf.m: the FIFO(m) position-resolved mean field.
template<class T>
CacheMissPosRmfResult< T >	line::cache::cache_miss_fifo_rmf_transient (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const T &t0, const T &t1, const std::vector< T > &x0init, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	cache_miss_fifo_rmf with the optional TSPAN/X0INIT transient.
template<class T>
CacheMissPosRmfResult< T >	line::cache::cache_miss_sfifo_rmf (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	Port of cache_miss_sfifo_rmf.m: the strict FIFO(m) position-resolved mean field.
template<class T>
CacheMissPosRmfResult< T >	line::cache::cache_miss_sfifo_rmf_transient (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const T &t0, const T &t1, const std::vector< T > &x0init, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	cache_miss_sfifo_rmf with the optional TSPAN/X0INIT transient.

Detailed Description

Position-resolved mean-field miss rates for FIFO(m) and strict FIFO(m).

Templated port of matlab/src/api/cache/cache_miss_fifo_rmf.m, cache_miss_sfifo_rmf.m and the drift they share, cache_pos_drift_graph.m.

WHY THESE EXIST AT ALL, GIVEN cache_miss_rmf. Gast and Van Houdt (SIGMETRICS 2015, Thm 1) prove pi_FIFO(m) = pi_RAND(m) EXACTLY, so on the linear access graph the FIFO STEADY STATE is served from the cheaper refined mean field of cache_miss_rmf and this file is not reached. Two things break that equality:

THE TRANSIENT. FIFO evicts the deterministic tail – residence is exactly m insertions – while RANDOM evicts a uniformly drawn victim, so residence is geometric. H(inf) agrees; H(t) from a cold cache does not, and a trajectory read off the RANDOM drift would ramp at the wrong rate.

A NON-LINEAR ACCESS GRAPH. The equality is proved for the linear chain. Once admission or promotion is item-dependent, the per-item per-list occupancy that RANDOM(m) tracks no longer determines the dynamics, and FIFO needs its own position-resolved state.

Strict FIFO(m) is a THIRD policy, not a spelling of FIFO(m). Gast and Van Houdt show it differs from RANDOM(m) and give it no mean-field model. The difference is the within-list age ordering: on a hit at position j of list i < h the demoted tail of list i+1 is reinserted at position 1 of list i and positions 1..j-1 shift back (strict), whereas FIFO(m) drops it into the VACATED position j with no shift. That single choice is the reinsert parameter of the shared drift, and it is why strict FIFO(m) is never served from cache_miss_rmf even on the linear chain – it degenerates to FIFO(m) only when m_1 = ... = m_{h-1} = 1, where there is no within-list order to disagree about.

THE STATE. x[k,i,j] = P(item k occupies position j of list i), over the sum(m) in-cache slots only; the out-of-cache mass is the complement 1 - sum_{i,j} x[k,i,j], which is what pos_out returns and what the miss probability is read from. That complement is CLIPPED to [0,1] rather than asserted, exactly as the reference does: the mean-field trajectory can leave the simplex by an integration tolerance without the fixed point being wrong.

THE INITIAL CONDITION DIFFERS BY PATH, and deliberately. The linear drift starts POPULARITY-ORDERED (the S most requested items pre-loaded, one per slot), which is near its own fixed point and integrates quickly. The general graph drift starts COLD (an empty cache), because a graph may make some items non-admissible and a pre-loaded non-admissible item has no outflow term that can drain it – it would sit in the cache forever and report a hit rate the policy never produces.

Definition in file cache_miss_pos_rmf.h.