 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
Refined mean field (RMF) miss rates of a multi-list RANDOM(m) cache. More...
#include <algorithm>#include <cmath>#include <complex>#include <cstddef>#include <limits>#include <type_traits>#include <vector>#include "line/num/number.h"#include "line/util/error.h"#include "line/util/eig.h"#include "line/util/linalg.h"#include "line/util/lu.h"#include "line/util/matrix.h"#include "line/util/lsoda.h"#include "line/util/ode.h"#include "line/util/sylvester.h"#include "line/api/cache/cache_sojourn.h"Go to the source code of this file.
Classes | |
| struct | line::cache::CacheMissRmfResult< T > |
| Return value of cache_miss_rmf, mirroring [M,MU,MI,pi0,tout,pi0_t,MU_t,xtraj]. More... | |
| struct | line::cache::CacheRmfExpansionTransient< T > |
| Result of cache_miss_rmf_expansion_transient. More... | |
Namespaces | |
| namespace | line |
| Conservation laws of a layered queueing network, enumerated from its structure. | |
| namespace | line::cache |
Functions | |
| std::size_t | line::cache::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 > | 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. | |
| 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. | |
| 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. | |
| 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, const std::vector< std::vector< Matrix< T > > > &accost, const CacheSojournClock< T > &clk=CacheSojournClock< T >()) |
| 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> | |
| 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, const CacheSojournClock< T > &clk=CacheSojournClock< T >()) |
| cache_miss_rmf_transient on the linear chain, i.e. | |
| 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. | |
Refined mean field (RMF) miss rates of a multi-list RANDOM(m) cache.
Templated port of matlab/src/api/cache/cache_miss_rmf.m, including its nested rmf_drift, rmf_jacobian, rmf_hessian, rmf_noise_matrix, rmf_fixed_point, rmf_dimension_reduction and rmf_expansion_steady_state.
The model is a density dependent population process (DDPP) whose state x(i,k) is the probability that item i sits in list k, k = 0 meaning "not cached". A request for item i in list k promotes it to list k+1 and demotes a uniformly chosen occupant of list k+1, so the drift is
flow(i,k) = p(i) x(i,k) - hit(k) x(i,k+1) / m(k+1), dx(i,k)/dt -= flow(i,k), dx(i,k+1)/dt += flow(i,k), hit(k) = sum_j p(j) x(j,k),
for k = 0..h-1. The mean-field fixed point pi is the t -> infinity limit of that drift, and Gast's refinement adds the 1/N correction
E[X] = pi + V/N + O(1/N^2), V = -(F')^-1 (1/2) sum_{b,c} F''_{bc} W_bc,
with W the solution of the Lyapunov equation F' W + W F'^T + Q = 0 and Q the noise intensity of the DDPP. Reference: N. Gast, "Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate", POMACS 2017.
WHAT UNBLOCKED THIS. The fixed point is reached by integrating the drift to t = 1e4, which MATLAB does with ode15s. The drift is stiff: the per-item request rates p(i) of a Zipf-like popularity profile span several orders of magnitude, so the fast items equilibrate in O(1/p_max) while the slow ones need O(1/p_min), and an explicit integrator would be pinned to the fast scale for the whole horizon. The port now has line/util/ode.h, an adaptive Rosenbrock-4 with an embedded lower-order estimate, and this file uses it. The Jacobian is supplied analytically (rmf_jacobian is needed for the refinement anyway), so the integrator never forms a numeric one here.
ALIGNMENT WITH THE REFERENCE. The fixed point is the single ode15s-style integration at RelTol 1e-8 / AbsTol 1e-10 over [0, tmax] that rmf_fixed_point performs (an earlier edition of this port polished it with a second pass at 1e-13 / 1e-16, which is no longer done), and the rank of the Jacobian is decided by a threshold of 1e-8 relative to sigma_1, the rule MATLAB, the JAR and python also use since BUG-102 (2026-10-06): rank()'s max(size) * eps(sigma_1) flipped on ULP-level changes of lambda, because the 1e-10 fixed point lifts one exact null direction to a singular value of that order, while the nonzero ones are O(0.1). Both choices are what makes the port return the reference's answer, including on the cases where the reference's refinement comes out non-finite and cache_miss_rmf.m silently keeps the plain mean-field fixed point: the port now takes the same branch there, which the result's refined flag reports. The one remaining difference is in the basis of the null space: LAPACK's SVD at T = double (the same quantity MATLAB reads out of svd(Fp)) and a pivoted elimination plus Gram-Schmidt at any other T. Only the SUBSPACE affects the result: writing C = [C1; C2], the block C1 Fp D1 that the reduction keeps depends on C2 only through ker(C2), and the expansion V = D1 V_r likewise, so any basis of the same subspace gives the same V. The LNA stationary covariance of the occupancy (rmf_lna_covariance) is returned as Wcov at T = double, empty when it is not computable or not finite, exactly as the reference's try/catch leaves it. MEASURED AGREEMENT (MATLAB R2025a, T = double), global miss rate M, as recorded for the earlier edition of this port: lambda = [0.5 0.3 0.15 0.05; 0.1 0.2 0.3 0.4] (2 users, 4 items) m = [2] MATLAB 0.992377021789716 m = [1 2] MATLAB 0.490863272756674 lambda = [49 49 49 49 7 1 1]/205 (1 user, 7 items) m = [1 1 3] MATLAB 0.024017720168154 m = [3] MATLAB 0.348362022568998 (refinement rejected as non-finite) When the reduced Jacobian is singular – a small or non-hyperbolic fixed point – MATLAB's linear solves emit a warning and return non-finite entries, which cache_miss_rmf.m detects and discards, keeping the plain mean-field fixed point. The port raises NumericError from the same solves and catches it in the same place, with the same outcome; the result carries a refined flag saying which of the two was used, which the reference does not expose.
ARITHMETIC. Gated: the fixed point is reached by a tolerance-driven integration, so it is an approximation in any arithmetic.
COST. The Hessian is a dense model_dim^3 tensor and the Lyapunov solve is a dense rk^2 by rk^2 system, exactly as in the reference. With n items and h lists model_dim = n(h+1), so the refinement is practical for tens of items and quickly stops being so; the plain mean-field path has no such limit.
Definition in file cache_miss_rmf.h.
1.18.0