cache_prob_is.h File Reference

Importance-sampling estimate of the cache hit-probability distribution. More...

#include <cmath>
#include <cstddef>
#include <random>
#include <vector>
#include "line/api/cache/cache_is.h"
#include "line/api/cache/cache_prob_erec.h"
#include "line/api/pfqn/pfqn_asympt_common.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for cache_prob_is.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
Matrix< T >	line::cache::cache_prob_is (const Matrix< T > &gamma, const std::vector< int > &m, std::size_t samples, std::uint64_t seed, const std::vector< int > &sigma, const std::vector< int > &k)
	Importance-sampling estimate of the cache hit-probability distribution.
template<class T>
Matrix< T >	line::cache::cache_prob_is (const Matrix< T > &gamma, const std::vector< int > &m, std::size_t samples, std::uint64_t seed)
	cache_prob_is without storage cost caps.
template<class T>
Matrix< T >	line::cache::cache_prob_is (const Matrix< T > &gamma, const std::vector< int > &m)
	cache_prob_is with the MATLAB default of 1e5 samples.

Detailed Description

Importance-sampling estimate of the cache hit-probability distribution.

Templated port of matlab/src/api/cache/cache_prob_is.m. The same proposal as cache_is is used; prob(i,1+j) is the ratio of the accumulated importance weight of the configurations that place item i on list j to the total weight, and prob(i,0) is the residual miss probability. The self-normalized form makes the constant proposal density cancel, so the estimator depends on the weights only through their ratios.

The reference scales the weights by exp(-50) before accumulating them, to keep the sum inside the double range; the constant cancels in the ratio and is kept here for entry-by-entry agreement with MATLAB.

Arithmetic. static_assert(has_transcendental) – Monte Carlo weights formed through logs and an exponential, as in cache_is.

Definition in file cache_prob_is.h.