api.retrieval

retrieval_rayint(gamma, m, n, nquad)

Approximates the cache normalizing constant E(m) by the ray/eikonal expansion

Evaluates the geometrical-optics (WKB) asymptotic expansion of the normalizing constant computed exactly by cache_erec, and returns it in the SAME normalization, so that the two are interchangeable:

E(m,n) = E(m,n-1) + sum_j gamma_{n,j} m_j E(m-1_j,n-1), E(0,0)=1

Writing E = prod_j m_j! * Et, the relaxation Et ~ H exp(phi/eps) with n = y/eps and m_j = x_j/eps turns the recursion into the eikonal equation e^{phi_y} = 1 + sum_j gamma_j(y) e^{-phi_j}, whose rays carry constants xi_j = e^{-phi_j}. With S(v) = 1 + sum_j gamma_j(v) xi_j the solution is

x_j = int_0^y gamma_j(v) xi_j / S(v) dv (the saddle conditions) phi = int_0^y log S(v) dv - sum_j x_j log xi_j H = (2 pi)^{-h/2} sqrt(S(y)/S(0)) / sqrt(prod_j xi_j * det A) A_{ik} = d x_i / d xi_k

and E ~ prod_j m_j! * eps^{h/2} H exp(phi/eps). Two evaluations are offered, selected by the type of the first argument.

DISCRETE (gamma given as an n x h matrix). The ray integrals are the sums they discretize and the expansion collapses to the Laplace form

Et ~ (2 pi)^{-h/2} exp(sum_k log D_k - sum_j m_j log xi_j) / sqrt(det Sigma)

with D_k = 1 + sum_j gamma_{k,j} xi_j, sum_k gamma_{k,j} xi_j / D_k = m_j and Sigma = A * diag(xi) the Hessian in log xi. This is the default and is the more accurate of the two; the sqrt(S(y)/S(0)) factor above is exactly the Euler-Maclaurin term relating sum_k to int dv and is already accounted for.

CONTINUUM (gamma given as a function handle v -> [numel(v) x h] on v in [0,1]). The ray integrals are evaluated by composite Simpson quadrature on the profile itself, which is the form written in the note; it costs roughly a factor two in accuracy relative to the discrete form but does not need the n rows.

ACCURACY. The relative error is O(1/n) at fixed occupancy but is governed by the smallest occupancy rather than by n, tracking 0.14 * ( 1/min_j m_j + 1/(n - sum_j m_j) ), so a per cent needs every m_j and n - sum_j m_j above about 15 and a part in a thousand needs them above about 150. The estimate is returned in OUT.relerrEst. Lists with m_j = 0 contribute nothing and are dropped before the saddle is solved, so they neither degrade the expansion nor make it singular.

This covers the no-fetch (q=0) case, i.e. the same quantity as cache_erec. The delayed-hit extension carrying the fetch coordinates is not implemented: its eikonal is known but its amplitude has not been derived, and a partial amplitude would be silently wrong rather than merely approximate.

Parameters:

• gamma – Access factors gamma(k,j), n x h; or a handle @(v) returning numel(v) x h for v in [0,1]

• m – Cache list capacities, 1 x h

• n – Number of items (required, and used only, with a function handle)

• nquad – (Optional) composite Simpson nodes for the continuum form (default 4097, forced odd)

Returns:

E – Normalizing constant, same normalization as cache_erec (Inf on overflow; use logE) logE: Natural logarithm of E, safe for large n out: Struct with the ray quantities: xi, phi, logdetSigma, S0, Sy, method, relerrEst, iter

See also

cache_erec(), retrieval_nc(), retrieval_mva(), retrieval_fpi()

Examples

E = retrieval_rayint(gamma, m)                 % gamma is n x h
E = retrieval_rayint(gfun, m, n)               % gfun is @(v) -> numel(v) x h
[E, logE, out] = retrieval_rayint(...)
[...] = retrieval_rayint(..., nquad)           % Simpson nodes, continuum form

References

G. Casale, “Accelerating Performance Inference over Closed Systems by Asymptotic Methods”, ACM SIGMETRICS, 2017 (asymptotic expansion of the normalizing constant integral); the ray/eikonal form used here follows the geometrical-optics construction for the RR cache.

cache_retrieval_inputs(sn, lambdaOverride)

Builds the inputs of the retrieval (delayed-hit) analytic algorithms from a model

Given the NetworkStruct of a cache equipped with a retrieval system (Cache.setRetrievalSystem), reconstructs the inputs required by the retrieval_* algorithms (retrieval_nc, retrieval_metrics, retrieval_fpi, retrieval_fpi_latency):

