cache_mva_miss.h File Reference

Per-item and global cache miss probabilities by mean value analysis. 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_miss.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheMvaMissResult< T >
	Return value of cache_mva_miss, mirroring [M,Mk]. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheMvaMissResult< T >	line::cache::cache_mva_miss (const std::vector< T > &p, const std::vector< int > &m, const Matrix< T > &R)
	Per-item and global cache miss probabilities by mean value analysis.

Detailed Description

Per-item and global cache miss probabilities by mean value analysis.

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

Recursion on the capacity vector: at capacity m the weight of item k in list j is w(k,j) = prod_{i<=j} R(i,k) p(k)^j |Mk(k; m - e_j)|, i.e. the item's miss probability one slot down, scaled by the probability of reaching list j through the routing chain R and by j independent requests. The per-list normalization x(j) = 1/sum_k |w(k,j)| turns the weights into occupancy shares and the miss probability of item k is what is left after removing the m(j) slots of every list:

Mk(k) = |1 - sum_j x(j) m(j) w(k,j)|, M = sum_k p(k) Mk(k).

The base case sum(m) == 0 (or any negative capacity, which the recursion reaches from a list of capacity zero) is Mk == 1: nothing is cached.

Only products, sums, integer powers and divisions, so the algorithm stays in the field and instantiates at exact arithmetic. The abs() calls of the reference are kept: they are no-ops on a correct instance (every weight is non-negative) but they change the answer on an over-committed one, so dropping them would silently diverge from MATLAB and the JAR.

Definition in file cache_mva_miss.h.