cache_mva.h File Reference

Exact mean value analysis of a multi-list cache. More...

#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for cache_mva.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheMvaResult< T >
	Return value of cache_mva, mirroring [pi,pi0,pij,x,u,E]. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheMvaResult< T >	line::cache::cache_mva (const Matrix< T > &gamma, const std::vector< int > &m)
	Exact mean value analysis of a multi-list cache.

Detailed Description

Exact mean value analysis of a multi-list cache.

Templated port of matlab/src/api/cache/cache_mva.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_mva.java.

Sweeps the box of cache occupancies {0..m(1)} x ... x {0..m(h)} in the order MATLAB's State.cartesian produces (first list varying fastest, so the predecessor state m - e_l always precedes m). At each state the MVA arrival-theorem step is

x(l) = m(l) / sum_k gamma(k,l) (1 - pi(k; m - e_l)) pij(k,l) = gamma(k,l) (1 - pi(k; m - e_l)) x(l) pi(k) = sum_l pij(k,l),

i.e. the list-l throughput normalizes the "item k is not already cached" probabilities seen at the previous population. Only divisions and products, so the exact instantiation carries the whole sweep in rationals; the conservation law sum_l pij(k,l) + pi0(k) = 1 then holds identically.

REFERENCE DEFECT (both codebases): the normalizing constant E of the return list is initialized to 1 and never updated – MATLAB sets E=1; before the sweep and returns it, and the JAR mirrors that with int E = 1;. The value is therefore not the cache normalizing constant (use cache_erec for that). It is reproduced here for interface compatibility and flagged in the result struct, not silently recomputed, since callers may rely on the constant.

Definition in file cache_mva.h.