cache_t_hlru.h File Reference

Characteristic times of the h-LRU / LRU(m) TTL approximation. More...

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

Include dependency graph for cache_t_hlru.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
std::vector< T >	line::cache::cache_t_hlru (const Matrix< T > &gamma, const std::vector< int > &m)
	Characteristic times of the h-LRU / LRU(m) TTL approximation.

Detailed Description

Characteristic times of the h-LRU / LRU(m) TTL approximation.

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

Under the characteristic-time (Che) approximation each list l of an h-LRU cache has a time T(l) such that an item of request rate lam is evicted from list l if it is not requested within T(l). The level of an item is then a birth-death chain with e(l) = exp(-lam T(l)), giving unnormalized weights

w(0) = 1, w(l) = w(l-1) (1 - e(l)) / e(l),

and pi_l = w(l)/sum(w). The times are fixed by sum_k pi_l(k;T) = m(l), one equation per list. sum_k pi_l is increasing in T(l), so each equation is solved by bisection (bracketed by doubling the upper end until the occupancy reaches the capacity, then 100 halvings), swept Gauss-Seidel over the lists until the times move by less than 1e-8 relative.

ARITHMETIC: exp is required and the answer is defined by a bisection tolerance, so this needs transcendental arithmetic.

Reference: Gast and Van Houdt, SIGMETRICS 2015. For h = 1 the fixed point reduces exactly to the Che approximation of LRU.

Definition in file cache_t_hlru.h.