solver_mva_cache_analyzer.m

function [QN,UN,RN,TN,CN,XN,lGN,runtime,iter,method,hitproblist,itemprob] = solver_mva_cache_analyzer(sn, options)
% [Q,U,R,T,C,X,LG,RUNTIME,ITER,METHOD,HITPROBLIST] = SOLVER_MVA_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);
lGN = NaN;
iter = NaN;
 
line_debug('MVA 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;
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
 
Rcost = ch.accost;
if isempty(Rcost)
    % Default linear cache routing: items flow from list l to list l+1
    Rcost = cell(u, n);
    for v = 1:u
        for k = 1:n
            Rmat = diag(ones(1, h), 1);
            Rmat(h+1, h+1) = 1;
            Rcost{v, k} = Rmat;
        end
    end
end
 
gamma = cache_gamma_lp(lambda,Rcost);
 
% per-list (per-level) hit probabilities are reported only from the exact
% kernel, 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). For
% the approximate kernels the 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'
        line_debug('Using exact cache method');
        switch sn.nodeparam{sn.nodetype == NodeType.Cache}.replacestrat
            case {ReplacementStrategy.RR, ReplacementStrategy.FIFO}
                line_debug('Replacement strategy: RR/FIFO, calling cache_mva');
                [~,~,pij] = cache_mva(gamma, m);
                pij = [abs(1-sum(pij,2)),pij];
                pijlist = pij(:, 2:end);
            otherwise
                line_error(mfilename,'MVA does not support exact solution of the specified cache replacement policy.')
        end
    otherwise
        line_debug('Default method: using approximate cache method\n');
        line_debug('Using approximate cache method');
        switch sn.nodeparam{sn.nodetype == NodeType.Cache}.replacestrat
            case {ReplacementStrategy.RR, ReplacementStrategy.FIFO}
                line_debug('Replacement strategy: RR/FIFO, calling cache_prob_fpi');
                pij = cache_prob_fpi(gamma,m); % FPI method
            case ReplacementStrategy.LRU
                line_debug('Replacement strategy: LRU, calling cache_ttl_lrua');
                %pij = cache_ttl_lrum(lambda, m);  % linear topology only
                pij = cache_ttl_lrua(lambda, Rcost, m);  % allows trees and access costs
            %case ReplacementStrategy.HLRU
                % this is integrated but the cache_ttl_hlru script is not
                % working correctly at present
                %pij = cache_ttl_hlru(lambda, m);  % without considering different graph of different items linear
            otherwise
                line_error(mfilename,'MVA does not support approximate solution of the specified cache replacement policy.')
        end
end
missRate = zeros(1,u);
for v=1:u
    missRate(v) = lambda(v,:,1)*pij(:,1);
end
 
% per-list (per-level) hit probabilities (access-weighted), only where the
% exact kernel 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).
% This requires a genuine per-list distribution (rows summing to 1):
%  - exact kernel: pij is already genuine;
%  - approximate LRU (cache_ttl_lrua): pij is a genuine per-list distribution;
%  - approximate RR/FIFO: the FPI kernel (cache_prob_fpi) replicates the
%    aggregate hit across list columns, so it is NOT a genuine per-list
%    breakdown; derive it from the exact product-form kernel cache_mva instead
%    (the FPI pij is still used above for the aggregate miss rate).
% The exact RR/FIFO recursion (cache_mva) is only tractable for small item
% sets, so it is skipped (NaN, with a warning) for caches with more than 10
% items.
itemprob = [];
if ~isempty(pijlist)
    itemprob = pij; % exact branch: already [n x (h+1)] with col 1 = miss
elseif size(pij,2) == h+1
    switch sn.nodeparam{sn.nodetype == NodeType.Cache}.replacestrat
        case {ReplacementStrategy.RR, ReplacementStrategy.FIFO}
            if n > 10
                line_warning(mfilename, 'Per-item cache occupancy (getAvgItemTable) requires the exact kernel for RR/FIFO and is skipped for caches with more than 10 items (%d items); reporting NaN.', n);
                itemprob = NaN(n, h+1);
            else
                [~,~,pij_ex] = cache_mva(gamma, m);
                itemprob = [abs(1-sum(pij_ex,2)), pij_ex];
            end
        otherwise
            itemprob = pij; % LRU-TTL: genuine per-list distribution
    end
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
 
% Set the actual method used
if strcmp(options.method, 'exact')
    method = 'exact';
else
    switch sn.nodeparam{sn.nodetype == NodeType.Cache}.replacestrat
        case {ReplacementStrategy.RR, ReplacementStrategy.FIFO}
            method = 'fpi';
        case ReplacementStrategy.LRU
            method = 'ttl';
        otherwise
            method = options.method;
    end
end
 
runtime=toc(T0);
end