Cache Algorithms

Cache performance analysis.

The cache module provides algorithms for analyzing cache systems with various replacement policies (LRU, FIFO, RR, etc.) and item popularity distributions.

Key function categories:

Cache Analysis Algorithms.

Native Python implementations for analyzing cache systems, including exact recursive methods, singular perturbation methods, importance sampling, TTL-based caches, and various approximation techniques.

Key algorithms:

cache_erec: Exact recursive normalizing constant cache_prob_erec: Exact recursive state probabilities cache_spm: Singular perturbation method cache_miss: Miss rate computation cache_is: Importance sampling cache_ttl_*: TTL-based cache analysis cache_rrm_*: Random replacement model

cache_erec(gamma, m)[source]

Compute the cache normalizing constant using exact recursive method.

This method serves as a wrapper that calls the auxiliary function to perform the actual computation.

Parameters:

  • gamma (ndarray) – Cache access factors matrix (n x h), where n is number of items and h is number of cache levels.

  • m (ndarray) – Cache capacity vector (1 x h or h,).

Returns:

Normalizing constant E.

Return type:

float

cache_erec_aux(gamma, m, k)[source]

Auxiliary method for computing cache normalizing constant using exact recursive method.

This method performs the core computation recursively, adjusting the size of the input matrix.

Parameters:

  • gamma (ndarray) – Cache access factors matrix (n x h).

  • m (ndarray) – Cache capacity vector (h,).

  • k (int) – Current number of rows in the recursive step.

Returns:

Normalizing constant for the given configuration.

Return type:

float

cache_prob_erec(gamma, m)[source]

Compute cache state probabilities using exact recursive method.

This method calculates the probabilities of the cache being in different states based on the cache access factors and capacity.

Parameters:

  • gamma (ndarray) – Cache access factors matrix (n x h), where n is number of items and h is number of cache levels.

  • m (ndarray) – Cache capacity vector (1 x h or h,).

Returns:

Matrix (n x h+1) containing cache state probabilities. Column 0 is miss probability, columns 1..h are hit probabilities at each cache level.

Return type:

ndarray

cache_mva(gamma, m)[source]

Mean Value Analysis for cache systems.

Computes cache performance metrics using MVA approach.

Parameters:

  • gamma (ndarray) – Request rate matrix (n x h).

  • m (ndarray) – Cache size parameters (h,).

Returns:

  • pi: Steady-state probabilities

  • pi0: Miss probabilities per item

  • pij: Hit probabilities per item per level (n x h)

  • x: Throughput vector

  • u: Utilization vector

  • E: Normalizing constant

Return type:

Tuple of (pi, pi0, pij, x, u, E) containing

cache_xi_iter(gamma, m, tol=1e-12, max_iter=1000)[source]

Compute cache xi terms using iterative method from Gast-van Houdt.

This method calculates the xi values which are important for understanding the distribution of items in the cache. The algorithm assumes that the access factors are monotone with the list index.

Parameters:

  • gamma (ndarray) – Cache access factors matrix (n x h).

  • m (ndarray) – Cache capacity vector (h,).

  • tol (float) – Convergence tolerance (default: 1e-12).

  • max_iter (int) – Maximum iterations (default: 1000).

Returns:

Vector of xi values (h,).

Return type:

ndarray

cache_spm(gamma, m)[source]

Approximate the normalizing constant using SPM method.

Computes the normalizing constant of the cache steady state distribution using the singular perturbation method (also known as ray integration).

Parameters:

  • gamma (ndarray) – Cache access factors matrix (n x h).

  • m (ndarray) – Cache capacity vector (h,).

Returns:

  • Z: Approximated normalizing constant

  • lZ: Log of normalizing constant

  • xi: Xi terms vector

Return type:

Tuple of (Z, lZ, xi) where

cache_prob_spm(gamma, m)[source]

Compute cache miss probabilities using singular perturbation method.

Uses the SPM (ray integration) method to compute miss probabilities for cache systems.

