Classes
struct	CacheBlockedPair
	One (item, list, blocking list) triple, all 0-based. More...
struct	CacheGammaGraphResult
	Return value of cache_gamma, mirroring the JAR's Ret.cacheGamma. More...
struct	CacheGammaResult
	Return value of cache_gamma_lp, mirroring [gamma,u,n,h]. More...
struct	CacheIsResult
struct	CacheLrumMapLevelStats
	Per-item level statistics, MATLAB's [prob, occ, hitfrac]. More...
struct	CacheMissIsResult
struct	CacheMissResult
	Return value of cache_miss, mirroring [M,MU,MI,pi0]. More...
struct	CacheMissRmfResult
	Return value of cache_miss_rmf, mirroring [M,MU,MI,pi0,tout,pi0_t,MU_t,xtraj]. More...
struct	CacheMissSpmResult
	Return value of cache_miss_spm, mirroring [M,MU,MI,pi0,lE]. More...
struct	CacheMvaMissResult
	Return value of cache_mva_miss, mirroring [M,Mk]. More...
struct	CacheMvaResult
	Return value of cache_mva, mirroring [pi,pi0,pij,x,u,E]. More...
struct	CacheRmfExpansionTransient
	Result of cache_miss_rmf_expansion_transient. More...
struct	CacheRrmMeanfieldResult
	Return value of cache_rrm_meanfield. More...
struct	CacheSpmResult
	Return value of cache_spm, mirroring [Z,lZ,xi]. More...
struct	CacheSpmSizeResult
	Outcome of the expansion. More...
struct	CacheTtlLrumMapResult
	Request-weighted and time-stationary level probabilities. More...
struct	CacheXiFpResult
	Return value of cache_xi_fp, mirroring [xi,pi0,pij,it]. More...

Typedefs
template<class T>
using	CacheMissPosRmfResult = CacheMissRmfResult<T>
	Return value of the position-resolved routines, as CacheMissRmfResult.

Enumerations
enum class	CacheCostMode { AtMost , Exact }
	Whether the caps bound the cost from above (matching cache_erec) or resolve it exactly. More...

Functions
template<class T>
std::vector< T >	cache_cost (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k, const Matrix< T > &pij)
	Mean per-list storage cost of a cache with item sizes, and the screen for promotion paths that storage cost caps make unreachable.
template<class T>
std::vector< T >	cache_cost (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k)
template<class T>
std::vector< CacheBlockedPair >	cache_cost_pathcheck (const Matrix< T > &gamma, const std::vector< int > &sigma, const std::vector< int > &k, const std::vector< int > &parent)
template<class T>
T	cache_erec (const Matrix< T > &gamma, const std::vector< int > &m)
	Exact recursive normalizing constant of a multi-list cache model.
template<class T>
T	cache_erec (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k)
	The normalizing constant under per-list storage cost caps.
template<class T>
CacheGammaGraphResult< T >	cache_gamma (const std::vector< Matrix< T > > &lambda, const std::vector< std::vector< Matrix< T > > > &R)
	Access factors of a multi-list cache whose lists form a general access GRAPH.
template<class T>
CacheGammaResult< T >	cache_gamma_lp (const std::vector< Matrix< T > > &lambda, const std::vector< std::vector< Matrix< T > > > &R)
	Access factors of a tree-structured multi-list cache.
template<class T>
CacheIsResult< T >	cache_is (const Matrix< T > &gamma_in, const std::vector< int > &m, std::size_t samples, std::uint64_t seed, const std::vector< int > &sigma_in, const std::vector< int > &k)
	Importance-sampling estimate of the cache normalizing constant.
template<class T>
CacheIsResult< T >	cache_is (const Matrix< T > &gamma_in, const std::vector< int > &m, std::size_t samples, std::uint64_t seed)
	cache_is without storage cost caps.
template<class T>
CacheIsResult< T >	cache_is (const Matrix< T > &gamma, const std::vector< int > &m)
	cache_is with the MATLAB default of 1e5 samples.
template<class T>
CacheLrumMapLevelStats< T >	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.
template<class T>
CacheMissResult< T >	cache_miss (const Matrix< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda)
	Exact cache miss rates from the recursive normalizing constant.
template<class T>
CacheMissResult< T >	cache_miss (const Matrix< T > &gamma, const std::vector< int > &m)
	Overload without request rates: only the global miss rate is defined.
template<class T>
T	cache_miss_asy (const Matrix< T > &gamma, const std::vector< int > &m, int maxIter, const T &tolerance)
	Asymptotic (large-cache) miss ratio by a rank-threshold fixed point.
template<class T>
T	cache_miss_asy (const Matrix< T > &gamma, const std::vector< int > &m)
	Reference defaults: 1000 sweeps at a 1e-8 sup-norm tolerance.
template<class T>
CacheMissResult< T >	cache_miss_fpi (const Matrix< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda)
	Cache miss rates from the fixed-point multipliers.
template<class T>
CacheMissIsResult< T >	cache_miss_is (const Matrix< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, std::size_t samples, std::uint64_t seed, const std::vector< int > &sigma, const std::vector< int > &cap)
	Cache miss rates from the importance-sampling hit probabilities.
template<class T>
CacheMissIsResult< T >	cache_miss_is (const Matrix< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, std::size_t samples, std::uint64_t seed)
	cache_miss_is without storage cost caps.
template<class T>
CacheMissIsResult< T >	cache_miss_is (const Matrix< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda)
	cache_miss_is with the MATLAB default of 1e5 samples.