m cache list capacities (1 x h) lambda per-item arrival rates (1 x n) = sourceRate * pread gamma access factors gamma_{i,j} (n x h) via cache_gamma_lp eta fetching demands eta_{s,i} (n x (r+1)) col 1 = IS, cols 2.. = PS alpha cell(1,S); alpha{s}(1,:,i) PH entry vector of item i at station s T cell(1,S); T{s}(:,:,i) PH subgenerator of item i at station s R (S+1) x (S+1) x n routing matrices (index 1 = cache/outside, 2..S+1 = retrieval stations), R(a,b,i) probability a->b for item i station_type (1 x S) string per retrieval station, one of “IS”, “PS”, “SIRO”, “FCFS”, “LCFSPR” (mapped from sn.sched)

The retrieval system is single-class (IRM): exactly one read class may route into the retrieval system. Supported retrieval scheduling policies are IS, PS, SIRO, FCFS and LCFSPR. IS is independent; PS, SIRO, FCFS and LCFSPR use the mean-field sharing slowdown. PS and LCFSPR (symmetric/insensitive BCMP disciplines) admit general phase-type service and class-dependent rates; SIRO and FCFS require exponential service with identical per-class rates. Any other scheduling policy raises an error, matching retrieval_fpi_latency.

Examples

[m,lambda,gamma,eta,alpha,T,R,station_type] = cache_retrieval_inputs(sn)

[…] = CACHE_RETRIEVAL_INPUTS(SN) builds the retrieval-algorithm inputs from an OPEN cache model (per-item rate lambda = sourceRate * pread).

[…] = CACHE_RETRIEVAL_INPUTS(SN, LAMBDAOVERRIDE) uses the supplied read-class arrival rate LAMBDAOVERRIDE (a scalar rate for the single read class) instead of the Source throughput, so the same inputs can be built for a CLOSED integrated cache-queueing sublayer where the read rate comes from the network solution (da_cacheqn_retrieval). All other inputs (gamma, eta, alpha, T, R) are unchanged.

retrieval_fpi_latency(m, lambda, gamma, alpha, T, R, station_type)

Approximates the mean delayed-hit count d_i and expected latency Z

Implements the latency-approximation algorithm of the paper (Appendix “sec:fpi-di”, Algorithm “Approximation procedure of the latency Z”), based on Theorem “thm:di”:

d_i = phi_i * lambda_i * E0[F_i^2] / (2 E0[F_i])

where F_i is the fetch-period duration of item i and E0[.] is the Palm expectation conditioned on a miss. The fetch moments are obtained from a reduced absorbing CTMC of item i’s visits to the retrieval stations:

E0[F_i^k] = k! * pi_e^{(i)} (-D0^{(i)})^{-k} e (eq. moments)

Steps (per the algorithm): 1. FPI on the full system -> phi_i, pi_{i,0} (retrieval_fpi) 2. For each i: FPI without item i -> phi^{(i)}_{s,k}; PS-station occupancy phi~_s^{(i)} = sum_{k!=i} phi^{(i)}_{s,k} 3. Reduced CTMC for item i: one block of PH phases per station; shared stations (PS/SIRO/FCFS/LCFSPR) have their rates slowed by 1/(1+phi~_s^{(i)}) while IS stations stay independent; routing per R; absorption = return to cache. D0^{(i)} = transient subgenerator, pi_e^{(i)} = entry distribution (R(outside->s) * PH-initial). 4. Moments via eq. moments -> d_i via Theorem thm:di. 5. Z = sum_i(phi_i + d_i) / sum_i lambda_i(phi_i + pi_{i,0}) (eq. latency tot)

Routing convention: R is (S+1) x (S+1) x n; index 1 = outside (entry on miss / return to cache on completion), indices 2..S+1 = retrieval stations 1..S; R(a,b,i) is the routing probability from a to b for item i (rows sum to 1).

Parameters:

• m – Cache list capacities (1 x h)

• lambda – Per-item arrival rates (1 x n)

• gamma – Access factors gamma(i,j)=gamma_{i,j}, (n x h)

• alpha – Cell(1,S); alpha{s}(1,:,i) PH entry vector of item i at station s

• T – Cell(1,S); T{s}(:,:,i) PH subgenerator of item i at station s

• R – (S+1) x (S+1) x n routing matrices (index 1 = outside, 2..S+1 = stations)

• station_type – (1 x S) string/cellstr per station, one of “IS”, “PS”, “SIRO”, “FCFS”, “LCFSPR”. PS and LCFSPR (symmetric/insensitive BCMP disciplines) admit general phase-type service and class-dependent rates. SIRO and FCFS require exponential (single-phase) service with identical per-class rates; otherwise an error is raised.