Parameters:

  • gamma (ndarray) – Cache access factors matrix (n x h).

  • m (ndarray) – Cache capacity vector (h,).

Returns:

Vector of miss probabilities for each item.

Return type:

ndarray

cache_prob_fpi(gamma, m, tol=1e-8, max_iter=1000)[source]

Compute cache hit probabilities using fixed point iteration (FPI method).

Matches MATLAB cache_prob_fpi: Uses fixed point iteration to compute cache hit probability distribution.

Parameters:

  • gamma (ndarray) – Cache access factors matrix (n x h).

  • m (ndarray) – Cache capacity vector (h,).

  • tol (float) – Convergence tolerance (unused, kept for API compatibility).

  • max_iter (int) – Maximum iterations (unused, kept for API compatibility).

Returns:

  • Column 0: miss probabilities

  • Columns 1:h: hit probabilities at each level

Return type:

Matrix (n x h+1) where

cache_miss(gamma, m, lambd=None)[source]

Compute miss rates for a cache system using exact recursive method.

Parameters:

  • gamma (ndarray) – Item popularity probabilities (n x h matrix)

  • m (ndarray) – Cache capacity vector (h,)

  • lambd (ndarray | None) – Optional arrival rates per user per item (u x n x h+1)

Returns:

  • M: Global miss rate

  • MU: Per-user miss rate (u,) or None

  • MI: Per-item miss rate (n,) or None

  • pi0: Per-item miss probability (n,) or None

Return type:

Tuple of (M, MU, MI, pi0) where

References

Original MATLAB: matlab/src/api/cache/cache_miss.m

cache_xi_fp(gamma, m, xi_init=None, tol=1e-14, max_iter=10000)[source]

Fixed-point iteration for computing cache performance metrics.

Computes cache performance metrics including Lagrange multipliers, miss probabilities, and hit probabilities.

Parameters:

  • gamma (ndarray) – Item popularity probabilities (n x h)

  • m (ndarray) – Cache capacity vector (h,)

  • xi_init (ndarray | None) – Optional initial guess for Lagrange multipliers

  • tol (float) – Convergence tolerance (default: 1e-14)

  • max_iter (int) – Maximum iterations (default: 10000)

Returns:

  • xi: Converged Lagrange multipliers (h,)

  • pi0: Miss probability per item (n,)

  • pij: Hit probability per item per list (n x h)

  • it: Number of iterations

Return type:

Tuple of (xi, pi0, pij, it) where

References

Original MATLAB: matlab/src/api/cache/cache_xi_fp.m

cache_miss_fpi(gamma, m, lambd=None)[source]

Compute cache miss rates using fixed-point iteration method.

Parameters:

  • gamma (ndarray) – Item popularity probabilities (n x h)

  • m (ndarray) – Cache capacity vector (h,)

  • lambd (ndarray | None) – Optional arrival rates per user per item (u x n x h+1)

Returns:

  • M: Global miss rate

  • MU: Per-user miss rate or None

  • MI: Per-item miss rate or None

  • pi0: Per-item miss probability or None

Return type:

Tuple of (M, MU, MI, pi0) where

References

Original MATLAB: matlab/src/api/cache/cache_miss_fpi.m

cache_miss_spm(gamma, m, lambd=None)[source]

Compute cache miss rates using saddle-point method.

Parameters:

  • gamma (ndarray) – Item popularity probabilities (n x h)

  • m (ndarray) – Cache capacity vector (h,)

  • lambd (ndarray | None) – Optional arrival rates per user per item (u x n x h+1)

Returns:

  • M: Global miss rate

  • MU: Per-user miss rate or None

  • MI: Per-item miss rate or None

  • pi0: Per-item miss probability or None

  • lE: Log of normalizing constant

Return type:

Tuple of (M, MU, MI, pi0, lE) where

References

Original MATLAB: matlab/src/api/cache/cache_miss_spm.m

cache_mva_miss(p, m, R)[source]

