retrieval_fpi.h File Reference

Fixed-point heuristic for a delayed-hit (list-based) cache. More...

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

Include dependency graph for retrieval_fpi.h:

Go to the source code of this file.

Classes
struct	line::retrieval::FpiOptions
	Options mirroring the trailing (max_iter, tol) arguments of the MATLAB function. More...
struct	line::retrieval::RetrievalFpiResult< T >
	Mirrors the [pmiss, phit, pdh] return list, plus the iteration diagnostics. More...

Namespaces
namespace	line
namespace	line::retrieval

Functions
template<class T>
RetrievalFpiResult< T >	line::retrieval::retrieval_fpi (const std::vector< int > &m, const std::vector< T > &lambda, const Matrix< T > &eta, const Matrix< T > &gamma, const FpiOptions &options=FpiOptions())
	Fixed-point heuristic for a delayed-hit (list-based) cache.

Detailed Description

Fixed-point heuristic for a delayed-hit (list-based) cache.

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

The exact recursion of retrieval_metrics costs O(2^n); the heuristic truncates the perturbation expansion at zeroth order, pi_{i,l}(m-1_j) ~ pi_{i,l}(m), and solves the resulting nonlinear system by successive substitution. One sweep is

F_{s,i} = 1 + sum_{k!=i} phi_{s,k} D_i = 1 + lambda_i eta_{0,i} + sum_s lambda_i eta_{s,i} F_{s,i} 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_{0,i} = lambda_i eta_{0,i} pi_i0, phi_{s,i} = lambda_i eta_{s,i} F_{s,i} pi_i0

stopping when the largest relative change of the miss, hit and delayed-hit ratios falls below tol. Note that xi and the "1 - sum_l pi_kl" factor read the PREVIOUS sweep's pi, exactly as MATLAB and the JAR do, so the port is iterate-for-iterate identical to them and not merely fixed-point identical.

ARITHMETIC: the iteration stops on a tolerance, so its answer is the fixed point only to within tol whatever the arithmetic; it is gated on has_transcendental so nobody instantiates it at exact arithmetic expecting an exact result. Use retrieval_metrics or retrieval_mva for that.

Definition in file retrieval_fpi.h.