template<class T>
CacheMissPosRmfResult< T >	cache_miss_fifo_rmf (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	Port of cache_miss_fifo_rmf.m: the FIFO(m) position-resolved mean field.
template<class T>
CacheMissPosRmfResult< T >	cache_miss_fifo_rmf_transient (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const T &t0, const T &t1, const std::vector< T > &x0init, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	cache_miss_fifo_rmf with the optional TSPAN/X0INIT transient.
template<class T>
CacheMissPosRmfResult< T >	cache_miss_sfifo_rmf (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	Port of cache_miss_sfifo_rmf.m: the strict FIFO(m) position-resolved mean field.
template<class T>
CacheMissPosRmfResult< T >	cache_miss_sfifo_rmf_transient (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda, const T &t0, const T &t1, const std::vector< T > &x0init, const std::vector< std::vector< Matrix< T > > > &accost=std::vector< std::vector< Matrix< T > > >())
	cache_miss_sfifo_rmf with the optional TSPAN/X0INIT transient.
std::size_t	cache_miss_rmf_index (std::size_t i, std::size_t k, std::size_t n_items)
	Flat index of (item i, list k), k = 0 meaning "not cached" (rmf_index.m).
template<class T>
CacheMissRmfResult< T >	cache_miss_rmf (const std::vector< T > &gamma, const std::vector< int > &m_in, const Matrix< T > &lambda, const T &tmax, const std::vector< std::vector< Matrix< T > > > &accost)
	Refined mean-field miss rates of a RANDOM(m) multi-list cache.
template<class T>
CacheMissRmfResult< T >	cache_miss_rmf (const std::vector< T > &gamma, const std::vector< int > &m_in, const Matrix< T > &lambda, const T &tmax)
	cache_miss_rmf on the linear chain, i.e.
template<class T>
CacheMissRmfResult< T >	cache_miss_rmf (const std::vector< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda)
	cache_miss_rmf with the reference horizon tmax = 1e4.
template<class T>
CacheMissRmfResult< T >	cache_miss_rmf_transient (const std::vector< int > &m_in, const Matrix< T > &lambda, const T &t0, const T &t1, const std::vector< T > &x0init)
	Transient mean-field trajectory over [t0,t1] from a given initial occupancy, the optional TSPAN/X0INIT path of cache_miss_rmf.m.
template<class T>
CacheRmfExpansionTransient< T >	cache_miss_rmf_expansion_transient (const std::vector< int > &m_in, const Matrix< T > &lambda, const T &time, std::size_t n_points, int order)
	Refined mean-field TRANSIENT, CacheRMF.meanFieldExpansionTransient.
template<class T>
CacheMissSpmResult< T >	cache_miss_spm (const Matrix< T > &gamma, const std::vector< int > &m, const Matrix< T > &lambda)
	Saddle-point approximation of the cache miss rates.
template<class T>
CacheMvaResult< T >	cache_mva (const Matrix< T > &gamma, const std::vector< int > &m)
	Exact mean value analysis of a multi-list cache.
template<class T>
CacheMvaMissResult< T >	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.
template<class T>
Matrix< T >	cache_prob_erec (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k)
	Per-item hit and miss probabilities under per-list storage cost caps, pi_ij = m_j gamma(i,j) E_i(m - e_j, k - sigma_i e_j) / E(m,k).
template<class T>
Matrix< T >	cache_prob_erec (const Matrix< T > &gamma, const std::vector< int > &m)
	Exact per-item hit and miss probabilities of a multi-list cache.
template<class T>
Matrix< T >	cache_prob_fpi (const Matrix< T > &gamma, const std::vector< int > &m)
	Cache hit and miss probabilities from the fixed-point multipliers.
template<class T>
Matrix< T >	cache_prob_is (const Matrix< T > &gamma, const std::vector< int > &m, std::size_t samples, std::uint64_t seed, const std::vector< int > &sigma, const std::vector< int > &k)
	Importance-sampling estimate of the cache hit-probability distribution.
template<class T>
Matrix< T >	cache_prob_is (const Matrix< T > &gamma, const std::vector< int > &m, std::size_t samples, std::uint64_t seed)
	cache_prob_is without storage cost caps.
template<class T>
Matrix< T >	cache_prob_is (const Matrix< T > &gamma, const std::vector< int > &m)
	cache_prob_is with the MATLAB default of 1e5 samples.
template<class T>
Matrix< T >	cache_prob_spm (const Matrix< T > &gamma, const std::vector< int > &m)
	Saddle-point approximation of the per-item cache hit probabilities.
Matrix< double >	cache_rmf_lna (const std::vector< double > &x, const std::vector< double > &p, const std::vector< double > &m, std::size_t n, std::size_t h, std::size_t dim)
	Stationary covariance of a RANDOM(m) cache occupancy, under the LNA.
template<class T>
CacheRrmMeanfieldResult< T >	cache_rrm_meanfield (const std::vector< T > &lambda, const std::vector< int > &m, const T &tmax)
	Steady state of the RANDOM(m) multi-list mean field.
template<class T>
CacheRrmMeanfieldResult< T >	cache_rrm_meanfield (const std::vector< T > &lambda, const std::vector< int > &m)
	cache_rrm_meanfield with the reference horizon tmax = 1e4.
template<class T>
std::vector< T >	cache_rrm_meanfield_ode (const std::vector< T > &x, const std::vector< T > &lambda, const std::vector< int > &m)
	Mean-field drift of the RANDOM(m) multi-list cache.
template<class T>
CacheSpmResult< T >	cache_spm (const Matrix< T > &gamma_in, const std::vector< int > &m)
	Saddle-point approximation of the cache normalizing constant.
template<class T>
CacheSpmSizeResult< T >	cache_spm_size (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k, CacheCostMode mode=CacheCostMode::AtMost)
	Ray (WKB) asymptotic expansion of the cost-capped cache normalizing constant.
template<class T>
std::vector< T >	cache_t_hlru (const Matrix< T > &gamma, const std::vector< int > &m)
	Characteristic times of the h-LRU / LRU(m) TTL approximation.
template<class T>
std::vector< T >	cache_t_lrum_map (const std::vector< mam::Map< T > > &items, const std::vector< T > &m, const T &tol, unsigned maxswp=200)
	Characteristic times of the LRU(m)-MAP TTL approximation.
template<class T>
Matrix< T >	cache_ttl_hlru (const Matrix< T > &lambda, const std::vector< int > &m)
	TTL (characteristic-time) approximation of an h-LRU / LRU(m) cache.
template<class T>
Matrix< T >	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.
template<class T>
CacheTtlLrumMapResult< T >	cache_ttl_lrum_map (const std::vector< mam::Map< T > > &items, const std::vector< T > &m, const T &tol)
	TTL approximation of an LRU(m) cache whose items are requested by Markovian arrival processes.
template<class T>
CacheXiFpResult< T >	cache_xi_fp (const Matrix< T > &gamma, const std::vector< int > &m)
	Lagrange multipliers of a multi-list cache by fixed-point iteration.
template<class T>
std::vector< T >	cache_xi_iter (const Matrix< T > &gamma, const std::vector< int > &m)
	Lagrange multipliers of a multi-list cache by the Gast-Van Houdt iteration.

Typedef Documentation

◆ CacheMissPosRmfResult

template<class T>

using line::cache::CacheMissPosRmfResult = CacheMissRmfResult<T>

Return value of the position-resolved routines, as CacheMissRmfResult.

Definition at line 78 of file cache_miss_pos_rmf.h.

Enumeration Type Documentation

◆ CacheCostMode

enum class line::cache::CacheCostMode

strong

Whether the caps bound the cost from above (matching cache_erec) or resolve it exactly.

Enumerator
AtMost
Exact

Definition at line 116 of file cache_spm_size.h.

Function Documentation

◆ cache_cost() [1/2]

template<class T>

std::vector< T > line::cache::cache_cost	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const std::vector< int > &	sigma,
		const std::vector< int > &	k )

Definition at line 82 of file cache_cost.h.

References cache_cost().

◆ cache_cost() [2/2]

template<class T>

std::vector< T > line::cache::cache_cost	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const std::vector< int > &	sigma,
		const std::vector< int > &	k,
		const Matrix< T > &	pij )

Mean per-list storage cost of a cache with item sizes, and the screen for promotion paths that storage cost caps make unreachable.

Parameters

gamma	(n x h) access factors
m	(h) list capacities
sigma	(n) per-item storage costs
k	(h) per-list storage cost caps; empty for none
pij	(n x (h+1)) occupancy, column 0 the miss probability; empty to recompute

Returns: (h) mean storage cost held by each list

Definition at line 63 of file cache_cost.h.

References cache_cost(), cache_prob_erec(), line::Matrix< T >::cols(), line::Matrix< T >::empty(), line::InputError::InputError(), and line::Matrix< T >::rows().

Referenced by cache_cost(), cache_cost(), and line::nc::solver_nc_cache_analyzer().

◆ cache_cost_pathcheck()

template<class T>

std::vector< CacheBlockedPair > line::cache::cache_cost_pathcheck	(	const Matrix< T > &	gamma,
		const std::vector< int > &	sigma,
		const std::vector< int > &	k,
		const std::vector< int > &	parent )

Parameters

gamma	(n x h) access factors
sigma	(n) per-item storage costs
k	(h) per-list storage cost caps
parent	(h) parent list of each list, 0-based, -1 for lists rooted in the miss list

Returns: the blocked (item, list, blocking list) triples, empty when none

Definition at line 95 of file cache_cost.h.

References line::cache::CacheBlockedPair::blocking_list, cache_cost_pathcheck(), line::Matrix< T >::cols(), line::cache::CacheBlockedPair::item, line::cache::CacheBlockedPair::list, and line::Matrix< T >::rows().

Referenced by cache_cost_pathcheck(), and line::nc::solver_nc_cache_analyzer().

◆ cache_erec() [1/2]

template<class T>

T line::cache::cache_erec	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Exact recursive normalizing constant of a multi-list cache model.

Parameters

gamma	(n x h) access factors, item by list
m	(h) list capacities

Returns: the normalizing constant E

Definition at line 201 of file cache_erec.h.

References cache_erec(), line::Matrix< T >::cols(), line::Matrix< T >::empty(), line::InputError::InputError(), and line::Matrix< T >::rows().

Referenced by cache_erec(), cache_erec(), cache_is(), cache_miss(), cache_prob_erec(), and cache_spm().

◆ cache_erec() [2/2]

template<class T>

T line::cache::cache_erec	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const std::vector< int > &	sigma,
		const std::vector< int > &	k )

