Cache Algorithms

Cache replacement policies and performance analysis.

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

Function List

• cache_erec - Recursive computation of the normalizing constant for cache models
• cache_gamma_lp - Computes gamma parameters for cache models using linear programming
• cache_miss_fpi - Computes miss rates using fixed-point iteration
• cache_miss - Cache miss rate computation
• cache_miss_spm - Computes miss rates using saddle-point method
• cache_mva - Exact Mean Value Analysis for caches
• cache_mva_miss - Computes miss rates using Mean Value Analysis
• cache_prob_erec - Computes cache hit probabilities using recursive method
• cache_prob_fpi - Computes cache hit probabilities using fixed-point iteration
• cache_prob_spm - Computes cache hit probabilities using saddle-point method
• cache_rrm_meanfield_ode - ODE function for RRM mean-field cache dynamics
• cache_spm - Computes normalizing constant using saddle-point method
• cache_t_hlru - Computes characteristic times for hierarchical LRU cache levels
• cache_t_lrum - Computes characteristic times for LRU(m) cache levels
• cache_ttl_hlru - Computes steady-state probabilities for TTL-based hierarchical LRU cache
• cache_ttl_lrua - Computes steady-state probabilities for TTL-LRU cache with arrivals
• cache_ttl_lrum - Computes steady-state probabilities for TTL-based LRU(m) cache
• cache_xi_fp - Fixed-point iteration for computing cache performance metrics
• cache_xi_iter - Computes Lagrange multipliers using Gast-van Houdt fixed-point iteration

cache_erec

Description: Recursive computation of the normalizing constant for cache models

Syntax:

cache_erec(...)

cache_gamma_lp

Description: Computes gamma parameters for cache models using linear programming

Syntax:

[gamma, u, n, h] = cache_gamma_lp(lambda, R)

Parameters:

Name	Description
lambda	Arrival rate(s)
R	Number of classes or R matrix

Returns:

Name	Description
gamma	Item popularity or rate parameters
u	Utilization or solution vector
n	Number of items, nodes, or states
h	Number of hierarchies or layers

cache_miss_fpi

Description: Computes miss rates using fixed-point iteration

Syntax:

[M, MU, MI, pi0] = cache_miss_fpi(gamma, m, lambda)

Parameters:

Name	Description
gamma	Item popularity probabilities
m	Cache capacity
lambda	Arrival rate(s)

Returns:

Name	Description
M	Global miss rate
MU	Per-user miss rate
MI	Per-item miss rate
pi0	Per-item miss probability

cache_miss

Description: Cache miss rate computation

Syntax:

[M, MU, MI, pi0] = cache_miss(gamma, m, lambda)

Parameters:

Name	Description
gamma	Item popularity probabilities
m	Cache capacity
lambda	Arrival rate(s)

Returns:

Name	Description
M	Global miss rate
MU	Per-user miss rate
MI	Per-item miss rate
pi0	Per-item miss probability

cache_miss_spm

Description: Computes miss rates using saddle-point method

Syntax:

[M, MU, MI, pi0, lE] = cache_miss_spm(gamma, m, lambda)

Parameters:

Name	Description
gamma	Item popularity probabilities
m	Cache capacity
lambda	Arrival rate(s)

Returns:

Name	Description
M	Global miss rate
MU	Per-user miss rate
MI	Per-item miss rate
pi0	Per-item miss probability
lE	Logarithm of partition function

cache_mva

Description: Exact Mean Value Analysis for caches

Syntax:

[pi, pi0, pij, x, u, E] = cache_mva(gamma, m)

Parameters:

Name	Description
gamma	Item popularity probabilities
m	Cache capacity

Returns:

Name	Description
pi	Steady-state probability distribution
pi0	Per-item miss probability
pij	Pairwise probabilities
x	State vector or solution
u	Utilization or solution vector
E	Expected value or partition function

cache_mva_miss

Description: Computes miss rates using Mean Value Analysis

Syntax:

[M, Mk] = cache_mva_miss(p, m, R)

Parameters:

Name	Description
p	Probability vector or parameter
m	Cache capacity
R	Number of classes or R matrix

Returns:

Name	Description
M	Global miss rate
Mk	k-th moment

cache_prob_erec

Description: Computes cache hit probabilities using recursive method

Syntax:

cache_prob_erec(...)

cache_prob_fpi

Description: Computes cache hit probabilities using fixed-point iteration

Syntax:

cache_prob_fpi(...)

cache_prob_spm

Description: Computes cache hit probabilities using saddle-point method

Syntax:

cache_prob_spm(...)

cache_rrm_meanfield_ode

Description: ODE function for RRM mean-field cache dynamics

Syntax:

cache_rrm_meanfield_ode(...)

cache_spm

Description: Computes normalizing constant using saddle-point method

Syntax:

[Z, lZ, xi] = cache_spm(gamma, m, xi0)

Parameters:

Name	Description
gamma	Item popularity probabilities
m	Cache capacity
xi0	Initial guess for Lagrange multipliers

Returns:

Name	Description
Z	Think times or partition function
lZ	Logarithm of partition function
xi	Lagrange multipliers

cache_t_hlru

Description: Computes characteristic times for hierarchical LRU cache levels

Syntax:

cache_t_hlru(...)

cache_t_lrum

Description: Computes characteristic times for LRU(m) cache levels

Syntax:

cache_t_lrum(...)

cache_ttl_hlru

Description: Computes steady-state probabilities for TTL-based hierarchical LRU cache

Syntax:

cache_ttl_hlru(...)

cache_ttl_lrua

Description: Computes steady-state probabilities for TTL-LRU cache with arrivals

Syntax:

cache_ttl_lrua(...)

cache_ttl_lrum

Description: Computes steady-state probabilities for TTL-based LRU(m) cache

Syntax:

cache_ttl_lrum(...)

cache_xi_fp

Description: Fixed-point iteration for computing cache performance metrics

Syntax:

[xi, pi0, pij, it] = cache_xi_fp(gamma, m, xi)

Parameters:

Name	Description
gamma	Item popularity probabilities
m	Cache capacity
xi	Lagrange multipliers

Returns:

Name	Description
xi	Lagrange multipliers
pi0	Per-item miss probability
pij	Pairwise probabilities
it	Number of iterations performed

cache_xi_iter

Description: Computes Lagrange multipliers using Gast-van Houdt fixed-point iteration

Syntax:

cache_xi_iter(...)