Compute cache miss rates using Mean Value Analysis.

Parameters:

  • p (ndarray) – Item popularity probabilities (n,)

  • m (ndarray) – Cache capacity vector (h,)

  • R (ndarray) – Routing probabilities (h+1 x n)

Returns:

  • M: Global miss rate

  • Mk: Per-item miss rate (n,)

Return type:

Tuple of (M, Mk) where

References

Original MATLAB: matlab/src/api/cache/cache_mva_miss.m

cache_is(gamma, m, samples=100000)[source]

Importance sampling estimation of cache normalizing constant.

Estimates the normalizing constant for cache models using Monte Carlo importance sampling.

Parameters:

  • gamma (ndarray) – Item popularity probabilities (n x h matrix)

  • m (ndarray) – Cache capacity vector (h,)

  • samples (int) – Number of Monte Carlo samples (default: 100000)

Returns:

  • E: Normalizing constant estimate

  • lE: Log of normalizing constant

Return type:

Tuple of (E, lE) where

References

Original MATLAB: matlab/src/api/cache/cache_is.m

cache_prob_is(gamma, m, samples=100000)[source]

Importance sampling estimation of cache hit probabilities.

Estimates cache hit probability distribution using Monte Carlo importance sampling.

Parameters:

  • gamma (ndarray) – Item popularity probabilities (n x h matrix)

  • m (ndarray) – Cache capacity vector (h,)

  • samples (int) – Number of Monte Carlo samples (default: 100000)

Returns:

prob[i, 0] = miss probability for item i prob[i, 1+j] = hit probability for item i at level j

Return type:

Cache hit probability matrix (n x h+1)

References

Original MATLAB: matlab/src/api/cache/cache_prob_is.m

cache_miss_is(gamma, m, lambd=None, samples=100000)[source]

Importance sampling estimation of cache miss rates.

Computes global, per-user, and per-item miss rates using Monte Carlo importance sampling.

Parameters:

  • gamma (ndarray) – Item popularity probabilities (n x h matrix)

  • m (ndarray) – Cache capacity vector (h,)

  • lambd (ndarray | None) – Optional arrival rates per user per item (u x n x h+1)

  • samples (int) – Number of Monte Carlo samples (default: 100000)

Returns:

  • M: Global miss rate

  • MU: Per-user miss rate or None

  • MI: Per-item miss rate or None

  • pi0: Per-item miss probability or None

  • lE: Log of normalizing constant

Return type:

Tuple of (M, MU, MI, pi0, lE) where

References

Original MATLAB: matlab/src/api/cache/cache_miss_is.m

logmeanexp(x)[source]

Compute log(mean(exp(x))) in a numerically stable way.

Uses the log-sum-exp trick for numerical stability.

cache_t_lrum(gamma, m)[source]

Compute characteristic times for LRU(m) cache levels.

Uses fixed-point iteration (fsolve) to compute the characteristic time for each level of an LRU(m) cache.

Parameters:

  • gamma (ndarray) – Item popularity probabilities or arrival rates (n x h)

  • m (ndarray) – Cache capacity vector (h,)

Returns:

Characteristic time for each cache level (h,)

Return type:

ndarray

References

Original MATLAB: matlab/src/api/cache/cache_t_lrum.m

cache_t_hlru(gamma, m)[source]

Compute characteristic times for hierarchical LRU cache levels.

Uses fixed-point iteration (fsolve) to compute the characteristic time for each level of a hierarchical LRU cache.

Parameters:

  • gamma (ndarray) – Item popularity probabilities or arrival rates (n x h)

  • m (ndarray) – Cache capacity vector (h,)

Returns:

Characteristic time for each cache level (h,)

Return type:

ndarray

References

Original MATLAB: matlab/src/api/cache/cache_t_hlru.m

cache_ttl_lrum(gamma, m)[source]

Compute steady-state probabilities for TTL-based LRU(m) cache.