The normalizing constant under per-list storage cost caps.

An EMPTY sigma or k selects the unconstrained recursion, so a caller can pass the model's (possibly absent) sizes through unconditionally.

Parameters

gamma	(n x h) access factors, item by list
m	(h) list capacities
sigma	(n) per-item storage costs, positive integers
k	(h) per-list storage cost caps, non-negative integers

Returns: the normalizing constant E(m,k)

Definition at line 223 of file cache_erec.h.

References cache_erec(), line::Matrix< T >::cols(), and line::InputError::InputError().

◆ cache_gamma()

template<class T>

CacheGammaGraphResult< T > line::cache::cache_gamma	(	const std::vector< Matrix< T > > &	lambda,
		const std::vector< std::vector< Matrix< T > > > &	R )

Access factors of a multi-list cache whose lists form a general access GRAPH.

Parameters

lambda	(u) matrices of size (n x (h+1)): lambda[v](i,t) is the rate at which user v requests item i while it sits at node t
R	(u x n) routing matrices of size ((h+1) x (h+1))

Definition at line 125 of file cache_gamma.h.

References cache_gamma(), line::cache::CacheGammaGraphResult< T >::gamma, line::cache::CacheGammaGraphResult< T >::h, line::InputError::InputError(), line::Matrix< T >::Matrix(), line::cache::CacheGammaGraphResult< T >::n, and line::cache::CacheGammaGraphResult< T >::u.

Referenced by cache_gamma().

◆ cache_gamma_lp()

template<class T>

CacheGammaResult< T > line::cache::cache_gamma_lp	(	const std::vector< Matrix< T > > &	lambda,
		const std::vector< std::vector< Matrix< T > > > &	R )

Access factors of a tree-structured multi-list cache.

Parameters

lambda	(u) matrices of size (n x (h+1)): lambda[v](i,t) is the rate at which user v requests item i while it sits at node t
R	(u x n) routing matrices of size ((h+1) x (h+1))

Definition at line 88 of file cache_gamma_lp.h.

References cache_gamma_lp(), line::Matrix< T >::cols(), line::cache::CacheGammaResult< T >::gamma, line::cache::CacheGammaResult< T >::h, line::InputError::InputError(), line::cache::CacheGammaResult< T >::n, line::cache::CacheGammaResult< T >::parent, line::Matrix< T >::rows(), and line::cache::CacheGammaResult< T >::u.

Referenced by cache_gamma_lp(), line::retrieval::cache_retrieval_inputs(), line::da::da_cache_isolate(), and line::nc::solver_nc_cache_analyzer().

◆ cache_is() [1/3]

template<class T>

CacheIsResult< T > line::cache::cache_is	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

cache_is with the MATLAB default of 1e5 samples.

Definition at line 220 of file cache_is.h.

References cache_is().

◆ cache_is() [2/3]

template<class T>

CacheIsResult< T > line::cache::cache_is	(	const Matrix< T > &	gamma_in,
		const std::vector< int > &	m,
		std::size_t	samples,
		std::uint64_t	seed )

cache_is without storage cost caps.

Definition at line 213 of file cache_is.h.

References cache_is().

◆ cache_is() [3/3]

template<class T>

CacheIsResult< T > line::cache::cache_is	(	const Matrix< T > &	gamma_in,
		const std::vector< int > &	m,
		std::size_t	samples,
		std::uint64_t	seed,
		const std::vector< int > &	sigma_in,
		const std::vector< int > &	k )

Importance-sampling estimate of the cache normalizing constant.

Parameters

gamma_in	(n x h) access factors
m	(h) list capacities
samples	number of Monte Carlo samples (MATLAB default 1e5)
seed	seed of the sampling stream
sigma_in	(n) per-item storage cost; empty for uncapped lists
k	(h) per-list cost cap; empty for uncapped lists

Definition at line 113 of file cache_is.h.

References cache_erec(), cache_is(), line::Matrix< T >::cols(), line::cache::CacheIsResult< T >::E, line::InputError::InputError(), line::cache::CacheIsResult< T >::lE, and line::Matrix< T >::rows().

Referenced by cache_is(), cache_is(), cache_is(), and cache_miss_is().

◆ cache_lrum_map_levelstats()

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.

Parameters

D0	(d x d) hidden-transition matrix of the item's request MAP
D1	(d x d) arrival matrix of the item's request MAP
Tv	(h) characteristic times, all positive

Definition at line 88 of file cache_lrum_map_levelstats.h.