Returns:

Z – Expected latency of the delayed-hit system d: Mean number of delayed hits awaiting fetch, per item (1 x n) phi: Delayed-hit ratio phi_i per item (1 x n) pi0: Miss ratio pi_{i,0} per item (1 x n)

Examples

[Z, d, phi, pi0] = retrieval_fpi_latency(m, lambda, gamma, alpha, T, R, station_type)

retrieval_nc(v, m, lambda, eta, gamma)

Computes the delayed-hit cache normalizing constant E(v,m) by the exact recurrence

This function recursively computes the normalizing constant E(v,m) of a list-based cache with delayed hits, whose retrieval system has one IS station (index s=0) and r PS stations (s=1,…,r), using the exact recurrence relation

E(v,m) = (1 + lambda_k*eta_{0,k}) E_k(v,m) + sum_{s=1}^{r} lambda_k*eta_{s,k}*(v_s+1) E_k(v+1_s, m) + sum_{j=1}^{h} m_j*gamma_{k,j} E_k(v, m-1_j)

where E_k is the same constant for the system without item k. Boundary conditions are E = 1 if there are no items left and E = 0 if sum_j m_j exceeds the number of items or any m_j < 0. The plain normalizing constant is recovered as E(m) = E(0,m).

Parameters:

• v – Moment-order vector for the PS stations (zeros(1,r) for the plain constant)

• m – Cache list capacities

• lambda – Per-item arrival rates

• eta – Fetching demands eta(i,s+1)=eta_{s,i} (column 1 = IS station s=0, columns 2..r+1 = PS stations). A PS column models any symmetric/identical-rate single-server discipline (PS, SIRO, FCFS, LCFS-PR), insensitive to the per-list service order.

• gamma – Access factors gamma(i,j)=gamma_{i,j}

Returns:

E – Normalizing constant E(v,m)

Examples

E = retrieval_nc(v, m, lambda, eta, gamma)

retrieval_mva(m, lambda, eta, gamma)

Computes exact miss, hit and delayed-hit metrics via the MVA recursion

Implements the exact recursive characterization of the paper (Theorems “thm:arvthm” and “thm:pi_xi”, and eq. motivation_to_pi0_FPI) that the FPI heuristic (retrieval_fpi) approximates. For a list-based cache with delayed hits whose retrieval system has one IS station (s=0) and r PS stations (s=1,…,r), with phi^{(k)}_{s,i} the delayed-hit probability of item i at station s in the system WITHOUT item k:

theta_{ij}(m) = gamma_{ij} / (1 + lambda_i eta_{0,i} + sum_{s=1}^r lambda_i eta_{s,i}(1 + sum_{k!=i} phi^{(i)}_{s,k}(m-1_j))) xi_j(m) = m_j / sum_i theta_{ij}(m)(1 - pihit_i(m-1_j)) pi_{ij}(m) = theta_{ij}(m) xi_j(m) (1 - pihit_i(m-1_j)) pihit_i(m) = sum_j pi_{ij}(m) pi_{i0}(m) = (1 - pihit_i(m)) / (1 + lambda_i eta_{0,i} + sum_{s=1}^r lambda_i eta_{s,i}(1 + sum_{k!=i} phi^{(i)}_{s,k}(m))) phi_{sk}(m) = lambda_k pi_{k0}(m) eta_{s,k}(1 + sum_{i!=k} phi^{(k)}_{s,i}(m)) (s=1..r) phi_{0k}(m) = lambda_k eta_{0,k} pi_{k0}(m)

The recursion terminates at the empty item set and at the empty cache (pihit_i = 0). This is exact and agrees with retrieval_nc / retrieval_metrics; it is memoized over (item-subset, capacity) with O(2^n n^2 h r prod_j(1+m_j)) time, so it is feasible only for small systems (use retrieval_fpi otherwise).

Parameters:

• m – Cache list capacities (1 x h)

• lambda – Per-item arrival rates (1 x n)

• eta – Fetching demands eta(i,s+1)=eta_{s,i} (column 1 = IS station s=0, columns 2..r+1 = PS stations), (n x (r+1))

• gamma – Access factors gamma(i,j)=gamma_{i,j}, (n x h)

Returns:

pmiss – Miss ratios pi_{i,0}, (1 x n) phit: Hit ratios pi_{i,j}, (h x n) pdh: Delayed-hit probabilities phi_{s,i} for s=0,…,r, ((r+1) x n)

Examples

[pmiss, phit, pdh] = retrieval_mva(m, lambda, eta, gamma)

retrieval_metrics(m, lambda, eta, gamma)

