Decomposition-aggregation driver for a CLOSED integrated cache-queueing model whose Cache carries a delayed-hit retrieval system. More...

#include <cmath>
#include <cstddef>
#include <functional>
#include <utility>
#include <vector>
#include "line/api/cache/cache_miss_fpi.h"
#include "line/api/da/da_cache_isolate.h"
#include "line/api/da/da_fpi.h"
#include "line/lang/qn/network_struct.h"
#include "line/num/number.h"
#include "line/solvers/mva/mva_types.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for da_cacheqn_retrieval.h:

Classes
struct	line::da::CacheqnRetrievalResult< T >
	What the delayed-hit decomposition returns. More...

Namespaces
namespace	line
namespace	line::da

Functions
template<class T>
CacheqnRetrievalResult< T >	line::da::da_cacheqn_retrieval (qn::NetworkStruct< T > sn, const std::function< mva::MvaSolution< T >(const qn::NetworkStruct< T > &)> &netfun, const mva::MvaOptions &opt)
	Port of da_cacheqn_retrieval.

Detailed Description

Decomposition-aggregation driver for a CLOSED integrated cache-queueing model whose Cache carries a delayed-hit retrieval system.

Templated port of matlab/src/api/da/da_cacheqn_retrieval.m.

THE FIXED POINT. The read rate reaching the cache depends on the network's throughput, which depends on how the cache splits that read rate between hits and fetches. One sweep therefore: solves the ISOLATED cache at the current read rate, rewrites the routing so the cache behaves as a class switch with that split, solves the network, and reads the new read rate back off the converged visits. da_fpi drives it under the 1-norm.

WHAT MAKES THIS DIFFERENT FROM da_cacheqn, and it is not the fixed point. A miss here does not leave the cache: it becomes a per-item RETRIEVAL CLASS that must be FETCHED through a backend station and returned. Two consequences are built into the driver rather than into the caller:

THE FETCH STATION IS GIVEN A LOAD-DEPENDENT RATE, and the shape of it is the coupon-collector correction alpha(k) = k / (n_eff (1 - (1-1/n_eff)^k)) with n_eff = nitems - total capacity. With k fetches in flight, the number of DISTINCT items among them is below k, because two misses may want the same item and one fetch serves both. alpha is the ratio, so the station is faster than k independent fetches would be. That is what makes the model load dependent, and it is why the caller's network solver must handle lldscaling.
THE CACHE BECOMES A ClassSwitch for the network solve, its routing rewritten each sweep: the read class goes to the hit class with probability hp, and to item i's retrieval class at the fetch node with probability pread(i) pi0(i); the retrieval class returns to the miss class.

THE MISS ALGORITHM IS FIXED HERE, deliberately, unlike da_cacheqn whose missfun is a handle. BOTH callers – SolverMVA and SolverNC – use cache_miss_fpi, and both report method = 'fpi' on this path. Nothing varies between them except the NETWORK solver, so netfun is the only handle and adding a missfun would be speculative generality. Checked against both call sites before fixing the type.

DELAYED HITS FOLD INTO MISS on this path: delayedprob is returned as zero and the reported hit is P(item cached). The open analyzer (solver_nc_retrieval_analyzer) is the one that separates the three.

Definition in file da_cacheqn_retrieval.h.

Classes

Namespaces

Functions

Detailed Description