References cache_lrum_map_levelstats(), line::Matrix< T >::cols(), line::mc::dtmc_solve(), line::expm(), line::eye(), line::cache::CacheLrumMapLevelStats< T >::hitfrac, line::InputError::InputError(), line::inverse(), line::mam::map_lambda(), line::matmul(), line::num_abs(), line::NumericError::NumericError(), line::cache::CacheLrumMapLevelStats< T >::occ, line::cache::CacheLrumMapLevelStats< T >::prob, line::Matrix< T >::rows(), and line::vecmul().

Referenced by cache_lrum_map_levelstats(), and cache_ttl_lrum_map().

◆ cache_miss() [1/2]

template<class T>

CacheMissResult< T > line::cache::cache_miss	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Overload without request rates: only the global miss rate is defined.

Definition at line 106 of file cache_miss.h.

References cache_miss().

◆ cache_miss() [2/2]

template<class T>

CacheMissResult< T > line::cache::cache_miss	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda )

Exact cache miss rates from the recursive normalizing constant.

Parameters

gamma	(n x h) access factors
m	(h) list capacities
lambda	(u x n) per-user per-item request rates, MATLAB's lambda(:,:,1); pass an empty matrix for the miss rate alone

Definition at line 65 of file cache_miss.h.

References cache_erec(), cache_miss(), line::Matrix< T >::cols(), line::Matrix< T >::empty(), line::InputError::InputError(), line::cache::CacheMissResult< T >::M, line::cache::CacheMissResult< T >::MI, line::cache::CacheMissResult< T >::MU, line::NumericError::NumericError(), line::cache::CacheMissResult< T >::pi0, and line::Matrix< T >::rows().

Referenced by cache_miss(), and cache_miss().

◆ cache_miss_asy() [1/2]

template<class T>

T line::cache::cache_miss_asy	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Reference defaults: 1000 sweeps at a 1e-8 sup-norm tolerance.

Definition at line 153 of file cache_miss_asy.h.

References cache_miss_asy().

◆ cache_miss_asy() [2/2]

template<class T>

T line::cache::cache_miss_asy	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		int	maxIter,
		const T &	tolerance )

Asymptotic (large-cache) miss ratio by a rank-threshold fixed point.

Parameters

gamma	(h x n) LIST-major access factors; see the note above
m	(h) list capacities
maxIter	cap on fixed-point sweeps
tolerance	sup-norm stopping tolerance on pi

Returns: the request-weighted asymptotic miss ratio

Definition at line 72 of file cache_miss_asy.h.

References cache_miss_asy(), line::Matrix< T >::cols(), line::InputError::InputError(), line::num_abs(), and line::Matrix< T >::rows().

Referenced by cache_miss_asy(), and cache_miss_asy().

◆ cache_miss_fifo_rmf()

template<class T>

CacheMissPosRmfResult< T > line::cache::cache_miss_fifo_rmf	(	const std::vector< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda,
		const std::vector< std::vector< Matrix< T > > > &	accost = std::vector<std::vector<Matrix<T> > >() )

Port of cache_miss_fifo_rmf.m: the FIFO(m) position-resolved mean field.

Parameters

gamma	present for signature compatibility; the reference marks it unused and so is it here
m	(h) list capacities
lambda	(u x n) per-user per-item request rates, the reference's lambda(:,:,1) page
accost	per-(user,item) access graph; empty is the linear chain

Definition at line 427 of file cache_miss_pos_rmf.h.

References cache_miss_fifo_rmf().

Referenced by cache_miss_fifo_rmf().

◆ cache_miss_fifo_rmf_transient()

template<class T>

CacheMissPosRmfResult< T > line::cache::cache_miss_fifo_rmf_transient	(	const std::vector< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda,
		const T &	t0,
		const T &	t1,
		const std::vector< T > &	x0init,
		const std::vector< std::vector< Matrix< T > > > &	accost = std::vector<std::vector<Matrix<T> > >() )

cache_miss_fifo_rmf with the optional TSPAN/X0INIT transient.

Definition at line 437 of file cache_miss_pos_rmf.h.

References cache_miss_fifo_rmf_transient().

Referenced by cache_miss_fifo_rmf_transient(), and line::fluid::solver_fld_cacheqn_tran().

◆ cache_miss_fpi()

template<class T>

CacheMissResult< T > line::cache::cache_miss_fpi	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda )

Cache miss rates from the fixed-point multipliers.

Parameters

gamma	(n x h) access factors
m	(h) list capacities
lambda	(u x n) per-user per-item request rates

Definition at line 49 of file cache_miss_fpi.h.

References cache_miss_fpi(), cache_xi_fp(), line::Matrix< T >::cols(), line::InputError::InputError(), line::cache::CacheMissResult< T >::M, line::cache::CacheMissResult< T >::MI, line::cache::CacheMissResult< T >::MU, line::cache::CacheMissResult< T >::pi0, line::Matrix< T >::rows(), and line::cache::CacheXiFpResult< T >::xi.

Referenced by cache_miss_fpi(), line::da::da_cacheqn(), and line::da::da_cacheqn_retrieval().

◆ cache_miss_is() [1/3]

template<class T>

CacheMissIsResult< T > line::cache::cache_miss_is	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda )

cache_miss_is with the MATLAB default of 1e5 samples.

Definition at line 113 of file cache_miss_is.h.

References cache_miss_is().

◆ cache_miss_is() [2/3]

template<class T>

CacheMissIsResult< T > line::cache::cache_miss_is	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda,
		std::size_t	samples,
		std::uint64_t	seed )

cache_miss_is without storage cost caps.

Definition at line 105 of file cache_miss_is.h.

References cache_miss_is().

◆ cache_miss_is() [3/3]

template<class T>

CacheMissIsResult< T > line::cache::cache_miss_is	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda,
		std::size_t	samples,
		std::uint64_t	seed,
		const std::vector< int > &	sigma,
		const std::vector< int > &	cap )

Cache miss rates from the importance-sampling hit probabilities.

Parameters

gamma	(n x h) access factors
m	(h) list capacities
lambda	(u x n) per-user per-item request rates, MATLAB's lambda(:,:,1); empty for the mean miss probability alone
samples	number of Monte Carlo samples
seed	seed of the sampling stream
sigma	(n) per-item storage cost; empty for uncapped lists
cap	(h) per-list cost cap; empty for uncapped lists

Definition at line 60 of file cache_miss_is.h.

References cache_is(), cache_miss_is(), cache_prob_is(), line::Matrix< T >::cols(), line::Matrix< T >::empty(), line::InputError::InputError(), line::cache::CacheMissIsResult< T >::lE, line::cache::CacheMissIsResult< T >::M, line::cache::CacheMissIsResult< T >::MI, line::cache::CacheMissIsResult< T >::MU, line::cache::CacheMissIsResult< T >::pi0, and line::Matrix< T >::rows().