Computes miss, hit and delayed-hit metrics for a delayed-hit cache

Evaluates the performance measures of Proposition “prop:performance_measures” for a list-based cache with delayed hits whose retrieval system has one IS station (s=0) and r PS stations (s=1,…,r). Letting E(m)=E(0,m) be the normalizing constant and E_i the constant of the system without item i (both computed with retrieval_nc), the metrics are

miss ratio pi_{i,0} = E_i(m)/E(m) hit ratio (list j) pi_{i,j} = m_j*gamma_{i,j}*E_i(m-1_j)/E(m) delayed hit (IS) phi_{0,i} = lambda_i*eta_{0,i}*E_i(m)/E(m) delayed hit (PS s) phi_{s,i} = lambda_i*eta_{s,i}*E_i(1_s,m)/E(m)

These satisfy the balance pi_{i,0} + sum_s phi_{s,i} + sum_j pi_{i,j} = 1 for every item i (eq. balance).

Parameters:

• m – Cache list capacities (1 x h)

• lambda – Per-item arrival rates (1 x n)

• eta – Fetching demands eta(i,s+1)=eta_{s,i} (column 1 = IS station s=0, columns 2..r+1 = PS stations), (n x (r+1)). A PS column models any symmetric/identical-rate single-server discipline (PS, SIRO, FCFS, LCFS-PR), insensitive to the per-list service order.

• gamma – Access factors gamma(i,j)=gamma_{i,j}, (n x h)

Returns:

pmiss – Miss ratios pi_{i,0}, (1 x n) phit: Hit ratios pi_{i,j}, (h x n) pdh: Delayed-hit probabilities phi_{s,i} for s=0,…,r, ((r+1) x n)

Examples

[pmiss, phit, pdh] = retrieval_metrics(m, lambda, eta, gamma)

retrieval_fpi(m, lambda, eta, gamma, max_iter, tol)

Approximates miss, hit and delayed-hit metrics of a delayed-hit cache via FPI

Implements the fixed-point heuristic of the paper (Sec. “Fixed-Point Heuristic”, eqs. theta/xi/pi/pi_0/phi_FPI) for a list-based cache with delayed hits whose retrieval system has one IS station (s=0) and r PS stations (s=1,…,r). The heuristic truncates the regular perturbation expansion at 0th order (pi_{i,l}(m-1_j) ~ pi_{i,l}(m)) and solves the resulting nonlinear system by successive substitution. Iteration t -> t+1:

D_i = 1 + lambda_i*eta_{0,i} + sum_{s=1}^r lambda_i*eta_{s,i}*(1 + sum_{k!=i} phi_{s,k}) theta_{ij} = gamma_{ij} / D_i xi_j = m_j / sum_k theta_{kj} (1 - sum_l pi_{kl}) pi_{ij} = theta_{ij} xi_j / (1 + sum_l theta_{il} xi_l) pi_{i0} = (1 - sum_j pi_{ij}) / D_i phi_{si} = lambda_i*eta_{s,i}*(1 + sum_{k!=i} phi_{s,k}) pi_{i0} (s=1..r) phi_{0i} = lambda_i*eta_{0,i} pi_{i0}

where phi_{s,k} is the delayed-hit probability of item k at PS station s. (The paper writes phi_{r,k} in eqs. theta_FPI/phi_FPI, but the exact recursion it approximates, eq. theta RS, uses the per-station index s; the two coincide for a single PS station.) The solution satisfies the balance pi_{i0} + sum_s phi_{si} + sum_j pi_{ij} = 1. Output orientation matches retrieval_metrics for direct comparison.

Parameters:

• m – Cache list capacities (1 x h)

• lambda – Per-item arrival rates (1 x n)

• eta – Fetching demands eta(i,s+1)=eta_{s,i} (column 1 = IS station s=0, columns 2..r+1 = PS stations), (n x (r+1)). A PS column models any symmetric/identical-rate single-server discipline (PS, SIRO, FCFS, LCFS-PR), all treated alike via the mean-field sharing slowdown.

• gamma – Access factors gamma(i,j)=gamma_{i,j}, (n x h)

• max_iter – Maximum number of iterations (default 1e5)

• tol – Convergence tolerance on relative change (default 1e-6)

Returns:

pmiss – Miss ratios pi_{i,0}, (1 x n) phit: Hit ratios pi_{i,j}, (h x n) pdh: Delayed-hit probabilities phi_{s,i} for s=0,…,r, ((r+1) x n)

Examples

[pmiss, phit, pdh] = retrieval_fpi(m, lambda, eta, gamma)
[pmiss, phit, pdh] = retrieval_fpi(m, lambda, eta, gamma, max_iter, tol)