Parameters:

  • gamma (ndarray) – Arrival rates per item per list. Can be (n x h) or (1 x n x h+1). If 3D, uses gamma[0, :, 1:] as the (n x h) input.

  • m (ndarray) – Cache capacity vector (h,)

Returns:

prob[:, 0] = miss probability prob[:, 1:] = hit probability at each level

Return type:

Steady-state probability distribution (n x h+1)

References

Original MATLAB: matlab/src/api/cache/cache_ttl_lrum.m

cache_ttl_hlru(gamma, m)[source]

Compute steady-state probabilities for TTL-based hierarchical LRU cache.

Parameters:

  • gamma (ndarray) – Arrival rates per item per list. Can be (n x h) or (1 x n x h+1). If 3D, uses gamma[0, :, 1:] as the (n x h) input.

  • m (ndarray) – Cache capacity vector (h,)

Returns:

prob[:, 0] = miss probability prob[:, 1] = hit probability at level h

Return type:

Steady-state probability distribution (n x 2)

References

Original MATLAB: matlab/src/api/cache/cache_ttl_hlru.m

cache_ttl_lrua(lambd, R, m, seed=23000)[source]

Compute steady-state probabilities for TTL-LRU cache with arrival routing.

Uses fixed-point iteration with DTMC solving for cache systems with multiple users, items, and levels with routing.

Parameters:

  • lambd (ndarray) – Arrival rates per user per item per list (u x n x h+1)

  • R (list) – Routing probability structure (list of n matrices, each (h+1 x h+1))

  • m (ndarray) – Cache capacity vector (h,)

  • seed (int) – Random seed for initialization (default: 23000)

Returns:

Steady-state probability distribution (n x h+1)

Return type:

ndarray

References

Original MATLAB: matlab/src/api/cache/cache_ttl_lrua.m

cache_rrm_meanfield_ode(t, x, lambd, m, n, h)[source]

ODE function for RRM mean-field cache dynamics.

Defines the differential equations for the Random Replacement Model mean-field cache dynamics.

Parameters:

  • t (float) – Time variable (unused, for ODE solver compatibility)

  • x (ndarray) – State vector of length n*(h+1), representing probabilities

  • lambd (ndarray) – Arrival rates per item (n,)

  • m (ndarray) – Cache capacity vector (h,)

  • n (int) – Number of items

  • h (int) – Number of cache levels

Returns:

Time derivative of state vector

Return type:

ndarray

References

Original MATLAB: matlab/src/api/cache/cache_rrm_meanfield_ode.m

cache_rrm_meanfield(lambd, m, t_end=10000.0, seed=23000)[source]

Solve RRM mean-field steady state using ODE integration.

Computes the steady-state probability distribution for a cache with random replacement policy using mean-field ODE dynamics.

Parameters:

  • lambd (ndarray) – Arrival rates per item (n,)

  • m (ndarray) – Cache capacity vector (h,)

  • t_end (float) – End time for ODE integration (default: 10000.0)

  • seed (int) – Random seed for initial conditions (default: 23000)

Returns:

  • prob: Steady-state probability matrix (n x h+1)

  • missrate: Global miss rate (lambda * miss_prob)

  • missratio: Miss ratio (missrate / sum(lambda))

Return type:

Tuple of (prob, missrate, missratio) where

References

Original MATLAB: matlab/src/api/cache/cache_rrm_meanfield.m

cache_gamma_lp(lambd, R)[source]

Compute gamma parameters for cache models using linear programming approach.

Computes item popularity probabilities at each cache level based on arrival rates and routing probabilities.

Parameters:

  • lambd (ndarray) – Arrival rates per user per item per list (u x n x h+1)

  • R (list) – Routing probability structure (list of lists, R[v][i] is matrix for user v, item i)

Returns:

  • gamma: Item popularity probabilities at each level (n x h)

  • u: Number of users

  • n: Number of items

  • h: Number of cache levels

Return type:

Tuple of (gamma, u, n, h) where

References

Original MATLAB: matlab/src/api/cache/cache_gamma_lp.m