retrieval_fpi_latency.h File Reference

FPI-based approximation of the delayed-hit count and the expected latency of a list-based cache with a phase-type retrieval system. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/retrieval/retrieval_fpi.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/linalg.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for retrieval_fpi_latency.h:

Go to the source code of this file.

Classes
struct	line::retrieval::RetrievalFpiLatencyResult< T >
	Mirrors the [Z, d, phi, pi0] return list of the MATLAB function. More...
struct	line::retrieval::RetrievalStationPH< T >
	Phase-type service of every item at one retrieval station. More...

Namespaces
namespace	line
namespace	line::retrieval

Enumerations
enum class	line::retrieval::RetrievalStationType {   line::retrieval::IS , line::retrieval::PS , line::retrieval::SIRO , line::retrieval::FCFS ,   line::retrieval::LCFSPR }
	Scheduling of a retrieval station, mirroring the MATLAB station_type strings. More...

Functions
bool	line::retrieval::is_shared_station (RetrievalStationType t)
	True for the disciplines that carry the mean-field sharing slowdown.
template<class T>
RetrievalFpiLatencyResult< T >	line::retrieval::retrieval_fpi_latency (const std::vector< int > &m, const std::vector< T > &lambda, const Matrix< T > &gamma, const std::vector< RetrievalStationPH< T > > &station, const std::vector< Matrix< T > > &R, const FpiOptions &options=FpiOptions())
	FPI-based approximation of the delayed-hit count and the expected latency of a list-based cache with a phase-type retrieval system.

Detailed Description

FPI-based approximation of the delayed-hit count and the expected latency of a list-based cache with a phase-type retrieval system.

Templated port of matlab/src/api/retrieval/retrieval_fpi_latency.m, cross-checked against jar/src/main/java/jline/api/retrieval/Retrieval_fpi_latency.java.

From the fetch-period duration F_i of item i, d_i = phi_i lambda_i E0[F_i^2] / (2 E0[F_i]), with the Palm moments of a reduced absorbing CTMC of item i's visits to the retrieval stations, E0[F_i^k] = k! pi_e (-D0)^{-k} e. The steps are

1. retrieval_fpi on the whole system -> phi_i, pi_{i,0}
2. retrieval_fpi without item i -> phitilde_s, the PS occupancy
3. one PH block per station, shared stations slowed by 1/(1+phitilde_s), routed by R, absorbing on return to the cache
4. the two moments, hence d_i
5. Z = sum_i (phi_i + d_i) / sum_i lambda_i (phi_i + pi_{i,0})

Routing convention, as in MATLAB: index 0 is the outside (entry on a miss, return to the cache on completion) and indices 1..S are the retrieval stations, R[i](a,b) being the probability of a -> b for item i.

Station types: IS fetches are independent; PS and LCFSPR are symmetric insensitive disciplines and admit general phase-type, class-dependent service; SIRO and FCFS reduce to the same single-exponential sojourn only with exponential service at a class-independent rate, and are rejected otherwise. Any other discipline is rejected outright, matching MATLAB.

ARITHMETIC: it calls retrieval_fpi, a tolerance-stopped successive substitution, so it is gated on has_transcendental for the same reason. The linear algebra around it (the visit-ratio solve and the two moment solves) would itself be exact, but the phitilde it is fed is not.

Definition in file retrieval_fpi_latency.h.