retrieval_mva.h File Reference

Exact MVA-style recursion for delayed-hit (list-based) cache metrics. More...

#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for retrieval_mva.h:

Go to the source code of this file.

Classes
struct	line::retrieval::RetrievalMvaResult< T >
	Mirrors the [pmiss, phit, pdh] return list of the MATLAB function. More...

Namespaces
namespace	line
namespace	line::retrieval

Functions
template<class T>
RetrievalMvaResult< T >	line::retrieval::retrieval_mva (const std::vector< int > &m, const std::vector< T > &lambda, const Matrix< T > &eta, const Matrix< T > &gamma)
	Exact MVA-style recursion for delayed-hit (list-based) cache metrics.

Detailed Description

Exact MVA-style recursion for delayed-hit (list-based) cache metrics.

Templated port of matlab/src/api/retrieval/retrieval_mva.m. There is no JAR counterpart: jline/api/retrieval/ ships nc, metrics, fpi and fpi_latency only, so MATLAB is the sole reference for this function.

This is the exact recursion that retrieval_fpi approximates. Writing phi^{(k)} for the delayed-hit probability in the system WITHOUT item k,

theta_ij(m) = gamma_ij / (1 + lambda_i eta_{0,i}

• sum_s 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)) pi_i0(m) = (1 - pihit_i(m)) / (1 + lambda_i eta_{0,i}
• sum_s lambda_i eta_{s,i}(1 + sum_{k!=i} phi^{(i)}_{s,k}(m))) phi_{s,k}(m)= lambda_k pi_k0(m) eta_{s,k}(1 + sum_{i!=k} phi^{(k)}_{s,i}(m)) phi_{0,k}(m)= lambda_k eta_{0,k} pi_k0(m)

memoized over (item subset, capacity vector). The recursion bottoms out at the empty item set and at any capacity able to hold every remaining item, where the items are permanently cached (pihit = 1, no fetching at all). Cost is O(2^n n^2 h r prod_j (1+m_j)) time and memory, so it is a small-case oracle: use retrieval_fpi beyond that.

ARITHMETIC: additions, multiplications and divisions of the inputs only, so a finite field computation, exact in the exact instantiation. It then agrees with retrieval_metrics as an identity between rationals, which is the strongest available check on either implementation.

Definition in file retrieval_mva.h.