retrieval_fpi.h File Reference

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

#include <cmath>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include "line/api/cache/cache_xi_fp.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/line_console.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
	Conservation laws of a layered queueing network, enumerated from its structure.
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 (paper eqs. theta/xi/pi/pi_0/phi_FPI). 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 : solved JOINTLY from m_j = sum_i theta_ij xi_j / (1 + sum_l theta_il xi_l), i.e. cache_xi_fp(theta, m), the no-delay cache fixed point with gamma := theta A_i = 1 / (1 + sum_l theta_il xi_l) pi_ij = theta_ij xi_j A_i pi_i0 = A_i / D_i phi_{0,i} = A_i lambda_i eta_{0,i} / D_i, phi_{s,i} = A_i lambda_i eta_{s,i} F_{s,i} / D_i

starting from phi = 0 and pi from the cache WITHOUT delayed hits (cache_xi_fp(gamma, m), pi_i0 = 1 - sum_j pi_ij), and stopping when the largest relative change of the miss, hit and delayed-hit ratios falls below tol. Every iterate is feasible, sum_i pi_ij = m_j. When r = 0 (no PS station) D does not depend on phi, so one sweep is the fixed point and the iteration stops after it.

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.