LINE Solver
MATLAB API documentation
Loading...
Searching...
No Matches
refreshLocalVars.m
1function nvars = refreshLocalVars(self)
2% NVARS = REFRESHLOCALVARS()
3
4R = self.getNumberOfClasses;
5nvars = zeros(self.getNumberOfNodes, 2*R+1);
6nodeparam = cell(self.getNumberOfNodes, 1);
7rtnodes = self.sn.rtnodes;
8% Draft SPN code:
9% isp = [];
10% ist = [];
11% nodeToPlace = zeros(1, self.getNumberOfNodes);
12% nodeToTransition = zeros(1, self.getNumberOfNodes);
13% for ind=1:self.getNumberOfNodes
14% node = self.getNodeByIndex(ind);
15% switch class(node)
16% case 'Place'
17% isp = [isp, ind];
18% nodeToPlace(ind) = length(isp);
19% case 'Transition'
20% ist = [ist, ind];
21% nodeToTransition(ind) = length(ist);
22% end
23% end
24sn = self.sn;
25
26for ind=1:self.getNumberOfNodes
27 node = self.getNodeByIndex(ind);
28 switch class(node)
29 case 'Cache'
30 nodeparam{ind} = struct();
31 nodeparam{ind}.nitems = 0;
32 nodeparam{ind}.accost = node.accessProb;
33 for r=1:self.getNumberOfClasses
34 if length(node.popularity) >= r && isa(node.popularity{r}, 'Distribution') && ~node.popularity{r}.isDisabled
35 nodeparam{ind}.nitems = max(nodeparam{ind}.nitems,node.popularity{r}.support(2));
36 end
37 end
38 % nvars holds the cache state width: cache contents plus, when a retrieval
39 % system is configured, a per-item occupancy bitmap (one column per item);
40 % otherwise only the cache contents are stored.
41 if node.retrievalSystemCapacity > 0
42 retrievalBitmapWidth = nodeparam{ind}.nitems;
43 else
44 retrievalBitmapWidth = 0;
45 end
46 nvars(ind,2*R+1) = node.totalCacheCapacity + retrievalBitmapWidth;
47 nodeparam{ind}.itemcap = node.itemLevelCap;
48 nodeparam{ind}.totalCacheCapacity = node.totalCacheCapacity;
49 nodeparam{ind}.retrievalSystemCapacity = node.retrievalSystemCapacity;
50 nodeparam{ind}.pread = cell(1,self.getNumberOfClasses);
51 for r=1:self.getNumberOfClasses
52 if length(node.popularity) < r || ~isa(node.popularity{r}, 'Distribution') || node.popularity{r}.isDisabled
53 nodeparam{ind}.pread{r} = NaN;
54 else
55 nodeparam{ind}.pread{r} = node.popularity{r}.evalPMF(1:nodeparam{ind}.nitems);
56 end
57 end
58 nodeparam{ind}.replacestrat = node.replacestrategy;
59 if isprop(node,'admissionProb') && ~isempty(node.admissionProb)
60 nodeparam{ind}.qlru = node.admissionProb;
61 else
62 nodeparam{ind}.qlru = 1.0;
63 end
64 % CLIMB is solved as an equivalent FIFO cache with unit-capacity
65 % lists: CLIMB on one list of capacity C equals FIFO on C lists of
66 % capacity 1 with chain promotion (identity, exact). Rewrite the
67 % analyzer inputs here so no bespoke CLIMB discipline is needed.
68 if node.replacestrategy == ReplacementStrategy.CLIMB
69 Cclimb = sum(nodeparam{ind}.itemcap);
70 nodeparam{ind}.itemcap = ones(1, Cclimb);
71 nodeparam{ind}.replacestrat = ReplacementStrategy.FIFO;
72 chainAc = diag(ones(1,Cclimb),1); chainAc(Cclimb+1,Cclimb+1) = 1;
73 Kclimb = self.getNumberOfClasses;
74 acClimb = cell(Kclimb, nodeparam{ind}.nitems);
75 for vClimb = 1:Kclimb
76 for kClimb = 1:nodeparam{ind}.nitems
77 acClimb{vClimb,kClimb} = chainAc;
78 end
79 end
80 nodeparam{ind}.accost = acClimb;
81 end
82 nodeparam{ind}.hitclass = zeros(1,self.getNumberOfClasses);
83 nodeparam{ind}.hitclass(1:length(node.server.hitClass)) = round(node.server.hitClass);
84 nodeparam{ind}.missclass = zeros(1,self.getNumberOfClasses);
85 nodeparam{ind}.missclass(1:length(node.server.missClass)) = round(node.server.missClass);
86
87 % retrieval-system class matrix: pad to current class count and -1 outside known entries
88 K = self.getNumberOfClasses;
89 if isprop(node.server, 'retrievalClasses') && ~isempty(node.server.retrievalClasses)
90 rc = -ones(nodeparam{ind}.nitems, K);
91 rc(1:size(node.server.retrievalClasses,1), 1:min(size(node.server.retrievalClasses,2),K)) = ...
92 node.server.retrievalClasses(1:size(node.server.retrievalClasses,1), 1:min(size(node.server.retrievalClasses,2),K));
93 nodeparam{ind}.retrievalClasses = rc;
94 else
95 nodeparam{ind}.retrievalClasses = -ones(max(nodeparam{ind}.nitems,1), K);
96 end
97 nodeparam{ind}.retrievalClassIndices = node.retrievalClassIndices;
98 nodeparam{ind}.retrievalSystemQueueIndices = containers.Map('KeyType','int32','ValueType','any');
99 keysList = keys(node.retrievalSystemQueueIndices);
100 for kk = 1:numel(keysList)
101 nodeparam{ind}.retrievalSystemQueueIndices(keysList{kk}) = node.retrievalSystemQueueIndices(keysList{kk});
102 end
103
104 % Store actual hit/miss/latency from solver results (if available)
105 if isprop(node.server, 'actualHitProb') && ~isempty(node.server.actualHitProb)
106 nodeparam{ind}.actualhitprob = full(node.server.actualHitProb);
107 nodeparam{ind}.actualmissprob = full(node.server.actualMissProb);
108 end
109 if isprop(node.server, 'actualDelayedHitProb') && ~isempty(node.server.actualDelayedHitProb)
110 nodeparam{ind}.actualdelayedhitprob = full(node.server.actualDelayedHitProb);
111 end
112 if isprop(node.server, 'actualResidT') && ~isempty(node.server.actualResidT)
113 nodeparam{ind}.actualresidt = full(node.server.actualResidT);
114 end
115 case 'Fork'
116 nodeparam{ind}.fanOut = node.output.tasksPerLink;
117 case 'Join'
118 nodeparam{ind}.joinStrategy = node.input.joinStrategy;
119 nodeparam{ind}.fanIn = cell(1,self.getNumberOfClasses);
120 for r=1:self.getNumberOfClasses
121 nodeparam{ind}.fanIn{r} = node.input.joinRequired{r};
122 end
123 case 'Logger'
124 nodeparam{ind}.fileName = node.fileName;
125 nodeparam{ind}.filePath = node.filePath;
126 nodeparam{ind}.startTime = node.getStartTime;
127 nodeparam{ind}.loggerName = node.getLoggerName;
128 nodeparam{ind}.timestamp = node.getTimestamp;
129 nodeparam{ind}.jobID = node.getJobID;
130 nodeparam{ind}.jobClass = node.getJobClass;
131 nodeparam{ind}.timeSameClass = node.getTimeSameClass;
132 nodeparam{ind}.timeAnyClass = node.getTimeAnyClass;
133 case {'Source'}
134 for r=1:self.getNumberOfClasses
135 if ~iscell(node.arrivalProcess) || length(node.arrivalProcess) < r || isempty(node.arrivalProcess{r})
136 continue;
137 end
138 switch class(node.arrivalProcess{r})
139 case {'MAP','MMPP2'} % Markov-modulated: track restart phase (see State.afterEvent ismkvmodclass)
140 nvars(ind,r) = nvars(ind,r) + 1;
141 case {'Replayer', 'Trace'}
142 if isempty(nodeparam{ind})
143 nodeparam{ind} = cell(1,self.getNumberOfClasses);
144 end
145 if isempty(nodeparam{ind}{r})
146 nodeparam{ind}{r} = struct();
147 end
148 nodeparam{ind}{r}.(node.arrivalProcess{r}.params{1}.paramName) = node.arrivalProcess{r}.params{1}.paramValue;
149 end
150 end
151 case {'Queue','QueueingStation','Delay','DelayStation','Transition'}
152 for r=1:self.getNumberOfClasses
153 switch class(node.server.serviceProcess{r}{3})
154 case {'MAP','MMPP2'} % Markov-modulated: track restart phase (see State.afterEvent ismkvmodclass)
155 nvars(ind,r) = nvars(ind,r) + 1;
156 case {'Replayer', 'Trace'}
157 if isempty(nodeparam{ind})
158 nodeparam{ind} = cell(1,self.getNumberOfClasses);
159 end
160 if isempty(nodeparam{ind}{r})
161 nodeparam{ind}{r} = struct();
162 end
163 nodeparam{ind}{r}.(node.server.serviceProcess{r}{3}.params{1}.paramName) = node.server.serviceProcess{r}{3}.params{1}.paramValue;
164 end
165 if ~isa(node,'Delay') && ~isa(node,'Transition') && ~isempty(node.setupTime) && ~isempty(node.setupTime{r})
166 if isempty(nodeparam{ind})
167 nodeparam{ind} = cell(1,self.getNumberOfClasses);
168 end
169 if isempty(nodeparam{ind}{r})
170 nodeparam{ind}{r} = struct();
171 end
172 nodeparam{ind}{r}.setupTime = node.setupTime{r}.getProcess();
173 nodeparam{ind}{r}.delayoffTime = node.delayoffTime{r}.getProcess();
174 end
175 if (isa(node,'Queue') || isa(node,'QueueingStation'))
176 if isempty(nodeparam{ind}) && (~isempty(node.pollingType) || ~isempty(node.switchoverTime))
177 nodeparam{ind} = cell(1,self.getNumberOfClasses);
178 for s=1:self.getNumberOfClasses
179 nodeparam{ind}{s} = struct();
180 end
181 end
182 if ~isempty(node.pollingType) && ~isempty(node.pollingType{r})
183 nodeparam{ind}{r}.pollingType = node.pollingType{r};
184 nodeparam{ind}{r}.pollingPar = node.pollingPar;
185 end
186 if ~isempty(node.switchoverTime) && ~isempty(node.switchoverTime{r})
187 if min(size(node.switchoverTime))==1
188 nodeparam{ind}{r}.switchoverTime = node.switchoverTime{r}.getProcess();
189 nodeparam{ind}{r}.switchoverProcId = ProcessType.toId(ProcessType.fromText(class(node.switchoverTime{r})));
190 else
191 for t=1:length(node.switchoverTime)
192 % A from-to switchover matrix can have empty
193 % cells (e.g. the diagonal, or pairs never set);
194 % treat those as a zero-time (Immediate) switch
195 % rather than dereferencing an empty entry.
196 so_rt = node.switchoverTime{r,t};
197 if isempty(so_rt)
198 so_rt = Immediate();
199 end
200 nodeparam{ind}{r}.switchoverTime{t} = so_rt.getProcess();
201 nodeparam{ind}{r}.switchoverProcId(t) = ProcessType.toId(ProcessType.fromText(class(so_rt)));
202 end
203 end
204 end
205 end
206 end
207 % Pass-and-swap (PAS) queues carry a node-level class
208 % compatibility/swap graph rather than per-class parameters.
209 if (isa(node,'Queue') || isa(node,'QueueingStation')) && ...
210 (SchedStrategy.toId(node.schedStrategy) == SchedStrategy.PAS || ...
211 SchedStrategy.toId(node.schedStrategy) == SchedStrategy.OI)
212 if isempty(nodeparam{ind})
213 nodeparam{ind} = struct();
214 end
215 if SchedStrategy.toId(node.schedStrategy) == SchedStrategy.OI
216 % Order-independent queue: swap graph is always zero (empty),
217 % so class order is preserved on completion (plain OI).
218 nodeparam{ind}.swapGraph = zeros(R,R);
219 elseif isempty(node.swapGraph)
220 % PAS default: complete compatibility graph (any class may
221 % swap with any other; no self-loops) when none was set.
222 nodeparam{ind}.swapGraph = ones(R,R) - eye(R);
223 else
224 nodeparam{ind}.swapGraph = node.swapGraph;
225 end
226 % Total service rate function mu(c) of the ordered state vector c.
227 nodeparam{ind}.svcRateFun = node.svcRateFun;
228 end
229 end
230
231 for r=1:R
232 switch sn.routing(ind,r)
233 case RoutingStrategy.KCHOICES
234 nodeparam{ind}{r}.k = node.output.outputStrategy{r}{3}{1};
235 nodeparam{ind}{r}.withMemory = node.output.outputStrategy{r}{3}{2};
236 if nodeparam{ind}{r}.withMemory
237 % Reserve a state slot per class to record the last
238 % selected destination so sub_kchoices can replicate the
239 % "Power-of-K with memory" semantics (Mitzenmacher 2002).
240 nvars(ind, R+r) = nvars(ind, R+r) + 1;
241 end
242 case RoutingStrategy.WRROBIN
243 nvars(ind,R+r) = nvars(ind,R+r) + 1;
244 % save indexes of outgoing links
245 if isempty(nodeparam) || isempty(nodeparam{ind}) % reinstantiate if not a cache
246 nodeparam{ind}{r} = struct();
247 end
248 nodeparam{ind}{r}.weights = zeros(1,self.sn.nnodes);
249 nodeparam{ind}{r}.outlinks = find(self.sn.connmatrix(ind,:));
250 for c=1:size(node.output.outputStrategy{1, r}{3},2)
251 destination = node.output.outputStrategy{1, r}{3}{c}{1};
252 weight = node.output.outputStrategy{1, r}{3}{c}{2};
253 nodeparam{ind}{r}.weights(destination.index) = weight;
254 end
255 % Build the WRR cycle by replicating each outlink by its weight.
256 % afterEventRouter walks this list one position per DEP. With
257 % unit weights this collapses to ordinary RR.
258 cycle = [];
259 for ol = nodeparam{ind}{r}.outlinks
260 w = nodeparam{ind}{r}.weights(ol);
261 if w > 0
262 cycle = [cycle, repmat(ol, 1, max(1, round(w)))]; %#ok<AGROW>
263 else
264 cycle = [cycle, ol]; %#ok<AGROW>
265 end
266 end
267 nodeparam{ind}{r}.weighted_outlinks = cycle;
268 case RoutingStrategy.RROBIN
269 nvars(ind,R+r) = nvars(ind,R+r) + 1;
270 % save indexes of outgoing links
271 if isempty(nodeparam) || isempty(nodeparam{ind}) % reinstantiate if not a cache
272 nodeparam{ind}{r} = struct();
273 end
274 nodeparam{ind}{r}.outlinks = find(self.sn.connmatrix(ind,:));
275 end
276 end
277end
278
279% True BAS: a station using Blocking-After-Service holds a completed job at its server
280% (blocked) until the downstream has room. Reserve one local state variable (nvars col
281% 2*R+1, otherwise used only by Cache) as the per-station blocked marker; it is
282% enumerated {0,1} in State.fromMarginal and driven by afterEventStation
283% (DEP-to-full-dest -> blocked; a blocked front job departs at rate 1e7 once the
284% destination has room). A station is either POLLING or BAS-FCFS, never both, so this
285% shares nvars col 2*R+1 with the polling controller below without collision.
286%
287% A station needs the marker when it can BE BLOCKED, and blocking is caused by the
288% DESTINATION being full, not by this station's own capacity. Testing this station's
289% own capacity (as this did) silently downgraded the canonical BAS shape -- upstream
290% unbounded, downstream finite -- to repetitive service, and made a NON-binding
291% capacity on the upstream change the answer by 29%. So the test is reachability: is
292% there a directly reachable destination station with a finite capacity, for which BAS
293% is declared HERE, on the station that does the blocking? (That is the convention of
294% examples/basic/closedQN/cqn_bas_blocking.m.) The marker column is shared with the
295% polling controller and the cache width, so State.fromMarginal disambiguates it by
296% re-testing this station's own BAS rule; declaration and enumeration must therefore
297% agree on that same test, which is why a destination-declared BAS (the JMT
298% convention, testsAdvFeatures/des/test_des_bas_closed.m) is NOT honoured here -- see
299% BUG-83. Mirrors Network.declaresBlockedMarker in the JAR.
300% sn.isbasblocking(ind) records the true-BAS blocking relation EXPLICITLY, instead
301% of overloading it onto the shared marker column nvars(:,2*R+1) (which also holds
302% the polling controller and the cache width). Enumeration (State.fromMarginal) and
303% the become-blocked edge (solver_ctmc) gate on this field rather than re-testing the
304% station's own drop rule, so declaration and enumeration agree for BOTH the upstream
305% and the destination declaration forms. Node-indexed (nnodes,1), default 0.
306isbasblocking = zeros(self.getNumberOfNodes, 1);
307for ind=1:self.getNumberOfNodes
308 node = self.getNodeByIndex(ind);
309 if isa(node,'Station') && ~isa(node,'Source') && ~isa(node,'Cache')
310 if declaresBlockedMarker(self, ind, R)
311 % Option B (BUG-83): the marker column is shared with the polling
312 % controller, and a station cannot carry both. A polling station that is
313 % also a BAS blocking station is rejected cleanly here, before the state
314 % space is built, rather than corrupting the shared column and failing
315 % later in State validation.
316 if self.sn.sched(self.sn.nodeToStation(ind)) == SchedStrategy.POLLING
317 line_error(mfilename, sprintf(['True BAS blocking is not supported at a polling station (%s): the ', ...
318 'polling controller and the BAS blocked marker share one local-state column. Use a non-polling ', ...
319 'scheduling strategy at the blocking station, or remove the BAS drop rule.'], self.sn.nodenames{ind}));
320 end
321 nvars(ind, 2*R+1) = 1;
322 isbasblocking(ind) = 1;
323 end
324 end
325end
326
327% Polling stations carry a controller (server position, switchover phase, visit
328% budget) in the trailing local-variable block. Its width depends on the
329% discipline and on which switchovers are non-immediate, so it is sized here,
330% after nodeparam has been fully populated above. State.pollingInfo derives the
331% width from the same nodeparam fields and is the single definition of the
332% block layout; it needs sn.nodeparam/sn.sched, hence the temporary write-back.
333if ~isempty(self.sn)
334 self.sn.nvars = nvars;
335 self.sn.nodeparam = nodeparam;
336 for ind=1:self.getNumberOfNodes
337 if self.sn.isstation(ind) && self.sn.sched(self.sn.nodeToStation(ind)) == SchedStrategy.POLLING
338 pinfo = State.pollingInfo(self.sn, ind);
339 nvars(ind, 2*R+1) = pinfo.width;
340 % memoize: State.pollingInfo is read once per state per
341 % synchronization while the generator is built
342 nodeparam{ind}{1}.pollinfo = pinfo;
343 self.sn.nodeparam = nodeparam;
344 end
345 end
346 self.sn.nvars = nvars;
347 self.sn.isbasblocking = isbasblocking;
348end
349end
350
351function tf = declaresBlockedMarker(self, ind, R)
352% TF = DECLARESBLOCKEDMARKER(SELF, IND, R)
353%
354% True when station IND is the BLOCKING (upstream) side of a true-BAS relation:
355% it has a directly reachable destination station with a finite capacity, and
356% BAS is declared EITHER on this station (upstream form, cqn_bas_blocking.m) OR
357% on that destination (destination form, the JMT/LDES convention used by
358% test_des_bas_closed.m; canonical since BUG-83). Both forms resolve to the same
359% blocking station -- the held job sits here and the become-blocked edge starts
360% here -- so the marker always lives on the upstream station. Whether the caller
361% keys enumeration on the station's own drop rule (which fails for the
362% destination form) or on the dedicated sn.isbasblocking field is what BUG-83
363% fixes. Mirrors Network.declaresBlockedMarker in the JAR.
364tf = false;
365node = self.getNodeByIndex(ind);
366dests = downstreamStations(self, ind);
367for r = 1:R
368 hereBAS = length(node.dropRule) >= r && node.dropRule(r) == DropStrategy.BAS;
369 for d = 1:length(dests)
370 dnode = self.getNodeByIndex(dests(d));
371 if ~isa(dnode,'Station') || isa(dnode,'Source')
372 continue
373 end
374 dcap = dnode.cap;
375 if isempty(dcap) || ~isfinite(dcap) || dcap <= 0
376 continue % the destination must be able to fill
377 end
378 thereBAS = length(dnode.dropRule) >= r && dnode.dropRule(r) == DropStrategy.BAS;
379 if hereBAS || thereBAS
380 tf = true; % BAS declared upstream or on the reachable full destination
381 return
382 end
383 end
384end
385end
386
387function out = downstreamStations(self, ind)
388% OUT = DOWNSTREAMSTATIONS(SELF, IND)
389%
390% Node indices of the stations directly downstream of IND, walking through
391% intermediate stateless nodes (Router, ClassSwitch, ...) but stopping at the first
392% station on each path, since a blocked job is held for its immediate destination.
393out = [];
394conn = self.sn.connmatrix;
395if isempty(conn)
396 return
397end
398n = self.getNumberOfNodes;
399seen = false(1,n);
400queue = ind;
401seen(ind) = true;
402while ~isempty(queue)
403 cur = queue(1); queue(1) = [];
404 for j = 1:min(n, size(conn,2))
405 if conn(cur,j) ~= 1 || seen(j)
406 continue
407 end
408 seen(j) = true;
409 if isa(self.getNodeByIndex(j),'Station')
410 out(end+1) = j; %#ok<AGROW>
411 else
412 queue(end+1) = j; %#ok<AGROW>
413 end
414 end
415end
416end
Definition fjtag.m:157
Definition Station.m:245