Referenced by cache_miss_is(), cache_miss_is(), cache_miss_is(), and line::nc::solver_nc_cache_analyzer().

◆ cache_miss_rmf() [1/3]

template<class T>

CacheMissRmfResult< T > line::cache::cache_miss_rmf	(	const std::vector< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda )

cache_miss_rmf with the reference horizon tmax = 1e4.

Definition at line 909 of file cache_miss_rmf.h.

References cache_miss_rmf().

◆ cache_miss_rmf() [2/3]

template<class T>

CacheMissRmfResult< T > line::cache::cache_miss_rmf	(	const std::vector< T > &	gamma,
		const std::vector< int > &	m_in,
		const Matrix< T > &	lambda,
		const T &	tmax )

cache_miss_rmf on the linear chain, i.e.

with no declared access graph.

Definition at line 902 of file cache_miss_rmf.h.

References cache_miss_rmf().

◆ cache_miss_rmf() [3/3]

template<class T>

CacheMissRmfResult< T > line::cache::cache_miss_rmf	(	const std::vector< T > &	gamma,
		const std::vector< int > &	m_in,
		const Matrix< T > &	lambda,
		const T &	tmax,
		const std::vector< std::vector< Matrix< T > > > &	accost )

Refined mean-field miss rates of a RANDOM(m) multi-list cache.

Parameters

gamma	item access factors. Present for signature compatibility with cache_miss_rmf.m, which marks it unused and reads only its size; nothing here depends on it either.
m_in	(h) list capacities
lambda	(u x n_items) per-user per-item request rates. The MATLAB argument is a three-dimensional array and the function reads only its first page, lambda(v,:,1); this is that page.
tmax	integration horizon for the fixed point (reference: 1e4)
accost	per-(user,item) access graph, each an (h+1)x(h+1) matrix; empty is the linear chain. A NON-LINEAR graph switches the solve to the general drift AND drops the 1/N refinement, exactly as the reference does: the refinement's Jacobian, Hessian and noise matrix are written for the chain drift, so applying it to another drift would correct the wrong system.

Definition at line 698 of file cache_miss_rmf.h.

References cache_miss_rmf(), cache_miss_rmf_index(), line::Matrix< T >::cols(), line::InputError::InputError(), line::inverse(), line::cache::CacheMissRmfResult< T >::M, line::matmul(), line::cache::CacheMissRmfResult< T >::MI, line::cache::CacheMissRmfResult< T >::MU, line::NumericError::NumericError(), line::cache::CacheMissRmfResult< T >::pi0, line::cache::CacheMissRmfResult< T >::refined, line::Matrix< T >::rows(), line::solve(), and line::cache::CacheMissRmfResult< T >::xss.

Referenced by cache_miss_rmf(), cache_miss_rmf(), and cache_miss_rmf().

◆ cache_miss_rmf_expansion_transient()

template<class T>

CacheRmfExpansionTransient< T > line::cache::cache_miss_rmf_expansion_transient	(	const std::vector< int > &	m_in,
		const Matrix< T > &	lambda,
		const T &	time,
		std::size_t	n_points,
		int	order )

Refined mean-field TRANSIENT, CacheRMF.meanFieldExpansionTransient.

The steady-state refinement solves F' V = -(1/2) sum F''_bc W_bc at the fixed point; the transient one carries the same three objects along the trajectory, as one coupled system in y = [X (d), V (d), W (d x d)]:

dX/dt = F(X), dV/dt = F'(X) V + (1/2) sum_{b,c} F''_{a,b,c} W_{b,c}, dW/dt = F'(X) W + W F'(X)^T + Q(X),

started from V(0) = 0, W(0) = 0 at the same initial occupancy the fixed point uses: the first m(1) items in list 1, the next m(2) in list 2, the rest outside. The reported trajectory is X(t) + V(t)/N.

order = 0 integrates the drift alone and returns V and W identically zero, which is the reference's own escape rather than a degenerate case of the coupled system.

DOUBLE ONLY, and for the reason the fluid solvers are: the coupled system is integrated by LSODA at the reference's own ode15s tolerances (RelTol 1e-6, AbsTol 1e-10) on the reference's own output grid linspace(0, time, n_points), and LSODA's coefficients assume double precision.

THE HESSIAN IS HOISTED OUT OF THE RIGHT-HAND SIDE. The drift is quadratic, so F'' does not depend on x – the reference recomputes it per step, which is d^3 work per evaluation for a value that never changes.

Definition at line 1020 of file cache_miss_rmf.h.

References line::LsodaOptions::atol, cache_miss_rmf_expansion_transient(), cache_miss_rmf_index(), line::Matrix< T >::cols(), line::InputError::InputError(), line::lsoda_integrate(), line::Matrix< T >::Matrix(), line::NumericError::NumericError(), line::Matrix< T >::rows(), line::LsodaOptions::rtol, line::LsodaSolution::success, line::cache::CacheRmfExpansionTransient< T >::t, line::LsodaSolution::t, line::UnsupportedError::UnsupportedError(), line::cache::CacheRmfExpansionTransient< T >::V, line::cache::CacheRmfExpansionTransient< T >::W, line::cache::CacheRmfExpansionTransient< T >::X, and line::LsodaSolution::y.

Referenced by cache_miss_rmf_expansion_transient().

◆ cache_miss_rmf_index()

std::size_t line::cache::cache_miss_rmf_index	(	std::size_t	i,
		std::size_t	k,
		std::size_t	n_items )

inline

Flat index of (item i, list k), k = 0 meaning "not cached" (rmf_index.m).

Definition at line 123 of file cache_miss_rmf.h.

References cache_miss_rmf_index().

Referenced by cache_miss_rmf(), cache_miss_rmf_expansion_transient(), cache_miss_rmf_index(), and cache_miss_rmf_transient().

◆ cache_miss_rmf_transient()

template<class T>

CacheMissRmfResult< T > line::cache::cache_miss_rmf_transient	(	const std::vector< int > &	m_in,
		const Matrix< T > &	lambda,
		const T &	t0,
		const T &	t1,
		const std::vector< T > &	x0init )

Transient mean-field trajectory over [t0,t1] from a given initial occupancy, the optional TSPAN/X0INIT path of cache_miss_rmf.m.

Fills tout, xtraj, pi0_t and MU_t of the result; the steady-state fields are left at their defaults because the reference computes them independently of the transient.

Definition at line 921 of file cache_miss_rmf.h.

References cache_miss_rmf_index(), cache_miss_rmf_transient(), line::Matrix< T >::cols(), line::InputError::InputError(), line::cache::CacheMissRmfResult< T >::M, line::Matrix< T >::Matrix(), line::cache::CacheMissRmfResult< T >::MU_t, line::ode_rosenbrock4(), line::cache::CacheMissRmfResult< T >::pi0_t, line::Matrix< T >::rows(), line::OdeSolution< T >::t, line::cache::CacheMissRmfResult< T >::tout, line::cache::CacheMissRmfResult< T >::xtraj, and line::OdeSolution< T >::y.

