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:
Miss probability:
cache_miss(),cache_miss_fpi(),cache_miss_spm(),cache_mva_miss()Hit probability:
cache_prob_erec(),cache_prob_fpi(),cache_prob_spm()TTL caches:
cache_ttl_hlru(),cache_ttl_lrua(),cache_ttl_lrum()Mean-field methods:
cache_rrm_meanfield(),cache_rrm_meanfield_ode()Characteristic time:
cache_t_hlru(),cache_t_lrum()MVA-based analysis:
cache_mva(),cache_spm()
Cache modeling algorithms and analysis functions.
This module provides low-level functions for analyzing cache systems, including miss ratios, replacement policies, and performance metrics for various cache configurations.
These functions are primarily used internally by higher-level cache models and solvers.
- cache_mva(gamma, m)[source]
Mean Value Analysis for cache systems.
Computes cache performance metrics using MVA approach.
- Parameters:
gamma – Request rate matrix.
m – Cache size parameters.
- Returns:
- (pi, pi0, pij, x, u, E) containing steady-state probabilities,
throughputs, utilizations, and error metrics.
- Return type:
- cache_prob_asy(gamma, m)[source]
Compute asymptotic cache miss probabilities.
- Parameters:
gamma – Request rate matrix.
m – Cache size parameters.
- Returns:
Asymptotic miss probabilities.
- Return type:
- cache_gamma_lp(lambda_array, R)[source]
Linear programming method for cache analysis using gamma parameters.
This function solves cache performance analysis using linear programming optimization techniques to compute hit probabilities and performance metrics.
- Parameters:
lambda_array – Array of arrival rate matrices for different cache levels.
R – 2D array of cache replacement rate matrices.
- Returns:
Cache performance metrics from the linear programming solution.
- cache_spm(gamma, m)[source]
Singular perturbation method for cache system analysis.
This function performs rayint (singular perturbation) analysis to compute cache performance and hit probabilities using specified gamma and m parameters.
- Parameters:
gamma – Gamma parameter matrix.
m – Cache configuration parameter matrix.
- Returns:
- (Z, lZ, xi) where:
Z: Normalization constant
lZ: Log normalization constant
xi: State probability matrix
- Return type:
- cache_xi_fp(gamma, m, xi=None)[source]
Fixed point iteration method for cache analysis.
This function uses fixed point iteration to solve for cache state probabilities and performance metrics.
- Parameters:
gamma – Gamma parameter matrix.
m – Cache configuration parameter matrix.
xi – Optional initial state probability matrix for iteration.
- Returns:
Cache performance metrics from fixed point iteration.
- cache_prob_erec(gamma, m)[source]
Compute cache miss probabilities using Exact Recursion method.
Estimates cache miss probabilities using the EREC (Exact Recursion) algorithm for LRU-based cache policies.
- Parameters:
gamma – Request rate matrix.
m – Cache size parameters.
- Returns:
Miss probabilities for each cache level.
- Return type:
- cache_prob_fpi(gamma, m)[source]
Compute cache miss probabilities using Fixed Point Iteration.
Uses fixed point iteration to compute steady-state miss probabilities for hierarchical cache systems with LRU replacement policies.
- Parameters:
gamma – Request rate matrix.
m – Cache size parameters.
- Returns:
Miss probabilities computed via FPI.
- Return type:
- cache_prob_spm(gamma, m)[source]
Compute cache miss probabilities using singular perturbation method.
Applies rayint (singular perturbation) method to compute miss probabilities for cache systems, providing accurate results for hierarchical cache configurations.
- Parameters:
gamma – Request rate matrix.
m – Cache size parameters.
- Returns:
Miss probabilities computed via singular perturbation.
- Return type:
- cache_erec(parameters)[source]
Exact Recursion algorithm for cache analysis.
Implements EREC (Exact Recursion) algorithm for analyzing cache replacement policies with precise computational methods.
- Parameters:
parameters – Configuration parameters (dict or matrix).
- Returns:
Performance metrics or numerical result from EREC computation.
- cache_t_hlru(lambda_rates, capacities, n_levels=2)[source]
Compute characteristic times for H-LRU cache replacement policy.
- Parameters:
lambda_rates – Request arrival rates matrix.
capacities – Cache capacity vector.
n_levels – Number of cache levels (default: 2).
- Returns:
Characteristic time values for each cache level.
- cache_t_lrum(lambda_rates, capacity, m_parameter=1)[source]
Compute characteristic times for LRU-M cache replacement policy.
- Parameters:
lambda_rates – Request arrival rates matrix.
capacity – Cache capacity.
m_parameter – LRU-M parameter (default: 1).
- Returns:
Characteristic time values.
- cache_t_lrum_map(MAP, capacity, m_parameter=1)[source]
Analyze cache performance with TTI-LRU policy for MAP request arrivals.
Computes cache performance metrics for a Time-To-Idle Least Recently Used (TTI-LRU) cache replacement policy with requests arriving according to a Markovian Arrival Process (MAP).
- Parameters:
MAP – Request arrival process as tuple (D0, D1) or MAP container {D0, D1}
capacity – Cache capacity (number of items that can be stored)
m_parameter – TTI-LRU specific parameter controlling idle time threshold (default: 1)
- Returns:
Cache performance metrics including hit rates, miss rates, and other statistics
Note
TTI-LRU (Time-To-Idle LRU) is a cache replacement policy that evicts items based on both recency and idle time considerations.
- cache_ttl_hlru(lambda_rates, capacities, ttl_values)[source]
Time-to-live analysis for hierarchical LRU cache.
- Parameters:
lambda_rates – Request rates for cache items
capacities – Cache capacities at each level
ttl_values – Time-to-live values for cache items
- Returns:
Cache performance metrics with TTL effects
- cache_ttl_lrua(lambda_rates, capacity, alpha=1.0)[source]
Time-to-live analysis for LRU-A cache policy.
- Parameters:
lambda_rates – Request rates for cache items
capacity – Cache capacity
alpha – Alpha parameter for LRU-A policy (default: 1.0)
- Returns:
Cache performance metrics with TTL effects
- cache_ttl_lrum(lambda_rates, capacity, m_parameter=1)[source]
Time-to-live analysis for LRU-M cache policy.
- Parameters:
lambda_rates – Request rates for cache items
capacity – Cache capacity
m_parameter – M parameter for LRU-M policy (default: 1)
- Returns:
Cache performance metrics with TTL effects
- cache_ttl_lrum_map(MAP, capacity, m_parameter=1)[source]
Analyze cache performance with TTL-LRU-M policy for MAP request arrivals.
Computes cache performance metrics for a Time-To-Live Least Recently Used with M-parameter (TTL-LRU-M) cache replacement policy with requests arriving according to a Markovian Arrival Process (MAP).
- Parameters:
MAP – Request arrival process as tuple (D0, D1) or MAP container {D0, D1}
capacity – Cache capacity (number of items that can be stored)
m_parameter – TTL-LRU-M specific parameter controlling eviction behavior (default: 1)
- Returns:
Cache performance metrics including hit rates, miss rates, and statistics
- Return type:
Note
TTL-LRU-M combines time-to-live expiration with LRU replacement, where the m_parameter controls the eviction threshold behavior.
- cache_ttl_tree(lambda_rates, tree_structure, capacities)[source]
Time-to-live analysis for tree-structured cache.
- Parameters:
lambda_rates – Request rates for cache items
tree_structure – Tree structure specification
capacities – Cache capacities at tree nodes
- Returns:
Cache performance metrics for tree structure with TTL
- cache_xi_bvh(lambda_rates, capacity, bvh_params)[source]
Cache analysis with bounded virtual heap parameters.
- Parameters:
lambda_rates – Request rates for cache items
capacity – Cache capacity
bvh_params – Bounded virtual heap parameters
- Returns:
Cache performance metrics with BVH effects
- cache_erec_aux(gamma, m, k)[source]
Auxiliary function for Exact Recursion cache analysis.
Helper function for the EREC (Exact Recursion) algorithm, handling specific parameter configurations.
- Parameters:
gamma – Cache request rate matrix.
m – Cache size configuration.
k – Auxiliary parameter for computation.
- Returns:
Auxiliary computation results.
- Return type:
- cache_gamma(rates, routing)[source]
Computes cache access factors from request arrival rates and routing matrices.
- Parameters:
rates – Arrival rates vector
routing – Routing probability matrix
- Returns:
Cache access factors (gamma values)
- Return type:
- cache_miss_fpi(cache_size, access_probs, replacement_policy='lru')[source]
Computes cache miss probabilities using fixed-point iteration methods.
- Parameters:
cache_size – Size of the cache
access_probs – Item access probabilities
replacement_policy – Cache replacement policy (default: ‘lru’)
- Returns:
Miss probabilities per item
- Return type:
- cache_rrm_meanfield_ode(cache_size, access_rates, time_horizon)[source]
Implements the mean field ordinary differential equation system for Random Replacement Model (RRM) cache analysis.
- Parameters:
cache_size – Size of the cache
access_rates – Item access rates
time_horizon – Time horizon for ODE solution
- Returns:
ODE solution with time points and state probabilities
- Return type:
- cache_rayint(cache_size, access_probs, num_items=None)[source]
Implements ray integration techniques for cache system analysis.
Uses ray method for solving partial differential equations to analyze cache behavior and compute steady-state probabilities.
- Parameters:
cache_size – Cache capacity.
access_probs – Item access probabilities.
num_items – Number of items (optional, defaults to length of access_probs).
- Returns:
Ray integration analysis results.
- Return type:
- cache_miss_rayint(cache_size, access_probs, replacement_policy='lru')[source]
Estimates cache miss rates using ray method for partial differential equations.
Applies ray integration techniques to compute miss probabilities for different cache replacement policies.
- Parameters:
cache_size – Cache capacity.
access_probs – Item access probabilities.
replacement_policy – Cache replacement policy (‘lru’, ‘fifo’, ‘random’).
- Returns:
Miss rate and analysis results.
- Return type:
- cache_prob_rayint(cache_size, access_probs, initial_state=None)[source]
Computes cache state probabilities using ray integration methods.
Solves the steady-state probability distribution using ray techniques for analyzing cache occupancy and state transitions.
- Parameters:
cache_size – Cache capacity.
access_probs – Item access probabilities.
initial_state – Initial cache state (optional).
- Returns:
State probabilities and convergence metrics.
- Return type: