Level statistics of one item's embedded (list, phase) chain in the LRU(m)-MAP TTL approximation. More...

#include <cstddef>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/api/mc/dtmc_solve.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/expm.h"
#include "line/util/linalg.h"
#include "line/util/matrix.h"

Include dependency graph for cache_lrum_map_levelstats.h:

Classes
struct	line::cache::CacheLrumMapLevelStats< T >
	Per-item level statistics, MATLAB's [prob, occ, hitfrac]. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheLrumMapLevelStats< T >	line::cache::cache_lrum_map_levelstats (const Matrix< T > &D0, const Matrix< T > &D1, const std::vector< T > &Tv)
	Level statistics of one item's embedded (list, phase) chain in the LRU(m)-MAP TTL approximation.

Detailed Description

Level statistics of one item's embedded (list, phase) chain in the LRU(m)-MAP TTL approximation.

Templated port of matlab/src/api/cache/cache_lrum_map_levelstats.m, cross-checked against the levelStats method of jar/src/main/java/jline/api/cache/Cache_t_lrum_map.java. Evaluates eqs. (5)-(9) of Gast and Van Houdt, Performance Evaluation 2017, for an item whose request process is the MAP (D0, D1) and whose lists have characteristic times T(1..h):

E_l = exp(D0 T_l), N_l = (I - E_l)(-D0)^-1, A_l = N_l D1, A_0 = (-D0)^-1 D1, N_0 = (-D0)^-1, R_h = A_{h-1} (I - A_h)^-1, R_l = A_{l-1} (I - R_{l+1} E_{l+1})^-1, l < h (A_0 for l = 1), pi_0 = pi_0 R_1 E_1, pi_l = pi_{l-1} R_l,

with the level-0 boundary vector pi_0 normalized to sum one. The reported probabilities weight each level by its mean holding time pi_l N_l e, and the hit fractions divide the hit throughput of each list by the item's stationary request rate pi D1 e.

PERRON VECTOR WITHOUT AN EIGENDECOMPOSITION: MATLAB computes pi_0 with eig(M') and picks the eigenvector of largest real part; the JAR runs power iteration. Neither is needed. M = R_1 E_1 has Perron root exactly one – it is the transition matrix of the embedded chain of returns to level 0, so it is stochastic in the (list, phase) sense – and this was verified in MATLAB on the reference instances, where max(real(eig(M'))) = 1 to 1e-15 at characteristic times both at and far from the capacity fixed point. So pi_0 is the stationary vector of a stochastic matrix, i.e. dtmc_solve(M), which the port already solves EXACTLY by LU. The assumption is not taken on faith: the residual ||pi_0 (M - I)||_inf is checked and a NumericError is raised if the Perron root is not one, rather than silently returning the stationary vector of a matrix that does not have one.

ARITHMETIC: exp(D0 T_l) is a tolerance-controlled approximation, so this requires transcendental arithmetic. Everything else (the inverses, pi_0, the stationary phase vector) is a linear solve and is exact.

DIVERGENCE, MATLAB vs JAR: MATLAB uses one MAP (D0, D1) per item, shared by every list. The JAR signature takes a MatrixCell per item and reads a DIFFERENT (D0, D1) per list, D0c.get(l) and D1c.get(l), which is a strictly larger model and is not what cache_ttl_lrum_map.m builds or what the paper states. This port follows MATLAB.

Definition in file cache_lrum_map_levelstats.h.

Classes

Namespaces

Functions

Detailed Description