LINE Solver
MATLAB API documentation
Loading...
Searching...
No Matches
afterEventCache.m
1function [outspace, outrate, outprob, eventCache] = afterEventCache(sn, ind, event, class, isSimulation, eventCache, R, space_buf, space_srv, space_var, key)
2% job arrives in class, then reads and moves into hit or miss
3% class, then departs
4
5outspace = [];
6outrate = [];
7outprob = 1;
8switch event
9 case EventType.ARV
10 space_srv(:,class) = space_srv(:,class) + 1;
11 outspace = [space_srv, space_var]; % buf is empty
12 outrate = -1*ones(size(outspace,1)); % passive action, rate is unspecified
13 case EventType.DEP
14 if space_srv(class)>0
15 % A retrieval-class job departs the cache only to BEGIN a retrieval
16 % (cache -> queue); record the item in the per-item occupancy bitmap.
17 beginBlocked = false;
18 if isfield(sn.nodeparam{ind}, 'retrievalClassIndices')
19 rciDep = sn.nodeparam{ind}.retrievalClassIndices;
20 else
21 rciDep = [];
22 end
23 if any(rciDep == class)
24 if isfield(sn.nodeparam{ind}, 'totalCacheCapacity')
25 tccDep = sn.nodeparam{ind}.totalCacheCapacity;
26 else
27 tccDep = sum(sn.nodeparam{ind}.itemcap);
28 end
29 pDep = sn.nodeparam{ind}.pread{class};
30 item = find(pDep == 1, 1, 'first'); % retrieval class reads its one-hot item
31 if ~isempty(item) && (tccDep + item <= size(space_var,2))
32 if any(space_var(:, tccDep + item) ~= 0)
33 beginBlocked = true; % already retrieving this item -> no transition
34 else
35 space_var(:, tccDep + item) = 1;
36 end
37 end
38 end
39 if ~beginBlocked
40 space_srv(:,class) = space_srv(:,class) - 1;
41 switch sn.routing(ind,class)
42 case RoutingStrategy.RROBIN
43 idx = find(space_var(sum(sn.nvars(ind,1:(R+class)))) == sn.nodeparam{ind}{class}.outlinks);
44 if idx < length(sn.nodeparam{ind}{class}.outlinks)
45 space_var(sum(sn.nvars(ind,1:(R+class)))) = sn.nodeparam{ind}{class}.outlinks(idx+1);
46 else
47 space_var(sum(sn.nvars(ind,1:(R+class)))) = sn.nodeparam{ind}{class}.outlinks(1);
48 end
49 end
50 outspace = [space_srv, space_var]; % buf is empty
51 outrate = GlobalConstants.Immediate*ones(size(outspace,1)); % immediate action
52 end
53 end
54 case EventType.READ
55 n = sn.nodeparam{ind}.nitems; % n items
56 m = sn.nodeparam{ind}.itemcap; % capacity
57 ac = sn.nodeparam{ind}.accost; % access cost
58 hitclass = sn.nodeparam{ind}.hitclass;
59 missclass = sn.nodeparam{ind}.missclass;
60 h = length(m);
61 replacement_id = sn.nodeparam{ind}.replacestrat;
62 % retrieval-system parameters (set by Cache.setRetrievalSystem; defaults below)
63 if isfield(sn.nodeparam{ind}, 'totalCacheCapacity')
64 totalCacheCapacity = sn.nodeparam{ind}.totalCacheCapacity;
65 else
66 totalCacheCapacity = sum(m);
67 end
68 if isfield(sn.nodeparam{ind}, 'retrievalClasses')
69 retrievalClasses = sn.nodeparam{ind}.retrievalClasses;
70 else
71 retrievalClasses = [];
72 end
73 if isfield(sn.nodeparam{ind}, 'retrievalClassIndices')
74 retrievalClassIndices = sn.nodeparam{ind}.retrievalClassIndices;
75 else
76 retrievalClassIndices = [];
77 end
78 if space_srv(class)>0 && sum(space_srv)==1 % a job of class is in
79 p = sn.nodeparam{ind}.pread{class};
80 en = space_srv(:,class) > 0;
81 space_srv_k = [];
82 space_var_k = [];
83 outrate = [];
84 if any(en)
85 for e=find(en)'
86 isFromRetrieval = any(retrievalClassIndices == class);
87 if isSimulation || isFromRetrieval
88 % pick one item (a returning retrieval reads exactly its own item)
89 kset = 1 + max([0,find( rand > cumsum(p) )]);
90 % pick one entry list for cache miss
91 % do not move this entry
92 l = 1 + max([0,find( rand > cumsum(ac{class,kset}(1,:)) )]);
93 else
94 kset = 1:n;
95 end
96 for k=kset % request to item k
97 space_srv_e = space_srv(e,:);
98 space_srv_e(class) = space_srv_e(class) - 1;
99 var = space_var(e,:);
100 % posk is searched only in the cache-contents region (1..totalCacheCapacity).
101 % The trailing retrieval-system slots (if any) are out of scope here.
102 posk = find(k==var(1:totalCacheCapacity),1,'first');
103 % A retrieval-complete READ always completes the miss that started
104 % the retrieval, so it must take the cache-miss branch even if the
105 % state-space enumeration produced a (then unreachable) state in
106 % which item k is already cached. This also avoids indexing the
107 % undefined hitClass of a retrieval-complete class.
108 if isFromRetrieval
109 posk = [];
110 end
111
112 if isempty(posk) % CACHE MISS or RETRIEVAL begin/return
113 % Retrieval-system occupancy bitmap: column (totalCacheCapacity+k)
114 % is non-zero iff item k is currently being retrieved.
115 inRetrieval = (totalCacheCapacity + k <= size(var,2)) && var(totalCacheCapacity + k) ~= 0;
116 rClass = -1;
117 if ~isempty(retrievalClasses) && ...
118 class <= size(retrievalClasses,2) && ...
119 k <= size(retrievalClasses,1)
120 rClass = retrievalClasses(k, class);
121 end
122
123 % A returning retrieval that is not recorded in the bitmap is an
124 % unreachable event-loop artifact; do not continue it.
125 if isFromRetrieval && ~inRetrieval
126 continue
127 end
128
129 % Begin a retrieval: the job switches to the retrieval class for
130 % item k. The occupancy bitmap is set on the subsequent DEP (when
131 % the job departs the cache for the queue), so the cache contents
132 % are unchanged here. A concurrent request for an item already
133 % being retrieved is served by the in-flight retrieval and exits
134 % (its class is not incremented, so the job is absorbed).
135 if ~isFromRetrieval && rClass ~= -1
136 if ~inRetrieval
137 space_srv_e(rClass) = space_srv_e(rClass) + 1;
138 end
139 space_srv_k = [space_srv_k; space_srv_e];
140 space_var_k = [space_var_k; var];
141 if isSimulation
142 outrate(end+1,1) = GlobalConstants.Immediate;
143 outprob(end+1,1) = p(k);
144 else
145 outrate(end+1,1) = p(k) * GlobalConstants.Immediate;
146 end
147 continue
148 end
149
150 % Item has now been retrieved (or there is no retrieval system):
151 % mark it as a miss and clear its retrieval-system bit.
152 space_srv_e(missclass(class)) = space_srv_e(missclass(class)) + 1;
153 if totalCacheCapacity + k <= size(var,2)
154 var(totalCacheCapacity + k) = 0;
155 end
156 switch replacement_id
157 case {ReplacementStrategy.FIFO, ReplacementStrategy.LRU, ReplacementStrategy.SFIFO, ReplacementStrategy.HLRU}
158 if isSimulation
159 listidx = l - 1; % l is accessCost column index, listidx is actual list (1-indexed)
160 if listidx > 0 % only cache if listidx is valid (l >= 2)
161 varp = var;
162 varp(cpos(listidx,2):cpos(listidx,m(listidx))) = var(cpos(listidx,1):cpos(listidx,m(listidx)-1));
163 varp(cpos(listidx,1)) = k; % head of list listidx
164 space_srv_k = [space_srv_k; space_srv_e];
165 space_var_k = [space_var_k; varp];
166 %% no p(k) weighting since that goes in the outprob vec
167 outrate(end+1,1) = GlobalConstants.Immediate;
168 outprob(end+1,1) = ac{class,k}(1,l) * p(k);
169 else
170 % Cache reject (l=1): pass through without caching
171 space_srv_k = [space_srv_k; space_srv_e];
172 space_var_k = [space_var_k; var];
173 outrate(end+1,1) = GlobalConstants.Immediate;
174 outprob(end+1,1) = ac{class,k}(1,l) * p(k);
175 end
176 else
177 % Cache reject (l=1): pass through without caching
178 if ac{class,k}(1,1) > 0
179 space_srv_k = [space_srv_k; space_srv_e];
180 space_var_k = [space_var_k; var];
181 outrate(end+1,1) = ac{class,k}(1,1) * p(k) * GlobalConstants.Immediate;
182 outprob(end+1,1) = 1;
183 end
184 for l=2:(h+1) % iterate over all possible target lists (columns 2 to h+1)
185 listidx = l - 1; % l is accessCost column index, listidx is actual list (1-indexed)
186 varp = var;
187 varp(cpos(listidx,2):cpos(listidx,m(listidx))) = var(cpos(listidx,1):cpos(listidx,m(listidx)-1));
188 varp(cpos(listidx,1)) = k; % head of list listidx
189 space_srv_k = [space_srv_k; space_srv_e];
190 space_var_k = [space_var_k; varp];
191 outrate(end+1,1) = ac{class,k}(1,l) * p(k) * GlobalConstants.Immediate;
192 outprob(end+1,1) = 1;
193 end
194 end
195 case ReplacementStrategy.RR
196 if isSimulation
197 listidx = l - 1; % l is accessCost column index, listidx is actual list (1-indexed)
198 if listidx > 0 % only cache if listidx is valid (l >= 2)
199 varp = var; % var'
200 r = randi(m(listidx),1,1);
201 varp(cpos(listidx,r)) = k;
202 space_srv_k = [space_srv_k; space_srv_e];
203 space_var_k = [space_var_k; (varp)];
204 outrate(end+1,1) = GlobalConstants.Immediate;
205 outprob(end+1,1) = ac{class,k}(1,l) * p(k);
206 else
207 % Cache reject (l=1): pass through without caching
208 space_srv_k = [space_srv_k; space_srv_e];
209 space_var_k = [space_var_k; var];
210 outrate(end+1,1) = GlobalConstants.Immediate;
211 outprob(end+1,1) = ac{class,k}(1,l) * p(k);
212 end
213 else
214 % Cache reject (l=1): pass through without caching
215 if ac{class,k}(1,1) > 0
216 space_srv_k = [space_srv_k; space_srv_e];
217 space_var_k = [space_var_k; var];
218 outrate(end+1,1) = ac{class,k}(1,1) * p(k) * GlobalConstants.Immediate;
219 end
220 for l=2:(h+1) % iterate over all possible target lists
221 listidx = l - 1; % l is accessCost column index, listidx is actual list (1-indexed)
222 for r=1:m(listidx) % random position in list listidx
223 varp = var;
224 varp(cpos(listidx,r)) = k;
225 space_srv_k = [space_srv_k; space_srv_e];
226 space_var_k = [space_var_k; (varp)];
227 outrate(end+1,1) = ac{class,k}(1,l) * p(k)/m(listidx) * GlobalConstants.Immediate;
228 end
229 end
230 end
231 case ReplacementStrategy.QLRU
232 % q-LRU: on a miss the item is admitted (LRU head insert)
233 % with probability q, else it passes through uncached.
234 if isfield(sn.nodeparam{ind},'qlru')
235 qadm = sn.nodeparam{ind}.qlru;
236 else
237 qadm = 1.0;
238 end
239 if isSimulation
240 listidx = l - 1;
241 if listidx > 0 && rand <= qadm
242 varp = var;
243 varp(cpos(listidx,2):cpos(listidx,m(listidx))) = var(cpos(listidx,1):cpos(listidx,m(listidx)-1));
244 varp(cpos(listidx,1)) = k;
245 space_srv_k = [space_srv_k; space_srv_e];
246 space_var_k = [space_var_k; varp];
247 outrate(end+1,1) = GlobalConstants.Immediate;
248 outprob(end+1,1) = ac{class,k}(1,l) * p(k);
249 else
250 space_srv_k = [space_srv_k; space_srv_e];
251 space_var_k = [space_var_k; var];
252 outrate(end+1,1) = GlobalConstants.Immediate;
253 outprob(end+1,1) = ac{class,k}(1,l) * p(k);
254 end
255 else
256 % pass-through mass: structural reject plus (1-q) non-admission
257 rejw = ac{class,k}(1,1) + (1-qadm)*(1 - ac{class,k}(1,1));
258 if rejw > 0
259 space_srv_k = [space_srv_k; space_srv_e];
260 space_var_k = [space_var_k; var];
261 outrate(end+1,1) = rejw * p(k) * GlobalConstants.Immediate;
262 outprob(end+1,1) = 1;
263 end
264 for l=2:(h+1)
265 listidx = l - 1;
266 varp = var;
267 varp(cpos(listidx,2):cpos(listidx,m(listidx))) = var(cpos(listidx,1):cpos(listidx,m(listidx)-1));
268 varp(cpos(listidx,1)) = k;
269 space_srv_k = [space_srv_k; space_srv_e];
270 space_var_k = [space_var_k; varp];
271 outrate(end+1,1) = qadm * ac{class,k}(1,l) * p(k) * GlobalConstants.Immediate;
272 outprob(end+1,1) = 1;
273 end
274 end
275 end
276 elseif posk <= sum(m(1:h-1)) % CACHE HIT in list i < h, move to list i+1
277 space_srv_e(hitclass(class)) = space_srv_e(hitclass(class)) + 1;
278 i = min(find(posk <= cumsum(m)));
279 j = posk - sum(m(1:i-1));
280
281 switch replacement_id
282 case ReplacementStrategy.FIFO
283 if isSimulation
284 varp = var;
285 inew = i+probchoose(ac{class,k}(1+i,(1+i):end)/sum(ac{class,k}(1+i,(1+i):end)))-1; % can choose i
286 if inew~=i
287 varp(cpos(i,j)) = var(cpos(inew,m(inew)));
288 varp(cpos(inew,2):cpos(inew,m(inew))) = var(cpos(inew,1):cpos(inew,m(inew)-1));
289 varp(cpos(inew,1)) = k;
290 end
291 %varp(cpos(i,j)) = var(cpos(i+1,m(i+1)));
292 %varp(cpos(i+1,2):cpos(i+1,m(i+1))) = var(cpos(i+1,1):cpos(i+1,m(i+1)-1));
293 %varp(cpos(i+1,1)) = k;
294
295 space_srv_k = [space_srv_k; space_srv_e];
296 space_var_k = [space_var_k; varp];
297 outrate(end+1,1) = GlobalConstants.Immediate;
298 outprob(end+1,1) = ac{class,k}(1+i,1+inew) * p(k);
299 else
300 for inew = i:h
301 varp = var;
302 varp(cpos(i,j)) = var(cpos(inew,m(inew)));
303 varp(cpos(inew,2):cpos(inew,m(inew))) = var(cpos(inew,1):cpos(inew,m(inew)-1));
304 varp(cpos(inew,1)) = k;
305 space_srv_k = [space_srv_k; space_srv_e];
306 space_var_k = [space_var_k; varp];
307 outrate(end+1,1) = ac{class,k}(1+i,1+inew) * p(k) * GlobalConstants.Immediate;
308 end
309 end
310 case ReplacementStrategy.RR
311 if isSimulation
312 inew = i+probchoose(ac{class,k}(1+i,(1+i):end)/sum(ac{class,k}(1+i,(1+i):end)))-1; % can choose i
313 varp = var;
314 r = randi(m(inew),1,1);
315 varp(cpos(i,j)) = var(cpos(inew,r));
316 varp(cpos(inew,r)) = k;
317 space_srv_k = [space_srv_k; space_srv_e];
318 space_var_k = [space_var_k; varp];
319 outrate(end+1,1) = GlobalConstants.Immediate;
320 outprob(end+1,1) = ac{class,k}(1+i,1+inew) * p(k)/m(inew);
321 else
322 for inew = i:h
323 for r=1:m(inew) % random position in new list
324 varp = var;
325 varp(cpos(i,j)) = var(cpos(inew,r));
326 varp(cpos(inew,r)) = k;
327 space_srv_k = [space_srv_k; space_srv_e];
328 space_var_k = [space_var_k; varp];
329 outrate(end+1,1) = ac{class,k}(1+i,1+inew) * p(k)/m(inew) * GlobalConstants.Immediate;
330 end
331 end
332 end
333 case {ReplacementStrategy.LRU, ReplacementStrategy.SFIFO, ReplacementStrategy.HLRU, ReplacementStrategy.QLRU}
334 if isSimulation
335 varp = var;
336 inew = i+probchoose(ac{class,k}(1+i,(1+i):end)/sum(ac{class,k}(1+i,(1+i):end)))-1; % can choose i
337 varp(cpos(i,2):cpos(i,j)) = var(cpos(i,1):cpos(i,j-1));
338 varp(cpos(i,1)) = var(cpos(inew,m(inew)));
339 varp(cpos(inew,2):cpos(inew,m(inew))) = var(cpos(inew,1):cpos(inew,m(inew)-1));
340 varp(cpos(inew,1)) = k;
341 space_srv_k = [space_srv_k; space_srv_e];
342 space_var_k = [space_var_k; varp];
343 outrate(end+1,1) = GlobalConstants.Immediate;
344 outprob(end+1,1) = ac{class,k}(1+i,1+inew) * p(k);
345 else
346 for inew = i:h
347 varp = var;
348 varp(cpos(i,2):cpos(i,j)) = var(cpos(i,1):cpos(i,j-1));
349 varp(cpos(i,1)) = var(cpos(inew,m(inew)));
350 varp(cpos(inew,2):cpos(inew,m(inew))) = var(cpos(inew,1):cpos(inew,m(inew)-1));
351 varp(cpos(inew,1)) = k;
352 space_srv_k = [space_srv_k; space_srv_e];
353 space_var_k = [space_var_k; varp];
354 outrate(end+1,1) = ac{class,k}(1+i,1+inew) * p(k) * GlobalConstants.Immediate;
355 end
356 end
357 end
358 else % CACHE HIT in list h
359 space_srv_e(hitclass(class)) = space_srv_e(hitclass(class)) + 1;
360 i=h;
361 j = posk - sum(m(1:i-1));
362 switch replacement_id
363 case {ReplacementStrategy.RR, ReplacementStrategy.FIFO, ReplacementStrategy.SFIFO}
364 space_srv_k = [space_srv_k; space_srv_e];
365 space_var_k = [space_var_k; var];
366 if isSimulation
367 outrate(end+1,1) = GlobalConstants.Immediate;
368 outprob(end+1,1) = p(k);
369 else
370 outrate(end+1,1) = p(k) * GlobalConstants.Immediate;
371 end
372 case {ReplacementStrategy.LRU, ReplacementStrategy.HLRU, ReplacementStrategy.QLRU}
373 varp = var;
374 varp(cpos(h,2):cpos(h,j)) = var(cpos(h,1):cpos(h,j-1));
375 varp(cpos(h,1)) = var(cpos(h,j));
376 space_srv_k = [space_srv_k; space_srv_e];
377 space_var_k = [space_var_k; varp];
378 if isSimulation
379 outrate(end+1,1) = GlobalConstants.Immediate;
380 outprob(end+1,1) = p(k);
381 else
382 outrate(end+1,1) = p(k) * GlobalConstants.Immediate;
383 end
384 end
385 end
386 end
387 end
388 % if state is unchanged, still add with rate 0
389 outspace = [space_srv_k, space_var_k];
390 end
391 end
392end
393 function pos = cpos(i,j)
394 % POS = CPOS(I,J)
395
396 pos = sum(m(1:i-1)) + j;
397 end
398
399end
400
the
Definition Station.m:245
Generated by doxygen 1.9.8