Referenced by cache_miss_rmf_transient(), and line::fluid::solver_fld_cacheqn_tran().

◆ cache_miss_sfifo_rmf()

template<class T>

CacheMissPosRmfResult< T > line::cache::cache_miss_sfifo_rmf	(	const std::vector< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda,
		const std::vector< std::vector< Matrix< T > > > &	accost = std::vector<std::vector<Matrix<T> > >() )

Port of cache_miss_sfifo_rmf.m: the strict FIFO(m) position-resolved mean field.

Same arguments as cache_miss_fifo_rmf; the policies differ only in where a demoted tail is reinserted (see the header comment).

Definition at line 450 of file cache_miss_pos_rmf.h.

References cache_miss_sfifo_rmf().

Referenced by cache_miss_sfifo_rmf().

◆ cache_miss_sfifo_rmf_transient()

template<class T>

CacheMissPosRmfResult< T > line::cache::cache_miss_sfifo_rmf_transient	(	const std::vector< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda,
		const T &	t0,
		const T &	t1,
		const std::vector< T > &	x0init,
		const std::vector< std::vector< Matrix< T > > > &	accost = std::vector<std::vector<Matrix<T> > >() )

cache_miss_sfifo_rmf with the optional TSPAN/X0INIT transient.

Definition at line 460 of file cache_miss_pos_rmf.h.

References cache_miss_sfifo_rmf_transient().

Referenced by cache_miss_sfifo_rmf_transient(), and line::fluid::solver_fld_cacheqn_tran().

◆ cache_miss_spm()

template<class T>

CacheMissSpmResult< T > line::cache::cache_miss_spm	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const Matrix< T > &	lambda )

Saddle-point approximation of the cache miss rates.

Parameters

gamma	(n x h) access factors
m	(h) list capacities
lambda	(u x n) per-user per-item request rates

Definition at line 69 of file cache_miss_spm.h.

References cache_miss_spm(), cache_spm(), line::Matrix< T >::cols(), line::Matrix< T >::empty(), line::InputError::InputError(), line::cache::CacheMissSpmResult< T >::lE, line::cache::CacheMissSpmResult< T >::M, line::cache::CacheMissSpmResult< T >::MI, line::cache::CacheMissSpmResult< T >::MU, line::cache::CacheMissSpmResult< T >::pi0, and line::Matrix< T >::rows().

Referenced by cache_miss_spm(), line::nc::solver_nc_cache_analyzer(), and line::nc::solver_nc_cacheqn_analyzer().

◆ cache_mva()

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.

Parameters

gamma	(n x h) access factors
m	(h) list capacities

Definition at line 66 of file cache_mva.h.

References cache_mva(), line::Matrix< T >::cols(), line::cache::CacheMvaResult< T >::E, line::InputError::InputError(), line::Matrix< T >::Matrix(), line::NumericError::NumericError(), line::cache::CacheMvaResult< T >::pi, line::cache::CacheMvaResult< T >::pi0, line::cache::CacheMvaResult< T >::pij, line::Matrix< T >::rows(), line::cache::CacheMvaResult< T >::u, and line::cache::CacheMvaResult< T >::x.

Referenced by cache_mva(), line::da::da_cacheqn(), and line::mva::solver_mva_cache_analyzer().

◆ cache_mva_miss()

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.

Parameters

p	(n) item popularities
m	(h) list capacities
R	(h x n) per-list routing probabilities

Definition at line 61 of file cache_mva_miss.h.

References cache_mva_miss(), line::Matrix< T >::cols(), line::InputError::InputError(), line::cache::CacheMvaMissResult< T >::M, line::cache::CacheMvaMissResult< T >::Mk, line::num_abs(), line::num_pow_int(), line::NumericError::NumericError(), and line::Matrix< T >::rows().

Referenced by cache_mva_miss().

◆ cache_prob_erec() [1/2]

template<class T>

Matrix< T > line::cache::cache_prob_erec	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Exact per-item hit and miss probabilities of a multi-list cache.

Parameters

gamma	(n x h) access factors
m	(h) list capacities

Returns: (n x (h+1)) matrix; column 0 is the miss probability, column 1+j the probability of a hit in list j

Definition at line 57 of file cache_prob_erec.h.

References cache_prob_erec().

◆ cache_prob_erec() [2/2]

template<class T>

Matrix< T > line::cache::cache_prob_erec	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const std::vector< int > &	sigma,
		const std::vector< int > &	k )

Per-item hit and miss probabilities under per-list storage cost caps, pi_ij = m_j gamma(i,j) E_i(m - e_j, k - sigma_i e_j) / E(m,k).

An EMPTY sigma or k selects the unconstrained expression.

Parameters

gamma	(n x h) access factors
m	(h) list capacities
sigma	(n) per-item storage costs; empty for none
k	(h) per-list storage cost caps; empty for none

Returns: (n x (h+1)) matrix; column 0 is the miss probability, column 1+j the probability of a hit in list j

Definition at line 74 of file cache_prob_erec.h.

References cache_erec(), cache_prob_erec(), line::Matrix< T >::cols(), line::InputError::InputError(), line::num_abs(), line::NumericError::NumericError(), and line::Matrix< T >::rows().

Referenced by cache_cost(), cache_prob_erec(), cache_prob_erec(), cache_prob_is(), line::da::da_cacheqn_itemprob(), line::nc::solver_nc_cache_analyzer(), and line::nc::solver_nc_cacheqn_analyzer().

◆ cache_prob_fpi()

template<class T>

Matrix< T > line::cache::cache_prob_fpi	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Cache hit and miss probabilities from the fixed-point multipliers.

Parameters

gamma	(n x h) access factors
m	(h) list capacities

Returns: (n x (h+1)); column 0 miss, columns 1..h hit (see the defect note)

Definition at line 55 of file cache_prob_fpi.h.

References cache_prob_fpi(), cache_xi_fp(), line::Matrix< T >::cols(), line::Matrix< T >::rows(), and line::cache::CacheXiFpResult< T >::xi.

Referenced by cache_prob_fpi(), and line::mva::solver_mva_cache_analyzer().

◆ cache_prob_is() [1/3]

template<class T>

Matrix< T > line::cache::cache_prob_is	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

cache_prob_is with the MATLAB default of 1e5 samples.

Definition at line 158 of file cache_prob_is.h.

References cache_prob_is().

◆ cache_prob_is() [2/3]

template<class T>

Matrix< T > line::cache::cache_prob_is	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		std::size_t	samples,
		std::uint64_t	seed )

cache_prob_is without storage cost caps.

Definition at line 151 of file cache_prob_is.h.

References cache_prob_is().

◆ cache_prob_is() [3/3]

