solver_nc_cache_analyzer.m

function [QN,UN,RN,TN,CN,XN,lG,pij,runtime,method,hitproblist,itemprob] = solver_nc_cache_analyzer(sn, options)
% [Q,U,R,T,C,X,LG,PIJ,RUNTIME,METHOD,HITPROBLIST] = SOLVER_NC_CACHE_ANALYZER(QN, OPTIONS)
 
% Copyright (c) 2012-2026, Imperial College London
% All rights reserved.
 
T0=tic;
QN = []; UN = [];
RN = []; TN = [];
CN = [];
XN = zeros(1,sn.nclasses);
lG = NaN;
iter = NaN;
 
line_debug('NC cache analyzer starting: method=%s, nclasses=%d', options.method, sn.nclasses);
 
source_ist = sn.nodeToStation(sn.nodetype == NodeType.Source);
sourceRate = sn.rates(source_ist,:);
sourceRate(isnan(sourceRate)) = 0;
TN(source_ist,:) = sourceRate;
 
ch = sn.nodeparam{sn.nodetype == NodeType.Cache};
 
m = ch.itemcap;
n = ch.nitems;
 
if n<m+2
    line_error(mfilename,'NC requires the number of items to exceed the cache capacity at least by 2.');
end
 
h = length(m);
u = sn.nclasses;
lambda = zeros(u,n,h);
 
for v=1:u
    for k=1:n
        for l=1:(h+1)
            if ~isnan(ch.pread{v})
                lambda(v,k,l) = sourceRate(v) * ch.pread{v}(k);
            end
        end
    end
end
 
R = ch.accost;
if isempty(R)
    % Default linear cache routing: items flow from list l to list l+1
    R = cell(u, n);
    for v = 1:u
        for k = 1:n
            Rmat = diag(ones(1, h), 1);
            Rmat(h+1, h+1) = 1;
            R{v, k} = Rmat;
        end
    end
end
gamma = cache_gamma_lp(lambda,R);
% per-list (per-level) hit probabilities are reported only from the exact
% algorithm, where the miss column and the per-list columns of pij share one
% consistent solution (so the per-list rows sum to the aggregate hit). The
% approximate algorithms derive miss and per-list from different expansions, so
% their per-list breakdown is left undefined (NaN).
pijlist = []; % genuine per-list occupancy (n x h), set in the exact branch
switch options.method
    case 'exact'
        % cache_prob_erec is exact only for the exchangeable (product-form)
        % family (RR/FIFO/RANDOM-type); recency-based policies (LRU, h-LRU,
        % q-LRU, CLIMB) have no product form and would silently return the
        % exchangeable solution instead.
        switch sn.nodeparam{sn.nodetype == NodeType.Cache}.replacestrat
            case {ReplacementStrategy.RR, ReplacementStrategy.FIFO}
                % supported
            otherwise
                line_error(mfilename,'NC does not support exact solution of the specified cache replacement policy; use the default (approximate) method or SolverCTMC.');
        end
        line_debug('Using exact method, calling cache_prob_erec');
        [pij] = cache_prob_erec(gamma, m);
        missRate = zeros(1,u);
        for v=1:u
            missRate(v) = lambda(v,:,1)*pij(:,1);
        end
        pijlist = pij(:, 2:end);
        method='exact';
    case 'sampling'
        line_debug('Using sampling method, calling cache_miss_is');
        [~,missRate,~,~,lE] = cache_miss_is(gamma, m, lambda, options.samples);
        pij = cache_prob_is(gamma, m, options.samples);
        method='sampling';
    otherwise
        line_debug('Default method: using SPM approximation method\n');
        line_debug('Using SPM approximation method, calling cache_miss_spm');
        [~,missRate,~,~,lE] = cache_miss_spm(gamma, m, lambda);
        pij = cache_prob_spm(gamma, m, lE);
        method='spm';
end
 
for r = 1:sn.nclasses
    if length(ch.hitclass)>=r && ch.missclass(r)>0 && ch.hitclass(r)>0
        XN(ch.missclass(r)) = XN(ch.missclass(r)) + missRate(r);
        XN(ch.hitclass(r)) = XN(ch.hitclass(r)) + (sourceRate(r) - missRate(r));
    end
end
 
% per-list (per-level) hit probabilities (access-weighted), only where the
% exact algorithm produced a genuine per-list occupancy matrix.
hitproblist = NaN(u, h);
if ~isempty(pijlist)
    for v=1:u
        if any(~isnan(ch.pread{v}))
            pread = ch.pread{v}(:).';
            for l=1:h
                hitproblist(v,l) = pread * pijlist(:,l);
            end
        end
    end
end
% per-item occupancy [nitems x (lists+1)] (col 1 = miss, cols 2..end per-list).
% Only the exact recursion (cache_prob_erec) yields a genuine per-list
% distribution: the spm/is algorithms approximate each per-list column
% independently and do not form a proper distribution for h>1. Since the cache
% is product-form, derive the per-item table from the exact algorithm in the
% approximate branches too (the approximate pij is still used above for the
% aggregate miss rate). The exact recursion is only tractable for small item
% sets, so it is skipped (NaN, with a warning) for caches with more than 10
% items.
if n > 10
    line_warning(mfilename, 'Per-item cache occupancy (getAvgItemTable) requires the exact algorithm and is skipped for caches with more than 10 items (%d items); reporting NaN.', n);
    itemprob = NaN(n, h+1);
elseif ~isempty(pijlist)
    itemprob = pij; % exact branch: already [n x (h+1)] with col 1 = miss
else
    itemprob = cache_prob_erec(gamma, m); % [n x (h+1)] with col 1 = miss
end
runtime=toc(T0);
end