solver_nc_cache.h File Reference

Port of solver_nc_cache_analyzer.m: the NON-REENTRANT cache, a model that is exactly a Source, a Cache and a Sink. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/cache/cache_gamma_lp.h"
#include <sstream>
#include "line/api/cache/cache_cost.h"
#include "line/api/cache/cache_miss_is.h"
#include "line/api/cache/cache_miss_spm.h"
#include "line/api/cache/cache_prob_erec.h"
#include "line/api/cache/cache_prob_is.h"
#include "line/api/cache/cache_prob_spm.h"
#include "line/api/cache/cache_spm_size.h"
#include "line/lang/qn/network_struct.h"
#include "line/solvers/nc/nc_types.h"
#include "line/solvers/nc/solver_nc.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for solver_nc_cache.h:

Go to the source code of this file.

Classes
struct	line::nc::NcCacheSolution< T >
	What the cache analyzer returns beyond the usual metric table. More...

Namespaces
namespace	line
namespace	line::nc

Functions
template<class T>
NcCacheSolution< T >	line::nc::solver_nc_cache_analyzer (const qn::NetworkStruct< T > &sn, const NcSolverOptions &opt)
	Port of solver_nc_cache_analyzer.m.
template<class T>
bool	line::nc::nc_is_noreentrant_cache (const qn::NetworkStruct< T > &sn)
	True when the model is exactly a Source, a Cache and a Sink.

Detailed Description

Port of solver_nc_cache_analyzer.m: the NON-REENTRANT cache, a model that is exactly a Source, a Cache and a Sink.

WHAT THE ANALYZER ACTUALLY COMPUTES. There is no queueing here at all. Each class reads item k with probability pread(v,k), the cache holds itemcap items per list, and the question is only which items are resident. The answer is a per-item occupancy pij – column 0 the miss probability, column 1+j the probability that the item sits on list j – from which the miss RATE follows by weighting with the read rates. The throughput table is then just the source rate split between each class's hit and miss classes.

THREE ALGORITHMS, AND ONLY ONE OF THEM IS EXACT.

exact cache_prob_erec, the exact recursion. REFUSED for any replacement policy outside the exchangeable (product-form) family: RR and FIFO have a product form, LRU / h-LRU / q-LRU / CLIMB do not, and the recursion would silently return the exchangeable answer for them. sampling cache_miss_is / cache_prob_is, importance sampling. default the SPM saddle point, which spm and rayint also name. With per-item storage costs it is cache_spm_size, the size-tilted expansion, reported as spm.size; without them it is cache_miss_spm / cache_prob_spm, reported as spm.

WHY THE PER-LIST BREAKDOWN IS NaN OUTSIDE THE EXACT BRANCH, which is a deliberate refusal to report a number rather than an omission. Only the exact recursion produces a miss column and per-list columns from ONE consistent solution, so that the per-list rows sum to the aggregate hit. The approximate algorithms derive the miss and the per-list columns from different expansions and their breakdown does not form a distribution for more than one list.

THE PER-ITEM TABLE IS ALWAYS TAKEN FROM THE EXACT RECURSION, even in the approximate branches: the cache is product-form, so the exact per-item table is available regardless of how the aggregate miss rate was obtained. It is skipped above 10 items, where the recursion stops being tractable.

Definition in file solver_nc_cache.h.