template<class T>

Matrix< T > line::cache::cache_prob_is	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		std::size_t	samples,
		std::uint64_t	seed,
		const std::vector< int > &	sigma,
		const std::vector< int > &	k )

Importance-sampling estimate of the cache hit-probability distribution.

Parameters

gamma	(n x h) access factors
m	(h) list capacities
samples	number of Monte Carlo samples (MATLAB default 1e5)
seed	seed of the sampling stream
sigma	(n) per-item storage cost; empty for uncapped lists
k	(h) per-list cost cap; empty for uncapped lists

Returns: (n x h+1); column 0 is the miss probability, column 1+j the probability that the item sits on list j

Definition at line 57 of file cache_prob_is.h.

References cache_prob_erec(), cache_prob_is(), line::Matrix< T >::cols(), line::InputError::InputError(), and line::Matrix< T >::rows().

Referenced by cache_miss_is(), cache_prob_is(), cache_prob_is(), cache_prob_is(), and line::nc::solver_nc_cache_analyzer().

◆ cache_prob_spm()

template<class T>

Matrix< T > line::cache::cache_prob_spm	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Saddle-point approximation of the per-item cache hit probabilities.

Parameters

gamma	(n x h) access factors
m	(h) list capacities

Returns: (n x (h+1)); column 0 miss, column 1+j hit in list j

Definition at line 51 of file cache_prob_spm.h.

References cache_prob_spm(), cache_spm(), line::Matrix< T >::cols(), line::InputError::InputError(), line::num_abs(), and line::Matrix< T >::rows().

Referenced by cache_prob_spm(), and line::nc::solver_nc_cache_analyzer().

◆ cache_rmf_lna()

Matrix< double > line::cache::cache_rmf_lna	(	const std::vector< double > &	x,
		const std::vector< double > &	p,
		const std::vector< double > &	m,
		std::size_t	n,
		std::size_t	h,
		std::size_t	dim )

inline

Stationary covariance of a RANDOM(m) cache occupancy, under the LNA.

Parameters

x	the fluid fixed point, flattened item-major (i + k*n)
p	per-item popularities
m	per-list capacities
n	number of items
h	number of cache lists

Returns: (dim x dim) stationary covariance, symmetric

Definition at line 116 of file cache_rmf_lna.h.

References cache_rmf_lna(), line::Matrix< T >::cols(), line::eig_values(), line::InputError::InputError(), line::lyap_solve(), and line::Matrix< T >::rows().

Referenced by cache_rmf_lna().

◆ cache_rrm_meanfield() [1/2]

template<class T>

CacheRrmMeanfieldResult< T > line::cache::cache_rrm_meanfield	(	const std::vector< T > &	lambda,
		const std::vector< int > &	m )

cache_rrm_meanfield with the reference horizon tmax = 1e4.

Definition at line 101 of file cache_rrm_meanfield.h.

References cache_rrm_meanfield().

◆ cache_rrm_meanfield() [2/2]

template<class T>

CacheRrmMeanfieldResult< T > line::cache::cache_rrm_meanfield	(	const std::vector< T > &	lambda,
		const std::vector< int > &	m,
		const T &	tmax )

Steady state of the RANDOM(m) multi-list mean field.

Parameters

lambda	(n) per-item request rates
m	(h) list capacities
tmax	integration horizon (the reference uses 1e4)

Definition at line 64 of file cache_rrm_meanfield.h.

References cache_rrm_meanfield(), cache_rrm_meanfield_ode(), line::InputError::InputError(), line::cache::CacheRrmMeanfieldResult< T >::missrate, line::cache::CacheRrmMeanfieldResult< T >::missratio, line::ode_rosenbrock4(), and line::cache::CacheRrmMeanfieldResult< T >::x.

Referenced by cache_rrm_meanfield(), and cache_rrm_meanfield().

◆ cache_rrm_meanfield_ode()

template<class T>

std::vector< T > line::cache::cache_rrm_meanfield_ode	(	const std::vector< T > &	x,
		const std::vector< T > &	lambda,
		const std::vector< int > &	m )

Mean-field drift of the RANDOM(m) multi-list cache.

Parameters

x	(n(h+1)) occupancies, x[k + sn] = x(item k, level s)
lambda	(n) per-item request rates
m	(h) list capacities

Returns: the drift, same layout as x

Definition at line 58 of file cache_rrm_meanfield_ode.h.

References cache_rrm_meanfield_ode(), and line::InputError::InputError().

Referenced by cache_rrm_meanfield(), and cache_rrm_meanfield_ode().

◆ cache_spm()

template<class T>

CacheSpmResult< T > line::cache::cache_spm	(	const Matrix< T > &	gamma_in,
		const std::vector< int > &	m )

Saddle-point approximation of the cache normalizing constant.

Parameters

gamma_in	(n x h) access factors; all-zero rows are dropped first
m	(h) list capacities

Definition at line 152 of file cache_spm.h.

References cache_erec(), cache_spm(), cache_xi_iter(), line::Matrix< T >::cols(), line::InputError::InputError(), line::cache::CacheSpmResult< T >::lZ, line::num_abs(), line::num_factorial(), line::num_pow_int(), line::NumericError::NumericError(), line::Matrix< T >::rows(), line::cache::CacheSpmResult< T >::xi, and line::cache::CacheSpmResult< T >::Z.

Referenced by cache_miss_spm(), cache_prob_spm(), and cache_spm().

◆ cache_spm_size()

template<class T>

CacheSpmSizeResult< T > line::cache::cache_spm_size	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m,
		const std::vector< int > &	sigma,
		const std::vector< int > &	k,
		CacheCostMode	mode = CacheCostMode::AtMost )

Ray (WKB) asymptotic expansion of the cost-capped cache normalizing constant.

Parameters

gamma	(n x h) access factors
m	(h) list capacities, non-negative
sigma	(n) per-item storage costs, positive
k	(h) per-list storage cost caps
mode	AtMost (matches cache_erec) or Exact

Definition at line 487 of file cache_spm_size.h.

Referenced by cache_spm_size(), and line::nc::solver_nc_cache_analyzer().

◆ cache_t_hlru()

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.

Parameters

gamma	(n x 1) per-item request rates; an (n x h) matrix is accepted for backward compatibility and its first column is used, as in the MATLAB reference
m	(h) list capacities

Returns: (h) characteristic times

Definition at line 151 of file cache_t_hlru.h.

References cache_t_hlru(), line::Matrix< T >::cols(), line::InputError::InputError(), and line::Matrix< T >::rows().

Referenced by cache_t_hlru().

◆ cache_t_lrum_map()

template<class T>

std::vector< T > line::cache::cache_t_lrum_map	(	const std::vector< mam::Map< T > > &	items,
		const std::vector< T > &	m,
		const T &	tol,
		unsigned	maxswp = 200 )

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

Parameters

