cache_miss_rmf.h File Reference

Refined mean field (RMF) miss rates of a multi-list RANDOM(m) cache. More...

#include <cstddef>
#include <limits>
#include <type_traits>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/eig.h"
#include "line/util/linalg.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"
#include "line/util/lsoda.h"
#include "line/util/ode.h"

Include dependency graph for cache_miss_rmf.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheMissRmfResult< T >
	Return value of cache_miss_rmf, mirroring [M,MU,MI,pi0,tout,pi0_t,MU_t,xtraj]. More...
struct	line::cache::CacheRmfExpansionTransient< T >
	Result of cache_miss_rmf_expansion_transient. More...

Namespaces
namespace	line
namespace	line::cache

Functions
std::size_t	line::cache::cache_miss_rmf_index (std::size_t i, std::size_t k, std::size_t n_items)
	Flat index of (item i, list k), k = 0 meaning "not cached" (rmf_index.m).
template<class T>
CacheMissRmfResult< T >	line::cache::cache_miss_rmf (const std::vector< T > &gamma, const std::vector< int > &m_in, const Matrix< T > &lambda, const T &tmax, const std::vector< std::vector< Matrix< T > > > &accost)
	Refined mean-field miss rates of a RANDOM(m) multi-list cache.
template<class T>
CacheMissRmfResult< T >	line::cache::cache_miss_rmf (const std::vector< T > &gamma, const std::vector< int > &m_in, const Matrix< T > &lambda, const T &tmax)
	cache_miss_rmf on the linear chain, i.e.
template<class T>
CacheMissRmfResult< T >	line::cache::cache_miss_rmf (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda)
	cache_miss_rmf with the reference horizon tmax = 1e4.
template<class T>
CacheMissRmfResult< T >	line::cache::cache_miss_rmf_transient (const std::vector< int > &m_in, const Matrix< T > &lambda, const T &t0, const T &t1, const std::vector< T > &x0init)
	Transient mean-field trajectory over [t0,t1] from a given initial occupancy, the optional TSPAN/X0INIT path of cache_miss_rmf.m.
template<class T>
CacheRmfExpansionTransient< T >	line::cache::cache_miss_rmf_expansion_transient (const std::vector< int > &m_in, const Matrix< T > &lambda, const T &time, std::size_t n_points, int order)
	Refined mean-field TRANSIENT, CacheRMF.meanFieldExpansionTransient.

Detailed Description

Refined mean field (RMF) miss rates of a multi-list RANDOM(m) cache.

Templated port of matlab/src/api/cache/cache_miss_rmf.m, including its nested rmf_drift, rmf_jacobian, rmf_hessian, rmf_noise_matrix, rmf_fixed_point, rmf_dimension_reduction and rmf_expansion_steady_state.

The model is a density dependent population process (DDPP) whose state x(i,k) is the probability that item i sits in list k, k = 0 meaning "not cached". A request for item i in list k promotes it to list k+1 and demotes a uniformly chosen occupant of list k+1, so the drift is

flow(i,k) = p(i) x(i,k) - hit(k) x(i,k+1) / m(k+1), dx(i,k)/dt -= flow(i,k), dx(i,k+1)/dt += flow(i,k), hit(k) = sum_j p(j) x(j,k),

for k = 0..h-1. The mean-field fixed point pi is the t -> infinity limit of that drift, and Gast's refinement adds the 1/N correction

