TTL (characteristic-time) approximation of an LRU cache whose lists form an arbitrary access graph. More...

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

Include dependency graph for cache_ttl_lrua.h:

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
Matrix< T >	line::cache::cache_ttl_lrua (const Matrix< T > &lambda, const std::vector< Matrix< T > > &R, const std::vector< T > &m, const T &tol, unsigned maxswp=200)
	TTL (characteristic-time) approximation of an LRU cache whose lists form an arbitrary access graph.

Detailed Description

TTL (characteristic-time) approximation of an LRU cache whose lists form an arbitrary access graph.

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

Each item moves over the h+1 nodes "not cached" (node 0) and "in list l" (node l), driven by the access graph R and by exponential timer races: given characteristic times x_1..x_h, an item in list l is promoted along R with probability 1 - exp(-lambda_l x_l) and demoted with probability exp(-lambda_l x_l). The embedded chain over the reachable nodes is solved by dtmc_solve, the mean holding times are 1/lambda_0 at node 0 and (1 - exp(-lambda_l x_l))/lambda_l in list l, and the time-stationary probabilities are the holding-time weighted normalization of the two. The times are then fixed by sum_k prob(k,l) = m_l, one equation per list.

HOW THE SYSTEM IS SOLVED: as in cache_t_lrum_map.h and cache_t_hlru.h, the occupancy of list l is increasing in its own characteristic time, so the system is h scalar bracketed root problems swept Gauss-Seidel, closed by bisection. This is deterministic. MATLAB instead calls fsolve from a RANDOM initial point – rng(seed,'twister') with a default seed of 23000 and x = 10*rand(1,h) – so its answer depends on the seed argument and on the Optimization Toolbox, and it stops at fsolve's default tolerance (the reference instance in the tests leaves capacity residuals of ~1.4e-7). The JAR uses a damped Newton on log(T) with a finite-difference Jacobian, which is deterministic but still needs a Jacobian and a line search.

ARITHMETIC: exp and a bisection tolerance, so transcendental arithmetic is required.

LATENT CONSTRAINT IN THE REFERENCE: MATLAB reads the demotion probability as exp(-lambda(1,i,k)*x(k-1)) for every k that is a successor of some node j, which for k = 1 (the "not cached" node, 0 here) indexes x(0) and is a hard MATLAB error. An access graph that routes back into the not-cached node is therefore not expressible; this port raises InputError on it instead of relying on an index-out-of-range.

ONE-USER REDUCTION: the MATLAB signature takes a (u x n x h+1) array but its body reads lambda(1,i,j) only, so every user beyond the first is ignored. The port takes the (n x h+1) matrix that MATLAB actually uses, which makes the reduction explicit rather than silent. The caller in solver_mva_cache_analyzer.m passes per-user rates whose relevant slice is already the aggregate.

Definition in file cache_ttl_lrua.h.

Namespaces

Functions

Detailed Description