items	(n) per-item request MAPs
m	(h) list capacities, 0 < sum(m) < n
tol	relative tolerance on the times, e.g. 1e-12
maxswp	cap on Gauss-Seidel sweeps

Returns: (h) characteristic times

Definition at line 83 of file cache_t_lrum_map.h.

References line::bracket_expand(), cache_t_lrum_map(), line::InputError::InputError(), line::num_abs(), line::NumericError::NumericError(), line::RootResult< T >::root, and line::root_bisect().

Referenced by cache_t_lrum_map(), and cache_ttl_lrum_map().

◆ cache_ttl_hlru()

template<class T>

Matrix< T > line::cache::cache_ttl_hlru	(	const Matrix< T > &	lambda,
		const std::vector< int > &	m )

TTL (characteristic-time) approximation of an h-LRU / LRU(m) cache.

Parameters

lambda	(u x n) per-user per-item request rates
m	(h) list capacities

Returns: (n x (h+1)); column 0 is "not cached", column 1+l is "in list l"

Definition at line 56 of file cache_ttl_hlru.h.

References cache_ttl_hlru(), line::Matrix< T >::cols(), line::Matrix< T >::empty(), line::InputError::InputError(), and line::Matrix< T >::rows().

Referenced by cache_ttl_hlru(), and line::mva::solver_mva_cache_analyzer().

◆ cache_ttl_lrua()

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.

Parameters

lambda	(n x h+1) request rate of each item while it is at each node; column 0 is the rate while not cached
R	(n) access graphs, each (h+1 x h+1)
m	(h) list capacities
tol	relative tolerance on the characteristic times
maxswp	cap on Gauss-Seidel sweeps

Returns: (n x h+1) time-stationary probabilities; column 0 is "not cached"

Definition at line 156 of file cache_ttl_lrua.h.

References cache_ttl_lrua(), line::Matrix< T >::cols(), line::InputError::InputError(), line::num_abs(), line::NumericError::NumericError(), line::RootResult< T >::root, line::root_bisect(), and line::Matrix< T >::rows().

Referenced by cache_ttl_lrua(), line::da::da_cacheqn_itemprob(), and line::mva::solver_mva_cache_analyzer().

◆ cache_ttl_lrum_map()

template<class T>

CacheTtlLrumMapResult< T > line::cache::cache_ttl_lrum_map	(	const std::vector< mam::Map< T > > &	items,
		const std::vector< T > &	m,
		const T &	tol )

TTL approximation of an LRU(m) cache whose items are requested by Markovian arrival processes.

Parameters

items	(n) per-item request MAPs
m	(h) list capacities
tol	relative tolerance passed to cache_t_lrum_map

Definition at line 63 of file cache_ttl_lrum_map.h.

References cache_lrum_map_levelstats(), cache_t_lrum_map(), cache_ttl_lrum_map(), line::cache::CacheLrumMapLevelStats< T >::hitfrac, line::Matrix< T >::Matrix(), line::cache::CacheTtlLrumMapResult< T >::pij, line::cache::CacheTtlLrumMapResult< T >::pijtime, line::cache::CacheLrumMapLevelStats< T >::prob, and line::cache::CacheTtlLrumMapResult< T >::t.

Referenced by cache_ttl_lrum_map().

◆ cache_xi_fp()

template<class T>

CacheXiFpResult< T > line::cache::cache_xi_fp	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Lagrange multipliers of a multi-list cache by fixed-point iteration.

Parameters

gamma	(n x h) access factors
m	(h) list capacities

Definition at line 65 of file cache_xi_fp.h.

References cache_xi_fp(), line::Matrix< T >::cols(), line::InputError::InputError(), line::cache::CacheXiFpResult< T >::it, line::num_abs(), line::NumericError::NumericError(), line::cache::CacheXiFpResult< T >::pi0, line::cache::CacheXiFpResult< T >::pij, line::Matrix< T >::rows(), and line::cache::CacheXiFpResult< T >::xi.

Referenced by cache_miss_fpi(), cache_prob_fpi(), and cache_xi_fp().

◆ cache_xi_iter()

template<class T>

std::vector< T > line::cache::cache_xi_iter	(	const Matrix< T > &	gamma,
		const std::vector< int > &	m )

Lagrange multipliers of a multi-list cache by the Gast-Van Houdt iteration.

Parameters

gamma	(n x h) access factors
m	(h) list capacities

Returns: (h) multipliers xi

Definition at line 79 of file cache_xi_iter.h.

References cache_xi_iter(), line::Matrix< T >::cols(), line::InputError::InputError(), line::num_abs(), line::NumericError::NumericError(), and line::Matrix< T >::rows().

Referenced by cache_spm(), and cache_xi_iter().

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ CacheMissPosRmfResult

Enumeration Type Documentation

◆ CacheCostMode

Function Documentation

◆ cache_cost() [1/2]

◆ cache_cost() [2/2]

◆ cache_cost_pathcheck()

◆ cache_erec() [1/2]

◆ cache_erec() [2/2]

◆ cache_gamma()

◆ cache_gamma_lp()

◆ cache_is() [1/3]

◆ cache_is() [2/3]

◆ cache_is() [3/3]

◆ cache_lrum_map_levelstats()

◆ cache_miss() [1/2]

◆ cache_miss() [2/2]

◆ cache_miss_asy() [1/2]

◆ cache_miss_asy() [2/2]

◆ cache_miss_fifo_rmf()

◆ cache_miss_fifo_rmf_transient()

◆ cache_miss_fpi()

◆ cache_miss_is() [1/3]

◆ cache_miss_is() [2/3]

◆ cache_miss_is() [3/3]

◆ cache_miss_rmf() [1/3]

◆ cache_miss_rmf() [2/3]

◆ cache_miss_rmf() [3/3]

◆ cache_miss_rmf_expansion_transient()

◆ cache_miss_rmf_index()

◆ cache_miss_rmf_transient()

◆ cache_miss_sfifo_rmf()

◆ cache_miss_sfifo_rmf_transient()

◆ cache_miss_spm()

◆ cache_mva()

◆ cache_mva_miss()

◆ cache_prob_erec() [1/2]

◆ cache_prob_erec() [2/2]

◆ cache_prob_fpi()

◆ cache_prob_is() [1/3]

◆ cache_prob_is() [2/3]

◆ cache_prob_is() [3/3]

◆ cache_prob_spm()

◆ cache_rmf_lna()

◆ cache_rrm_meanfield() [1/2]

◆ cache_rrm_meanfield() [2/2]

◆ cache_rrm_meanfield_ode()

◆ cache_spm()

◆ cache_spm_size()

◆ cache_t_hlru()

◆ cache_t_lrum_map()

◆ cache_ttl_hlru()

◆ cache_ttl_lrua()

◆ cache_ttl_lrum_map()

◆ cache_xi_fp()

◆ cache_xi_iter()