E[X] = pi + V/N + O(1/N^2), V = -(F')^-1 (1/2) sum_{b,c} F''_{bc} W_bc,

with W the solution of the Lyapunov equation F' W + W F'^T + Q = 0 and Q the noise intensity of the DDPP. Reference: N. Gast, "Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate", POMACS 2017.

WHAT UNBLOCKED THIS. The fixed point is reached by integrating the drift to t = 1e4, which MATLAB does with ode15s. The drift is stiff: the per-item request rates p(i) of a Zipf-like popularity profile span several orders of magnitude, so the fast items equilibrate in O(1/p_max) while the slow ones need O(1/p_min), and an explicit integrator would be pinned to the fast scale for the whole horizon. The port now has line/util/ode.h, an adaptive Rosenbrock-4 with an embedded lower-order estimate, and this file uses it. The Jacobian is supplied analytically (rmf_jacobian is needed for the refinement anyway), so the integrator never forms a numeric one here.

DIFFERENCES FROM THE REFERENCE. Three, all in the dimension reduction, and all forced by the same fact: the Jacobian of this drift is singular by construction (each item's occupancies are conserved, so the item-indicator vectors are exact left null vectors) and the refinement divides by its reduced version.

1. The fixed point is polished. The reference stops when ode15s's LOCAL error estimate meets AbsTol 1e-10, which leaves a residual drift of that order; this port runs a second integration pass from there at the tightest tolerances the arithmetic supports, which costs a handful of steps and leaves a residual of 1e-15. The miss rates move by about 1e-9, the rank decision below moves from meaningless to unambiguous.
2. The rank threshold is 1e-8 relative, not MATLAB's rank() threshold of max(size)*eps*sigma_1. A fixed point located to 1e-10 lifts one of the exact null directions to a singular value of about 1e-10, which MATLAB's threshold counts as nonzero; the reduced Jacobian then inherits it and the 1/N correction comes out orders of magnitude too large. The nonzero singular values here are O(0.1) and the null ones below 1e-13, so any threshold in that gap gives the same rank.
3. The null-space basis comes from LAPACK's SVD at T = double (the same quantity MATLAB reads out of svd(Fp)) and from a pivoted elimination plus Gram-Schmidt at any other T. Only the SUBSPACE affects the result: writing C = [C1; C2], the block C1 Fp D1 that the reduction keeps depends on C2 only through ker(C2), and the expansion V = D1 V_r likewise, so any basis of the same subspace gives the same V.

MEASURED AGREEMENT (MATLAB R2025a, T = double), global miss rate M:

lambda = [0.5 0.3 0.15 0.05; 0.1 0.2 0.3 0.4] (2 users, 4 items) m = [2] MATLAB 0.992377021789716 port 0.992377021789764 5e-14 m = [1 2] MATLAB 0.490863272756674 port 0.490863283075726 2.1e-8 lambda = [49 49 49 49 7 1 1]/205 (1 user, 7 items) m = [1 1 3] MATLAB 0.024017720168154 port 0.024017720912976 3.1e-8 m = [3] MATLAB 0.348362022568998 port 0.345660745093153 7.8e-3

The last row is not a discrepancy in the arithmetic but in which answer is returned: on that case the reference's refinement produces non-finite entries and cache_miss_rmf.m silently keeps the plain mean-field fixed point (its value agrees with the port's unrefined value to 1e-9), whereas the port's rank decision leaves the reduced Jacobian non-singular and the 1/N correction is applied, moving the miss rate by 0.8 percent. The result's refined flag says which of the two happened, so the caller can tell.

When the reduced Jacobian is singular – a small or non-hyperbolic fixed point – MATLAB's linear solves emit a warning and return non-finite entries, which cache_miss_rmf.m detects and discards, keeping the plain mean-field fixed point. The port raises NumericError from the same solves and catches it in the same place, with the same outcome; the result carries a refined flag saying which of the two was used, which the reference does not expose.

ARITHMETIC. Gated: the fixed point is reached by a tolerance-driven integration, so it is an approximation in any arithmetic.

COST. The Hessian is a dense model_dim^3 tensor and the Lyapunov solve is a dense rk^2 by rk^2 system, exactly as in the reference. With n items and h lists model_dim = n(h+1), so the refinement is practical for tens of items and quickly stops being so; the plain mean-field path has no such limit.

Definition in file cache_miss_rmf.h.