Cache.m

classdef Cache < StatefulNode
    % Multi-level cache node with hit/miss class switching
    %
    % Models cache memory systems with multiple levels and replacement strategies.
    %
    % Copyright (c) 2012-2026, Imperial College London
    % All rights reserved.
    
    properties
        cap;
        schedPolicy;
        schedStrategy;
        replacestrategy;
        popularity;
        nLevels;
        itemLevelCap;
        items;
        accessProb;
        graph;
        totalCacheCapacity;           % sum(itemLevelCap)
        retrievalSystemCapacity;      % 0 until setRetrievalSystem is called; nitems-totalCacheCapacity otherwise
        retrievalSystemQueueIndices;  % containers.Map jobinClassIdx -> [queue node indices]
        retrievalClassIndices;        % set of indices of retrieval classes (used in afterEventCache READ)
        retrievalRoutingEntries;      % cell array of [fromCls,toCls,srcNode,dstNode,prob] routing tuples;
                                      % link() injects these into the routing matrix P (the auto-generated
                                      % retrieval classes are not part of the user-supplied P).
    end
    
    methods
        %Constructor
        function self = Cache(model, name, nitems, itemLevelCap, replStrat, graph)
            % CACHE Create a Cache node instance
            %
            % @brief Creates a Cache node with configurable levels and replacement strategy
            % @param model Network model to add the cache to
            % @param name String identifier for the cache node
            % @param nitems Total number of cacheable items
            % @param itemLevelCap Vector specifying capacity of each cache level
            % @param replStrat Replacement strategy (LRU, FIFO, Random, etc.)
            % @param graph Optional graph structure for cache hierarchy
            % @return self Cache instance configured for the given model
            %
            % The constructor creates a multi-level cache with the specified
            % total items and per-level capacities. The replacement strategy
            % determines how items are evicted when cache levels become full.
            
            self@StatefulNode(name);
            if model.isMatlabNative()
                if ~exist('itemLevelCap','var')
                    levels = 1;
                end
                classes = model.getClasses();
                self.input = Buffer(classes);
                self.output = Dispatcher(classes);
                self.schedPolicy = SchedStrategyType.NP;
                self.schedStrategy = SchedStrategy.FCFS;
                self.items = ItemSet(model, [name,'_','Items'], nitems, self);
                self.nLevels = nnz(itemLevelCap);
                self.cap = Inf; % job capacity
                self.accessProb = {};
                self.itemLevelCap = itemLevelCap; % item capacity
                self.totalCacheCapacity = sum(itemLevelCap);
                self.retrievalSystemCapacity = 0;  % no retrieval system by default
                if self.totalCacheCapacity > nitems
                    line_error(mfilename,sprintf('The number of items is smaller than the capacity of %s.',name));
                end
                self.retrievalSystemQueueIndices = containers.Map('KeyType','int32','ValueType','any');
                self.retrievalClassIndices = [];
                self.retrievalRoutingEntries = {};
                self.replacestrategy = replStrat;
                %probHit = min(sum(itemLevelCap)/nitems,1.0); % initial estimate of hit probability
                %self.setResultHitProb(probHit);
                %self.setResultMissProb(1-probHit);
                self.server =  CacheClassSwitcher(classes, nitems, itemLevelCap); % replace Server created by Queue
                self.popularity = {};
                self.setModel(model);
                self.model.addNode(self);
                if nargin<6
                    self.graph = [];
                else
                    self.graph = graph;
                end
            elseif model.isJavaNative()
                self.setModel(model);
                if nargin<6 || isempty(graph)
                    self.obj = jline.lang.nodes.Cache(model.obj, name, nitems, itemLevelCap, replStrat);
                else
                    self.obj = jline.lang.nodes.Cache(model.obj, name, nitems, itemLevelCap, replStrat, graph);
                end
                self.index = model.obj.getNodeIndex(self.obj);
            end            
        end
        
        %         function setMissTime(self, distribution)
        % SETMISSTIME(DISTRIBUTION)
        
        %             itemclass = self.items;
        %             self.server.serviceProcess{1, itemclass.index} = {[], ServiceStrategy.SD, distribution};
        %         end
        %
        %         function setHitTime(self, distribution, level)
        % SETHITTIME(DISTRIBUTION, LEVEL)
        
        %             itemclass = self.items;
        %             if ~exist('level','var')
        %                 levels = 2:self.nLevels;
        %             else
        %                 levels = level;
        %             end
        %             for level = levels
        %                 self.server.serviceProcess{1+level, itemclass.index} = {[], ServiceStrategy.SD, distribution};
        %             end
        %         end
        
        function self = reset(self)
            % SELF = RESET()
            %
            % Reset internal data structures when the network model is
            % reset
            self.server.actualHitProb = sparse([]);
            self.server.actualMissProb = sparse([]);
            self.server.actualDelayedHitProb = sparse([]);
            self.server.actualHitProbList = sparse([]);
            self.server.actualItemProb = sparse([]);
            self.server.actualResidT = sparse([]);
        end
 
        function self = setResultResidT(self, actualResidT)
            self.server.actualResidT = actualResidT;
        end
 
        function p = getResidT(self)
            p = full(self.server.actualResidT);
        end
 
        function tc = getTotalCacheCapacity(self)
            tc = self.totalCacheCapacity;
        end
 
        function rc = getRetrievalSystemCapacity(self)
            rc = self.retrievalSystemCapacity;
        end
 
        function m = getRetrievalClasses(self)
            m = self.server.retrievalClasses;
        end
 
        function idx = getRetrievalClassIndices(self)
            idx = self.retrievalClassIndices;
        end
 
        function q = getRetrievalSystemQueueIndicesFor(self, jobinClassIdx)
            % q = getRetrievalSystemQueueIndicesFor(jobinClassIdx)
            % Return node indices of the queues comprising the retrieval system for the
            % given (0-indexed) arrival class, or [] if no retrieval system is set.
            if isKey(self.retrievalSystemQueueIndices, int32(jobinClassIdx))
                q = self.retrievalSystemQueueIndices(int32(jobinClassIdx));
            else
                q = [];
            end
        end
 
        function setRetrievalClass(self, jobinClass, joboutClass, item)
            % SETRETRIEVALCLASS(jobinClass, joboutClass, item)
            % item is 1-based (MATLAB convention).
            self.server.retrievalClasses(item, jobinClass.index) = joboutClass.index;
        end
                
        function self = setResultHitProb(self, actualHitProb)
            self.server.actualHitProb = actualHitProb;
        end
        
        function self = setResultMissProb(self, actualMissProb)
            self.server.actualMissProb = actualMissProb;
        end
 
        function self = setResultDelayedHitProb(self, actualDelayedHitProb)
            % SETRESULTDELAYEDHITPROB  Per-class delayed-hit fraction
            % (requests arriving for an item whose fetch is already in
            % progress in the retrieval system). Zero for caches without a
            % retrieval system.
            self.server.actualDelayedHitProb = actualDelayedHitProb;
        end
 
        function p = getHitRatio(self)
            % GETHITRATIO  Actual (true) hit fraction per class: the item is
            % resident in the cache. Delayed hits are reported separately by
            % getDelayedHitRatio.
            p = full(self.server.actualHitProb);
        end
 
        function p = getMissRatio(self)
            p = full(self.server.actualMissProb);
        end
 
        function p = getDelayedHitRatio(self)
            % GETDELAYEDHITRATIO  Actual delayed-hit fraction per class
            % (empty/zero when the cache has no retrieval system).
            if isprop(self.server, 'actualDelayedHitProb')
                p = full(self.server.actualDelayedHitProb);
            else
                p = [];
            end
        end
 
        function self = setResultHitProbList(self, actualHitProbList)
            % SETRESULTHITPROBLIST  Per-class, per-list (per-level) hit
            % fraction matrix [classes x lists]; rows sum to getHitRatio.
            self.server.actualHitProbList = actualHitProbList;
        end
 
        function p = getHitRatioByList(self)
            % GETHITRATIOBYLIST  Per-class, per-list hit fraction matrix
            % [classes x lists]; empty when not computed by the solver.
            if isprop(self.server, 'actualHitProbList')
                p = full(self.server.actualHitProbList);
            else
                p = [];
            end
        end
 
        function self = setResultItemProb(self, actualItemProb)
            % SETRESULTITEMPROB  Per-item occupancy matrix [items x (lists+1)];
            % column 1 = miss (item not cached), columns 2..end = per-list.
            self.server.actualItemProb = actualItemProb;
        end
 
        function p = getItemProb(self)
            % GETITEMPROB  Per-item occupancy matrix [items x (lists+1)]: column 1
            % is the miss probability, columns 2..end the per-list probabilities;
            % empty when not computed by the solver.
            if isprop(self.server, 'actualItemProb')
                p = full(self.server.actualItemProb);
            else
                p = [];
            end
        end
        
        function setHitClass(self, jobinclass, joboutclass)
            % SETHITCLASS(JOBINCLASS, JOBOUTCLASS)
            
            self.server.hitClass(jobinclass.index) = joboutclass.index;
        end
        
        function setMissClass(self, jobinclass, joboutclass)
            % SETMISSCLASS(JOBINCLASS, JOBOUTCLASS)
            
            self.server.missClass(jobinclass.index) = joboutclass.index;
        end
        
       
        function setRead(self, jobclass, distribution)
            % SETREAD(JOBCLASS, DISTRIBUTION)
            
            itemclass = self.items;
            if distribution.isDiscrete                
                self.popularity{itemclass.index, jobclass.index} = distribution.copy;
                if self.popularity{itemclass.index, jobclass.index}.support(2) ~= itemclass.nitems
                    line_error(mfilename,sprintf('The reference model is defined on a number of items different from the ones used to instantiate %s.',self.name));
                end
                switch class(distribution)
                    case 'Zipf'
                        self.popularity{itemclass.index, jobclass.index}.setParam(2, 'n', itemclass.nitems);
                end
                %                self.probselect(itemclass.index, jobclass.index) = probselect;
            else
                line_error(mfilename,'A discrete popularity distribution is required.');
            end
        end
        
        function setReadItemEntry(self, jobclass, popularity, cardinality)
            % SETREAD(JOBCLASS, DISTRIBUTION)
            
            if popularity.isDiscrete
                
                self.popularity{jobclass.index} = popularity.copy;
                switch class(popularity)
                    case 'Zipf'
                        self.popularity{jobclass.index}.setParam(2, 'n', cardinality);
                end
                
            else
                line_error(mfilename,'A discrete popularity distribution is required.');
            end
        end
        function setAccessProb(self, R)
            % SETACCESSCOSTS(R)
            
            self.accessProb = R;
        end
        
        
        function setProbRouting(self, class, destination, probability)
            % SETPROBROUTING(CLASS, DESTINATION, PROBABILITY)
            
            setRouting(self, class, RoutingStrategy.PROB, destination, probability);
        end
                
        function hitClass = getHitClass(self)
            % HITCLASS = GETHITCLASS
            %
            % For an incoming job of class r, HITCLASS(r) is the new class
            % of that job after a hit
            
            hitClass = self.server.hitClass;
        end
        
        function missClass = getMissClass(self)
            % MISSCLASS = GETMISSCLASS
            %
            % For an incoming job of class r, MISSCLASS(r) is the new class
            % of that job after a miss
 
            missClass = self.server.missClass;
        end
 
        function addRetrievalRoutingEntry(self, fromCls, toCls, srcNode, dstNode, prob)
            % ADDRETRIEVALROUTINGENTRY(fromCls, toCls, srcNode, dstNode, prob)
            % Register a routing edge for an auto-generated retrieval class. link()
            % injects all such entries into the routing matrix P. Entries are 1-based
            % class indices and 1-based node indices; prob is the routing probability.
            % Later entries override earlier ones for the same (fromCls,toCls,src,dst).
            if prob <= 0
                return
            end
            self.retrievalRoutingEntries{end+1} = [fromCls, toCls, srcNode, dstNode, prob];
        end
 
        function setItemServiceRateAtQueue(self, jobinClass, item, queue, serviceRate)
            % SETITEMSERVICERATEATQUEUE(jobinClass, item, queue, serviceRate)
            % Set the service rate for a single item at one of the queues that comprise
            % the retrieval system for read requests originating from jobinClass.
            % item is 1-based.
            rClassIdx = self.server.retrievalClasses(item, jobinClass.index);
            if rClassIdx <= 0
                line_error(mfilename,'No retrieval class defined for the given class/item; call setRetrievalSystem first.');
            end
            rClass = self.model.classes{rClassIdx};
            queue.setService(rClass, Exp(serviceRate));
        end
 
        function setItemQueueEntryProbability(self, jobinClass, item, queue, probability)
            % SETITEMQUEUEENTRYPROBABILITY(jobinClass, item, queue, probability)
            % Probability of routing the retrieval class for `item` from the cache
            % into `queue` upon entering the retrieval system.
            rClassIdx = self.server.retrievalClasses(item, jobinClass.index);
            if rClassIdx <= 0
                line_error(mfilename,'No retrieval class defined for the given class/item; call setRetrievalSystem first.');
            end
            self.addRetrievalRoutingEntry(rClassIdx, rClassIdx, self.index, queue.index, probability);
        end
 
        function setItemQueueExitProbability(self, jobinClass, item, queue, probability)
            % SETITEMQUEUEEXITPROBABILITY(jobinClass, item, queue, probability)
            % Probability of routing the retrieval class for `item` out of `queue`
            % back to the cache (where the returning READ logs the miss).
            rClassIdx = self.server.retrievalClasses(item, jobinClass.index);
            if rClassIdx <= 0
                line_error(mfilename,'No retrieval class defined for the given class/item; call setRetrievalSystem first.');
            end
            self.addRetrievalRoutingEntry(rClassIdx, rClassIdx, queue.index, self.index, probability);
        end
 
        function setItemRoutingProbability(self, jobinClass, item, sourceQueue, destQueue, probability)
            % SETITEMROUTINGPROBABILITY(jobinClass, item, sourceQueue, destQueue, probability)
            % Probability of routing the retrieval class for `item` between two queues
            % inside the retrieval system.
            rClassIdx = self.server.retrievalClasses(item, jobinClass.index);
            if rClassIdx <= 0
                line_error(mfilename,'No retrieval class defined for the given class/item; call setRetrievalSystem first.');
            end
            self.addRetrievalRoutingEntry(rClassIdx, rClassIdx, sourceQueue.index, destQueue.index, probability);
        end
 
        function setRetrievalSystem(self, jobinClass, missClass, queues, serviceRates, routingMatrices)
            % SETRETRIEVALSYSTEM(jobinClass, missClass, queues, serviceRates, routingMatrices)
            %
            % Initialise the retrieval system through which a request that misses the cache
            % is fetched. The request switches to a per-item retrieval class that circulates
            % the queues and returns to the cache, where the returning READ logs it as a
            % miss (switching into `missClass`). getResidT reports the per-class
            % queueing time in the retrieval sub-network.
            %
            % Arguments:
            %   jobinClass      arrival JobClass that can route through the retrieval system
            %   missClass       JobClass into which a completed retrieval transitions
            %   queues          single Queue or array/cell of Queue nodes comprising the system
            %   serviceRates    one of:
            %                     - scalar:        same rate at every queue for every item
            %                     - row vector [1 x nItems]: rate per item, duplicated across queues
            %                     - matrix [nQueues x nItems]: rate per (queue, item)
            %   routingMatrices one of:
            %                     - matrix [(nQueues+1) x (nQueues+1)] shared across all items
            %                     - cell array of nItems such matrices (one per item)
            %                   Index nQueues+1 (last row/col) corresponds to entering/leaving
            %                   the retrieval system to/from the cache node.
 
            % --- normalise inputs ---
            if isa(queues, 'Queue')
                queueArr = {queues};
            elseif iscell(queues)
                queueArr = queues;
            elseif isnumeric(queues)
                line_error(mfilename,'queues must be a Queue or a cell/array of Queues.');
            else
                queueArr = num2cell(queues);
            end
            nQueues = numel(queueArr);
            nItems = self.items.nitems;
            self.retrievalSystemCapacity = nItems - self.totalCacheCapacity;
 
            if nQueues == 0
                line_error(mfilename,'Retrieval system cannot be initialised with no stations.');
            end
 
            % broadcast serviceRates
            if isscalar(serviceRates)
                serviceRateMat = serviceRates * ones(nQueues, nItems);
            elseif isvector(serviceRates) && numel(serviceRates) == nItems
                serviceRateMat = repmat(serviceRates(:).', nQueues, 1);
            elseif size(serviceRates,1) == nQueues && size(serviceRates,2) == nItems
                serviceRateMat = serviceRates;
            else
                line_error(mfilename,'serviceRates must be a scalar, a [1 x nItems] row vector, or a [nQueues x nItems] matrix.');
            end
 
            % broadcast routingMatrices
            if nargin < 6 || isempty(routingMatrices)
                empty = zeros(nQueues+1, nQueues+1);
                routingMatrixCell = repmat({empty}, 1, nItems);
            elseif iscell(routingMatrices)
                if numel(routingMatrices) ~= nItems
                    line_error(mfilename,'There must exist a routing matrix for every item in the cache node.');
                end
                routingMatrixCell = routingMatrices;
            else
                routingMatrixCell = repmat({routingMatrices}, 1, nItems);
            end
            for i = 1:nItems
                if size(routingMatrixCell{i},1) ~= nQueues+1 || size(routingMatrixCell{i},2) ~= nQueues+1
                    line_error(mfilename,'Each routing matrix must be of shape [nQueues+1, nQueues+1].');
                end
            end
 
            % --- record queue node indices ---
            queueIdxs = zeros(1, nQueues);
            for q = 1:nQueues
                queueIdxs(q) = queueArr{q}.index;
            end
            self.retrievalSystemQueueIndices(int32(jobinClass.index-1)) = queueIdxs;
 
            % --- create one retrieval class per item ---
            retrievalList = cell(1, nItems);
            for i = 1:nItems
                if isa(jobinClass, 'ClosedClass')
                    refStation = jobinClass.refstat;
                    retrievalList{i} = ClosedClass(self.model, [jobinClass.name '_retrievalClass_' num2str(i)], 0, refStation, 0);
                else
                    retrievalList{i} = OpenClass(self.model, [jobinClass.name '_retrievalClass_' num2str(i)], 0);
                end
                self.retrievalClassIndices(end+1) = retrievalList{i}.index;
            end
 
            % --- register routing for each item's retrieval class ---
            % The single retrieval class circulates through the queues and then
            % routes back to the cache as itself; the returning READ reads item i
            % (one-hot popularity) and switches it to the miss class. These routes
            % are recorded as deferred entries and injected into the routing matrix
            % P by link() (the auto-generated retrieval classes are not part of the
            % user-supplied P).
            for i = 1:nItems
                routingMatrix = routingMatrixCell{i};
                rClass = retrievalList{i};
 
                % switch arrival jobinClass -> retrieval class for item i
                self.setRetrievalClass(jobinClass, rClass, i);
 
                % the retrieval class triggers a read of item i (one-hot popularity)
                itemPopularity = zeros(1, nItems);
                itemPopularity(i) = 1.0;
                self.popularity{self.items.index, rClass.index} = DiscreteSampler(itemPopularity);
 
                % on the returning READ the retrieval is logged as a miss
                self.setMissClass(rClass, missClass);
 
                for sourceQueueIdx = 1:nQueues
                    sourceQueue = queueArr{sourceQueueIdx};
 
                    % Cache -> queue (begin retrieval): routingMatrix(nQueues+1, sourceQueueIdx)
                    self.addRetrievalRoutingEntry(rClass.index, rClass.index, ...
                        self.index, sourceQueue.index, routingMatrix(nQueues+1, sourceQueueIdx));
 
                    % service for the retrieval class at this queue
                    sourceQueue.setService(rClass, Exp(serviceRateMat(sourceQueueIdx, i)));
 
                    % at most one retrieval in flight at a time for this class
                    if length(sourceQueue.classCap) < rClass.index
                        sourceQueue.classCap((length(sourceQueue.classCap)+1):rClass.index) = Inf;
                    end
                    sourceQueue.classCap(rClass.index) = 1;
 
                    % queue -> other queues (stays in the retrieval class)
                    for destQueueIdx = 1:nQueues
                        self.addRetrievalRoutingEntry(rClass.index, rClass.index, ...
                            sourceQueue.index, queueArr{destQueueIdx}.index, ...
                            routingMatrix(sourceQueueIdx, destQueueIdx));
                    end
 
                    % queue -> cache (return; the returning READ logs the miss)
                    self.addRetrievalRoutingEntry(rClass.index, rClass.index, ...
                        sourceQueue.index, self.index, routingMatrix(sourceQueueIdx, nQueues+1));
                end
            end
        end
    end
end