LINE Solver (C++)
Templated C++ port of the LINE queueing solver
Loading...
Searching...
No Matches
state_events.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
3 * All rights reserved.
4 */
5#ifndef LINE_LANG_QN_STATE_EVENTS_H
6#define LINE_LANG_QN_STATE_EVENTS_H
7
8/**
9 * @file
10 * @ingroup line_lang
11 * Port of the event half of MATLAB's `+State` package: the successor states an
12 * event produces at one node, with their rates and probabilities. This is what
13 * turns the enumerated state space of `state.h` into a generator.
14 *
15 * THE ACTIVE / PASSIVE CONVENTION. An event is ACTIVE at the node that
16 * schedules it and PASSIVE at the node that receives it -- a DEP at one station
17 * IS the ARV at the next. Only the active half knows a rate, so the passive
18 * half returns the sentinel -1 and the generator assembly substitutes the
19 * active rate. The sentinel is unambiguous because a rate is never negative.
20 *
21 * WHY PROBABILITIES ARE SEPARATE FROM RATES. One event can have several
22 * successors: an entering job picks its service phase, a signal picks the job
23 * it removes, a random-order queue picks whom to serve. The rate belongs to the
24 * event and the probability to the choice, so a single (state, event) pair
25 * yields a ROW of successors and the generator entry is rate * prob.
26 */
27
28#include <cmath>
29#include <cstddef>
30#include <limits>
31#include <algorithm>
32#include <functional>
33#include <utility>
34#include <vector>
35
41#include "line/lang/qn/state.h"
42#include "line/util/error.h"
43
44namespace line {
45namespace qn {
46
47using lang::EventType;
48
49/**
50 * What one event produces at one node: the successor rows, their rates and
51 * their probabilities, all three the same length.
52 */
53template <class T>
55 std::vector<std::vector<T>> space; ///< successor local state rows
56 std::vector<T> rate; ///< per-row rate, -1 on a passive half
57 std::vector<T> prob; ///< per-row probability of the choice
58 /// START annotation: the 1-based classes that BEGIN or RESUME holding a
59 /// server on each successor row. An instantaneous tag on the arc the row
60 /// already carries, never an event of its own, so no rate, probability or
61 /// state depends on it. Usually empty; kept as a list so one arc can start
62 /// several jobs (a region release cascade does).
63 std::vector<std::vector<std::size_t>> start;
64 /// PREEMPT annotation: the 1-based classes pushed back into the buffer.
65 std::vector<std::vector<std::size_t>> preempt;
66 bool empty() const { return space.empty(); }
67};
68
69/**
70 * Tag the successor row just appended to OUT: START_CLS begins service on it
71 * and PREEMPT_CLS is displaced by it, either 0 for none. The tag vectors are
72 * grown to match `space`, so only the arcs that carry a tag need to say
73 * anything and every other row is an empty list.
74 */
75template <typename T>
76inline void tag_last(EventOutcome<T>& out, std::size_t start_cls, std::size_t preempt_cls) {
77 if (out.space.empty()) return;
78 out.start.resize(out.space.size());
79 out.preempt.resize(out.space.size());
80 if (start_cls) out.start.back().push_back(start_cls);
81 if (preempt_cls) out.preempt.back().push_back(preempt_cls);
82}
83
84/**
85 * Bring the tag vectors up to one entry per successor, so a caller can index
86 * them exactly like `space`.
87 */
88template <typename T>
89inline void pad_tags(EventOutcome<T>& out) {
90 out.start.resize(out.space.size());
91 out.preempt.resize(out.space.size());
92}
93
94/**
95 * Port of `State.toMarginalAggr`: the job counts of one node's state row,
96 * without the per-phase detail `to_marginal` also computes.
97 *
98 * It is NOT simply a projection of `to_marginal`: it accepts stateful
99 * non-stations (whose row is a plain per-class count ahead of the local
100 * variables), and it leaves the preemptive families out of its buffer switch,
101 * so for those it reports only the jobs IN SERVICE. That asymmetry is the
102 * reference's, and it is load-bearing -- the arrival branch uses this to test
103 * for room, where counting a preempted job twice would refuse a valid arrival.
104 *
105 * @param sn the network struct
106 * @param ind NODE index (1-based), as in the reference
107 * @param state_i the node's state row
108 * @return (ni, nir): total jobs and jobs per class
109 */
110template <class T>
111std::pair<T, std::vector<T>> to_marginal_aggr(const NetworkStruct<T>& sn, std::size_t ind,
112 const std::vector<T>& state_i) {
113 const std::size_t R = sn.nclasses;
114 const T zero = num_traits<T>::from_int(0);
115 std::vector<T> nir(R, zero);
116 if (ind == 0 || ind > sn.nodes.size())
117 throw InputError("to_marginal_aggr: node index is out of range");
118 const NodeDef& nd = sn.nodes[ind - 1];
119 const std::size_t ist = nd.station;
120 const std::size_t nvar = sn.nvars_of(ind);
121
122 // A Join of an FJ-augmented struct is a station whose row is a bare per-class
123 // count: it holds jobs waiting to synchronize, with no buffer/phase split and
124 // no service at all, so the station path below would read its counts as
125 // buffer tags.
126 if (sn.isfjaugmented && nd.nodetype == NodeType::Join && state_i.size() >= R) {
127 T ni = zero;
128 for (std::size_t r = 0; r < R; ++r) {
129 nir[r] = state_i[state_i.size() - R + r];
130 ni += nir[r];
131 }
132 return std::make_pair(ni, nir);
133 }
134
135 // A stateful non-station carries a per-class count ahead of its local
136 // variables. A node with nothing but bookkeeping (a Router's round-robin
137 // pointer) still has to report R zeros, so callers can index nir[r].
138 if (ist == 0) {
139 const std::size_t bufw = state_i.size() > nvar ? state_i.size() - nvar : 0;
140 for (std::size_t r = 0; r < R && r < bufw; ++r) nir[r] = state_i[r];
141 T ni = zero;
142 for (std::size_t r = 0; r < R; ++r) ni += nir[r];
143 return std::make_pair(ni, nir);
144 }
145
146 // A Source reports zero, not Inf: its jobs are external, and the EXT
147 // sentinel `to_marginal` returns describes the encoding, not a count that
148 // an arrival branch could compare against a capacity.
149 if (nd.nodetype == NodeType::Source) return std::make_pair(zero, nir);
150
151 std::vector<std::size_t> K(R, 1), Ks(R, 0);
152 std::size_t srvw = 0;
153 for (std::size_t r = 0; r < R; ++r) {
154 K[r] = sn.phasessz_of(ist, r + 1);
155 Ks[r] = srvw;
156 srvw += K[r];
157 }
158 if (state_i.size() < nvar + srvw)
159 throw InputError("to_marginal_aggr: state row is narrower than its server block");
160 const std::size_t srv0 = state_i.size() - nvar - srvw;
161
162 for (std::size_t r = 0; r < R; ++r)
163 for (std::size_t k = 0; k < K[r]; ++k) nir[r] += state_i[srv0 + Ks[r] + k];
164
165 const SchedStrategy sched = sn.stations[ist - 1].sched;
166 if (sched == SchedStrategy::EXT) {
167 // Reached only by an EXT station that is not a Source node, since the
168 // Source returns zero above. It carries the same clamp as `to_marginal`
169 // and for the same reason: an exact type has no infinity, and building
170 // one from a double Inf throws rather than saturating.
171 const T ext = num_traits<T>::is_exact
174 std::numeric_limits<double>::infinity());
175 for (std::size_t r = 0; r < R; ++r) nir[r] = ext;
176 } else if (state_detail::buffer_is_class_tag(sched)) {
177 for (std::size_t r = 0; r < R; ++r) {
178 const T tag = num_traits<T>::from_int(static_cast<long>(r + 1));
179 for (std::size_t b = 0; b < srv0; ++b)
180 if (state_i[b] == tag) nir[r] += num_traits<T>::from_int(1);
181 }
182 } else if (state_detail::buffer_is_tag_phase_pairs(sched)) {
183 // Only the EVEN positions are class tags; the odd ones record the phase
184 // each preempted job was interrupted in. Without this arm a preempted
185 // job was invisible here and nir counted the server alone, unlike
186 // `to_marginal`, which has carried the paired decode all along.
187 if (srv0 > 1)
188 for (std::size_t r = 0; r < R; ++r) {
189 const T tag = num_traits<T>::from_int(static_cast<long>(r + 1));
190 for (std::size_t b = 0; b < srv0; b += 2)
191 if (state_i[b] == tag) nir[r] += num_traits<T>::from_int(1);
192 }
193 } else if (state_detail::buffer_is_per_class_count(sched)) {
194 for (std::size_t r = 0; r < R && r < srv0; ++r) nir[r] += state_i[r];
195 } else if (sched == SchedStrategy::PAS || sched == SchedStrategy::OI) {
196 // A PAS / OI row is the ORDERED JOB LIST and nothing else: entry `b` is
197 // the 1-based class of the job in position b, 0 for an empty slot, which
198 // is the encoding `after_event_station_pas` reads and writes. It has no
199 // buffer/server split at all, so the server-block sum taken above
200 // counted the LAST LIST POSITION as a phase occupancy -- it is discarded
201 // here and the whole row is scanned instead.
202 //
203 // WITHOUT THIS BRANCH the station reports a queue length of about zero
204 // while the jobs are demonstrably in it, in EVERY solver that reduces a
205 // state through this function (SolverCTMC's `solver_ctmc_avg_from_pi`
206 // and SolverSSA's serial analyzer both do), and the capacity filter in
207 // `after_event_station_arv` compares that zero against the station's
208 // bound. A wrong NUMBER, never an error.
209 for (std::size_t r = 0; r < R; ++r) nir[r] = zero;
210 const std::size_t w = state_i.size() > nvar ? state_i.size() - nvar : 0;
211 for (std::size_t b = 0; b < w; ++b) {
212 const double v = num_traits<T>::to_double(state_i[b]);
213 const long tag = static_cast<long>(v + 0.5);
214 if (tag >= 1 && static_cast<std::size_t>(tag) <= R)
215 nir[tag - 1] += num_traits<T>::from_int(1);
216 }
217 }
218
219 // A disabled class holds no jobs whatever the row says. A Place is exempt:
220 // its tokens are not services, so it has no rate to be disabled.
221 if (nd.nodetype != NodeType::Place)
222 for (std::size_t r = 0; r < R; ++r)
223 if (sn.disabled[ist - 1][r]) nir[r] = zero;
224
225 T ni = zero;
226 for (std::size_t r = 0; r < R; ++r) ni += nir[r];
227 return std::make_pair(ni, nir);
228}
229
230/**
231 * Port of `State.isPhysicalCapacity`: true when the bound at (ist, class) is a
232 * PHYSICAL capacity rather than a state-space CUTOFF on an open class.
233 *
234 * The distinction decides what a refused arrival means. The producer's
235 * capacity arguments have the cutoff folded in -- `solver_ssa` overwrites
236 * cap/classcap with min(cutoff, physical) -- so at a cutoff boundary they read
237 * finite even with no physical cap. Treating that as physical would turn a
238 * state-space TRUNCATION into a self-loop loss, which reports a wrong arrival
239 * rate and perturbs the sample path.
240 *
241 * The in-producer signal is the DROP RULE: `refreshCapacity` sets a non-WAITQ
242 * rule exactly when the capacity is physical, and a cutoff-bounded open class
243 * keeps the WAITQ default.
244 */
245template <class T>
246bool is_physical_capacity(const NetworkStruct<T>& sn, std::size_t ist, std::size_t cls) {
247 if (sn.droprule.size() < ist || sn.droprule[ist - 1].size() < cls) return false;
248 const DropStrategy dr = sn.droprule[ist - 1][cls - 1];
249 return dr != DropStrategy::WAITQ && static_cast<int>(dr) != 0;
250}
251
252/**
253 * Port of `State.arrivalIsLost`: true when an arrival that finds no room is
254 * LOST, false when it must BLOCK the upstream instead. Every refusal path
255 * branches on this, and the two outcomes are encoded differently:
256 *
257 * LOST -> leave the state UNCHANGED, a self-loop. The event still fires,
258 * so the OFFERED job reaches the arrival-rate statistic and the
259 * loss appears as ArvR - Tput. A self-loop cancels on the
260 * generator diagonal, so it cannot move the stationary law.
261 * BLOCKED -> return NO rows. That disables the upstream departure until room
262 * frees, which is what the become-blocked edge tests for.
263 *
264 * The rule is the CLASS TYPE, not the drop rule: a closed network's population
265 * is a defining invariant, so a closed job can never be dropped. An explicit
266 * BAS/BBS/RSRD rule asks for blocking for any class.
267 */
268template <class T>
269bool arrival_is_lost(const NetworkStruct<T>& sn, std::size_t ist, std::size_t cls) {
270 if (sn.droprule.size() >= ist && sn.droprule[ist - 1].size() >= cls) {
271 const DropStrategy dr = sn.droprule[ist - 1][cls - 1];
272 if (dr == DropStrategy::BAS || dr == DropStrategy::BBS || dr == DropStrategy::RSRD)
273 return false; // the user asked for blocking explicitly
274 }
275 // The rule above sees only THIS station's declaration. Under the upstream
276 // declaration form the BAS rule sits on the blocking station, not on the
277 // destination where the refusal happens, so the destination side is recorded
278 // separately by `refresh_bas_blocking`. Without this branch an open class
279 // refused here would be declared lost, the become-blocked edge would never
280 // fire, and the blocking station would behave as if its destination were
281 // unbounded.
282 if (sn.isbasdestination.size() >= ist && sn.isbasdestination[ist - 1].size() >= cls &&
283 sn.isbasdestination[ist - 1][cls - 1])
284 return false;
285 // Open -> lost, closed -> blocked. This decides only what happens once the
286 // arrival has already been refused, never whether it is refused.
287 const double nj = sn.njobs()[cls - 1];
288 return !std::isfinite(nj);
289}
290
291/** How a station's state row splits into [buffer | server | local vars]. */
292template <class T>
293struct RowLayout {
294 std::vector<std::size_t> K; ///< phases per class
295 std::vector<std::size_t> Ks; ///< offset of class r's phase block
296 std::size_t srvw = 0; ///< total server width
297 std::size_t nvar = 0; ///< local-variable width
298 std::size_t bufw = 0; ///< buffer width, the only discipline-dependent part
299};
300
301template <class T>
302RowLayout<T> row_layout(const NetworkStruct<T>& sn, std::size_t ind, std::size_t width) {
303 const std::size_t R = sn.nclasses;
304 const std::size_t ist = sn.nodes[ind - 1].station;
305 RowLayout<T> L;
306 L.K.assign(R, 1);
307 L.Ks.assign(R, 0);
308 for (std::size_t r = 0; r < R; ++r) {
309 L.K[r] = sn.phasessz_of(ist, r + 1);
310 L.Ks[r] = L.srvw;
311 L.srvw += L.K[r];
312 }
313 L.nvar = sn.nvars_of(ind);
314 if (width < L.nvar + L.srvw)
315 throw InputError("after_event_station: the state row is narrower than its server block");
316 L.bufw = width - L.nvar - L.srvw;
317 return L;
318}
319
320/**
321 * The entry-phase distribution `pie{ist}{class}`: which phase a service STARTS
322 * in. This is `map_pie`, the equilibrium embedded at DEPARTURE instants, and
323 * NOT `map_prob`, the time-stationary law of D0+D1 -- the two differ whenever
324 * the process is not exponential (for Erlang-2, entry is [1,0] while the
325 * time-stationary law is [0.5,0.5]).
326 *
327 * A Place has no service process, so its "phases" carry no rate; the reference
328 * falls back on a uniform choice there rather than leaving the vector NaN.
329 */
330template <class T>
331std::vector<T> entry_phase_dist(const NetworkStruct<T>& sn, std::size_t ist, std::size_t cls) {
332 const std::size_t nph = sn.phases_of(ist, cls);
333 const lang::Distrib<T>& d = sn.service[ist - 1][cls - 1];
334 std::vector<T> pie;
335 if (d.D0.rows() == nph && d.D1.rows() == nph && nph > 0 && !d.disabled) {
336 mam::Map<T> m;
337 m.D0 = d.D0;
338 m.D1 = d.D1;
339 try {
340 pie = mam::map_pie(m);
341 } catch (const Error&) {
342 pie.clear(); // a zero-rate process has no entry law; fall back below
343 }
344 }
345 bool ok = pie.size() == nph;
346 if (ok) {
348 for (std::size_t k = 0; k < nph; ++k) s += pie[k];
349 ok = num_traits<T>::to_double(s) > 0 && std::isfinite(num_traits<T>::to_double(s));
350 }
351 if (!ok) {
352 pie.assign(nph, num_traits<T>::from_int(0));
353 if (nph > 0) {
355 static_cast<long>(nph)));
356 for (std::size_t k = 0; k < nph; ++k) pie[k] = u;
357 }
358 }
359 return pie;
360}
361
362/** Where node `ind` keeps its reply-block counters inside the local vars. */
364 std::vector<std::size_t> classes; ///< 1-based calling classes holding a block
365 std::vector<std::size_t> slot; ///< slot[r-1] = 0-based column, or npos
366 std::size_t width = 0;
367};
368
369/** Defined below; the polling branches of ARV, DEP and SWITCH use these. */
370template <class T>
371void polling_get(const PollingInfo<T>& pi, const std::vector<T>& var, std::size_t srvclass,
372 std::size_t& pos, std::size_t& swk, long& ctr);
373template <class T>
374std::vector<T> polling_set(const PollingInfo<T>& pi, std::vector<T> var, std::size_t pos,
375 std::size_t swk, long ctr);
376template <class T>
377void polling_next(const PollingInfo<T>& pi, std::size_t pos, const std::vector<long>& nbuf,
378 std::size_t R, bool arrived, std::size_t& q, int& mode, long& budget);
379template <class T>
380void polling_land(const NetworkStruct<T>& sn, std::size_t ist, const PollingInfo<T>& pi,
381 std::size_t q, int mode, long budget, const std::vector<T>& buf,
382 const std::vector<T>& srv, const std::vector<T>& var, const RowLayout<T>& L,
383 std::vector<std::vector<T>>& rows, std::vector<T>& probs);
384
385/** Defined below; the reply block subtracts held servers in the ARV branch. */
386template <class T>
387double reply_blocked(const NetworkStruct<T>& sn, std::size_t ind, const std::vector<T>& var);
388
389/** Defined below; the departure branch records a server held for a reply. */
390template <class T>
391ReplyBlockInfo reply_block_info(const NetworkStruct<T>& sn, std::size_t ind);
392
393/** Defined below; the ARV and DEP branches divert to it before any slicing. */
394template <class T>
396 const std::vector<T>& inspace, EventType event,
397 std::size_t cls);
398
399/**
400 * Port of the ARV branch of `State.afterEventStation`: an arriving class-`cls`
401 * job joins node `ind`, whose local state is `inspace`.
402 *
403 * The event is PASSIVE -- the upstream departure sets the rate -- so every row
404 * returned carries the -1 sentinel. It is nevertheless the branch with the most
405 * successors, because the entering job chooses its service phase, and under the
406 * preemptive disciplines it also chooses which job to displace.
407 *
408 * ONE ROW IN, MANY ROWS OUT. The reference threads a whole matrix of input
409 * rows through this handler and partitions them with logical masks
410 * (`idle_srv`, `all_busy_srv`). Every caller in the CTMC and SSA paths passes a
411 * single row, so those masks degenerate to a branch, which is what this port
412 * writes. The successor set is identical.
413 */
414template <class T>
416 const std::vector<T>& inspace, std::size_t cls) {
417 const std::size_t R = sn.nclasses;
418 const std::size_t ist = sn.nodes[ind - 1].station;
419 const T zero = num_traits<T>::from_int(0), one = num_traits<T>::from_int(1);
420 const T minus_one = num_traits<T>::from_int(-1);
421 EventOutcome<T> out;
422 if (ist == 0) throw InputError("after_event_station_arv: node is not a station");
423 const SchedStrategy sched = sn.stations[ist - 1].sched;
424 // A pass-and-swap station has no buffer/server split at all, so it must be
425 // diverted before any slicing happens.
426 if (sched == SchedStrategy::PAS || sched == SchedStrategy::OI)
427 return after_event_station_pas(sn, ind, inspace, EventType::ARV, cls);
428 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
429
430 // A Place holds a marking, not a service facility: it has no servers and no
431 // phases, so an arriving token only increments the class marking. Running
432 // it through the scheduling branches below would write into a phase slot
433 // the row does not have, widening the state so it no longer matches the
434 // enumerated space -- and the arrival would then be silently dropped.
435 if (sn.nodes[ind - 1].nodetype == NodeType::Place) {
436 std::vector<T> row = inspace;
437 const double cap = sn.classcap[ist - 1][cls - 1];
438 if (num_traits<T>::to_double(inspace[cls - 1]) < cap) {
439 row[cls - 1] += one;
440 out.space.push_back(row);
441 out.rate.push_back(minus_one);
442 out.prob.push_back(one);
443 } else {
444 // Place full: the arrival is blocked and lost, with no state change.
445 out.space.push_back(row);
446 out.rate.push_back(minus_one);
447 out.prob.push_back(zero);
448 }
449 return out;
450 }
451
452 const std::pair<T, std::vector<T>> mg = to_marginal_aggr(sn, ind, inspace);
453 const double ni = num_traits<T>::to_double(mg.first);
454 const double nir_c = num_traits<T>::to_double(mg.second[cls - 1]);
455 const double cap_i = sn.cap[ist - 1];
456 const double ccap = sn.classcap[ist - 1][cls - 1];
457 const double S = sn.stations[ist - 1].nservers;
458 std::vector<T> pentry = entry_phase_dist(sn, ist, cls);
459 // MAP service in pair form (`ctmc_mapc`): a start from the class memory h enters pair (h,j)
460 // w.p. V(h,j); pairs starting elsewhere are unreachable, and an idle start sets h := j.
461 const CtmcMapc<T>* mcA = sn.mapc_of(ist, cls);
462 const std::size_t mslotA = mcA ? sn.map_var_slot(ind, cls) : 0;
463 if (mcA) {
464 const long hA = static_cast<long>(num_traits<T>::to_double(inspace[L.bufw + L.srvw + mslotA]));
465 for (std::size_t t = 0; t < mcA->pairs.size(); ++t)
466 pentry[t] = static_cast<long>(mcA->pairs[t].first) + 1 == hA
467 ? mcA->V(mcA->pairs[t].first, mcA->pairs[t].second) : zero;
468 for (std::size_t t = 0; mcA->single && t < mcA->p; ++t) // c = 1: start in the carried phase
469 pentry[t] = static_cast<long>(t) + 1 == hA ? one : zero;
470 }
471
472 for (std::size_t kentry = 0; kentry < L.K[cls - 1]; ++kentry) {
473 if (mcA && num_traits<T>::to_double(pentry[kentry]) == 0) continue;
474 std::vector<T> buf(inspace.begin(), inspace.begin() + L.bufw);
475 std::vector<T> srv(inspace.begin() + L.bufw, inspace.begin() + L.bufw + L.srvw);
476 std::vector<T> var(inspace.begin() + L.bufw + L.srvw, inspace.end());
477 std::vector<std::vector<T>> cand; // (buf, srv, var) triples, flattened below
478 std::vector<T> cand_prob;
479 // START/PREEMPT tag of each candidate: the class that takes a server on
480 // that row and the class it displaces, 0 for neither. Filtered with the
481 // rows themselves at the capacity gate below.
482 std::vector<std::size_t> cand_start, cand_preempt;
483
484 double occ = 0; // jobs currently in service
485 for (std::size_t j = 0; j < srv.size(); ++j) occ += num_traits<T>::to_double(srv[j]);
486
487 if (sched == SchedStrategy::EXT) {
488 // A Source accepts a virtual arrival from the Sink for any open
489 // class: the reservoir is unbounded, so the state does not move.
490 if (!std::isfinite(sn.njobs()[cls - 1])) {
491 out.space.push_back(inspace);
492 out.rate.push_back(zero);
493 out.prob.push_back(one);
494 return out;
495 }
496 continue;
497 }
498
499 if (sched == SchedStrategy::PS || sched == SchedStrategy::INF ||
500 sched == SchedStrategy::DPS || sched == SchedStrategy::GPS ||
501 sched == SchedStrategy::PSPRIO || sched == SchedStrategy::DPSPRIO ||
502 sched == SchedStrategy::GPSPRIO || sched == SchedStrategy::LPS) {
503 // Every job is in service at once, so the arrival never queues.
504 const std::size_t col = L.Ks[cls - 1] + kentry;
505 std::size_t started = 0;
506 if (num_traits<T>::to_double(srv[col]) < ccap) {
507 srv[col] += one;
508 started = cls; // the job enters service at once
509 cand_prob.push_back(pentry[kentry]);
510 } else {
511 cand_prob.push_back(zero);
512 }
513 std::vector<T> row = buf;
514 row.insert(row.end(), srv.begin(), srv.end());
515 row.insert(row.end(), var.begin(), var.end());
516 cand.push_back(row);
517 cand_start.push_back(started);
518 cand_preempt.push_back(0);
519 } else if (sched == SchedStrategy::POLLING) {
520 // The CONTROLLER decides who is served, not the arrival: a job
521 // joins its class buffer and waits for the server to walk to it,
522 // even when the facility is idle, because the server is then in a
523 // switchover. The one exception is a PARKED server, which only
524 // arises with an empty station and immediate switchovers: it
525 // reaches the arriving job in zero time and opens a visit at once.
526 const PollingInfo<T> pinfo = polling_info(sn, ind);
527 std::size_t srvclass = 0;
528 for (std::size_t r = 1; r <= R; ++r) {
529 double tot = 0;
530 for (std::size_t p = 0; p < L.K[r - 1]; ++p)
531 tot += num_traits<T>::to_double(srv[L.Ks[r - 1] + p]);
532 if (tot > 0) { srvclass = r; break; }
533 }
534 std::size_t pos = 0, swk = 0;
535 long ctr = 0;
536 polling_get(pinfo, var, srvclass, pos, swk, ctr);
537 if (srvclass == 0 && swk == 0) {
538 std::vector<long> nbuf(R, 0);
539 for (std::size_t r = 0; r < R && r < L.bufw; ++r)
540 nbuf[r] = static_cast<long>(num_traits<T>::to_double(buf[r]));
541 nbuf[cls - 1] += 1;
542 std::size_t q = 0;
543 int mode = 0;
544 long budget = 0;
545 polling_next(pinfo, pos, nbuf, R, true, q, mode, budget);
546 srv[L.Ks[cls - 1] + kentry] += one;
547 var = polling_set(pinfo, var, q, 0, budget);
548 cand_start.push_back(cls); // a parked server takes it at once
549 } else {
550 buf[cls - 1] += one;
551 cand_start.push_back(0);
552 }
553 cand_preempt.push_back(0);
554 cand_prob.push_back(pentry[kentry]);
555 std::vector<T> row = buf;
556 row.insert(row.end(), srv.begin(), srv.end());
557 row.insert(row.end(), var.begin(), var.end());
558 cand.push_back(row);
559 } else if (sched == SchedStrategy::SIRO || sched == SchedStrategy::SEPT ||
560 sched == SchedStrategy::LEPT) {
561 // Test the SERVER occupancy, not the total count: the two agree in
562 // work-conserving states, but an immediate-feedback self-loop
563 // transiently leaves an idle server with a non-empty buffer, and
564 // the fed-back job must re-enter the vacated server.
565 if (occ < S) {
566 srv[L.Ks[cls - 1] + kentry] += one;
567 cand_start.push_back(cls);
568 } else {
569 buf[cls - 1] += one;
570 cand_start.push_back(0);
571 }
572 cand_preempt.push_back(0);
573 cand_prob.push_back(pentry[kentry]);
574 std::vector<T> row = buf;
575 row.insert(row.end(), srv.begin(), srv.end());
576 row.insert(row.end(), var.begin(), var.end());
577 cand.push_back(row);
578 } else if (state_detail::buffer_is_class_tag(sched)) {
579 // ORDERED BUFFER. An idle server takes the job; otherwise it goes
580 // to the first empty slot, and if there is none the arrival is
581 // refused -- which is a LOSS or a BLOCK, never a silent drop.
582 // Servers held for a pending REPLY are NOT available to an
583 // arriving job, so a job may already have to wait while the raw
584 // occupancy is below the server count. Zero for every model
585 // without reply signals.
586 const double seff = S - reply_blocked(sn, ind, var);
587 if (occ < seff) {
588 srv[L.Ks[cls - 1] + kentry] += one;
589 if (mcA && !mcA->single)
590 var[mslotA] = num_traits<T>::from_int(static_cast<long>(mcA->pairs[kentry].second + 1));
591 std::vector<T> row = buf;
592 row.insert(row.end(), srv.begin(), srv.end());
593 row.insert(row.end(), var.begin(), var.end());
594 cand.push_back(row);
595 cand_prob.push_back(pentry[kentry]);
596 cand_start.push_back(cls);
597 cand_preempt.push_back(0);
598 } else {
599 std::size_t slot = 0; // 1-based index of the LAST empty slot
600 for (std::size_t b = 0; b < L.bufw; ++b)
601 if (num_traits<T>::to_double(buf[b]) == 0) slot = b + 1;
602 // A structurally free column is not enough: the CAPACITY must
603 // also permit the placement. Gating on the capacity only for a
604 // PHYSICAL bound keeps a state-space cutoff a truncation --
605 // firing the gate at a cutoff would turn it into a self-loop.
606 const bool has_room = is_physical_capacity(sn, ist, cls)
607 ? (ni < cap_i && nir_c < ccap)
608 : true;
609 if (slot > 0 && has_room) {
610 buf[slot - 1] = num_traits<T>::from_int(static_cast<long>(cls));
611 if (sched == SchedStrategy::LCFSPRIO) {
612 // Keep the buffer priority-canonical (from_marginal): the job moves right past every waiting
613 // job of a strictly less urgent level, landing at the tail of its own level (MATLAB
614 // afterEventStation). The order ACROSS levels is never read by an LCFSPRIO server.
615 const int pc = sn.classes[cls - 1].prio;
616 for (std::size_t c = slot - 1; c + 1 < L.bufw; ++c) {
617 const double nb = num_traits<T>::to_double(buf[c + 1]);
618 if (!(nb > 0) || sn.classes[static_cast<std::size_t>(nb) - 1].prio <= pc) break;
619 buf[c] = buf[c + 1];
620 buf[c + 1] = num_traits<T>::from_int(static_cast<long>(cls));
621 }
622 }
623 std::vector<T> row = buf;
624 row.insert(row.end(), srv.begin(), srv.end());
625 row.insert(row.end(), var.begin(), var.end());
626 cand.push_back(row);
627 cand_prob.push_back(pentry[kentry]);
628 cand_start.push_back(0); // the job waits in the buffer
629 cand_preempt.push_back(0);
630 } else if (arrival_is_lost(sn, ist, cls) &&
631 is_physical_capacity(sn, ist, cls)) {
632 // LOST: keep the row unchanged, so the event still fires
633 // and the OFFERED job reaches the arrival-rate statistic.
634 // A self-loop cancels on the generator diagonal, so the
635 // stationary law cannot move.
636 //
637 // ONLY A DECLARED BUFFER MAY LOSE A JOB. `slot == 0` also
638 // fires when the row is merely as wide as the STATE-SPACE
639 // CUTOFF let it be, and there the reference emits no
640 // successor at all -- the state above the cutoff is absent,
641 // not refused. Emitting the self-loop there costs nothing on
642 // the generator (the diagonal absorbs it) and everything on
643 // the RATES, which count the loop as a departure of the
644 // upstream Source: on mqn_multiserver_fcfs 20 such loops
645 // moved Source Tput from 0.24763 to 0.26040, an arrival rate
646 // no job ever carried, and left ArvR above Tput at a station
647 // that drops nothing. `has_room` above already draws exactly
648 // this line for the capacity test.
649 cand.push_back(inspace);
650 cand_prob.push_back(pentry[kentry]);
651 cand_start.push_back(0); // the job is lost: it starts nothing
652 cand_preempt.push_back(0);
653 }
654 // BLOCKED: emit nothing, which disables the upstream departure
655 // until room frees. That absence is what the become-blocked
656 // edge tests for.
657 }
658 } else if (state_detail::buffer_is_tag_phase_pairs(sched)) {
659 // PREEMPTIVE FAMILY. The buffer holds [class, phase] pairs, because
660 // a displaced job must remember where it was interrupted. An idle
661 // server simply takes the arrival; a busy one forces a CHOICE of
662 // victim, so the event has one successor per (class, phase) in
663 // service, weighted by that server's share of the occupancy.
664 if (occ < S) {
665 srv[L.Ks[cls - 1] + kentry] += one;
666 std::vector<T> row = buf;
667 row.insert(row.end(), srv.begin(), srv.end());
668 row.insert(row.end(), var.begin(), var.end());
669 cand.push_back(row);
670 cand_prob.push_back(pentry[kentry]);
671 cand_start.push_back(cls);
672 cand_preempt.push_back(0);
673 } else {
674 // Priority-awareness is a property of the DECLARED policy, never
675 // of the data: inferring it from the class priorities turned
676 // plain LCFSPR/FCFSPR into something that is neither the base
677 // policy nor the PRIO variant.
678 const bool prio_aware = sched == SchedStrategy::FCFSPRPRIO ||
679 sched == SchedStrategy::FCFSPIPRIO ||
680 sched == SchedStrategy::LCFSPRPRIO ||
681 sched == SchedStrategy::LCFSPIPRIO;
682 const bool lcfs_family = sched == SchedStrategy::LCFSPRPRIO ||
683 sched == SchedStrategy::LCFSPIPRIO;
684 // FCFS-PR/PI: an ARRIVAL NEVER PREEMPTS. The base discipline
685 // serves in arrival order, and the PLAIN variants read no
686 // priorities at all, so every class sits in ONE group and the
687 // arrival can only wait; preemption belongs to the PRIO variants
688 // and only ACROSS groups. LCFS-PR/PI is the opposite case, keeping
689 // the NEWEST job in service, so there a plain arrival always
690 // preempts. Letting plain FCFSPR/FCFSPI preempt made them LCFS-PR
691 // by another name: invisible on an exponential single-chain queue,
692 // whose queue-length process is the same either way, and wrong
693 // wherever WHICH job holds the server matters -- a fork-join, where
694 // the sibling that completes decides when the Join fires, or any
695 // phase-type service, where the interrupted phase is carried.
696 const bool fcfs_never_preempts = sched == SchedStrategy::FCFSPR ||
697 sched == SchedStrategy::FCFSPI;
698 // PR resumes the victim in the phase it held; PI restarts it
699 // from the entry phase. That single value is the whole
700 // difference between the two families in this branch.
701 const bool resume = sched == SchedStrategy::LCFSPR ||
702 sched == SchedStrategy::LCFSPRPRIO ||
703 sched == SchedStrategy::FCFSPR ||
704 sched == SchedStrategy::FCFSPRPRIO;
705 bool can_preempt_any = false;
706 for (std::size_t cp = 1; cp <= R && !fcfs_never_preempts; ++cp) {
707 if (prio_aware) {
708 // Across priority groups a strictly higher-priority
709 // arrival preempts. WITHIN a group the base discipline
710 // decides: LCFS-PR keeps the NEWEST job in service, so
711 // an equal-priority arrival preempts; FCFS-PR never
712 // lets an arrival preempt.
713 const int pa = sn.classes[cls - 1].prio;
714 const int pv = sn.classes[cp - 1].prio;
715 if (lcfs_family ? (pa > pv) : (pa >= pv)) continue;
716 }
717 for (std::size_t pp = 0; pp < L.K[cp - 1]; ++pp) {
718 const std::size_t vcol = L.Ks[cp - 1] + pp;
719 const double busy = num_traits<T>::to_double(srv[vcol]);
720 if (busy <= 0) continue;
721 can_preempt_any = true;
722 std::vector<T> b2 = buf, s2 = srv;
723 s2[vcol] -= one;
724 s2[L.Ks[cls - 1] + kentry] += one;
725 // Rightmost empty PAIR, which is where a displaced job
726 // is stored; the class column is one left of the zero
727 // the scan finds.
728 std::size_t slot = 0;
729 for (std::size_t b = 0; b < L.bufw; ++b)
730 if (num_traits<T>::to_double(b2[b]) == 0) slot = b;
731 if (slot == 0) continue; // no room to hold the victim
732 b2[slot - 1] = num_traits<T>::from_int(static_cast<long>(cp));
733 b2[slot] = resume ? num_traits<T>::from_int(static_cast<long>(pp + 1))
734 : one;
735 std::vector<T> row = b2;
736 row.insert(row.end(), s2.begin(), s2.end());
737 row.insert(row.end(), var.begin(), var.end());
738 cand.push_back(row);
739 // the displaced job leaves the server and the arriving
740 // one takes it, on the same arc
741 cand_start.push_back(cls);
742 cand_preempt.push_back(cp);
743 // The victim is drawn uniformly among the jobs in
744 // service, so its share of the occupancy weights the
745 // successor.
746 cand_prob.push_back(T(pentry[kentry] * num_traits<T>::from_double(busy / occ)));
747 }
748 }
749 // Every busy server holds a job this arrival may not displace,
750 // so the job WAITS instead. Without this the loop above emits
751 // nothing, the arrival transition does not exist at all, and
752 // the class can never enter a busy station -- its queue is
753 // then silently understated. It is stored as a (class, entry
754 // phase) pair exactly as a preempted job is, so promotion
755 // resumes it from that phase.
756 if ((prio_aware || fcfs_never_preempts) && !can_preempt_any) {
757 std::size_t slot = 0;
758 for (std::size_t b = 0; b < L.bufw; ++b)
759 if (num_traits<T>::to_double(buf[b]) == 0) slot = b;
760 if (slot > 0) {
761 std::vector<T> b2 = buf;
762 b2[slot - 1] = num_traits<T>::from_int(static_cast<long>(cls));
763 b2[slot] = num_traits<T>::from_int(static_cast<long>(kentry + 1));
764 std::vector<T> row = b2;
765 row.insert(row.end(), srv.begin(), srv.end());
766 row.insert(row.end(), var.begin(), var.end());
767 cand.push_back(row);
768 cand_prob.push_back(pentry[kentry]);
769 cand_start.push_back(0); // it preempts nothing and waits
770 cand_preempt.push_back(0);
771 }
772 }
773 }
774 } else {
775 throw UnsupportedError(ErrorKind{"SchedStrategy"},
776 std::string("after_event_station_arv: the ") + lang::sched_to_text(sched) +
777 " discipline is not ported yet");
778 }
779
780 // The capacity filter of the reference: drop any successor that would
781 // exceed the station or class bound.
782 for (std::size_t c = 0; c < cand.size(); ++c) {
783 const std::pair<T, std::vector<T>> og = to_marginal_aggr(sn, ind, cand[c]);
784 if (num_traits<T>::to_double(og.second[cls - 1]) > ccap) continue;
785 if (num_traits<T>::to_double(og.first) > cap_i) continue;
786 out.space.push_back(cand[c]);
787 out.rate.push_back(minus_one);
788 out.prob.push_back(cand_prob[c]);
789 // the capacity gate drops rows, so the tags are attached here
790 tag_last(out, c < cand_start.size() ? cand_start[c] : 0,
791 c < cand_preempt.size() ? cand_preempt[c] : 0);
792 }
793 }
794 pad_tags(out);
795 return out;
796}
797
798/**
799 * `sn.mu` and `sn.phi` for one (station, class), derived as MATLAB's
800 * `Markovian.getMu` / `getPhi` derive them from the (D0, D1) pair:
801 *
802 * mu(k) = -D0(k,k) total exit rate of phase k
803 * phi(k) = sum_j D1(k,j) / -D0(k,k) probability the exit COMPLETES service
804 *
805 * so mu*phi is the departure rate and mu*(1-phi) the phase-advance rate. An
806 * Immediate process has D0(1,1) = 0 and takes phi = 1, since every exit of a
807 * zero-duration service is a completion.
808 */
809template <class T>
810std::pair<std::vector<T>, std::vector<T>> phase_rates(const NetworkStruct<T>& sn,
811 std::size_t ist, std::size_t cls) {
812 const lang::Distrib<T>& d = sn.service[ist - 1][cls - 1];
813 const std::size_t n = sn.phases_of(ist, cls);
814 std::vector<T> mu(n, num_traits<T>::from_int(0)), phi(n, num_traits<T>::from_int(1));
815 if (d.D0.rows() != n || d.D1.rows() != n) return std::make_pair(mu, phi);
816 for (std::size_t k = 0; k < n; ++k) {
817 const T dk = T(-d.D0(k, k));
818 mu[k] = dk;
819 if (num_traits<T>::to_double(dk) == 0) {
820 phi[k] = num_traits<T>::from_int(1); // Immediate: every exit completes
821 continue;
822 }
824 for (std::size_t j = 0; j < n; ++j) s += d.D1(k, j);
825 phi[k] = T(s / dk);
826 }
827 return std::make_pair(mu, phi);
828}
829
830/** The limited-load-dependent multiplier at population `n`, 1 when unset. */
831template <class T>
832T lld_factor(const NetworkStruct<T>& sn, std::size_t ist, double n) {
833 const std::vector<T>& s = sn.stations[ist - 1].lldscaling;
834 if (s.empty()) return num_traits<T>::from_int(1);
835 // Beyond the declared levels the scaling holds at its last value, which is
836 // what "limited" load-dependence means: the curve is flat past the limit.
837 if (!std::isfinite(n) || n >= static_cast<double>(s.size())) return s.back();
838 if (n < 1) return num_traits<T>::from_int(1);
839 return s[static_cast<std::size_t>(n) - 1];
840}
841
842/**
843 * Port of `State.cdclassfactor`: the class-dependence multiplier of a class-`cls`
844 * rate at the per-class population `nir`.
845 *
846 * `cdscaling` maps a 1 x R population vector to the R dimensionless scalings
847 * beta_r(n); the component of the class whose service is firing is the factor.
848 * A handle returning a SCALAR is the neutral case and yields 1 for every class,
849 * which is why the read is clamped to the vector's last entry rather than
850 * indexed blindly -- the reference's `v(min(class, numel(v)))`.
851 *
852 * `jdscaling` is folded in multiplicatively here, exactly as
853 * `State.afterEventInit` folds eta_i into the effective per-station handle.
854 * Doing it at the point of use rather than by rewriting the struct keeps the two
855 * fields distinguishable for the product-form tests elsewhere.
856 */
857template <class T>
858T cd_factor(const NetworkStruct<T>& sn, std::size_t ist, const std::vector<T>& nir,
859 std::size_t cls) {
860 const T one = num_traits<T>::from_int(1);
861 const Station<T>& st = sn.stations[ist - 1];
862 if (!st.cdscaling && !st.jdscaling) return one;
863 T f = one;
864 const CdScaling<T>* handles[2] = {&st.cdscaling, &st.jdscaling};
865 for (std::size_t h = 0; h < 2; ++h) {
866 const CdScaling<T>& fun = *handles[h];
867 if (!fun) continue;
868 const std::vector<T> v = fun(nir);
869 if (v.empty())
870 throw InputError(
871 "cd_factor: the class-dependence map returned an empty scaling vector");
872 f = T(f * v[std::min(cls, v.size()) - 1]);
873 }
874 return f;
875}
876
877/**
878 * The population the *PRIO disciplines actually share the server among.
879 *
880 * While every job fits in a server nobody is waiting and precedence is moot, so
881 * this is the plain marginal. Once the station saturates only the MOST URGENT
882 * group present is served (a LOWER `classprio` value is more urgent in LINE),
883 * and both the share and the load-dependent lookup are taken over that group
884 * alone -- `nirprio` / `niprio` in `State.afterEventStation`.
885 */
886template <class T>
887struct PrioPop {
888 std::vector<T> nir; ///< `nirprio` when masked, the plain marginal otherwise
889 double ni = 0; ///< `niprio` when masked, the plain total otherwise
890 bool masked = false; ///< whether the saturated-station mask was applied
891 bool served = true; ///< false when `cls` is not in the most urgent group
892};
893
894/** Compute the *PRIO effective population; a no-op for every other discipline. */
895template <class T>
896PrioPop<T> prio_pop(const NetworkStruct<T>& sn, std::size_t ist, const Marginal<T>& m,
897 std::size_t cls, double ni, double S) {
898 const std::size_t R = sn.nclasses;
899 const SchedStrategy sched = sn.stations[ist - 1].sched;
900 PrioPop<T> p;
901 p.nir = m.nir;
902 p.ni = ni;
903 const bool prio_aware = sched == SchedStrategy::PSPRIO ||
904 sched == SchedStrategy::DPSPRIO ||
905 sched == SchedStrategy::GPSPRIO;
906 if (!prio_aware || ni <= S) return p;
907 double best = std::numeric_limits<double>::infinity();
908 for (std::size_t r = 0; r < R; ++r)
909 if (num_traits<T>::to_double(m.nir[r]) > 0)
910 best = std::min(best, static_cast<double>(sn.classes[r].prio));
911 if (static_cast<double>(sn.classes[cls - 1].prio) != best) {
912 p.served = false;
913 return p;
914 }
915 p.masked = true;
916 p.ni = 0;
917 for (std::size_t r = 0; r < R; ++r) {
918 if (static_cast<double>(sn.classes[r].prio) != best)
921 }
922 return p;
923}
924
925/** Defined below; DEP and PHASE must share one definition of the share. */
926template <class T>
927T service_share(const NetworkStruct<T>& sn, std::size_t ist, const Marginal<T>& m,
928 std::size_t cls, double ni, double S);
929
930/**
931 * Port of the DEP branch of `State.afterEventStation`: a class-`cls` job
932 * completes service at station `ind`.
933 *
934 * This is the ACTIVE half, so unlike ARV it carries real rates, and the rate is
935 * where the disciplines actually differ -- the state update is nearly the same
936 * for all of them. Two rate conventions appear, and they are not
937 * interchangeable:
938 *
939 * mu(k)*phi(k)*kir -- the processor-sharing family, where the completion
940 * rate is the phase rate times the share of the server
941 * D1(k,kdest)*kir -- the FCFS family, where the MAP matrix already encodes
942 * both the completion and the phase the NEXT service
943 * starts in, so the destination phase is enumerated
944 */
945template <class T>
947 const std::vector<T>& inspace, std::size_t cls,
948 bool no_promote = false) {
949 const std::size_t R = sn.nclasses;
950 const std::size_t ist = sn.nodes[ind - 1].station;
951 const T zero = num_traits<T>::from_int(0), one = num_traits<T>::from_int(1);
952 EventOutcome<T> out;
953 if (ist == 0) throw InputError("after_event_station_dep: node is not a station");
954 const SchedStrategy sched = sn.stations[ist - 1].sched;
955 if (sched == SchedStrategy::PAS || sched == SchedStrategy::OI)
956 return after_event_station_pas(sn, ind, inspace, EventType::DEP, cls);
957 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
958 const double S = sn.stations[ist - 1].nservers;
959
960 std::vector<std::size_t> ph(R, 1), shift(R, 0);
961 for (std::size_t r = 0; r < R; ++r) {
962 ph[r] = L.K[r];
963 shift[r] = L.Ks[r];
964 }
965 // THE MARK OF A MARKED (MMAP) SOURCE CLASS, and the class whose phase block
966 // its departures actually read. All marks share ONE modulating chain, held
967 // in the CARRIER's block (mark 1); a later mark owns a single always-zero
968 // column (`phasessz_of`), so reading its own block would find no token and
969 // the class would never emit. `markof == 0` leaves every other station and
970 // every unmarked class on `cls`, exactly as before.
971 const std::size_t markof = sched == SchedStrategy::EXT ? sn.markidx_of(ist, cls) : 0;
972 std::size_t phcls = cls;
973 if (markof > 0) {
974 const std::size_t carrier = sn.mark_carrier_of(ist);
975 if (carrier >= 1 && carrier <= R) phcls = carrier;
976 }
977
978 const Marginal<T> m = to_marginal(sn, ist, inspace, ph, shift, L.nvar);
979 if (num_traits<T>::to_double(m.sir[phcls - 1]) <= 0) return out; // nothing to depart
980
981 const std::pair<std::vector<T>, std::vector<T>> mp = phase_rates(sn, ist, cls);
982 const std::vector<T>& mu = mp.first;
983 const std::vector<T>& phi = mp.second;
984 const lang::Distrib<T>& d = sn.service[ist - 1][cls - 1];
985
986 double ni = 0;
987 for (std::size_t r = 0; r < R; ++r) ni += num_traits<T>::to_double(m.nir[r]);
988 // Both dependence factors multiply every rate this branch emits, so they are
989 // folded into ONE scalar named `lld` for the arithmetic below. Their
990 // ARGUMENTS differ at a saturated *PRIO station, and the reference is not
991 // uniform about it: the load-dependent lookup takes the priority-masked
992 // total `niprio` for all three *PRIO disciplines, while the class-dependence
993 // handle takes the masked vector `nirprio` only for DPSPRIO and GPSPRIO and
994 // the plain marginal for PSPRIO (afterEventStation.m:709-711 vs :746-748 and
995 // :808-810). That asymmetry is reproduced rather than smoothed: smoothing it
996 // would move every reported metric on a model that has both.
997 const PrioPop<T> pp = prio_pop(sn, ist, m, cls, ni, S);
998 const bool cd_takes_prio =
999 pp.masked && (sched == SchedStrategy::DPSPRIO || sched == SchedStrategy::GPSPRIO);
1000 const T lld = T(lld_factor(sn, ist, pp.ni) *
1001 cd_factor(sn, ist, cd_takes_prio ? pp.nir : m.nir, cls));
1002
1003 // A retrial station does NOT promote from the orbit on completion: an
1004 // orbiting job re-enters only through a RETRY at the retrial rate. The
1005 // same suppression serves an immediate-feedback self-loop, where the
1006 // departing job holds the server for its own re-arrival.
1007 bool suppress_promote = no_promote;
1008 {
1009 const typename std::map<std::size_t, RetrialParam<T>>::const_iterator rit =
1010 sn.retrialparam.find(ist);
1011 if (rit != sn.retrialparam.end())
1012 for (std::size_t r = 0; r < rit->second.retrial_proc.size(); ++r)
1013 if (!rit->second.retrial_proc[r].disabled) { suppress_promote = true; break; }
1014 }
1015
1016 for (std::size_t k = 0; k < L.K[phcls - 1]; ++k) {
1017 std::vector<T> buf(inspace.begin(), inspace.begin() + L.bufw);
1018 std::vector<T> srv(inspace.begin() + L.bufw, inspace.begin() + L.bufw + L.srvw);
1019 std::vector<T> var(inspace.begin() + L.bufw + L.srvw, inspace.end());
1020 const std::size_t col = L.Ks[phcls - 1] + k;
1021 if (num_traits<T>::to_double(srv[col]) <= 0) continue;
1022 const T kir = m.kir[phcls - 1][k];
1023
1024 if (sched == SchedStrategy::EXT) {
1025 // A Source EMITS an arrival. Its reservoir is unbounded, so no job
1026 // count changes; what moves is the MODULATING PHASE, from k to
1027 // kentry at rate D1(k, kentry). For an exponential source that is
1028 // the single entry lambda and the state is unchanged, which is why
1029 // the arrival stream is memoryless; for a MAP it is exactly the
1030 // correlation the source is there to produce.
1031 if (!std::isfinite(sn.njobs()[cls - 1])) {
1032 // THE MARK'S OWN BLOCK, not the aggregate. `d.D1` is the sum
1033 // over marks, so reading it for a marked class gives every one
1034 // of them the WHOLE stream: two read classes off one MMAP each
1035 // arrived at the full 2.5/s instead of the 1.9 and 0.6 their
1036 // blocks carry, doubling the offered load and erasing the
1037 // popularity difference the marks exist to express.
1038 const Matrix<T>& D1k =
1039 markof > 0 && markof <= d.Dmark.size() ? d.Dmark[markof - 1] : d.D1;
1040 for (std::size_t ke = 0; ke < L.K[phcls - 1]; ++ke) {
1041 const T arv = D1k(k, ke);
1042 if (num_traits<T>::to_double(arv) <= 0) continue;
1043 std::vector<T> row = inspace;
1044 row[L.bufw + L.Ks[phcls - 1] + k] -= one;
1045 row[L.bufw + L.Ks[phcls - 1] + ke] += one;
1046 out.space.push_back(row);
1047 out.rate.push_back(T(lld * arv));
1048 out.prob.push_back(one);
1049 }
1050 }
1051 } else if (sched == SchedStrategy::INF || sched == SchedStrategy::PS ||
1052 sched == SchedStrategy::LPS || sched == SchedStrategy::DPS ||
1053 sched == SchedStrategy::GPS || sched == SchedStrategy::PSPRIO ||
1054 sched == SchedStrategy::DPSPRIO || sched == SchedStrategy::GPSPRIO) {
1055 srv[col] -= one;
1056 // The same share PHASE uses: a completion and an internal phase
1057 // advance are driven by the identical fraction of the server, so
1058 // they must never be computed two different ways.
1059 const T rate = T(mu[k] * phi[k] * kir * service_share(sn, ist, m, cls, ni, S));
1060 std::vector<T> row = buf;
1061 row.insert(row.end(), srv.begin(), srv.end());
1062 row.insert(row.end(), var.begin(), var.end());
1063 out.space.push_back(row);
1064 out.rate.push_back(T(lld * rate));
1065 out.prob.push_back(one);
1066 } else if (state_detail::buffer_is_class_tag(sched) && sched != SchedStrategy::FCFS) {
1067 // HOL, LCFS and LCFSPRIO share FCFS's ordered buffer but NOT its
1068 // rate convention: the completion rate is mu*phi*kir, summed over
1069 // destination phases rather than enumerated. What separates the
1070 // three is only WHICH waiting job is promoted.
1071 const bool has_waiting = ni > S && !suppress_promote;
1072 const T rate = T(mu[k] * phi[k] * kir);
1073 srv[col] -= one;
1074 if (!has_waiting) {
1075 std::vector<T> row = buf;
1076 row.insert(row.end(), srv.begin(), srv.end());
1077 row.insert(row.end(), var.begin(), var.end());
1078 out.space.push_back(row);
1079 out.rate.push_back(T(lld * rate));
1080 out.prob.push_back(one);
1081 continue;
1082 }
1083 // Position of the job that starts service, 0-based; L.bufw = none.
1084 std::size_t pos = L.bufw;
1085 if (sched == SchedStrategy::LCFS) {
1086 // Plain LCFS is NOT priority-aware: it always promotes the most
1087 // recent arrival. Arrivals fill the rightmost empty slot, so
1088 // the newest job is the FIRST nonzero column. Branching here on
1089 // the class priorities would silently turn every LCFS station
1090 // with distinct priorities into an LCFSPRIO one.
1091 for (std::size_t b = 0; b < L.bufw; ++b)
1092 if (num_traits<T>::to_double(buf[b]) != 0) { pos = b; break; }
1093 } else {
1094 // HOL and LCFSPRIO serve the highest-priority waiting group
1095 // first; in LINE a LOWER classprio value is more urgent. Within
1096 // the group HOL takes the oldest job (rightmost) and LCFSPRIO
1097 // the newest (leftmost), which is how each relates to its
1098 // non-priority base discipline.
1099 double best = std::numeric_limits<double>::infinity();
1100 for (std::size_t b = 0; b < L.bufw; ++b) {
1101 const double v = num_traits<T>::to_double(buf[b]);
1102 if (v <= 0) continue;
1103 const double p = sn.classes[static_cast<std::size_t>(v) - 1].prio;
1104 if (p < best) best = p;
1105 }
1106 if (std::isfinite(best))
1107 for (std::size_t b = 0; b < L.bufw; ++b) {
1108 const double v = num_traits<T>::to_double(buf[b]);
1109 if (v <= 0) continue;
1110 if (sn.classes[static_cast<std::size_t>(v) - 1].prio != best) continue;
1111 pos = b;
1112 if (sched == SchedStrategy::LCFSPRIO) break; // leftmost
1113 }
1114 }
1115 if (pos == L.bufw) continue;
1116 const std::size_t hc = static_cast<std::size_t>(num_traits<T>::to_double(buf[pos]));
1117 std::vector<T> b2 = buf;
1118 if (sched == SchedStrategy::LCFS) {
1119 // LCFS clears the slot IN PLACE, leaving a hole; the next
1120 // arrival refills it, since arrivals seek the rightmost empty
1121 // slot. The priority variants instead close the gap.
1122 b2[pos] = zero;
1123 } else {
1124 for (std::size_t b = pos; b > 0; --b) b2[b] = b2[b - 1];
1125 b2[0] = zero;
1126 }
1127 const std::vector<T> pentry = entry_phase_dist(sn, ist, hc);
1128 for (std::size_t ke = 0; ke < L.K[hc - 1]; ++ke) {
1129 std::vector<T> s3 = srv;
1130 s3[L.Ks[hc - 1] + ke] += one;
1131 std::vector<T> row = b2;
1132 row.insert(row.end(), s3.begin(), s3.end());
1133 row.insert(row.end(), var.begin(), var.end());
1134 out.space.push_back(row);
1135 out.rate.push_back(T(lld * rate * pentry[ke]));
1136 out.prob.push_back(one);
1137 tag_last(out, hc, 0); // the promoted job takes the freed server
1138 }
1139 } else if (state_detail::buffer_is_class_tag(sched)) {
1140 // FCFS. D1(k, kdest) is the completion rate that leaves the process
1141 // in phase kdest, so the destination phase has to be enumerated
1142 // rather than summed away.
1143 //
1144 // A synchronous call: this departing job KEEPS its server until its
1145 // REPLY returns here, so the server is not handed to a waiting job;
1146 // it is recorded as held in the reply block instead. Servers already
1147 // held that way are likewise unavailable, so a job can be waiting
1148 // while the raw occupancy is below the server count.
1149 std::vector<T> var2 = var;
1150 bool holds_reply = false;
1151 if (sn.replyblock.size() >= ind && sn.replyblock[ind - 1].size() >= cls &&
1152 sn.replyblock[ind - 1][cls - 1]) {
1153 const ReplyBlockInfo ri = reply_block_info(sn, ind);
1154 const std::size_t sl = ri.slot[cls - 1];
1155 if (sl != static_cast<std::size_t>(-1) && sl < var2.size()) {
1156 var2[sl] += one;
1157 holds_reply = true;
1158 }
1159 }
1160 const double nb = reply_blocked(sn, ind, var);
1161 const bool has_waiting = ni > (S - nb) && !suppress_promote && !holds_reply;
1162 // Pair form: the completion rate is done(k) and the class memory is left as it is. A single
1163 // server instead records the phase kd the completion leaves the MAP in.
1164 const CtmcMapc<T>* mcD = sn.mapc_of(ist, cls);
1165 const bool pairD = mcD && !mcD->single;
1166 const std::size_t mslotD = mcD ? sn.map_var_slot(ind, cls) : 0;
1167 const std::vector<T> var2_in = var2;
1168 for (std::size_t kd = 0; kd < L.K[cls - 1]; ++kd) {
1169 if (pairD && kd > 0) break;
1170 const T rate = pairD ? T(mcD->done[k] * kir) : T(d.D1(k, kd) * kir);
1171 var2 = var2_in;
1172 if (mcD && mcD->single) var2[mslotD] = num_traits<T>::from_int(static_cast<long>(kd + 1));
1173 std::vector<T> s2 = srv;
1174 s2[col] -= one;
1175 if (!has_waiting) {
1176 std::vector<T> row = buf;
1177 row.insert(row.end(), s2.begin(), s2.end());
1178 row.insert(row.end(), var2.begin(), var2.end());
1179 out.space.push_back(row);
1180 out.rate.push_back(T(lld * rate));
1181 out.prob.push_back(one);
1182 continue;
1183 }
1184 // Promote the head of the buffer. The head is the LAST column:
1185 // the buffer shifts RIGHT as jobs join, so the oldest job sits
1186 // at the end -- which is what makes the discipline first-come.
1187 const double headv = num_traits<T>::to_double(buf[L.bufw - 1]);
1188 if (headv <= 0) continue;
1189 const std::size_t hc = static_cast<std::size_t>(headv);
1190 std::vector<T> b2(L.bufw, zero);
1191 for (std::size_t b = 1; b < L.bufw; ++b) b2[b] = buf[b - 1];
1192 std::vector<T> pentry = entry_phase_dist(sn, ist, hc);
1193 // Pair form of the promoted class: it starts from its memory h, as in ARV.
1194 const CtmcMapc<T>* mcP = sn.mapc_of(ist, hc);
1195 const std::size_t mslotP = mcP ? sn.map_var_slot(ind, hc) : 0;
1196 if (mcP) {
1197 const long hP = static_cast<long>(num_traits<T>::to_double(var2[mslotP]));
1198 for (std::size_t t = 0; t < mcP->pairs.size(); ++t)
1199 pentry[t] = static_cast<long>(mcP->pairs[t].first) + 1 == hP
1200 ? mcP->V(mcP->pairs[t].first, mcP->pairs[t].second) : zero;
1201 for (std::size_t t = 0; mcP->single && t < mcP->p; ++t)
1202 pentry[t] = static_cast<long>(t) + 1 == hP ? one : zero;
1203 }
1204 for (std::size_t ke = 0; ke < L.K[hc - 1]; ++ke) {
1205 if (mcP && num_traits<T>::to_double(pentry[ke]) == 0) continue;
1206 std::vector<T> s3 = s2;
1207 s3[L.Ks[hc - 1] + ke] += one;
1208 std::vector<T> var3 = var2;
1209 if (mcP && !mcP->single)
1210 var3[mslotP] = num_traits<T>::from_int(static_cast<long>(mcP->pairs[ke].second + 1));
1211 std::vector<T> row = b2;
1212 row.insert(row.end(), s3.begin(), s3.end());
1213 row.insert(row.end(), var3.begin(), var3.end());
1214 const T r3 = T(lld * rate * pentry[ke]);
1215 out.space.push_back(row);
1216 out.rate.push_back(r3);
1217 // A branch that cannot happen carries probability zero, not
1218 // one: a PH whose entry vector does not reach every phase
1219 // would otherwise contribute phantom departures.
1220 out.prob.push_back(num_traits<T>::to_double(r3) == 0 ? zero : one);
1221 tag_last(out, hc, 0); // the head of the buffer takes the freed server
1222 }
1223 }
1224 } else if (sched == SchedStrategy::POLLING) {
1225 // A completion ends the VISIT unless the discipline still allows
1226 // another job of the same class; when it ends, the server walks the
1227 // cyclic order to the next tangible controller state.
1228 const PollingInfo<T> pinfo = polling_info(sn, ind);
1229 const T rate = T(mu[k] * phi[k] * kir);
1230 if (num_traits<T>::to_double(rate) <= 0) continue;
1231 std::size_t pos = 0, swk = 0;
1232 long ctr = 0;
1233 polling_get(pinfo, var, cls, pos, swk, ctr);
1234 // No job can complete while the server is walking.
1235 if (swk != 0) continue;
1236 std::vector<long> nbuf(R, 0);
1237 for (std::size_t r = 0; r < R && r < L.bufw; ++r)
1238 nbuf[r] = static_cast<long>(num_traits<T>::to_double(buf[r]));
1239 srv[col] -= one;
1240 long ctrnext = 0;
1241 bool goon = false;
1242 switch (pinfo.ptype) {
1244 ctrnext = 0;
1245 goon = nbuf[cls - 1] > 0; // the visit ends when it drains
1246 break;
1248 ctrnext = ctr - 1; // one of the gated jobs completed
1249 goon = ctrnext > 0;
1250 break;
1252 ctrnext = ctr - 1; // one of the K permitted services used
1253 goon = ctrnext > 0 && nbuf[cls - 1] > 0;
1254 break;
1256 ctrnext = ctr; // the target level is fixed for the visit
1257 goon = nbuf[cls - 1] > ctr;
1258 break;
1259 }
1260 std::size_t q = cls;
1261 int mode = 1;
1262 long budget = ctrnext;
1263 if (!goon) polling_next(pinfo, cls, nbuf, R, false, q, mode, budget);
1264 std::vector<std::vector<T>> rows;
1265 std::vector<T> probs;
1266 polling_land(sn, ist, pinfo, q, mode, budget, buf, srv, var, L, rows, probs);
1267 for (std::size_t j = 0; j < rows.size(); ++j) {
1268 out.space.push_back(rows[j]);
1269 out.rate.push_back(T(lld * rate * probs[j]));
1270 out.prob.push_back(one);
1271 // mode 1 opens a visit, pulling a waiting class-q job into the
1272 // server; a switchover or a park starts nobody
1273 tag_last(out, mode == 1 ? q : 0, 0);
1274 }
1275 } else if (state_detail::buffer_is_tag_phase_pairs(sched)) {
1276 // THE PREEMPT-RESUME / PREEMPT-INDEPENDENT FAMILY, all eight members.
1277 // Every arm of the reference carries the same rate law, mu*phi*kir
1278 // summed over destination phases (afterEventStation.m:1045, :1081,
1279 // :1118, :1150, :1188, :1234, :1286, :1332); what separates them is
1280 // WHICH waiting job is promoted and in WHICH phase it restarts.
1281 const T rate = T(mu[k] * phi[k] * kir);
1282 srv[col] -= one;
1283 const bool prio_aware = sched == SchedStrategy::FCFSPRPRIO ||
1284 sched == SchedStrategy::FCFSPIPRIO ||
1285 sched == SchedStrategy::LCFSPRPRIO ||
1286 sched == SchedStrategy::LCFSPIPRIO;
1287 const bool lcfs = sched == SchedStrategy::LCFSPR ||
1288 sched == SchedStrategy::LCFSPI ||
1289 sched == SchedStrategy::LCFSPRPRIO ||
1290 sched == SchedStrategy::LCFSPIPRIO;
1291 // PR resumes the promoted job in the phase it was interrupted in;
1292 // PI discards that phase and restarts from the entry distribution.
1293 // That single value is the whole PR-vs-PI difference.
1294 const bool resume = sched == SchedStrategy::LCFSPR ||
1295 sched == SchedStrategy::LCFSPRPRIO ||
1296 sched == SchedStrategy::FCFSPR ||
1297 sched == SchedStrategy::FCFSPRPRIO;
1298 // Class column, 0-based and hence EVEN; L.bufw means "nobody waits".
1299 std::size_t pos = L.bufw;
1300 if (ni > S && !suppress_promote && L.bufw >= 2) {
1301 double best = std::numeric_limits<double>::infinity();
1302 if (prio_aware)
1303 // Only the class columns carry a class tag: reading the
1304 // phase columns too would let a phase index masquerade as a
1305 // class and win the group, which is what the reference's
1306 // FCFSPIPRIO/LCFSPIPRIO arms do (:1290, :1336) while its
1307 // PR-PRIO arms correctly restrict to `class_cols` (:1194).
1308 for (std::size_t b = 0; b + 1 < L.bufw; b += 2) {
1309 const double v = num_traits<T>::to_double(buf[b]);
1310 if (v <= 0) continue;
1311 const double p = sn.classes[static_cast<std::size_t>(v) - 1].prio;
1312 if (p < best) best = p;
1313 }
1314 for (std::size_t b = 0; b + 1 < L.bufw; b += 2) {
1315 const double v = num_traits<T>::to_double(buf[b]);
1316 if (v <= 0) continue;
1317 if (prio_aware && sn.classes[static_cast<std::size_t>(v) - 1].prio != best)
1318 continue;
1319 pos = b;
1320 // The buffer is newest-first, so LCFS takes the FIRST such
1321 // pair (:1052 colfirstnnz) and FCFS the LAST (:1121
1322 // colLastNnz). LCFS does NOT take the rightmost slot.
1323 if (lcfs) break;
1324 }
1325 }
1326 if (pos == L.bufw) {
1327 std::vector<T> row = buf;
1328 row.insert(row.end(), srv.begin(), srv.end());
1329 row.insert(row.end(), var.begin(), var.end());
1330 out.space.push_back(row);
1331 out.rate.push_back(T(lld * rate));
1332 out.prob.push_back(one);
1333 continue;
1334 }
1335 const std::size_t hc = static_cast<std::size_t>(num_traits<T>::to_double(buf[pos]));
1336 const std::size_t kst =
1337 static_cast<std::size_t>(num_traits<T>::to_double(buf[pos + 1]));
1338 if (hc == 0 || hc > R || kst == 0 || kst > L.K[hc - 1])
1339 throw InputError("after_event_station_dep: station '" +
1340 sn.stations[ist - 1].name +
1341 "' holds a waiting job whose [class, phase] pair is malformed");
1342 // Close the hole by padding a whole EMPTY PAIR on the left, keeping
1343 // the buffer right-aligned as `from_marginal` enumerates it and as
1344 // afterEventStation.m:1267-1274 requires. Removing the pair in place
1345 // (:1055, :1125) or padding one slot on each side (:1222) leaves a
1346 // layout the enumerator never emits, so the successor is unreachable
1347 // and the generator becomes reducible.
1348 std::vector<T> b2(L.bufw, zero);
1349 for (std::size_t b = 2; b <= pos + 1; ++b) b2[b] = buf[b - 2];
1350 for (std::size_t b = pos + 2; b < L.bufw; ++b) b2[b] = buf[b];
1351 if (resume) {
1352 std::vector<T> s3 = srv;
1353 s3[L.Ks[hc - 1] + kst - 1] += one;
1354 std::vector<T> row = b2;
1355 row.insert(row.end(), s3.begin(), s3.end());
1356 row.insert(row.end(), var.begin(), var.end());
1357 out.space.push_back(row);
1358 out.rate.push_back(T(lld * rate));
1359 out.prob.push_back(one);
1360 tag_last(out, hc, 0); // the promoted job resumes on the freed server
1361 } else {
1362 const std::vector<T> pentry = entry_phase_dist(sn, ist, hc);
1363 for (std::size_t ke = 0; ke < L.K[hc - 1]; ++ke) {
1364 std::vector<T> s3 = srv;
1365 s3[L.Ks[hc - 1] + ke] += one;
1366 std::vector<T> row = b2;
1367 row.insert(row.end(), s3.begin(), s3.end());
1368 row.insert(row.end(), var.begin(), var.end());
1369 out.space.push_back(row);
1370 out.rate.push_back(T(lld * rate * pentry[ke]));
1371 out.prob.push_back(one);
1372 tag_last(out, hc, 0);
1373 }
1374 }
1375 } else if (state_detail::buffer_is_per_class_count(sched)) {
1376 // A per-class-count buffer promotes by COUNT, since no order is
1377 // recorded. SIRO picks the next job at random, so every waiting
1378 // class is a distinct successor with its share of the queue.
1379 srv[col] -= one;
1380 const T rate = T(mu[k] * phi[k] * kir);
1381 double waiting = 0;
1382 for (std::size_t r = 0; r < R; ++r) waiting += num_traits<T>::to_double(buf[r]);
1383 if (waiting <= 0 || suppress_promote) {
1384 std::vector<T> row = buf;
1385 row.insert(row.end(), srv.begin(), srv.end());
1386 row.insert(row.end(), var.begin(), var.end());
1387 out.space.push_back(row);
1388 out.rate.push_back(T(lld * rate));
1389 out.prob.push_back(one);
1390 continue;
1391 }
1392 for (std::size_t r = 1; r <= R; ++r) {
1393 const double nb = num_traits<T>::to_double(buf[r - 1]);
1394 if (nb <= 0) continue;
1395 const std::vector<T> pentry = entry_phase_dist(sn, ist, r);
1396 for (std::size_t ke = 0; ke < L.K[r - 1]; ++ke) {
1397 std::vector<T> b2 = buf, s2 = srv;
1398 b2[r - 1] -= one;
1399 s2[L.Ks[r - 1] + ke] += one;
1400 std::vector<T> row = b2;
1401 row.insert(row.end(), s2.begin(), s2.end());
1402 row.insert(row.end(), var.begin(), var.end());
1403 out.space.push_back(row);
1404 out.rate.push_back(T(lld * rate));
1405 out.prob.push_back(T(num_traits<T>::from_double(nb / waiting) * pentry[ke]));
1406 tag_last(out, r, 0); // the drawn waiting class takes the server
1407 }
1408 }
1409 } else {
1410 throw UnsupportedError(ErrorKind{"SchedStrategy"},
1411 std::string("after_event_station_dep: the ") + lang::sched_to_text(sched) +
1412 " discipline is not ported yet");
1413 }
1414 }
1415 pad_tags(out);
1416 return out;
1417}
1418
1419/**
1420 * The fraction of the station's capacity a class-`cls` job in phase `k`
1421 * receives, which is the only part of the rate the discipline decides.
1422 *
1423 * PHASE and DEP share this factor exactly: an internal phase transition is
1424 * driven by the same server share as a completion, which is why a job under PS
1425 * advances through its phases more slowly when the station is busy. Only the
1426 * MATRIX differs -- D0(k,kdest) for a phase advance, D1 for a completion.
1427 */
1428template <class T>
1429T service_share(const NetworkStruct<T>& sn, std::size_t ist, const Marginal<T>& m,
1430 std::size_t cls, double ni, double S) {
1431 const std::size_t R = sn.nclasses;
1432 const SchedStrategy sched = sn.stations[ist - 1].sched;
1433 const T zero = num_traits<T>::from_int(0), one = num_traits<T>::from_int(1);
1434
1435 // The *PRIO variants behave as their base discipline while every job fits
1436 // in a server -- with n <= c nobody is waiting, so precedence is moot. Once
1437 // the station saturates, only the MOST URGENT group present is served, and
1438 // the sharing is computed among that group alone. `prio_pop` is the single
1439 // definition of that group, shared with the load-dependent lookup.
1440 const PrioPop<T> p = prio_pop(sn, ist, m, cls, ni, S);
1441 if (!p.served) return zero; // a lower-priority class gets no service at all
1442 const std::vector<T>& nir = p.nir;
1443 const double nieff = p.ni;
1444
1445 if (sched == SchedStrategy::PS || sched == SchedStrategy::LPS ||
1446 sched == SchedStrategy::PSPRIO)
1447 return nieff > 0 ? num_traits<T>::from_double(std::min(nieff, S) / nieff) : zero;
1448 if (sched == SchedStrategy::DPS || sched == SchedStrategy::GPS ||
1449 sched == SchedStrategy::DPSPRIO || sched == SchedStrategy::GPSPRIO) {
1450 if (S > 1)
1451 throw UnsupportedError(ErrorKind{"MultiServer"},
1452 "state_events: multi-server DPS/GPS stations are not supported");
1453 const bool dps = sched == SchedStrategy::DPS || sched == SchedStrategy::DPSPRIO;
1454 const std::vector<T>& w = sn.stations[ist - 1].schedparam;
1455 T wsum = zero;
1456 for (std::size_t r = 0; r < R; ++r) wsum += w[r];
1457 T denom = zero;
1458 for (std::size_t r = 0; r < R; ++r) {
1459 // DPS weights by the job COUNTS; GPS shares between the classes
1460 // PRESENT, so each contributes at most one however many it holds.
1461 const T nr = dps ? nir[r] : (num_traits<T>::to_double(nir[r]) > 0 ? one : zero);
1462 denom += T(w[r] / wsum * nr);
1463 }
1464 const T nc = nir[cls - 1];
1465 if (num_traits<T>::to_double(denom) == 0 || num_traits<T>::to_double(nc) == 0)
1466 return zero;
1467 const T sh = T((w[cls - 1] / wsum) / denom);
1468 return dps ? sh : T(sh / nc);
1469 }
1470 // INF and the queueing disciplines: a job in service holds a whole server.
1471 return one;
1472}
1473
1474/**
1475 * Port of the PHASE branch of `State.afterEventStation`: service advances a
1476 * phase WITHOUT completing.
1477 *
1478 * The rate is D0(k, kdest), the off-diagonal of the hidden generator, times the
1479 * same server share a completion gets. Keeping PHASE and DEP on one share is
1480 * what makes a phase-type service slow down consistently under contention; a
1481 * phase advance at full speed under PS would shorten the effective service.
1482 */
1483template <class T>
1485 const std::vector<T>& inspace, std::size_t cls) {
1486 const std::size_t R = sn.nclasses;
1487 const std::size_t ist = sn.nodes[ind - 1].station;
1488 const T one = num_traits<T>::from_int(1);
1489 EventOutcome<T> out;
1490 if (ist == 0) throw InputError("after_event_station_phase: node is not a station");
1491 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
1492 const double S = sn.stations[ist - 1].nservers;
1493
1494 std::vector<std::size_t> ph(R, 1), shift(R, 0);
1495 for (std::size_t r = 0; r < R; ++r) {
1496 ph[r] = L.K[r];
1497 shift[r] = L.Ks[r];
1498 }
1499 const Marginal<T> m = to_marginal(sn, ist, inspace, ph, shift, L.nvar);
1500 if (num_traits<T>::to_double(m.nir[cls - 1]) <= 0) return out;
1501
1502 double ni = 0;
1503 for (std::size_t r = 0; r < R; ++r) ni += num_traits<T>::to_double(m.nir[r]);
1504 // Unlike DEP, the PHASE branch takes the UNMASKED population for both
1505 // factors even at a saturated *PRIO station (afterEventStation.m:1688): the
1506 // masking there is a property of the completion rate, not of the lookup, and
1507 // `service_share` already zeroes a non-urgent class's advance.
1508 const T lld = T(lld_factor(sn, ist, ni) * cd_factor(sn, ist, m.nir, cls));
1509 const T share = service_share(sn, ist, m, cls, ni, S);
1510 const lang::Distrib<T>& d = sn.service[ist - 1][cls - 1];
1511 if (d.D0.rows() != L.K[cls - 1]) return out;
1512 const CtmcMapc<T>* mcS = sn.mapc_of(ist, cls);
1513
1514 for (std::size_t k = 0; k < L.K[cls - 1]; ++k) {
1515 if (num_traits<T>::to_double(inspace[L.bufw + L.Ks[cls - 1] + k]) <= 0) continue;
1516 for (std::size_t kd = 0; kd < L.K[cls - 1]; ++kd) {
1517 if (kd == k) continue; // the diagonal is the exit rate, not a move
1518 std::vector<T> row = inspace;
1519 row[L.bufw + L.Ks[cls - 1] + k] -= one;
1520 row[L.bufw + L.Ks[cls - 1] + kd] += one;
1521 // A single-server MAP in carried form keeps its memory equal to the phase in service.
1522 if (mcS && mcS->single)
1523 row[L.bufw + L.srvw + sn.map_var_slot(ind, cls)] = num_traits<T>::from_int(static_cast<long>(kd + 1));
1524 out.space.push_back(row);
1525 out.rate.push_back(T(lld * d.D0(k, kd) * m.kir[cls - 1][k] * share));
1526 out.prob.push_back(one);
1527 }
1528 }
1529 return out;
1530}
1531
1532/**
1533 * `sn.impatienceMu(ist,cls)`: the rate of an exponential reneging patience, 0 when the class
1534 * declares none. The analyzers refuse a non-exponential patience before any event fires.
1535 */
1536template <class T>
1537T station_renege_mu(const NetworkStruct<T>& sn, std::size_t ist, std::size_t cls) {
1538 const Station<T>& st = sn.stations[ist - 1];
1539 if (cls > st.impatience.size() || st.impatience[cls - 1] != lang::ImpatienceType::RENEGING ||
1540 cls > st.patience.size() || st.patience[cls - 1].disabled ||
1541 !(st.patience[cls - 1].mean > num_traits<T>::from_int(0)))
1542 return num_traits<T>::from_int(0);
1543 return T(num_traits<T>::from_int(1) / st.patience[cls - 1].mean);
1544}
1545
1546/**
1547 * Port of `solver_ctmc_state_supports.m`: the impatience laws the state machinery cannot
1548 * serve, as the refusal sentence, or "" when it can. RENEGE and RETRY fire at a memoryless
1549 * rate and balking reads the station population, so a non-exponential patience or retrial
1550 * delay, a wait-based balking rule, a finite attempt count, orbit abandonment and a
1551 * multi-class retrial station would otherwise be answered as if they were absent.
1552 */
1553template <class T>
1554std::string state_impatience_unsupported(const NetworkStruct<T>& sn, const std::string& solver) {
1555 // RENEGE fires at (waiting jobs) * impatienceMu with no per-job patience phase, so the law
1556 // must be EXPONENTIAL, not merely Markovian (MATLAB sn_patience_exp_refusal)
1557 const std::string patWhy = ::line::api::sn_patience_exp_refusal(sn);
1558 if (!patWhy.empty()) return patWhy + " Use SolverLDES or SolverJMT for any other patience.";
1559 for (std::size_t i = 0; i < sn.stations.size(); ++i) {
1560 const Station<T>& st = sn.stations[i];
1561 for (std::size_t r = 0; r < st.balking.size(); ++r)
1562 if (st.balking[r].strategy != lang::BalkingStrategy::NONE &&
1564 return solver + " supports only QUEUE_LENGTH balking. Use SolverLDES or SolverJMT "
1565 "for wait-time-based balking.";
1566 }
1567 for (const auto& kv : sn.retrialparam) {
1568 const RetrialParam<T>& rp = kv.second;
1569 const Station<T>& st = sn.stations[kv.first - 1];
1570 bool any = false;
1571 for (std::size_t r = 0; r < rp.retrial_proc.size(); ++r) {
1572 if (rp.retrial_proc[r].disabled) continue;
1573 any = true;
1574 if (rp.retrial_proc[r].type != lang::ProcessType::EXP)
1575 return solver + " supports only exponential (memoryless) retrial delay. Use "
1576 "SolverLDES for a non-exponential retrial delay (SolverMAM requires an exponential one too).";
1577 if (r < rp.max_attempts.size() && rp.max_attempts[r] > 0)
1578 return solver + " supports only unlimited retrials. Use SolverLDES for finite "
1579 "max-attempts.";
1580 if (r < st.orbit_impatience.size() && !st.orbit_impatience[r].disabled)
1581 return solver + " does not model abandonment from the retrial orbit "
1582 "(set_orbit_impatience). Use SolverMAM or SolverLDES.";
1583 }
1584 if (!any) continue;
1585 std::size_t served = 0;
1586 for (std::size_t r = 0; r < sn.nclasses; ++r)
1587 if (!sn.disabled[kv.first - 1][r] && sn.service[kv.first - 1][r].D0.rows() > 0) ++served;
1588 if (served > 1)
1589 return solver + " supports retrial only for single-class stations. Use SolverLDES for "
1590 "multi-class retrial.";
1591 }
1592 return "";
1593}
1594
1595/** True when station `ist` declares exponential reneging for some class. */
1596template <class T>
1597bool station_has_reneging(const NetworkStruct<T>& sn, std::size_t ist) {
1598 for (std::size_t r = 1; r <= sn.nclasses; ++r)
1599 if (station_renege_mu(sn, ist, r) > num_traits<T>::from_int(0)) return true;
1600 return false;
1601}
1602
1603/**
1604 * `sn.retrialMu(ist,cls)`: the rate of the exponential retrial delay, falling back to the
1605 * scalar `retrial_rate` when no process is given; 0 when the class has no orbit.
1606 */
1607template <class T>
1608T station_retrial_mu(const NetworkStruct<T>& sn, std::size_t ist, std::size_t cls) {
1609 const T zero = num_traits<T>::from_int(0);
1610 const typename std::map<std::size_t, RetrialParam<T>>::const_iterator rit =
1611 sn.retrialparam.find(ist);
1612 if (rit == sn.retrialparam.end()) return zero;
1613 const RetrialParam<T>& rp = rit->second;
1614 if (cls <= rp.retrial_proc.size() && !rp.retrial_proc[cls - 1].disabled &&
1615 rp.retrial_proc[cls - 1].mean > zero)
1616 return T(num_traits<T>::from_int(1) / rp.retrial_proc[cls - 1].mean);
1617 if (cls <= rp.retrial_rate.size() && rp.retrial_rate[cls - 1] > zero)
1618 return rp.retrial_rate[cls - 1];
1619 return zero;
1620}
1621
1622/** `sn.retrialPolicy(ist,cls) == CONSTANT`: one retry clock for the whole orbit. */
1623template <class T>
1624bool station_retrial_constant(const NetworkStruct<T>& sn, std::size_t ist, std::size_t cls) {
1625 const typename std::map<std::size_t, RetrialParam<T>>::const_iterator rit =
1626 sn.retrialparam.find(ist);
1627 return rit != sn.retrialparam.end() && cls <= rit->second.policy.size() &&
1628 rit->second.policy[cls - 1] == 2;
1629}
1630
1631/**
1632 * Port of the QUEUE_LENGTH balking branch of the ARV event: with the probability of the
1633 * threshold band holding the PRE-arrival station population, the arriving job refuses to
1634 * join and is lost, so the station row is left unchanged; every admitted branch is scaled
1635 * by one minus that probability. EXPECTED_WAIT and COMBINED read a mean wait, not the
1636 * state, and are refused by the analyzers.
1637 */
1638template <class T>
1639void apply_station_balking(const NetworkStruct<T>& sn, std::size_t ind,
1640 const std::vector<T>& inspace, std::size_t cls, EventOutcome<T>& out) {
1641 const std::size_t ist = sn.nodes[ind - 1].station;
1642 if (ist == 0 || out.space.empty()) return;
1643 const Station<T>& st = sn.stations[ist - 1];
1644 if (cls > st.balking.size() || st.balking[cls - 1].strategy != lang::BalkingStrategy::QUEUE_LENGTH)
1645 return;
1646 const std::size_t R = sn.nclasses;
1647 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
1648 std::vector<std::size_t> ph(R, 1), shift(R, 0);
1649 for (std::size_t r = 0; r < R; ++r) {
1650 ph[r] = L.K[r];
1651 shift[r] = L.Ks[r];
1652 }
1653 const double qlen = num_traits<T>::to_double(to_marginal(sn, ist, inspace, ph, shift, L.nvar).ni);
1654 T pbalk = num_traits<T>::from_int(0);
1655 for (const typename Station<T>::BalkingThreshold& th : st.balking[cls - 1].thresholds)
1656 if (qlen >= th.min_jobs && (th.max_jobs < 0 || qlen <= th.max_jobs)) {
1657 pbalk = th.probability;
1658 break;
1659 }
1660 if (!(pbalk > num_traits<T>::from_int(0))) return;
1661 for (std::size_t i = 0; i < out.prob.size(); ++i)
1662 out.prob[i] = T(out.prob[i] * (num_traits<T>::from_int(1) - pbalk));
1663 out.space.push_back(inspace);
1664 out.rate.push_back(num_traits<T>::from_int(-1));
1665 out.prob.push_back(pbalk);
1666 pad_tags(out);
1667}
1668
1669/**
1670 * Port of the RENEGE branch: a WAITING class-`cls` job abandons the queue.
1671 *
1672 * Patience is exponential, so every waiting job abandons at the same rate and
1673 * the aggregate out of this state is (waiting count) * mu. Which job leaves is
1674 * therefore immaterial -- waiting jobs are exchangeable under memoryless
1675 * patience -- so the reference removes the first tagged slot and re-pads a zero
1676 * on the left, keeping the buffer in the right-aligned form the arrival handler
1677 * expects.
1678 */
1679template <class T>
1681 const std::vector<T>& inspace, std::size_t cls,
1682 const T& impatience_mu) {
1683 const std::size_t R = sn.nclasses;
1684 const std::size_t ist = sn.nodes[ind - 1].station;
1685 EventOutcome<T> out;
1686 if (ist == 0) throw InputError("after_event_station_renege: node is not a station");
1687 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
1688
1689 std::vector<std::size_t> ph(R, 1), shift(R, 0);
1690 for (std::size_t r = 0; r < R; ++r) {
1691 ph[r] = L.K[r];
1692 shift[r] = L.Ks[r];
1693 }
1694 const Marginal<T> m = to_marginal(sn, ist, inspace, ph, shift, L.nvar);
1695 const double waiting = num_traits<T>::to_double(m.nir[cls - 1]) -
1696 num_traits<T>::to_double(m.sir[cls - 1]);
1697 if (waiting <= 0) return out;
1698 // The station's own impatienceMu unless the caller supplies one, as for breakdowns.
1699 const T mu = impatience_mu > num_traits<T>::from_int(0) ? impatience_mu
1700 : station_renege_mu(sn, ist, cls);
1701 if (!(mu > num_traits<T>::from_int(0))) return out;
1702
1703 const T tag = num_traits<T>::from_int(static_cast<long>(cls));
1704 std::size_t slot = L.bufw;
1705 for (std::size_t b = 0; b < L.bufw; ++b)
1706 if (inspace[b] == tag) { slot = b; break; }
1707 if (slot == L.bufw) return out;
1708
1709 std::vector<T> row = inspace;
1710 for (std::size_t b = slot; b > 0; --b) row[b] = row[b - 1];
1711 row[0] = num_traits<T>::from_int(0);
1712 out.space.push_back(row);
1713 out.rate.push_back(T(num_traits<T>::from_double(waiting) * mu));
1714 out.prob.push_back(num_traits<T>::from_int(1));
1715 return out;
1716}
1717
1718/**
1719 * Port of the RETRY branch: an ORBITING class-`cls` job retries entry.
1720 *
1721 * The retry succeeds only when a server is free; otherwise the job stays in
1722 * orbit and the event is not generated at all, which is exactly what
1723 * distinguishes a retrial queue from a queue whose buffer is called an orbit.
1724 *
1725 * @param constant_policy CONSTANT retrial: one controller retries for the whole
1726 * orbit, so the rate does NOT scale with the orbit size. Under the
1727 * default LINEAR policy every orbiting job carries its own timer and the
1728 * aggregate rate is (orbit size) * mu.
1729 * @param sn the refreshed network struct
1730 * @param ind index of the station the event fires at
1731 * @param inspace the state the event is applied to
1732 * @param cls class of the retrying job
1733 * @param retrial_mu retrial rate of that class
1734 */
1735template <class T>
1737 const std::vector<T>& inspace, std::size_t cls,
1738 const T& retrial_mu, bool constant_policy = false) {
1739 const std::size_t R = sn.nclasses;
1740 const std::size_t ist = sn.nodes[ind - 1].station;
1741 const T one = num_traits<T>::from_int(1);
1742 EventOutcome<T> out;
1743 if (ist == 0) throw InputError("after_event_station_retry: node is not a station");
1744 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
1745 const double S = sn.stations[ist - 1].nservers;
1746
1747 std::vector<std::size_t> ph(R, 1), shift(R, 0);
1748 for (std::size_t r = 0; r < R; ++r) {
1749 ph[r] = L.K[r];
1750 shift[r] = L.Ks[r];
1751 }
1752 const Marginal<T> m = to_marginal(sn, ist, inspace, ph, shift, L.nvar);
1753 const double orbit = num_traits<T>::to_double(m.nir[cls - 1]) -
1754 num_traits<T>::to_double(m.sir[cls - 1]);
1755 double occ = 0;
1756 for (std::size_t j = 0; j < L.srvw; ++j) occ += num_traits<T>::to_double(inspace[L.bufw + j]);
1757 if (orbit <= 0 || occ >= S) return out;
1758
1759 const T tag = num_traits<T>::from_int(static_cast<long>(cls));
1760 std::size_t slot = L.bufw;
1761 for (std::size_t b = 0; b < L.bufw; ++b)
1762 if (inspace[b] == tag) { slot = b; break; }
1763 if (slot == L.bufw) return out;
1764
1765 const std::vector<T> pentry = entry_phase_dist(sn, ist, cls);
1766 // The station's own retrialMu and policy unless the caller supplies a rate, as for breakdowns.
1767 const bool from_struct = !(retrial_mu > num_traits<T>::from_int(0));
1768 const T mu = from_struct ? station_retrial_mu(sn, ist, cls) : retrial_mu;
1769 if (!(mu > num_traits<T>::from_int(0))) return out;
1770 const bool constant = from_struct ? station_retrial_constant(sn, ist, cls) : constant_policy;
1771 const T agg = constant ? mu : T(num_traits<T>::from_double(orbit) * mu);
1772 for (std::size_t ke = 0; ke < L.K[cls - 1]; ++ke) {
1773 if (num_traits<T>::to_double(pentry[ke]) <= 0) continue;
1774 std::vector<T> row = inspace;
1775 for (std::size_t b = slot; b > 0; --b) row[b] = row[b - 1];
1776 row[0] = num_traits<T>::from_int(0);
1777 row[L.bufw + L.Ks[cls - 1] + ke] += one;
1778 out.space.push_back(row);
1779 out.rate.push_back(T(agg * pentry[ke]));
1780 out.prob.push_back(one);
1781 // A successful retry is the only way into the server at a retrial
1782 // station (its departures never promote from the orbit), so it carries
1783 // the START the startRate == TN + preemptRate identity needs.
1784 tag_last(out, cls, 0);
1785 }
1786 pad_tags(out);
1787 return out;
1788}
1789
1790/**
1791 * Port of the FAILURE and REPAIR branches: the server goes down, or comes back.
1792 *
1793 * Only the STATUS column moves, which is the trailing local variable. Jobs in
1794 * service are NOT lost: service is memoryless here, so an interrupted job
1795 * resumes on repair with no state to remember. The passive half of the
1796 * synchronization is LOCAL, so no job moves anywhere in the network either.
1797 *
1798 * @param up true for REPAIR (0 -> 1), false for FAILURE (1 -> 0)
1799 * @param mu breakdownMu for a failure, repairMu for a repair
1800 * @param sn the refreshed network struct
1801 * @param ind index of the station the event fires at
1802 * @param inspace the state the event is applied to
1803 */
1804template <class T>
1806 const std::vector<T>& inspace, bool up,
1807 const T& mu) {
1808 EventOutcome<T> out;
1809 if (inspace.empty() || !sn.has_breakdown_node(ind)) return out;
1810 const double status = num_traits<T>::to_double(inspace.back());
1811 // A failure needs an UP server and a repair a DOWN one; anything else is
1812 // not an admissible transition and must produce no edge at all.
1813 if ((up && status != 0) || (!up && status != 1)) return out;
1814 std::vector<T> row = inspace;
1815 row.back() = num_traits<T>::from_int(up ? 1 : 0);
1816 // The rate is the station's own breakdownMu / repairMu unless the caller
1817 // supplies one; no caller does today, so the struct is the source of truth.
1818 T rate = mu;
1819 if (!(rate > num_traits<T>::from_int(0))) {
1820 const BreakdownParam<T>& bp = sn.breakdownparam.at(sn.nodes[ind - 1].station);
1821 rate = up ? bp.repair_rate : bp.failure_rate;
1822 }
1823 out.space.push_back(row);
1824 out.rate.push_back(rate);
1825 out.prob.push_back(num_traits<T>::from_int(1));
1826 return out;
1827}
1828
1829/**
1830 * Port of `State.afterEventFork`: an event at a STATEFUL Fork node.
1831 *
1832 * The fork's state is a plain per-class count of PARENT jobs momentarily held
1833 * between their arrival and the firing. An arrival buffers one; a DEPARTURE DOES
1834 * NOT EXIST, because the multi-branch emission is atomic across several nodes and
1835 * cannot be decomposed into a departure here plus an arrival there --
1836 * `refresh_sync` emits no DEP sync for a Fork and `after_fj_event` fires instead.
1837 *
1838 * The arrival rate is left UNSET (the reference writes -1) because an ARV is the
1839 * PASSIVE half of a synchronization: the rate belongs to the active departure
1840 * upstream.
1841 */
1842template <class T>
1844 const std::vector<T>& inspace, EventType event,
1845 std::size_t cls) {
1846 const std::size_t R = sn.nclasses;
1847 EventOutcome<T> out;
1848 if (event != EventType::ARV) return out;
1849 if (inspace.size() < R)
1850 throw InputError("after_event_fork: the Fork state row at node '" + sn.nodes[ind - 1].name +
1851 "' is narrower than the class set");
1852 std::vector<T> row = inspace;
1853 // The counts are the LAST R columns, which is where `from_marginal_node`
1854 // puts them and where `after_fj_event` reads them.
1855 row[row.size() - R + cls - 1] += num_traits<T>::from_int(1);
1856 out.space.push_back(row);
1857 out.rate.push_back(num_traits<T>::from_int(-1));
1858 out.prob.push_back(num_traits<T>::from_int(1));
1859 return out;
1860}
1861
1862/**
1863 * Port of `State.afterEventJoin`: an event at a Join node of an FJ-augmented
1864 * struct.
1865 *
1866 * The join's state is a plain per-class count vector of BUFFERED jobs, so it
1867 * bypasses the buffer/server/local slicing every other station takes -- a join
1868 * performs no service, it performs a rendezvous.
1869 *
1870 * ARV buffers the arriving job or sibling. DEP in an ORIGINAL class r fires when
1871 * either a plain (never-forked) class-r job is buffered, or some tag has its full
1872 * required sibling multiset present; the firing consumes the siblings of the
1873 * LOWEST complete tag, which is the same canonical choice the fork's allocation
1874 * makes and is what keeps the two in step. DEP in an AUXILIARY class is refused
1875 * outright: a sibling never departs on its own, it is consumed by the parent's
1876 * firing, and letting it depart would release a job the fork never emitted.
1877 */
1878template <class T>
1880 const std::vector<T>& inspace, EventType event,
1881 std::size_t cls) {
1882 const std::size_t R = sn.nclasses;
1883 const T one = num_traits<T>::from_int(1);
1884 EventOutcome<T> out;
1885 if (inspace.size() < R)
1886 throw InputError("after_event_join: the Join state row at node '" + sn.nodes[ind - 1].name +
1887 "' is narrower than the class set");
1888 const std::size_t off = inspace.size() - R;
1889
1890 if (event == EventType::ARV) {
1891 std::vector<T> row = inspace;
1892 row[off + cls - 1] += one;
1893 out.space.push_back(row);
1894 out.rate.push_back(num_traits<T>::from_int(-1));
1895 out.prob.push_back(one);
1896 return out;
1897 }
1898 if (event != EventType::DEP) return out;
1899
1900 const typename std::map<std::size_t, FjJoinParam>::const_iterator jit =
1901 sn.fjjoinparam.find(ind);
1902 const FjJoinParam* fjp = jit == sn.fjjoinparam.end() ? 0 : &jit->second;
1903
1904 if (fjp) {
1905 for (std::size_t x = 0; x < fjp->origclasses.size(); ++x) {
1906 const std::map<std::size_t, std::vector<std::vector<std::size_t>>>::const_iterator ait =
1907 fjp->auxmatrix.find(fjp->origclasses[x]);
1908 if (ait == fjp->auxmatrix.end()) continue;
1909 for (std::size_t b = 0; b < ait->second.size(); ++b)
1910 for (std::size_t t = 0; t < ait->second[b].size(); ++t)
1911 if (ait->second[b][t] == cls) return out; // an auxiliary class
1912 }
1913 }
1914
1916 if (num_traits<T>::to_double(inspace[off + cls - 1]) > 0) {
1917 // A plain job that never went through the fork: it passes straight
1918 // through, since a join is a rendezvous only for siblings.
1919 std::vector<T> row = inspace;
1920 row[off + cls - 1] -= one;
1921 out.space.push_back(row);
1922 out.rate.push_back(imm);
1923 out.prob.push_back(one);
1924 return out;
1925 }
1926 if (!fjp) return out;
1927 const std::map<std::size_t, std::vector<std::vector<std::size_t>>>::const_iterator ait =
1928 fjp->auxmatrix.find(cls);
1929 const std::map<std::size_t, std::vector<std::size_t>>::const_iterator rit =
1930 fjp->required.find(cls);
1931 if (ait == fjp->auxmatrix.end() || rit == fjp->required.end()) return out;
1932 const std::vector<std::vector<std::size_t>>& aux = ait->second;
1933 const std::vector<std::size_t>& req = rit->second;
1934 if (aux.empty()) return out;
1935 const std::size_t B = aux.size(), Tt = aux[0].size();
1936 for (std::size_t t = 0; t < Tt; ++t) {
1937 bool complete = true;
1938 for (std::size_t b = 0; b < B && complete; ++b) {
1939 const std::size_t a = aux[b][t];
1940 const double need = b < req.size() ? static_cast<double>(req[b]) : 1.0;
1941 if (num_traits<T>::to_double(inspace[off + a - 1]) < need) complete = false;
1942 }
1943 if (!complete) continue;
1944 std::vector<T> row = inspace;
1945 for (std::size_t b = 0; b < B; ++b) {
1946 const std::size_t a = aux[b][t];
1947 const long need = b < req.size() ? static_cast<long>(req[b]) : 1;
1948 row[off + a - 1] -= num_traits<T>::from_int(need);
1949 }
1950 out.space.push_back(row);
1951 out.rate.push_back(imm);
1952 out.prob.push_back(one);
1953 return out; // the LOWEST complete tag only; the rest are permutations
1954 }
1955 return out;
1956}
1957
1958/**
1959 * Port of `State.afterEventStation`'s dispatch: the successors of one event at
1960 * one station.
1961 *
1962 * The event-specific rates that are not derivable from `sn` alone -- patience,
1963 * retrial and breakdown -- are passed in, because the reference reads them from
1964 * fields (`impatienceMu`, `retrialMu`, `breakdownMu`) that this port has not
1965 * yet grown. Every rate that IS derivable is computed from the struct.
1966 */
1967template <class T>
1968void rr_advance_row(const NetworkStruct<T>& sn, std::size_t ind, std::size_t cls,
1969 std::vector<std::vector<T>>& rows);
1970
1971/**
1972 * Port of `State.afterEventRouter`: a Router holds a job for the instant it
1973 * takes to decide where it goes.
1974 *
1975 * The row is [per-class counts | local vars], with no buffer and no phase: a
1976 * Router serves nothing, so there is no service state to carry. An ARRIVAL adds
1977 * the job at an UNSPECIFIED rate (-1), which is the reference's marker for a
1978 * passive half whose rate the active half sets; a DEPARTURE removes it at the
1979 * Immediate rate and advances the dispatch pointer, so the router never holds a
1980 * job for a positive length of time.
1981 */
1982template <class T>
1984 const std::vector<T>& inspace, EventType event,
1985 std::size_t cls) {
1986 EventOutcome<T> out;
1987 const std::size_t R = sn.nclasses;
1988 if (inspace.size() < R) return out;
1989 const T one = num_traits<T>::from_int(1);
1990 if (event == EventType::ARV) {
1991 std::vector<T> row = inspace;
1992 row[cls - 1] = T(row[cls - 1] + one);
1993 out.space.push_back(row);
1994 // Passive action: the rate is the active half's, not this node's.
1995 out.rate.push_back(num_traits<T>::from_int(-1));
1996 out.prob.push_back(one);
1997 return out;
1998 }
1999 if (event == EventType::DEP) {
2000 if (!(num_traits<T>::to_double(inspace[cls - 1]) > 0)) return out;
2001 std::vector<T> row = inspace;
2002 row[cls - 1] = T(row[cls - 1] - one);
2003 out.space.push_back(row);
2005 out.prob.push_back(one);
2006 rr_advance_row(sn, ind, cls, out.space);
2007 return out;
2008 }
2009 return out;
2010}
2011
2012/**
2013 * Advance the round-robin dispatch pointer of (IND, CLS) in every successor row.
2014 *
2015 * The local-variable block is the TAIL of a state row, so the pointer is located
2016 * from the right; `rr_var_slot` gives its 1-based index inside that block. A
2017 * no-op wherever the pair does not dispatch round-robin.
2018 */
2019template <class T>
2020void rr_advance_row(const NetworkStruct<T>& sn, std::size_t ind, std::size_t cls,
2021 std::vector<std::vector<T>>& rows) {
2022 if (sn.rr_var_slot(ind, cls) == 0) return;
2023 const std::size_t w = sn.nvars_of(ind);
2024 if (w == 0) return;
2025 for (std::size_t i = 0; i < rows.size(); ++i) {
2026 if (rows[i].size() < w) continue;
2027 std::vector<T> var(rows[i].end() - w, rows[i].end());
2028 sn.rr_advance(ind, cls, var);
2029 std::copy(var.begin(), var.end(), rows[i].end() - w);
2030 }
2031}
2032
2033namespace pool_detail {
2034
2035/** One successor of a pooled service start: the buffer, the servers, its weight and the class started. */
2036template <class T>
2038 std::vector<T> buf, srv;
2039 T p;
2040 std::size_t cls;
2041};
2042
2043/** Class s starts service on pool t in every entry phase of the pool's block. */
2044template <class T>
2045void pool_start(const CtmcPool<T>& pool, const std::vector<std::size_t>& Ks,
2046 const std::vector<T>& buf, const std::vector<T>& srv, std::size_t s,
2047 std::size_t t, const T& w, std::vector<PoolStart<T>>& out) {
2048 const std::vector<std::size_t>& ps = pool.pools[s - 1];
2049 std::size_t k = 0;
2050 while (k < ps.size() && ps[k] != t) ++k;
2051 const std::vector<T>& a = pool.alpha[s - 1][k];
2052 for (std::size_t j = 0; j < a.size(); ++j) {
2053 if (!(num_traits<T>::to_double(a[j]) > 0)) continue;
2054 PoolStart<T> st{buf, srv, T(w * a[j]), s};
2055 st.srv[Ks[s - 1] + pool.off[s - 1][k] + j] += num_traits<T>::from_int(1);
2056 out.push_back(st);
2057 }
2058}
2059
2060/** The freed server of pool t takes the next compatible waiting job, in the discipline's order. */
2061template <class T>
2062std::vector<PoolStart<T>> pool_serve_next(const NetworkStruct<T>& sn, const CtmcPool<T>& pool,
2063 SchedStrategy sched, const std::vector<std::size_t>& Ks,
2064 const std::vector<T>& buf, const std::vector<T>& srv,
2065 std::size_t t) {
2066 const std::size_t R = sn.nclasses;
2067 const T one = num_traits<T>::from_int(1), zero = num_traits<T>::from_int(0);
2068 std::vector<PoolStart<T>> out;
2069 if (sched == SchedStrategy::SIRO) {
2070 double tot = 0;
2071 for (std::size_t s = 0; s < R; ++s)
2072 if (pool.compat[t - 1][s]) tot += num_traits<T>::to_double(buf[s]);
2073 if (tot <= 0) {
2074 out.push_back(PoolStart<T>{buf, srv, one, 0});
2075 return out;
2076 }
2077 for (std::size_t s = 0; s < R; ++s) {
2078 const double bs = num_traits<T>::to_double(buf[s]);
2079 if (!pool.compat[t - 1][s] || bs <= 0) continue;
2080 std::vector<T> b = buf;
2081 b[s] -= one;
2082 pool_start(pool, Ks, b, srv, s + 1, t, num_traits<T>::from_double(bs / tot), out);
2083 }
2084 return out;
2085 }
2086 std::vector<std::size_t> pos;
2087 for (std::size_t p = 0; p < buf.size(); ++p) {
2088 const long c = static_cast<long>(num_traits<T>::to_double(buf[p]) + 0.5);
2089 if (c >= 1 && static_cast<std::size_t>(c) <= R && pool.compat[t - 1][c - 1]) pos.push_back(p);
2090 }
2091 if (pos.empty()) {
2092 out.push_back(PoolStart<T>{buf, srv, one, 0});
2093 return out;
2094 }
2095 const auto cls_at = [&](std::size_t p) {
2096 return static_cast<std::size_t>(num_traits<T>::to_double(buf[p]) + 0.5);
2097 };
2098 if (sched == SchedStrategy::HOL || sched == SchedStrategy::LCFSPRIO) {
2099 int best = sn.classes[cls_at(pos[0]) - 1].prio;
2100 for (std::size_t i = 1; i < pos.size(); ++i)
2101 best = std::min(best, sn.classes[cls_at(pos[i]) - 1].prio); // lower value, higher priority
2102 std::vector<std::size_t> keep;
2103 for (std::size_t i = 0; i < pos.size(); ++i)
2104 if (sn.classes[cls_at(pos[i]) - 1].prio == best) keep.push_back(pos[i]);
2105 pos.swap(keep);
2106 }
2107 // LCFS takes the leftmost (newest) job, the others the rightmost (oldest)
2108 const bool lcfs = sched == SchedStrategy::LCFS || sched == SchedStrategy::LCFSPRIO;
2109 const std::size_t p = lcfs ? pos.front() : pos.back();
2110 const std::size_t s = cls_at(p);
2111 std::vector<T> b(1, zero);
2112 for (std::size_t q = 0; q < buf.size(); ++q)
2113 if (q != p) b.push_back(buf[q]);
2114 pool_start(pool, Ks, b, srv, s, t, one, out);
2115 return out;
2116}
2117
2118} // namespace pool_detail
2119
2120/**
2121 * Port of `State.afterEventStationPool`: ARV, DEP and PHASE at a station whose
2122 * heterogeneous server pools `ctmc::ctmc_pools` rewrote (`sn.ctmcpool`). The row is
2123 * [buffer | servers | pool order]: the buffer holds the WAITING jobs only (class ids
2124 * right-aligned, the rightmost the oldest; per-class counts under SIRO), and the
2125 * class-r server block holds one sub-block of phases per compatible pool. LDES
2126 * semantics: an arrival takes a compatible pool with a free server, chosen by the
2127 * HeteroSchedPolicy (ORDER lowest index, ALFS least flexible, FSF fastest, RAIS
2128 * uniform, ALIS/FAIRNESS first of the rotating order, rotated only when there was
2129 * more than one candidate), or waits; a freed server of pool t takes the first
2130 * waiting job, in the discipline's order, that t can serve.
2131 */
2132template <class T>
2134 const std::vector<T>& inspace, EventType event,
2135 std::size_t cls) {
2137 const std::size_t R = sn.nclasses;
2138 const std::size_t ist = sn.nodes[ind - 1].station;
2139 const CtmcPool<T>& pool = sn.ctmcpool.at(ind);
2140 const SchedStrategy sched = sn.stations[ist - 1].sched;
2141 const T one = num_traits<T>::from_int(1), minus_one = num_traits<T>::from_int(-1);
2142 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
2143 const std::vector<T> buf(inspace.begin(), inspace.begin() + L.bufw);
2144 const std::vector<T> srv(inspace.begin() + L.bufw, inspace.begin() + L.bufw + L.srvw);
2145 const std::vector<T> var(inspace.begin() + L.bufw + L.srvw, inspace.end());
2146 const std::vector<std::size_t>& myp = pool.pools[cls - 1];
2147 EventOutcome<T> out;
2148 const auto emit = [&](const std::vector<T>& b, const std::vector<T>& s, const std::vector<T>& v,
2149 const T& rate, const T& prob, std::size_t started) {
2150 std::vector<T> row = b;
2151 row.insert(row.end(), s.begin(), s.end());
2152 row.insert(row.end(), v.begin(), v.end());
2153 out.space.push_back(row);
2154 out.rate.push_back(rate);
2155 out.prob.push_back(prob);
2156 tag_last(out, started, 0);
2157 };
2158 if (myp.empty()) return out; // the class is not served here
2159 if (event == EventType::ARV) {
2160 const std::pair<T, std::vector<T>> mg = to_marginal_aggr(sn, ind, inspace);
2161 const double ni = num_traits<T>::to_double(mg.first);
2162 const double nir = num_traits<T>::to_double(mg.second[cls - 1]);
2163 if (is_physical_capacity(sn, ist, cls) &&
2164 (ni >= sn.cap[ist - 1] || nir >= sn.classcap[ist - 1][cls - 1])) {
2165 // a lost job leaves the state unchanged, so the arrival still fires; else blocked
2166 if (arrival_is_lost(sn, ist, cls)) emit(buf, srv, var, minus_one, one, 0);
2167 pad_tags(out);
2168 return out;
2169 }
2170 std::vector<double> busy(pool.ntypes, 0.0);
2171 for (std::size_t r = 0; r < R; ++r)
2172 for (std::size_t k = 0; k < pool.pools[r].size(); ++k)
2173 for (std::size_t j = 0; j < pool.len[r][k]; ++j)
2174 busy[pool.pools[r][k] - 1] +=
2175 num_traits<T>::to_double(srv[L.Ks[r] + pool.off[r][k] + j]);
2176 std::vector<std::size_t> cand;
2177 for (std::size_t k = 0; k < myp.size(); ++k)
2178 if (busy[myp[k] - 1] < pool.count[myp[k] - 1]) cand.push_back(myp[k]);
2179 if (cand.empty()) {
2180 // no free compatible server: the job waits
2181 std::vector<T> b = buf;
2182 if (sched == SchedStrategy::SIRO) {
2183 b[cls - 1] += one;
2184 } else {
2185 std::size_t slot = 0; // 1-based index of the last empty slot
2186 for (std::size_t q = 0; q < b.size(); ++q)
2187 if (num_traits<T>::to_double(b[q]) == 0) slot = q + 1;
2188 if (slot == 0) {
2189 b.insert(b.begin(), num_traits<T>::from_int(0));
2190 slot = 1;
2191 }
2192 b[slot - 1] = num_traits<T>::from_int(static_cast<long>(cls));
2193 }
2194 emit(b, srv, var, minus_one, one, 0);
2195 pad_tags(out);
2196 return out;
2197 }
2198 std::vector<std::size_t> choice(1, cand[0]);
2199 std::vector<T> pchoice(1, one);
2200 std::vector<T> varc = var;
2201 if (cand.size() > 1) {
2202 switch (pool.policy) {
2204 for (std::size_t q = 0; q < pool.alfsorder.size(); ++q)
2205 if (std::find(cand.begin(), cand.end(), pool.alfsorder[q]) != cand.end()) {
2206 choice[0] = pool.alfsorder[q];
2207 break;
2208 }
2209 break;
2211 std::size_t at = 0; // the first maximum wins ties
2212 for (std::size_t q = 1; q < cand.size(); ++q)
2213 if (pool.fsfrate[cand[q] - 1][cls - 1] > pool.fsfrate[cand[at] - 1][cls - 1]) at = q;
2214 choice[0] = cand[at];
2215 break;
2216 }
2218 choice = cand;
2219 pchoice.assign(cand.size(), num_traits<T>::from_double(1.0 / static_cast<double>(cand.size())));
2220 break;
2223 if (pool.rotate) {
2224 const std::size_t vp = varc.size() - 1;
2225 const std::size_t pid =
2226 static_cast<std::size_t>(num_traits<T>::to_double(varc[vp]) + 0.5);
2227 std::vector<std::size_t> ord = pool.perms.at(pid - 1);
2228 for (std::size_t q = 0; q < ord.size(); ++q)
2229 if (std::find(cand.begin(), cand.end(), ord[q]) != cand.end()) {
2230 choice[0] = ord[q];
2231 ord.erase(ord.begin() + static_cast<std::ptrdiff_t>(q));
2232 ord.push_back(choice[0]);
2233 break;
2234 }
2235 varc[vp] = num_traits<T>::from_int(static_cast<long>(pool.perm_index(ord)));
2236 }
2237 break;
2238 default:
2239 break; // ORDER: the lowest index
2240 }
2241 }
2242 std::vector<PoolStart<T>> starts;
2243 for (std::size_t c = 0; c < choice.size(); ++c)
2244 pool_detail::pool_start(pool, L.Ks, buf, srv, cls, choice[c], pchoice[c], starts);
2245 for (std::size_t i = 0; i < starts.size(); ++i)
2246 emit(starts[i].buf, starts[i].srv, varc, minus_one, starts[i].p, cls);
2247 pad_tags(out);
2248 return out;
2249 }
2250 for (std::size_t k = 0; k < myp.size(); ++k) {
2251 const std::size_t t = myp[k];
2252 for (std::size_t j = 0; j < pool.len[cls - 1][k]; ++j) {
2253 const std::size_t col = L.Ks[cls - 1] + pool.off[cls - 1][k] + j;
2254 const T nj = srv[col];
2255 if (!(num_traits<T>::to_double(nj) > 0)) continue;
2256 if (event == EventType::DEP) {
2257 const T ex = pool.exit[cls - 1][k][j];
2258 if (!(num_traits<T>::to_double(ex) > 0)) continue;
2259 std::vector<T> sd = srv;
2260 sd[col] -= one;
2261 const std::vector<PoolStart<T>> nx =
2262 pool_detail::pool_serve_next(sn, pool, sched, L.Ks, buf, sd, t);
2263 for (std::size_t b = 0; b < nx.size(); ++b)
2264 emit(nx[b].buf, nx[b].srv, var, T(ex * nj * nx[b].p), one, nx[b].cls);
2265 } else if (event == EventType::PHASE) {
2266 const Matrix<T>& D0 = pool.D0[cls - 1][k];
2267 for (std::size_t jd = 0; jd < pool.len[cls - 1][k]; ++jd) {
2268 if (jd == j || !(num_traits<T>::to_double(D0(j, jd)) > 0)) continue;
2269 std::vector<T> sp = srv;
2270 sp[col] -= one;
2271 sp[L.Ks[cls - 1] + pool.off[cls - 1][k] + jd] += one;
2272 emit(buf, sp, var, T(D0(j, jd) * nj), one, 0);
2273 }
2274 }
2275 }
2276 }
2277 pad_tags(out);
2278 return out;
2279}
2280
2281template <class T>
2283 const std::vector<T>& inspace, EventType event,
2284 std::size_t cls, bool no_promote = false,
2285 const T& aux_rate = num_traits<T>::from_int(0)) {
2286 // SERVER BREAKDOWN, `afterEventStation.m:36-65`. A down server (trailing
2287 // status 0) does not serve, so DEP and PHASE produce nothing -- unless a
2288 // degraded down-server rate is configured for the class, in which case the
2289 // up-server outcome is computed below and its rates rescaled by
2290 // downRate/upRate. Gating here keeps every scheduling branch unaware of it.
2291 if ((event == EventType::DEP || event == EventType::PHASE) && !inspace.empty() &&
2292 sn.has_breakdown_node(ind) && num_traits<T>::to_double(inspace.back()) == 0) {
2293 const std::size_t ist = sn.nodes[ind - 1].station;
2294 const T down = sn.breakdownparam.at(ist).down_rate_of(cls);
2295 if (!(down > num_traits<T>::from_int(0))) return EventOutcome<T>();
2296 const T upr = sn.rates(ist - 1, cls - 1);
2297 const double upd = num_traits<T>::to_double(upr);
2298 if (!std::isfinite(upd) || !(upd > 0.0))
2299 throw InputError("Station '" + sn.nodes[ind - 1].name +
2300 "' declares a down-server service rate for class '" +
2301 sn.classes[cls - 1].name +
2302 "' but has no finite up-server service rate to rescale.");
2303 // Evaluate the UP handler on the same row with the status set to up, then
2304 // put the status back to down in every successor: the outage does not end
2305 // because a job completed.
2306 std::vector<T> upspace = inspace;
2307 upspace.back() = num_traits<T>::from_int(1);
2308 EventOutcome<T> o =
2309 after_event_station(sn, ind, upspace, event, cls, no_promote, aux_rate);
2310 const T scale = T(down / upr);
2311 for (std::size_t i = 0; i < o.space.size(); ++i) {
2312 if (!o.space[i].empty()) o.space[i].back() = num_traits<T>::from_int(0);
2313 o.rate[i] = T(o.rate[i] * scale);
2314 }
2315 return o;
2316 }
2317 // heterogeneous server pools rewritten for the CTMC (`ctmc::ctmc_pools`)
2318 if ((event == EventType::ARV || event == EventType::DEP || event == EventType::PHASE) &&
2319 !sn.ctmcpool.empty() && sn.ctmcpool.count(ind))
2320 return after_event_station_pool(sn, ind, inspace, event, cls);
2321 switch (event) {
2322 case EventType::ARV:
2323 // A signal class arriving is not an arrival at all: it removes
2324 // jobs and is annihilated, so it never reaches the scheduling
2325 // branches. A REPLY signal is the exception -- it completes a
2326 // synchronous call and then joins as an ordinary job.
2327 if (sn.issignal.size() >= cls && sn.issignal[cls - 1]) {
2328 if (!(sn.signaltype.size() >= cls &&
2329 sn.signaltype[cls - 1] == lang::SignalType::REPLY))
2330 return after_event_station_signal(sn, ind, inspace, cls);
2331 // A REPLY takes the reply path only at a station that actually
2332 // holds a block for it; elsewhere it is a plain job class and
2333 // falls through to ordinary arrival handling.
2334 if (reply_block_info(sn, ind).width > 0)
2335 return after_event_station_reply(sn, ind, inspace, cls);
2336 }
2337 {
2338 EventOutcome<T> out = after_event_station_arv(sn, ind, inspace, cls);
2339 apply_station_balking(sn, ind, inspace, cls, out);
2340 return out;
2341 }
2342 case EventType::DEP: {
2343 EventOutcome<T> out = after_event_station_dep(sn, ind, inspace, cls, no_promote);
2344 // ROUND-ROBIN DISPATCH advances on every completion, which is what
2345 // makes the next destination deterministic; the generator then reads
2346 // the pointer OUT OF THIS SUCCESSOR to pick the link. Without the
2347 // advance the pointer is a frozen coordinate and every job takes the
2348 // same link, which is random routing with the wrong support rather
2349 // than round robin. Reference: `afterEventStation.m:632-658`.
2350 rr_advance_row(sn, ind, cls, out.space);
2351 // TRUE BAS, the departure half. When the marker is already set the
2352 // front job has COMPLETED and is being held, so this DEP is not a
2353 // service completion at all -- it is the instant transfer of that
2354 // held job downstream, which the generator only offers when the
2355 // destination has room. It therefore fires at the Immediate rate and
2356 // CLEARS the marker; the complementary become-blocked edge (0 -> 1) is
2357 // added by the generator, the only place that can see the
2358 // destination's occupancy.
2359 //
2360 // Gate on `isbasblocking`, not on this station's own drop rule: under
2361 // the destination declaration form the rule is not here.
2362 if (ind <= sn.isbasblocking.size() && sn.isbasblocking[ind - 1] &&
2363 !inspace.empty() && num_traits<T>::to_double(inspace.back()) == 1 &&
2364 !out.space.empty()) {
2365 // 1e7 VERBATIM, not GlobalConstants::Immediate (1e8). The rate is
2366 // large but FINITE, so the blocked states keep a proportional
2367 // share of the stationary mass and the analyzer's queue-length
2368 // shift reads it; using 1e8 would divide that share by ten and
2369 // move every reported queue length. The reference hardcodes 1e7.
2370 const T imm = num_traits<T>::from_double(1e7);
2371 for (std::size_t i = 0; i < out.space.size(); ++i) {
2372 out.space[i].back() = num_traits<T>::from_int(0);
2373 out.rate[i] = imm;
2374 }
2375 }
2376 return out;
2377 }
2378 case EventType::PHASE:
2379 return after_event_station_phase(sn, ind, inspace, cls);
2380 case EventType::RENEGE:
2381 return after_event_station_renege(sn, ind, inspace, cls, aux_rate);
2382 case EventType::RETRY:
2383 return after_event_station_retry(sn, ind, inspace, cls, aux_rate);
2384 case EventType::SWITCH:
2385 return after_event_station_switch(sn, ind, inspace, cls);
2386 case EventType::FAILURE:
2387 return after_event_station_breakdown(sn, ind, inspace, false, aux_rate);
2388 case EventType::REPAIR:
2389 return after_event_station_breakdown(sn, ind, inspace, true, aux_rate);
2390 case EventType::LOCAL:
2391 return EventOutcome<T>(); // a dummy event moves nothing
2392 default:
2393 throw UnsupportedError(ErrorKind{"Event"}, std::string("after_event_station: the ") +
2394 lang::event_to_text(event) +
2395 " event is not ported yet");
2396 }
2397}
2398
2399/**
2400 * Port of `State.afterEventTransition`, the PHASE arm: one running server of
2401 * the given mode advances its firing phase (`cls` is interpreted as the MODE,
2402 * as in the reference). ENABLE and FIRE are global events handled by
2403 * `after_global_event`, so they return an empty outcome here, matching the
2404 * reference's no-op arms.
2405 *
2406 * RATE. The MATLAB body multiplies the phase-k move rate by BOTH
2407 * kir(:,mode,k) and nir(mode) (afterEventTransition.m:38-40), but nir is the
2408 * sum of kir over the phases, so the extra factor counts the running servers
2409 * twice; the JAR and the native python carry D0(k,kdest) * kir alone, and
2410 * this port follows them.
2411 *
2412 * The row layout is the one `after_global_event` slices:
2413 * [buf(nmodes) | srv(sum fK) | fired(nmodes) | var].
2414 */
2415template <class T>
2417 const std::vector<T>& inspace, EventType event,
2418 std::size_t mode) {
2419 EventOutcome<T> out;
2420 if (event != EventType::PHASE) return out; // ENABLE / FIRE are global
2421 const typename std::map<std::size_t, TransitionParam<T>>::const_iterator it =
2422 sn.transparam.find(ind);
2423 if (it == sn.transparam.end())
2424 throw InputError("after_event_transition: node has no TransitionParam");
2425 const TransitionParam<T>& tp = it->second;
2426 if (mode == 0 || mode > tp.nmodes)
2427 throw InputError("after_event_transition: mode index is out of range");
2428 const T one = num_traits<T>::from_int(1);
2429
2430 std::vector<std::size_t> fK(tp.nmodes, 1), fKs(tp.nmodes, 0);
2431 std::size_t tot = 0;
2432 for (std::size_t m = 0; m < tp.nmodes; ++m) {
2433 fK[m] = m < tp.firingphases.size() && tp.firingphases[m] > 0 ? tp.firingphases[m] : 1;
2434 fKs[m] = tot;
2435 tot += fK[m];
2436 }
2437 if (fK[mode - 1] <= 1) return out; // a single phase has no internal move
2438 if (mode - 1 >= tp.firingproc.size() ||
2439 tp.firingproc[mode - 1].D0.rows() != fK[mode - 1])
2440 return out;
2441 const Matrix<T>& D0 = tp.firingproc[mode - 1].D0;
2442
2443 for (std::size_t k = 0; k < fK[mode - 1]; ++k) {
2444 const std::size_t idx = tp.nmodes + fKs[mode - 1] + k;
2445 const T cnt = inspace[idx];
2446 if (!(num_traits<T>::to_double(cnt) > 0)) continue;
2447 for (std::size_t kd = 0; kd < fK[mode - 1]; ++kd) {
2448 if (kd == k) continue; // the diagonal is the exit rate, not a move
2449 if (!(num_traits<T>::to_double(D0(k, kd)) > 0)) continue;
2450 std::vector<T> row = inspace;
2451 row[idx] -= one;
2452 row[tp.nmodes + fKs[mode - 1] + kd] += one;
2453 out.space.push_back(row);
2454 out.rate.push_back(T(D0(k, kd) * cnt));
2455 out.prob.push_back(one);
2456 }
2457 }
2458 return out;
2459}
2460
2461/**
2462 * Port of `State.afterEvent`: the successors of one event at one NODE.
2463 *
2464 * The reference's body is mostly slicing -- it cuts `inspace` into buffer,
2465 * server and local-variable blocks and hands the pieces to the per-node-type
2466 * handler. This port slices inside each handler instead (`row_layout`), so what
2467 * remains here is the dispatch itself and the guards that precede it.
2468 *
2469 * A class the station does not accept short-circuits: `phases_of` is zero
2470 * there, and every downstream index into the server block would be out of
2471 * range. That guard is the reference's `K(class) == 0` test.
2472 *
2473 * `cls` IS A MODE, NOT A CLASS, on a Transition's PHASE action; see the guard.
2474 */
2475template <class T>
2477 const std::vector<T>& inspace, EventType event, std::size_t cls,
2478 bool no_promote = false,
2479 const T& aux_rate = num_traits<T>::from_int(0)) {
2480 if (ind == 0 || ind > sn.nodes.size())
2481 throw InputError("after_event: node index is out of range");
2482 const NodeDef& nd = sn.nodes[ind - 1];
2483 // THE `cls` SLOT IS NOT ALWAYS A CLASS. On a Transition's PHASE action it
2484 // carries the MODE, which `refresh_sync` puts there deliberately ("one
2485 // server phase-change action per MODE, not per class") and
2486 // `after_event_transition` reads back as such. Bounding it by `nclasses`
2487 // refused every mode past the class count: spn_basic_closed is one class
2488 // and three modes, so modes 2 and 3 raised "class index is out of range"
2489 // and no closed SPN with more modes than classes could be walked at all.
2490 // The mode bound belongs to the handler, which already applies it against
2491 // `tp.nmodes`, so only the non-Transition case is checked here.
2492 const bool cls_is_mode = (nd.nodetype == NodeType::Transition && event == EventType::PHASE);
2493 if (!cls_is_mode && (cls == 0 || cls > sn.nclasses))
2494 throw InputError("after_event: class index is out of range");
2495
2496 // A Join of an FJ-augmented struct IS a station, but its state is a bare
2497 // per-class count vector: it performs a rendezvous, not a service, so it must
2498 // bypass the buffer/server slicing before `after_event_station` sees it.
2499 if (sn.isfjaugmented && nd.nodetype == NodeType::Join)
2500 return after_event_join(sn, ind, inspace, event, cls);
2501
2502 if (nd.station != 0) {
2503 // A class with no service process at this station cannot be involved
2504 // in any event here.
2505 if (sn.phases_of(nd.station, cls) == 0) return EventOutcome<T>();
2506 return after_event_station(sn, ind, inspace, event, cls, no_promote, aux_rate);
2507 }
2508 if (!nd.stateful) return EventOutcome<T>(); // a stateless node holds nothing
2509
2510 if (nd.nodetype == NodeType::Cache) return after_event_cache(sn, ind, inspace, event, cls);
2511 if (nd.nodetype == NodeType::Fork) return after_event_fork(sn, ind, inspace, event, cls);
2512 if (nd.nodetype == NodeType::Transition)
2513 return after_event_transition(sn, ind, inspace, event, cls);
2514 if (nd.nodetype == NodeType::Router) return after_event_router(sn, ind, inspace, event, cls);
2515
2516 throw UnsupportedError(ErrorKind{"Event"}, "after_event: events at stateful non-station node '" + nd.name +
2517 "' are not ported yet");
2518}
2519
2520namespace signal_detail {
2521
2522/** Merge duplicate destinations so the generator sees one entry per state. */
2523template <class T>
2524void merge_states(std::vector<std::vector<T>>& sp, std::vector<T>& pr) {
2525 std::vector<std::vector<T>> us;
2526 std::vector<T> up;
2527 for (std::size_t i = 0; i < sp.size(); ++i) {
2528 std::size_t at = us.size();
2529 for (std::size_t j = 0; j < us.size(); ++j)
2530 if (us[j] == sp[i]) { at = j; break; }
2531 if (at == us.size()) {
2532 us.push_back(sp[i]);
2533 up.push_back(pr[i]);
2534 } else {
2535 up[at] += pr[i];
2536 }
2537 }
2538 sp.swap(us);
2539 pr.swap(up);
2540}
2541
2542} // namespace signal_detail
2543
2544/**
2545 * Port of `State.signalBatchPMF`: the batch size a negative signal removes.
2546 *
2547 * The pmf is CLIPPED at the eligible population: an oversized batch empties
2548 * the station rather than driving the queue negative, so the whole tail
2549 * P(B >= n) lumps onto "remove all n". That is the same clipping LDES applies
2550 * with min(B,n) and the tail term MAM uses.
2551 */
2552template <class T>
2553std::pair<std::vector<std::size_t>, std::vector<T>> signal_batch_pmf(
2554 const NetworkStruct<T>& sn, std::size_t cls, std::size_t ntot) {
2555 std::vector<std::size_t> kv;
2556 std::vector<T> kp;
2557 if (sn.signalremdist.size() < cls || sn.signalremdist[cls - 1].empty()) {
2558 kv.push_back(1);
2559 kp.push_back(num_traits<T>::from_int(1));
2560 return std::make_pair(kv, kp);
2561 }
2562 const std::vector<T>& d = sn.signalremdist[cls - 1];
2563 T head_sum = num_traits<T>::from_int(0);
2564 for (std::size_t b = 0; b < ntot; ++b) {
2565 const T p = b < d.size() ? d[b] : num_traits<T>::from_int(0);
2566 if (num_traits<T>::to_double(p) > 0) {
2567 kv.push_back(b);
2568 kp.push_back(p);
2569 }
2570 head_sum += p;
2571 }
2572 const double tail = 1.0 - num_traits<T>::to_double(head_sum);
2573 if (tail > 0) {
2574 kv.push_back(ntot);
2575 kp.push_back(num_traits<T>::from_double(tail));
2576 }
2577 if (kv.empty()) {
2578 kv.push_back(1);
2579 kp.push_back(num_traits<T>::from_int(1));
2580 return std::make_pair(kv, kp);
2581 }
2582 T tot = num_traits<T>::from_int(0);
2583 for (std::size_t i = 0; i < kp.size(); ++i) tot += kp[i];
2584 if (num_traits<T>::to_double(tot) > 0)
2585 for (std::size_t i = 0; i < kp.size(); ++i) kp[i] = T(kp[i] / tot);
2586 return std::make_pair(kv, kp);
2587}
2588
2589/**
2590 * Port of `State.afterEventStationSignal`: a G-network signal arrives.
2591 *
2592 * A signal NEVER joins the station. It removes jobs already there and is
2593 * annihilated, so the event is passive throughout and the successors differ
2594 * only in which victims were taken.
2595 *
2596 * Victim selection has two tiers, and conflating them is the trap: FCFS and
2597 * LCFS rank by AGE, which only an ordered buffer records, so at a per-class
2598 * count buffer an age policy degenerates to a uniform draw. They also drain
2599 * the waiting line completely before touching a server, whereas RANDOM draws
2600 * uniformly across waiting and in-service jobs alike.
2601 */
2602template <class T>
2604 const std::vector<T>& inspace, std::size_t cls) {
2605 const std::size_t R = sn.nclasses;
2606 const std::size_t ist = sn.nodes[ind - 1].station;
2607 const T zero = num_traits<T>::from_int(0), one = num_traits<T>::from_int(1);
2608 const T minus_one = num_traits<T>::from_int(-1);
2609 EventOutcome<T> out;
2610 if (ist == 0) throw InputError("after_event_station_signal: node is not a station");
2611 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
2612 const SchedStrategy sched = sn.stations[ist - 1].sched;
2613 const double S = sn.stations[ist - 1].nservers;
2614
2615 std::vector<std::size_t> ph(R, 1), shift(R, 0);
2616 for (std::size_t r = 0; r < R; ++r) {
2617 ph[r] = L.K[r];
2618 shift[r] = L.Ks[r];
2619 }
2620 const Marginal<T> m = to_marginal(sn, ist, inspace, ph, shift, L.nvar);
2621
2622 // A CATASTROPHE empties the station outright, ignoring the batch pmf: a
2623 // catastrophe removes every job by definition.
2624 if (sn.signaltype.size() >= cls && sn.signaltype[cls - 1] == lang::SignalType::CATASTROPHE) {
2625 std::vector<T> row(L.bufw + L.srvw, zero);
2626 row.insert(row.end(), inspace.end() - L.nvar, inspace.end());
2627 out.space.push_back(row);
2628 out.rate.push_back(minus_one);
2629 out.prob.push_back(one);
2630 return out;
2631 }
2632
2633 // Eligible victim classes: the declared target, or every non-signal class
2634 // for the classic untargeted negative customer.
2635 std::vector<std::size_t> tgt;
2636 const std::size_t declared = sn.signaltarget.size() >= cls ? sn.signaltarget[cls - 1] : 0;
2637 if (declared >= 1) {
2638 tgt.push_back(declared);
2639 } else {
2640 for (std::size_t r = 1; r <= R; ++r)
2641 if (sn.issignal.size() < r || !sn.issignal[r - 1]) tgt.push_back(r);
2642 }
2643 std::vector<std::size_t> elig;
2644 std::size_t ntot = 0;
2645 for (std::size_t i = 0; i < tgt.size(); ++i) {
2646 const double nr = num_traits<T>::to_double(m.nir[tgt[i] - 1]);
2647 if (nr > 0) {
2648 elig.push_back(tgt[i]);
2649 ntot += static_cast<std::size_t>(nr);
2650 }
2651 }
2652 if (elig.empty()) {
2653 // No victim: the signal simply vanishes, leaving the state unchanged.
2654 out.space.push_back(inspace);
2655 out.rate.push_back(minus_one);
2656 out.prob.push_back(one);
2657 return out;
2658 }
2659
2660 const lang::RemovalPolicy policy = sn.signalrempolicy.size() >= cls
2661 ? sn.signalrempolicy[cls - 1]
2663 const bool ordered = state_detail::buffer_is_class_tag(sched) ||
2664 state_detail::buffer_is_tag_phase_pairs(sched);
2665 const bool paired = state_detail::buffer_is_tag_phase_pairs(sched);
2666 const bool counted = state_detail::buffer_is_per_class_count(sched);
2667 const std::pair<std::vector<std::size_t>, std::vector<T>> pmf =
2668 signal_batch_pmf(sn, cls, ntot);
2669
2670 std::vector<std::vector<T>> acc;
2671 std::vector<T> accp;
2672 for (std::size_t ik = 0; ik < pmf.first.size(); ++ik) {
2673 if (num_traits<T>::to_double(pmf.second[ik]) <= 0) continue;
2674 std::vector<std::vector<T>> cur(1, inspace);
2675 std::vector<T> curp(1, one);
2676 // Remove one job at a time: sequential draws without replacement give
2677 // a uniform choice of the removed SUBSET.
2678 for (std::size_t step = 0; step < pmf.first[ik]; ++step) {
2679 std::vector<std::vector<T>> nxt;
2680 std::vector<T> nxtp;
2681 for (std::size_t row = 0; row < cur.size(); ++row) {
2682 std::vector<T> buf(cur[row].begin(), cur[row].begin() + L.bufw);
2683 std::vector<T> srv(cur[row].begin() + L.bufw,
2684 cur[row].begin() + L.bufw + L.srvw);
2685 const std::vector<T> var(cur[row].begin() + L.bufw + L.srvw, cur[row].end());
2686
2687 // Waiting victims, as (position, class, multiplicity).
2688 std::vector<std::size_t> wpos, wcls, wwt;
2689 if (ordered) {
2690 for (std::size_t b = 0; b < L.bufw; b += paired ? 2 : 1) {
2691 const double v = num_traits<T>::to_double(buf[b]);
2692 if (v <= 0) continue;
2693 bool ok = false;
2694 for (std::size_t e = 0; e < elig.size(); ++e)
2695 if (elig[e] == static_cast<std::size_t>(v)) ok = true;
2696 if (!ok) continue;
2697 wpos.push_back(b);
2698 wcls.push_back(static_cast<std::size_t>(v));
2699 wwt.push_back(1);
2700 }
2701 } else if (counted) {
2702 for (std::size_t e = 0; e < elig.size(); ++e) {
2703 const std::size_t r = elig[e];
2704 if (r > L.bufw) continue;
2705 const double v = num_traits<T>::to_double(buf[r - 1]);
2706 if (v <= 0) continue;
2707 wpos.push_back(r - 1);
2708 wcls.push_back(r);
2709 wwt.push_back(static_cast<std::size_t>(v));
2710 }
2711 }
2712 // In-service victims, per (class, phase).
2713 std::vector<std::size_t> scls, sph, scnt;
2714 for (std::size_t e = 0; e < elig.size(); ++e) {
2715 const std::size_t r = elig[e];
2716 for (std::size_t p = 0; p < L.K[r - 1]; ++p) {
2717 const double v = num_traits<T>::to_double(srv[L.Ks[r - 1] + p]);
2718 if (v <= 0) continue;
2719 scls.push_back(r);
2720 sph.push_back(p);
2721 scnt.push_back(static_cast<std::size_t>(v));
2722 }
2723 }
2724 std::size_t nwait = 0, nsrv = 0;
2725 for (std::size_t i = 0; i < wwt.size(); ++i) nwait += wwt[i];
2726 for (std::size_t i = 0; i < scnt.size(); ++i) nsrv += scnt[i];
2727 if (nwait == 0 && nsrv == 0) {
2728 // Already drained: nothing left for this step to remove.
2729 nxt.push_back(cur[row]);
2730 nxtp.push_back(curp[row]);
2731 continue;
2732 }
2733
2734 std::vector<std::vector<T>> sp;
2735 std::vector<T> pr;
2736 const bool age_ordered =
2737 ordered && (policy == lang::RemovalPolicy::FCFS ||
2738 policy == lang::RemovalPolicy::LCFS);
2739 if (age_ordered && nwait > 0) {
2740 // The head of line is the LAST occupied slot, the newest
2741 // arrival the first: the buffer is right-aligned.
2742 std::size_t pick = 0;
2743 for (std::size_t i = 0; i < wpos.size(); ++i)
2744 if (policy == lang::RemovalPolicy::FCFS ? wpos[i] > wpos[pick]
2745 : wpos[i] < wpos[pick])
2746 pick = i;
2747 std::vector<T> b2 = buf;
2748 b2.erase(b2.begin() + wpos[pick], b2.begin() + wpos[pick] + (paired ? 2 : 1));
2749 b2.insert(b2.begin(), paired ? 2 : 1, zero);
2750 std::vector<T> nr = b2;
2751 nr.insert(nr.end(), srv.begin(), srv.end());
2752 nr.insert(nr.end(), var.begin(), var.end());
2753 sp.push_back(nr);
2754 pr.push_back(one);
2755 } else {
2756 // RANDOM draws over everything present; FCFS/LCFS at a
2757 // count buffer drain the waiting line first, and only reach
2758 // the servers once it is empty.
2759 const std::size_t total = policy == lang::RemovalPolicy::RANDOM
2760 ? nwait + nsrv
2761 : (nwait > 0 ? nwait : nsrv);
2762 for (std::size_t i = 0; i < wpos.size(); ++i) {
2763 std::vector<T> b2 = buf;
2764 if (counted) {
2765 b2[wcls[i] - 1] -= one;
2766 } else {
2767 b2.erase(b2.begin() + wpos[i],
2768 b2.begin() + wpos[i] + (paired ? 2 : 1));
2769 b2.insert(b2.begin(), paired ? 2 : 1, zero);
2770 }
2771 std::vector<T> nr = b2;
2772 nr.insert(nr.end(), srv.begin(), srv.end());
2773 nr.insert(nr.end(), var.begin(), var.end());
2774 sp.push_back(nr);
2775 pr.push_back(num_traits<T>::from_double(static_cast<double>(wwt[i]) /
2776 static_cast<double>(total)));
2777 }
2778 if (policy == lang::RemovalPolicy::RANDOM || nwait == 0) {
2779 for (std::size_t i = 0; i < scls.size(); ++i) {
2780 std::vector<T> b2 = buf, s2 = srv;
2781 s2[L.Ks[scls[i] - 1] + sph[i]] -= one;
2782 // The freed server pulls in the head of line, where
2783 // the station keeps one at all.
2784 double occ = 0;
2785 for (std::size_t j = 0; j < s2.size(); ++j)
2786 occ += num_traits<T>::to_double(s2[j]);
2787 if (L.bufw > 0 && occ < S) {
2788 if (ordered) {
2789 std::size_t hp = L.bufw;
2790 for (std::size_t b = 0; b < L.bufw; b += paired ? 2 : 1)
2791 if (num_traits<T>::to_double(b2[b]) > 0) hp = b;
2792 if (hp != L.bufw) {
2793 const std::size_t pc = static_cast<std::size_t>(
2794 num_traits<T>::to_double(b2[hp]));
2795 std::size_t pp = 0;
2796 if (paired) {
2797 const double v =
2798 num_traits<T>::to_double(b2[hp + 1]);
2799 pp = v >= 1 ? static_cast<std::size_t>(v) - 1 : 0;
2800 }
2801 b2.erase(b2.begin() + hp,
2802 b2.begin() + hp + (paired ? 2 : 1));
2803 b2.insert(b2.begin(), paired ? 2 : 1, zero);
2804 s2[L.Ks[pc - 1] + pp] += one;
2805 }
2806 } else if (counted) {
2807 // A count buffer carries no order, so the
2808 // lowest-indexed waiting class is promoted
2809 // to keep the map single-valued; the actual
2810 // service order is resolved by the rates.
2811 for (std::size_t r = 1; r <= R && r <= L.bufw; ++r)
2812 if (num_traits<T>::to_double(b2[r - 1]) > 0) {
2813 b2[r - 1] -= one;
2814 s2[L.Ks[r - 1]] += one;
2815 break;
2816 }
2817 }
2818 }
2819 std::vector<T> nr = b2;
2820 nr.insert(nr.end(), s2.begin(), s2.end());
2821 nr.insert(nr.end(), var.begin(), var.end());
2822 sp.push_back(nr);
2823 pr.push_back(num_traits<T>::from_double(
2824 static_cast<double>(scnt[i]) / static_cast<double>(total)));
2825 }
2826 }
2827 }
2828 signal_detail::merge_states(sp, pr);
2829 for (std::size_t i = 0; i < sp.size(); ++i) {
2830 nxt.push_back(sp[i]);
2831 nxtp.push_back(T(curp[row] * pr[i]));
2832 }
2833 }
2834 signal_detail::merge_states(nxt, nxtp);
2835 cur.swap(nxt);
2836 curp.swap(nxtp);
2837 }
2838 for (std::size_t i = 0; i < cur.size(); ++i) {
2839 acc.push_back(cur[i]);
2840 accp.push_back(T(pmf.second[ik] * curp[i]));
2841 }
2842 }
2843 signal_detail::merge_states(acc, accp);
2844 out.space.swap(acc);
2845 out.prob.swap(accp);
2846 out.rate.assign(out.space.size(), minus_one);
2847 return out;
2848}
2849
2850/**
2851 * Port of `State.passAndSwap`: the transition a service completion triggers at
2852 * a pass-and-swap station (Dorsman and Gardner 2024, Sect. 2.3).
2853 *
2854 * The completing job scans FORWARD from its own position for the first job it
2855 * may swap with per the graph G, takes that job's place and ejects it; the
2856 * ejected job repeats the scan. The chain ends at a job with no swappable
2857 * successor, and THAT job departs -- which is why the departing class is in
2858 * general not the class whose service completed.
2859 *
2860 * @param c 0-based list of 1-based class indices, oldest first
2861 * @param p 0-based position whose service token completed
2862 * @param G class-compatibility graph, G[a][b] true when a may swap with b
2863 * @return (the list after the transition, the 1-based departing class)
2864 */
2865template <class T>
2866std::pair<std::vector<std::size_t>, std::size_t> pass_and_swap(
2867 const std::vector<std::size_t>& c, std::size_t p,
2868 const std::vector<std::vector<bool>>& G) {
2869 const std::size_t n = c.size();
2870 if (p >= n) throw InputError("pass_and_swap: position is out of range for the state");
2871 std::vector<std::size_t> chain(1, p);
2872 std::size_t moving = c[p], cur = p;
2873 for (;;) {
2874 std::size_t q = n;
2875 for (std::size_t j = cur + 1; j < n; ++j)
2876 if (moving - 1 < G.size() && c[j] - 1 < G[moving - 1].size() &&
2877 G[moving - 1][c[j] - 1]) {
2878 q = j;
2879 break;
2880 }
2881 if (q == n) break; // no swappable successor: this job departs
2882 chain.push_back(q);
2883 moving = c[q];
2884 cur = q;
2885 }
2886 const std::size_t dep = c[chain.back()];
2887 // Shift classes one step along the chain; the last is overwritten because
2888 // it departed, and the head-of-chain slot is then removed.
2889 std::vector<std::size_t> cnew = c;
2890 for (std::size_t i = 0; i + 1 < chain.size(); ++i) cnew[chain[i + 1]] = c[chain[i]];
2891 cnew.erase(cnew.begin() + chain[0]);
2892 return std::make_pair(cnew, dep);
2893}
2894
2895/**
2896 * Per-position service rate increments Delta_mu(c1..cp) = mu(c1..cp) - mu(c1..c_{p-1}).
2897 */
2898template <class T, class F>
2899inline std::vector<double> pas_increments(const F& mu_fun, const std::vector<std::size_t>& c) {
2900 std::vector<double> inc(c.size(), 0.0);
2901 double mu_prev = 0.0;
2902 for (std::size_t p = 0; p < c.size(); ++p) {
2903 const std::vector<std::size_t> prefix(c.begin(), c.begin() + p + 1);
2904 const double mu_cur = num_traits<T>::to_double(mu_fun(prefix));
2905 inc[p] = mu_cur - mu_prev;
2906 mu_prev = mu_cur;
2907 }
2908 return inc;
2909}
2910
2911/**
2912 * Tag the successor just appended to OUT with the PAS positions that started
2913 * service on it: those of CNEW that are served (Delta_mu > 0) and were not
2914 * served in COLD. Under a swap the tag follows the POSITION rather than the job
2915 * identity, since pass-and-swap redefines which job holds a position.
2916 */
2917template <class T, class F>
2918inline void pas_tag_started(EventOutcome<T>& out, const F& mu_fun,
2919 const std::vector<std::size_t>& cold,
2920 const std::vector<std::size_t>& cnew) {
2921 if (!mu_fun || out.space.empty()) return;
2922 const std::vector<double> inc_new = pas_increments<T>(mu_fun, cnew);
2923 const std::vector<double> inc_old = pas_increments<T>(mu_fun, cold);
2924 for (std::size_t p = 0; p < inc_new.size(); ++p) {
2925 if (inc_new[p] <= 0) continue;
2926 if (p < inc_old.size() && inc_old[p] > 0) continue; // already served
2927 tag_last(out, cnew[p], 0);
2928 }
2929}
2930
2931/**
2932 * Port of `State.afterEventStationPAS`: events at a pass-and-swap station.
2933 *
2934 * The state here is NOT the [buffer | server] split every other discipline
2935 * uses: it is the full ordered list of class indices, left-aligned and zero
2936 * padded, with no server block at all. Service is governed by the rate
2937 * function mu(c) rather than by a per-class rate, so the whole notion of "in
2938 * service" is replaced by a token at each position.
2939 */
2940template <class T>
2942 const std::vector<T>& inspace, EventType event,
2943 std::size_t cls) {
2944 const std::size_t ist = sn.nodes[ind - 1].station;
2945 const T one = num_traits<T>::from_int(1), zero = num_traits<T>::from_int(0);
2946 EventOutcome<T> out;
2947 if (ist == 0) throw InputError("after_event_station_pas: node is not a station");
2948 const typename std::map<std::size_t, typename NetworkStruct<T>::PasParam>::const_iterator it =
2949 sn.pasparam.find(ist);
2950 if (it == sn.pasparam.end() || !it->second.svc_rate_fun)
2951 throw InputError(
2952 "after_event_station_pas: the station has no service rate function mu(c); set one "
2953 "with set_pas");
2954
2955 const std::size_t V = sn.nvars_of(ind);
2956 const std::size_t W = inspace.size() - V;
2957 std::vector<std::size_t> c;
2958 for (std::size_t i = 0; i < W; ++i) {
2959 const double v = num_traits<T>::to_double(inspace[i]);
2960 if (v > 0) c.push_back(static_cast<std::size_t>(v));
2961 }
2962 const std::vector<T> var(inspace.begin() + W, inspace.end());
2963 const double cap = sn.cap[ist - 1];
2964
2965 if (event == EventType::ARV) {
2966 // The arrival joins at the BACK of the list, which is what records the
2967 // order the rate function is a function of.
2968 if (static_cast<double>(c.size()) >= cap) return out; // full: lost
2969 std::vector<std::size_t> nc = c;
2970 nc.push_back(cls);
2971 // NO SLOT IN THE ENCODING IS A BLOCK, NOT A LOSS. The list occupies one
2972 // row position per job, so a row of width W holds W jobs; emitting a
2973 // successor here and letting `row.resize(W, zero)` cut the list back to
2974 // W would DESTROY the job that did not fit while reporting a state that
2975 // looks exactly like the pre-arrival one -- a customer silently gone
2976 // from a closed network, with no error anywhere. Returning no successor
2977 // disables the upstream departure instead, which is what every other
2978 // discipline's capacity filter does and what the enumerated CTMC space
2979 // does at its own width boundary.
2980 if (nc.size() > W) return out;
2981 std::vector<T> row;
2982 for (std::size_t i = 0; i < nc.size(); ++i)
2983 row.push_back(num_traits<T>::from_int(static_cast<long>(nc[i])));
2984 row.resize(W, zero);
2985 row.insert(row.end(), var.begin(), var.end());
2986 out.space.push_back(row);
2987 out.rate.push_back(num_traits<T>::from_int(-1));
2988 out.prob.push_back(one);
2989 // A PAS station has one clock for the whole station and no server to
2990 // hold, so "in service" means "at a position whose rate increment
2991 // Delta_mu is positive": a job starts exactly when a position goes from
2992 // a zero increment to a positive one. With mu(c) = 1 only the head is
2993 // served (M/M/1), with mu(c) = |c| every position is (M/M/inf), and the
2994 // rule reproduces both.
2995 pas_tag_started<T>(out, it->second.svc_rate_fun, c, nc);
2996 pad_tags(out);
2997 return out;
2998 }
2999 if (event != EventType::DEP) return out; // PAS service is exponential: no PHASE
3000
3001 // Each position holds a service token firing at the INCREMENT of mu over
3002 // the prefix ending there. Summing the increments telescopes to mu(c), so
3003 // the station's total service rate is exactly the rate function.
3004 T mu_prev = zero;
3005 for (std::size_t p = 0; p < c.size(); ++p) {
3006 const std::vector<std::size_t> prefix(c.begin(), c.begin() + p + 1);
3007 const T mu_cur = it->second.svc_rate_fun(prefix);
3008 const T ratep = T(mu_cur - mu_prev);
3009 mu_prev = mu_cur;
3010 if (num_traits<T>::to_double(ratep) <= 0) continue; // position unserved
3011 const std::pair<std::vector<std::size_t>, std::size_t> ps =
3012 pass_and_swap<T>(c, p, it->second.swap_graph);
3013 // The completing token need not eject its own class, so only the
3014 // positions whose chain ends in THIS class contribute to its departure.
3015 if (ps.second != cls) continue;
3016 std::vector<T> row;
3017 for (std::size_t i = 0; i < ps.first.size(); ++i)
3018 row.push_back(num_traits<T>::from_int(static_cast<long>(ps.first[i])));
3019 row.resize(W, zero);
3020 row.insert(row.end(), var.begin(), var.end());
3021 out.space.push_back(row);
3022 out.rate.push_back(ratep);
3023 out.prob.push_back(one);
3024 pas_tag_started<T>(out, it->second.svc_rate_fun, c, ps.first);
3025 }
3026 pad_tags(out);
3027 return out;
3028}
3029
3030/**
3031 * Port of `State.replyBlockInfo`: the layout of the reply block.
3032 *
3033 * The block trails the modulation, routing and shared-node columns of nvars,
3034 * occupying columns 2R+1+r. Appending is deliberate -- every existing nvars
3035 * reader keeps its indices, and the columns stay zero-width for models without
3036 * reply signals, so no other model changes state width.
3037 */
3038template <class T>
3040 const std::size_t R = sn.nclasses;
3041 ReplyBlockInfo ri;
3042 ri.slot.assign(R, static_cast<std::size_t>(-1));
3043 if (sn.nvars.size() < ind || sn.nvars[ind - 1].size() < 3 * R + 1) return ri;
3044 std::size_t pos = 0;
3045 for (std::size_t j = 0; j < 2 * R + 1; ++j) pos += sn.nvars[ind - 1][j];
3046 for (std::size_t r = 1; r <= R; ++r)
3047 if (sn.nvars[ind - 1][2 * R + r] > 0) {
3048 ri.slot[r - 1] = pos;
3049 ri.classes.push_back(r);
3050 ++pos;
3051 ++ri.width;
3052 }
3053 return ri;
3054}
3055
3056/** How many servers node `ind` is holding for pending replies, from its vars. */
3057template <class T>
3058double reply_blocked(const NetworkStruct<T>& sn, std::size_t ind, const std::vector<T>& var) {
3059 const ReplyBlockInfo ri = reply_block_info(sn, ind);
3060 double nb = 0;
3061 for (std::size_t i = 0; i < ri.classes.size(); ++i) {
3062 const std::size_t s = ri.slot[ri.classes[i] - 1];
3063 // The slot is an index into the local-variable block, which is the
3064 // TAIL of the row, so it is offset from the start of `var`.
3065 if (s != static_cast<std::size_t>(-1) && s < var.size())
3066 nb += num_traits<T>::to_double(var[s]);
3067 }
3068 return nb;
3069}
3070
3071/**
3072 * Port of `State.afterEventStationReply`: a REPLY signal completes a
3073 * synchronous call at the station holding the server for it.
3074 *
3075 * A REPLY is not a negative customer. It releases one held server and then
3076 * JOINS as an ordinary job carrying the call result onward, so unlike
3077 * NEGATIVE or CATASTROPHE it is not annihilated.
3078 *
3079 * PASS-THROUGH is the subtle part: the released server is taken by the reply
3080 * ITSELF, never by a waiting job. The reply is work this station already paid
3081 * for, so queueing it behind the residents both misreports its residence and
3082 * steals capacity. Its service is typically Immediate, so the server is handed
3083 * straight back and the ordinary departure path then promotes the head of
3084 * line -- which also keeps the occupancy within the server count, unlike
3085 * admitting the reply on top of a promoted job.
3086 */
3087template <class T>
3089 const std::vector<T>& inspace, std::size_t cls) {
3090 const std::size_t R = sn.nclasses;
3091 const std::size_t ist = sn.nodes[ind - 1].station;
3092 const T one = num_traits<T>::from_int(1), zero = num_traits<T>::from_int(0);
3093 EventOutcome<T> out;
3094 if (ist == 0) throw InputError("after_event_station_reply: node is not a station");
3095 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
3096 const ReplyBlockInfo ri = reply_block_info(sn, ind);
3097 const double S = sn.stations[ist - 1].nservers;
3098
3099 // The calling class this reply releases: the one whose expected reply IS
3100 // this class and which holds a block here.
3101 std::size_t callclass = 0;
3102 for (std::size_t i = 0; i < ri.classes.size(); ++i) {
3103 const std::size_t r = ri.classes[i];
3104 if (sn.syncreply.size() >= r && sn.syncreply[r - 1] == cls) {
3105 callclass = r;
3106 break;
3107 }
3108 }
3109
3110 std::vector<T> buf(inspace.begin(), inspace.begin() + L.bufw);
3111 std::vector<T> srv(inspace.begin() + L.bufw, inspace.begin() + L.bufw + L.srvw);
3112 std::vector<T> var(inspace.begin() + L.bufw + L.srvw, inspace.end());
3113
3114 if (callclass > 0) {
3115 const std::size_t s = ri.slot[callclass - 1];
3116 if (s != static_cast<std::size_t>(-1) && s < var.size() &&
3117 num_traits<T>::to_double(var[s]) > 0)
3118 var[s] -= one;
3119 }
3120
3121 // The reply joins: into a free server, enumerating its entry phase, or at
3122 // the tail of the buffer. Servers still held for OTHER pending replies are
3123 // not available, which is what `Seff` subtracts.
3124 const double seff = S - reply_blocked(sn, ind, var);
3125 double occ = 0;
3126 for (std::size_t j = 0; j < srv.size(); ++j) occ += num_traits<T>::to_double(srv[j]);
3127 if (occ < seff) {
3128 const std::vector<T> pentry = entry_phase_dist(sn, ist, cls);
3129 for (std::size_t ke = 0; ke < L.K[cls - 1]; ++ke) {
3130 if (num_traits<T>::to_double(pentry[ke]) <= 0) continue;
3131 std::vector<T> s2 = srv;
3132 s2[L.Ks[cls - 1] + ke] += one;
3133 std::vector<T> row = buf;
3134 row.insert(row.end(), s2.begin(), s2.end());
3135 row.insert(row.end(), var.begin(), var.end());
3136 out.space.push_back(row);
3137 out.rate.push_back(num_traits<T>::from_int(-1));
3138 out.prob.push_back(pentry[ke]);
3139 }
3140 return out;
3141 }
3142 // Every available server is busy: queue at the tail, which for a
3143 // right-aligned buffer is the LAST empty slot.
3144 std::vector<T> b2 = buf;
3145 std::size_t slot = b2.size();
3146 for (std::size_t b = 0; b < b2.size(); ++b)
3147 if (num_traits<T>::to_double(b2[b]) == 0) slot = b;
3148 if (slot == b2.size()) {
3149 b2.insert(b2.begin(), zero);
3150 slot = 0;
3151 }
3152 b2[slot] = num_traits<T>::from_int(static_cast<long>(cls));
3153 std::vector<T> row = b2;
3154 row.insert(row.end(), srv.begin(), srv.end());
3155 row.insert(row.end(), var.begin(), var.end());
3156 out.space.push_back(row);
3157 out.rate.push_back(num_traits<T>::from_int(-1));
3158 out.prob.push_back(one);
3159 return out;
3160}
3161
3162
3163/** Read (pos, swk, ctr) out of the local-variable block. */
3164template <class T>
3165void polling_get(const PollingInfo<T>& pi, const std::vector<T>& var, std::size_t srvclass,
3166 std::size_t& pos, std::size_t& swk, long& ctr) {
3167 pos = pi.ipos != static_cast<std::size_t>(-1)
3168 ? static_cast<std::size_t>(num_traits<T>::to_double(var[pi.off + pi.ipos]))
3169 : (srvclass > 0 ? srvclass : 1);
3170 swk = pi.iswk != static_cast<std::size_t>(-1)
3171 ? static_cast<std::size_t>(num_traits<T>::to_double(var[pi.off + pi.iswk]))
3172 : 0;
3173 ctr = pi.ictr != static_cast<std::size_t>(-1)
3174 ? static_cast<long>(num_traits<T>::to_double(var[pi.off + pi.ictr]))
3175 : 0;
3176}
3177
3178/** Write (pos, swk, ctr) back into the local-variable block. */
3179template <class T>
3180std::vector<T> polling_set(const PollingInfo<T>& pi, std::vector<T> var, std::size_t pos,
3181 std::size_t swk, long ctr) {
3182 if (pi.ipos != static_cast<std::size_t>(-1))
3183 var[pi.off + pi.ipos] = num_traits<T>::from_int(static_cast<long>(pos));
3184 if (pi.iswk != static_cast<std::size_t>(-1))
3185 var[pi.off + pi.iswk] = num_traits<T>::from_int(static_cast<long>(swk));
3186 if (pi.ictr != static_cast<std::size_t>(-1))
3187 var[pi.off + pi.ictr] = num_traits<T>::from_int(ctr);
3188 return var;
3189}
3190
3191/** Port of `State.pollingBudget`: how many services this visit may perform. */
3192template <class T>
3193long polling_budget(const PollingInfo<T>& pi, long nbufq) {
3194 switch (pi.ptype) {
3195 case lang::PollingType::EXHAUSTIVE: return 0; // unused: drains instead
3196 case lang::PollingType::GATED: return nbufq; // exactly those found
3197 case lang::PollingType::KLIMITED: return static_cast<long>(pi.pk);
3198 case lang::PollingType::DECREMENTING: return nbufq - 1;
3199 default: throw UnsupportedError(ErrorKind{"SchedStrategy_POLLING"}, "polling_budget: unsupported polling type");
3200 }
3201}
3202
3203/**
3204 * Port of `State.pollingNext`: where the server goes from buffer `pos`.
3205 *
3206 * Returns mode 1 to open a visit at q, 2 to enter the switchover into q, and 0
3207 * to PARK. Parking is reachable only with every switchover immediate, where a
3208 * server completing a full lap without finding work would otherwise cycle in
3209 * zero time forever.
3210 */
3211template <class T>
3212void polling_next(const PollingInfo<T>& pi, std::size_t pos, const std::vector<long>& nbuf,
3213 std::size_t R, bool arrived, std::size_t& q, int& mode, long& budget) {
3214 if (arrived && pi.polled[pos - 1] && nbuf[pos - 1] > 0) {
3215 // The switchover into pos is already paid for, so a visit starts here.
3216 q = pos;
3217 mode = 1;
3218 budget = polling_budget(pi, nbuf[pos - 1]);
3219 return;
3220 }
3221 std::size_t p = pos;
3222 for (std::size_t step = 0; step < R; ++step) { // a full lap, ending at pos
3223 p = p % R + 1;
3224 if (!pi.polled[p - 1]) continue;
3225 if (pi.has_sw[p - 1]) {
3226 q = p;
3227 mode = 2;
3228 budget = 0;
3229 return;
3230 }
3231 if (nbuf[p - 1] > 0) {
3232 q = p;
3233 mode = 1;
3234 budget = polling_budget(pi, nbuf[p - 1]);
3235 return;
3236 }
3237 }
3238 q = pos;
3239 mode = 0;
3240 budget = 0;
3241}
3242
3243/** Port of `State.pollingLand`: the states the walk lands in, with weights. */
3244template <class T>
3245void polling_land(const NetworkStruct<T>& sn, std::size_t ist, const PollingInfo<T>& pi,
3246 std::size_t q, int mode, long budget, const std::vector<T>& buf,
3247 const std::vector<T>& srv, const std::vector<T>& var, const RowLayout<T>& L,
3248 std::vector<std::vector<T>>& rows, std::vector<T>& probs) {
3249 const T one = num_traits<T>::from_int(1);
3250 if (mode == 1) {
3251 // Open or continue a visit at q: pull a waiting class-q job in.
3252 std::vector<T> b2 = buf;
3253 b2[q - 1] -= one;
3254 const std::vector<T> pentry = entry_phase_dist(sn, ist, q);
3255 for (std::size_t ke = 0; ke < L.K[q - 1]; ++ke) {
3256 if (num_traits<T>::to_double(pentry[ke]) <= 0) continue;
3257 std::vector<T> s2 = srv;
3258 s2[L.Ks[q - 1] + ke] += one;
3259 std::vector<T> row = b2;
3260 row.insert(row.end(), s2.begin(), s2.end());
3261 const std::vector<T> v2 = polling_set(pi, var, q, 0, budget);
3262 row.insert(row.end(), v2.begin(), v2.end());
3263 rows.push_back(row);
3264 probs.push_back(pentry[ke]);
3265 }
3266 } else if (mode == 2) {
3267 // Enter the switchover into q: the facility stays EMPTY while walking.
3268 for (std::size_t ke = 0; ke < pi.ksw[q - 1]; ++ke) {
3269 if (num_traits<T>::to_double(pi.sw_pie[q - 1][ke]) <= 0) continue;
3270 std::vector<T> row = buf;
3271 row.insert(row.end(), srv.begin(), srv.end());
3272 const std::vector<T> v2 = polling_set(pi, var, q, ke + 1, 0);
3273 row.insert(row.end(), v2.begin(), v2.end());
3274 rows.push_back(row);
3275 probs.push_back(pi.sw_pie[q - 1][ke]);
3276 }
3277 } else {
3278 // Park: held until the next arrival wakes the server.
3279 std::vector<T> row = buf;
3280 row.insert(row.end(), srv.begin(), srv.end());
3281 const std::vector<T> v2 = polling_set(pi, var, q, 0, 0);
3282 row.insert(row.end(), v2.begin(), v2.end());
3283 rows.push_back(row);
3284 probs.push_back(one);
3285 }
3286}
3287
3288
3289/**
3290 * Port of the SWITCH branch: a polling server advances its switchover timer.
3291 *
3292 * Unlike PHASE, which carries only the internal transitions of a phase-type and
3293 * leaves the absorption to DEP, this event carries BOTH -- a completed
3294 * switchover moves no job, so there is no departure to attach the absorption
3295 * to. It is therefore emitted even for a single-phase switchover, where it
3296 * consists of the absorption alone.
3297 */
3298template <class T>
3300 const std::vector<T>& inspace, std::size_t cls) {
3301 const std::size_t R = sn.nclasses;
3302 const std::size_t ist = sn.nodes[ind - 1].station;
3303 const T one = num_traits<T>::from_int(1);
3304 EventOutcome<T> out;
3305 if (ist == 0) throw InputError("after_event_station_switch: node is not a station");
3306 const PollingInfo<T> pinfo = polling_info(sn, ind);
3307 if (!pinfo.valid || !pinfo.has_sw[cls - 1]) return out;
3308 const RowLayout<T> L = row_layout(sn, ind, inspace.size());
3309
3310 const std::vector<T> buf(inspace.begin(), inspace.begin() + L.bufw);
3311 const std::vector<T> srv(inspace.begin() + L.bufw, inspace.begin() + L.bufw + L.srvw);
3312 const std::vector<T> var(inspace.begin() + L.bufw + L.srvw, inspace.end());
3313
3314 std::size_t pos = 0, swk = 0;
3315 long ctr = 0;
3316 polling_get(pinfo, var, 0, pos, swk, ctr);
3317 // The server must actually be inside the switchover into this buffer.
3318 if (pos != cls || swk == 0) return out;
3319
3320 // Internal transitions of the switchover phase-type.
3321 for (std::size_t kd = 0; kd < pinfo.ksw[cls - 1]; ++kd) {
3322 if (kd + 1 == swk) continue;
3323 const T r0 = pinfo.sw_d0[cls - 1](swk - 1, kd);
3324 if (num_traits<T>::to_double(r0) <= 0) continue;
3325 std::vector<T> row = buf;
3326 row.insert(row.end(), srv.begin(), srv.end());
3327 const std::vector<T> v2 = polling_set(pinfo, var, cls, kd + 1, 0);
3328 row.insert(row.end(), v2.begin(), v2.end());
3329 out.space.push_back(row);
3330 out.rate.push_back(r0);
3331 out.prob.push_back(one);
3332 }
3333 // Absorption: the server arrives and either opens a visit or walks on.
3334 T rate = num_traits<T>::from_int(0);
3335 for (std::size_t j = 0; j < pinfo.ksw[cls - 1]; ++j) rate += pinfo.sw_d1[cls - 1](swk - 1, j);
3336 if (num_traits<T>::to_double(rate) <= 0) return out;
3337 std::vector<long> nbuf(R, 0);
3338 for (std::size_t r = 0; r < R && r < L.bufw; ++r)
3339 nbuf[r] = static_cast<long>(num_traits<T>::to_double(buf[r]));
3340 std::size_t q = 0;
3341 int mode = 0;
3342 long budget = 0;
3343 polling_next(pinfo, cls, nbuf, R, true, q, mode, budget);
3344 std::vector<std::vector<T>> rows;
3345 std::vector<T> probs;
3346 polling_land(sn, ist, pinfo, q, mode, budget, buf, srv, var, L, rows, probs);
3347 for (std::size_t j = 0; j < rows.size(); ++j) {
3348 // A switchover completing over an empty buffer starts the next leg at
3349 // once, and when that leg re-enters the SAME phase of the same
3350 // switchover the landing state IS the departure state. Such a self-loop
3351 // is not a transition: emitting it would inflate the row's exit rate.
3352 if (rows[j] == inspace) continue;
3353 out.space.push_back(rows[j]);
3354 out.rate.push_back(T(rate * probs[j]));
3355 out.prob.push_back(one);
3356 // A completed switchover that opens a visit pulls a waiting class-q job
3357 // into the server, so it starts service just as an ARV or a DEP
3358 // promotion does. This is the one service start a polling station
3359 // reaches through neither, and leaving it untagged would break
3360 // startRate == TN + preemptRate there for no reason other than the name
3361 // of the carrier event.
3362 tag_last(out, mode == 1 ? q : 0, 0);
3363 }
3364 pad_tags(out);
3365 return out;
3366}
3367
3368
3369/**
3370 * Port of `State.afterEventCache`: events at a Cache node.
3371 *
3372 * A Cache is stateful but is NOT a station, so its row is [per-class counts |
3373 * cache contents | retrieval bitmap] with no buffer or server block. The
3374 * contents region holds one column per cached slot, laid out list by list;
3375 * `cpos(i,j)` is position j of list i.
3376 *
3377 * A READ is INSTANTANEOUS: every branch fires at `GlobalConstants::Immediate`,
3378 * because the read is a routing decision rather than a service. The job enters
3379 * in its read class and leaves in the hit or miss class, so the transition
3380 * both moves the job between classes and rewrites the cache contents.
3381 */
3382template <class T>
3384 const std::vector<T>& inspace, EventType event,
3385 std::size_t cls) {
3386 const std::size_t R = sn.nclasses;
3387 const T one = num_traits<T>::from_int(1), zero = num_traits<T>::from_int(0);
3389 EventOutcome<T> out;
3390 const typename std::map<std::size_t, CacheParam<T>>::const_iterator ci = sn.nodeparam.find(ind);
3391 if (ci == sn.nodeparam.end()) throw InputError("after_event_cache: node has no CacheParam");
3392 const CacheParam<T>& cp = ci->second;
3393 const std::size_t h = cp.itemcap.size();
3394 const std::size_t n = cp.nitems;
3395 std::size_t tcc = 0; // total cache capacity, the width of the contents region
3396 for (std::size_t i = 0; i < h; ++i)
3397 if (cp.itemcap[i] > 0) tcc += static_cast<std::size_t>(cp.itemcap[i]);
3398 // cpos(i,j): position j (1-based) of list i (1-based) in the contents region.
3399 const std::vector<int>& m = cp.itemcap;
3400 struct Cpos {
3401 const std::vector<int>& m;
3402 std::size_t operator()(std::size_t i, std::size_t j) const {
3403 std::size_t base = 0;
3404 for (std::size_t t = 0; t + 1 < i; ++t) base += static_cast<std::size_t>(m[t]);
3405 return base + j - 1;
3406 }
3407 } cpos{m};
3408
3409 std::vector<T> srv(inspace.begin(), inspace.begin() + R);
3410 std::vector<T> var(inspace.begin() + R, inspace.end());
3411
3412 if (event == EventType::ARV) {
3413 srv[cls - 1] += one;
3414 std::vector<T> row = srv;
3415 row.insert(row.end(), var.begin(), var.end());
3416 out.space.push_back(row);
3417 out.rate.push_back(num_traits<T>::from_int(-1)); // passive
3418 out.prob.push_back(one);
3419 return out;
3420 }
3421
3422 if (event == EventType::DEP) {
3423 if (num_traits<T>::to_double(srv[cls - 1]) <= 0) return out;
3424 // A retrieval-class job departs the cache only to BEGIN a retrieval
3425 // (cache -> queue). Nothing in the cache state separates such an outbound job
3426 // from an inbound one, back from the retrieval stations and due to complete its
3427 // fetch on the next READ: both sit in the same per-class server slot. Left
3428 // ambiguous, the DEP and the READ syncs are both enabled and, both being
3429 // immediate, split the probability evenly, so a fetch spans a Geom(1/2) number
3430 // of station visits. Its mean is unchanged (E[N]=1), but its second moment gains
3431 // 2*E0[F]^2 and with it the delayed-hit queue length
3432 // d_i = phi_i lambda_i E0[F_i^2]/(2 E0[F_i]), which for an exponential fetch
3433 // comes out exactly twice too large. The per-item in-flight bit resolves the
3434 // ambiguity: the outbound departure below sets it and the READ that completes
3435 // the fetch clears it, so an outbound job (bit clear) may depart, while an
3436 // inbound one (bit set) may not and is left with its READ as the only action.
3437 // The block lifts as soon as another job shares the cache server, because the
3438 // READ cannot fire then either (it requires exactly one job present) and the
3439 // departure is the only way out of the state.
3440 if (cp.retrieval_capacity > 0 && !cp.retrieval_classes.empty()) {
3441 std::size_t item_dep = 0;
3442 for (std::size_t i = 0; i < cp.retrieval_classes.size() && item_dep == 0; ++i)
3443 for (std::size_t c = 0; c < cp.retrieval_classes[i].size(); ++c)
3444 if (cp.retrieval_classes[i][c] == cls) {
3445 item_dep = i + 1;
3446 break;
3447 }
3448 if (item_dep != 0) {
3449 const std::size_t bitcol = tcc + item_dep - 1;
3450 if (bitcol < var.size()) {
3451 if (num_traits<T>::to_double(var[bitcol]) != 0) {
3452 double srvtot = 0;
3453 for (std::size_t r = 0; r < R; ++r)
3454 srvtot += num_traits<T>::to_double(srv[r]);
3455 if (srvtot == 1) return out; // inbound: only its READ is enabled
3456 } else {
3457 var[bitcol] = one;
3458 }
3459 }
3460 } else {
3461 // A read class that owns retrieval classes always switches at the READ,
3462 // into a hit, a miss or a retrieval class; its cache -> station routing
3463 // exists only so that the retrieval classes can inherit it, and must
3464 // never carry the reading job itself out of the cache unread.
3465 bool owns = false;
3466 for (std::size_t i = 0; i < cp.retrieval_classes.size(); ++i)
3467 if (cls - 1 < cp.retrieval_classes[i].size() &&
3468 cp.retrieval_classes[i][cls - 1] != 0) {
3469 owns = true;
3470 break;
3471 }
3472 if (owns) {
3473 const std::size_t hc =
3474 cls - 1 < cp.hitclass.size() ? static_cast<std::size_t>(cp.hitclass[cls - 1]) : 0;
3475 const std::size_t mc =
3476 cls - 1 < cp.missclass.size() ? static_cast<std::size_t>(cp.missclass[cls - 1]) : 0;
3477 if (hc != cls && mc != cls) return out;
3478 }
3479 }
3480 }
3481 srv[cls - 1] -= one;
3482 std::vector<T> row = srv;
3483 row.insert(row.end(), var.begin(), var.end());
3484 out.space.push_back(row);
3485 out.rate.push_back(imm); // the departure is instantaneous
3486 out.prob.push_back(one);
3487 return out;
3488 }
3489
3490 if (event != EventType::READ) return out;
3491
3492 // A READ needs exactly one job present, and it must be of the reading class.
3493 double tot = 0;
3494 for (std::size_t r = 0; r < R; ++r) tot += num_traits<T>::to_double(srv[r]);
3495 if (num_traits<T>::to_double(srv[cls - 1]) <= 0 || tot != 1) return out;
3496 if (cls - 1 >= cp.pread.size() || cp.pread[cls - 1].empty()) return out;
3497 const std::vector<T>& p = cp.pread[cls - 1];
3498
3499 // The delayed-hit retrieval system. Block A (n columns) marks the items in
3500 // flight; block B (one column per retrieval class) counts the secondary
3501 // requests merged onto those fetches. Its width is read off the row rather
3502 // than off the parameters, because a struct whose space predates the block
3503 // still has to be walkable.
3504 const bool retr = cp.retrieval_capacity > 0 && !cp.retrieval_classes.empty();
3505 std::vector<std::size_t> rc_list, rc_items, rc_orig;
3506 if (retr) cache_retrieval_class_map(cp, rc_list, rc_items, rc_orig);
3507 const std::size_t block_b = tcc + n;
3508 std::size_t width_b = var.size() > block_b ? var.size() - block_b : 0;
3509 if (width_b != rc_list.size()) width_b = 0;
3510 // -1 is the sample path's unbounded merge; an exact solver enumerates block
3511 // B only up to the level it declared, and a merge past that level is refused
3512 // rather than folded into a state the space does not hold.
3513 const double maxpend = cp.max_pending_retrieval < 0
3514 ? std::numeric_limits<double>::infinity()
3515 : static_cast<double>(cp.max_pending_retrieval);
3516 bool from_retrieval = false;
3517 for (std::size_t j = 0; j < rc_list.size(); ++j)
3518 if (rc_list[j] == cls) from_retrieval = true;
3519
3520 for (std::size_t k = 1; k <= n; ++k) {
3521 if (k - 1 >= p.size() || num_traits<T>::to_double(p[k - 1]) <= 0) continue;
3522 std::vector<T> srv_e = srv;
3523 srv_e[cls - 1] -= one;
3524 // The item is searched ONLY in the contents region; the trailing
3525 // retrieval slots are a different namespace.
3526 std::size_t posk = 0;
3527 for (std::size_t c = 0; c < tcc && c < var.size(); ++c)
3528 if (static_cast<std::size_t>(num_traits<T>::to_double(var[c])) == k) {
3529 posk = c + 1;
3530 break;
3531 }
3532 // A RETURNING RETRIEVAL always completes the miss that started it, so it
3533 // takes the miss branch even where the enumeration produced a (then
3534 // unreachable) state holding item k. A retrieval class has no hit class
3535 // to switch into either.
3536 if (from_retrieval) posk = 0;
3537 const Matrix<T>& ac = cp.accost.empty() || cls - 1 >= cp.accost.size() ||
3538 k - 1 >= cp.accost[cls - 1].size()
3539 ? Matrix<T>()
3540 : cp.accost[cls - 1][k - 1];
3541 const bool have_ac = ac.rows() >= h + 1 && ac.cols() >= h + 1;
3542
3543 if (posk == 0) {
3544 // CACHE MISS, or one leg of a retrieval. A fetch is in flight iff
3545 // block A's bit for item k is set.
3546 const bool in_flight =
3547 retr && tcc + k <= var.size() && num_traits<T>::to_double(var[tcc + k - 1]) != 0;
3548 std::size_t r_class = 0;
3549 if (retr && k - 1 < cp.retrieval_classes.size() &&
3550 cls - 1 < cp.retrieval_classes[k - 1].size())
3551 r_class = cp.retrieval_classes[k - 1][cls - 1];
3552 // A retrieval-class job whose item is not recorded in the bitmap is
3553 // outbound: it has not reached the retrieval stations yet, so it has no
3554 // fetch to complete and only its departure is enabled.
3555 if (from_retrieval && !in_flight) continue;
3556
3557 if (!from_retrieval && r_class != 0) {
3558 // BEGIN a fetch, or MERGE onto one already running. The merge is
3559 // the delayed hit: it adds nothing to the cache's server block,
3560 // and is held in block B until the fetch completes and releases
3561 // it in the hit class of the class that issued it.
3562 std::vector<T> srv_b = srv_e;
3563 std::vector<T> var_b = var;
3564 if (!in_flight) {
3565 // The job switches to item k's retrieval class and waits in the cache
3566 // server for the departure that carries it to the retrieval stations.
3567 // That departure, not this READ, sets the in-flight bit, so that an
3568 // outbound retrieval job (bit clear) is distinguishable from an
3569 // inbound one (bit set); see the DEP branch above.
3570 srv_b[r_class - 1] += one;
3571 } else {
3572 if (width_b == 0) continue;
3573 std::size_t bslot = width_b;
3574 for (std::size_t j = 0; j < rc_list.size(); ++j)
3575 if (rc_list[j] == r_class) { bslot = j; break; }
3576 if (bslot >= width_b) continue;
3577 double pend = 0;
3578 for (std::size_t j = 0; j < width_b; ++j)
3579 pend += num_traits<T>::to_double(var_b[block_b + j]);
3580 if (pend >= maxpend) continue; // beyond the truncation level
3581 var_b[block_b + bslot] += one;
3582 }
3583 std::vector<T> row = srv_b;
3584 row.insert(row.end(), var_b.begin(), var_b.end());
3585 out.space.push_back(row);
3586 out.rate.push_back(T(p[k - 1] * imm));
3587 out.prob.push_back(one);
3588 continue;
3589 }
3590
3591 // The fetch is complete (or there is no retrieval system): the job
3592 // leaves in the miss class, the item may be admitted into one of the
3593 // lists, and every request merged onto this fetch is released in the
3594 // SAME transition as a delayed hit.
3595 if (cls - 1 >= cp.missclass.size() || cp.missclass[cls - 1] == 0) continue;
3596 std::vector<T> srv_m = srv_e;
3597 srv_m[cp.missclass[cls - 1] - 1] += one;
3598 std::vector<T> var_m = var;
3599 if (tcc + k <= var_m.size()) var_m[tcc + k - 1] = zero; // retrieval done
3600 for (std::size_t j = 0; j < width_b; ++j) {
3601 if (rc_items[j] != k) continue;
3602 const double held = num_traits<T>::to_double(var_m[block_b + j]);
3603 if (held <= 0) continue;
3604 const std::size_t oc = rc_orig[j];
3605 if (oc - 1 >= cp.hitclass.size() || cp.hitclass[oc - 1] == 0) continue;
3606 srv_m[cp.hitclass[oc - 1] - 1] += var_m[block_b + j];
3607 var_m[block_b + j] = zero;
3608 }
3609
3610 // Column 1 of the access cost is the REJECT branch: the item passes
3611 // through without being cached at all.
3612 const T rej = have_ac ? ac(0, 0) : zero;
3613 if (num_traits<T>::to_double(rej) > 0) {
3614 std::vector<T> row = srv_m;
3615 row.insert(row.end(), var_m.begin(), var_m.end());
3616 out.space.push_back(row);
3617 out.rate.push_back(T(rej * p[k - 1] * imm));
3618 out.prob.push_back(one);
3619 }
3620 for (std::size_t l = 1; l <= h; ++l) {
3621 const T w = have_ac ? ac(0, l) : (l == 1 ? one : zero);
3622 if (num_traits<T>::to_double(w) <= 0) continue;
3623 if (m[l - 1] <= 0) continue;
3624 const std::size_t ml = static_cast<std::size_t>(m[l - 1]);
3626 // Random replacement: the item lands uniformly in any slot.
3627 for (std::size_t rr = 1; rr <= ml; ++rr) {
3628 std::vector<T> vp = var_m;
3629 vp[cpos(l, rr)] = num_traits<T>::from_int(static_cast<long>(k));
3630 std::vector<T> row = srv_m;
3631 row.insert(row.end(), vp.begin(), vp.end());
3632 out.space.push_back(row);
3633 out.rate.push_back(T(w * p[k - 1] /
3634 num_traits<T>::from_int(static_cast<long>(ml)) * imm));
3635 out.prob.push_back(one);
3636 }
3637 } else {
3638 // The ordered families insert at the HEAD, shifting the list
3639 // down by one and evicting its tail.
3640 std::vector<T> vp = var_m;
3641 for (std::size_t j = ml; j >= 2; --j) vp[cpos(l, j)] = var_m[cpos(l, j - 1)];
3642 vp[cpos(l, 1)] = num_traits<T>::from_int(static_cast<long>(k));
3643 T rate = T(w * p[k - 1] * imm);
3644 // q-LRU admits a miss only with probability q; the rest
3645 // passes through uncached.
3647 const T q = cp.qlru;
3648 if (num_traits<T>::to_double(q) < 1) {
3649 std::vector<T> row0 = srv_m;
3650 row0.insert(row0.end(), var_m.begin(), var_m.end());
3651 out.space.push_back(row0);
3652 out.rate.push_back(T(rate * T(one - q)));
3653 out.prob.push_back(one);
3654 }
3655 rate = T(rate * q);
3656 }
3657 if (num_traits<T>::to_double(rate) <= 0) continue;
3658 std::vector<T> row = srv_m;
3659 row.insert(row.end(), vp.begin(), vp.end());
3660 out.space.push_back(row);
3661 out.rate.push_back(rate);
3662 out.prob.push_back(one);
3663 }
3664 }
3665 } else {
3666 // CACHE HIT: the job leaves in the hit class. Which list it was
3667 // found in decides how the contents move.
3668 if (cls - 1 >= cp.hitclass.size() || cp.hitclass[cls - 1] == 0) continue;
3669 std::vector<T> srv_h = srv_e;
3670 srv_h[cp.hitclass[cls - 1] - 1] += one;
3671 std::size_t li = 1, acc = 0;
3672 for (std::size_t t = 0; t < h; ++t) {
3673 const std::size_t mt = m[t] > 0 ? static_cast<std::size_t>(m[t]) : 0;
3674 if (posk <= acc + mt) { li = t + 1; break; }
3675 acc += mt;
3676 }
3677 const std::size_t j = posk - acc;
3678 if (li < h) {
3679 // A HIT BELOW THE TERMINAL LIST PROMOTES, and that is what makes
3680 // an h-list cache more than h caches side by side. Row `li` of
3681 // the access cost routes the item from list li into list
3682 // inew >= li, exactly as `afterEventCache.m` does over `inew =
3683 // i:h`; an empty accost is the reference default
3684 // `diag(ones(1,h),1)` with a 1 in the bottom-right, the linear
3685 // cache that moves the item one list up. Omitting this branch
3686 // froze every list above the first at its initial contents: on
3687 // m=[2,1] only 12 of the 60 configurations stayed reachable, and
3688 // the CTMC hit ratio of cache_compare_replc came out 4.9% low.
3689 for (std::size_t inew = li; inew <= h; ++inew) {
3690 if (m[inew - 1] <= 0) continue;
3691 const std::size_t mn = static_cast<std::size_t>(m[inew - 1]);
3692 const T w = have_ac ? ac(li, inew) : (inew == li + 1 ? one : zero);
3693 if (num_traits<T>::to_double(w) <= 0) continue;
3694 if (inew == li) {
3695 // A hit that stays in list li is a leaf hit (Gast-Van Houdt, QUESTA 2016): the LRU family
3696 // moves the item to the head of list li, while FIFO, strict FIFO and RR change nothing.
3697 std::vector<T> vp = var;
3698 const bool lru = cp.replacestrat != lang::ReplacementStrategy::RR &&
3701 if (lru) {
3702 for (std::size_t t = j; t >= 2; --t) vp[cpos(li, t)] = var[cpos(li, t - 1)];
3703 vp[cpos(li, 1)] = var[cpos(li, j)];
3704 }
3705 std::vector<T> row = srv_h;
3706 row.insert(row.end(), vp.begin(), vp.end());
3707 out.space.push_back(row);
3708 out.rate.push_back(T(w * p[k - 1] * imm));
3709 out.prob.push_back(one);
3710 continue;
3711 }
3713 // Random replacement swaps with a uniformly drawn slot.
3714 for (std::size_t r = 1; r <= mn; ++r) {
3715 std::vector<T> vp = var;
3716 vp[cpos(li, j)] = var[cpos(inew, r)];
3717 vp[cpos(inew, r)] = num_traits<T>::from_int(static_cast<long>(k));
3718 std::vector<T> row = srv_h;
3719 row.insert(row.end(), vp.begin(), vp.end());
3720 out.space.push_back(row);
3721 out.rate.push_back(
3722 T(w * p[k - 1] /
3723 num_traits<T>::from_int(static_cast<long>(mn)) * imm));
3724 out.prob.push_back(one);
3725 }
3726 continue;
3727 }
3728 // Every read below is of the UNMODIFIED row; inew > li here, so
3729 // the source and target lists are distinct.
3730 std::vector<T> vp = var;
3731 // The LRU family closes the gap in list li; FIFO orders by
3732 // insertion and so leaves list li otherwise untouched.
3733 const bool ordered = cp.replacestrat != lang::ReplacementStrategy::FIFO;
3734 if (ordered)
3735 for (std::size_t t = j; t >= 2; --t) vp[cpos(li, t)] = var[cpos(li, t - 1)];
3736 // The tail evicted from the target list takes the slot the
3737 // promoted item vacated.
3738 vp[cpos(li, ordered ? 1 : j)] = var[cpos(inew, mn)];
3739 for (std::size_t t = mn; t >= 2; --t) vp[cpos(inew, t)] = var[cpos(inew, t - 1)];
3740 vp[cpos(inew, 1)] = num_traits<T>::from_int(static_cast<long>(k));
3741 std::vector<T> row = srv_h;
3742 row.insert(row.end(), vp.begin(), vp.end());
3743 out.space.push_back(row);
3744 out.rate.push_back(T(w * p[k - 1] * imm));
3745 out.prob.push_back(one);
3746 }
3750 // A hit in the terminal list does not reorder these: FIFO orders
3751 // by INSERTION, and random replacement has no order to disturb.
3752 std::vector<T> row = srv_h;
3753 row.insert(row.end(), var.begin(), var.end());
3754 out.space.push_back(row);
3755 out.rate.push_back(T(p[k - 1] * imm));
3756 out.prob.push_back(one);
3757 } else {
3758 // LRU and its relatives promote the hit item to the head of its
3759 // list, which is the whole content of "recently used".
3760 std::vector<T> vp = var;
3761 for (std::size_t t = j; t >= 2; --t) vp[cpos(li, t)] = var[cpos(li, t - 1)];
3762 vp[cpos(li, 1)] = var[cpos(li, j)];
3763 std::vector<T> row = srv_h;
3764 row.insert(row.end(), vp.begin(), vp.end());
3765 out.space.push_back(row);
3766 out.rate.push_back(T(p[k - 1] * imm));
3767 out.prob.push_back(one);
3768 }
3769 }
3770 }
3771 return out;
3772}
3773
3774
3775/** One half of a GLOBAL synchronization: a mode event at a node. */
3776template <class T>
3778 EventType event = EventType::LOCAL;
3779 std::size_t node = 0; ///< 1-based node index (a Transition, or a place)
3780 std::size_t mode = 0; ///< 1-based mode index
3781 std::size_t cls = 1; ///< 1-based class the arc moves
3782 T weight = num_traits<T>::from_int(1); ///< arc multiplicity
3783};
3784
3785/**
3786 * A GLOBAL synchronization: an SPN mode event and the place arcs it drives.
3787 *
3788 * Unlike an ordinary Sync, which pairs ONE active with ONE passive, a firing
3789 * touches every input and output place at once -- that atomicity is what makes
3790 * a Petri net transition a transition. PRE passives consume, POST produce, and
3791 * LOCAL passives are read-only (an inhibitor place, whose marking is tested but
3792 * never moved).
3793 */
3794template <class T>
3797 std::vector<ModeEvent<T>> passive;
3798};
3799
3800/**
3801 * Port of `MNetwork.refreshGlobalSync`: the ENABLE and FIRE synchronizations.
3802 *
3803 * An inhibiting place enters as a LOCAL passive rather than a PRE, and only
3804 * when it is not already an enabling or firing place: its marking is read for
3805 * the inhibition test but no token crosses the arc.
3806 */
3807template <class T>
3808std::vector<GlobalSync<T>> refresh_global_sync(const NetworkStruct<T>& sn) {
3809 std::vector<GlobalSync<T>> gsync;
3810 const T one = num_traits<T>::from_int(1);
3811 for (std::size_t ind = 1; ind <= sn.nodes.size(); ++ind) {
3812 if (sn.nodes[ind - 1].nodetype != NodeType::Transition) continue;
3813 const typename std::map<std::size_t, TransitionParam<T>>::const_iterator it =
3814 sn.transparam.find(ind);
3815 if (it == sn.transparam.end()) continue;
3816 const TransitionParam<T>& tp = it->second;
3817 for (int pass = 0; pass < 2; ++pass) {
3818 for (std::size_t m = 1; m <= tp.nmodes; ++m) {
3819 // ONE ENTRY PER (place, class) ARC, which is what makes a
3820 // multiclass net a different net from the class-summed one: a
3821 // Class2 token at a place must not satisfy a Class1 pre-arc, so
3822 // the pair travels into the passive rather than the place alone.
3823 std::vector<std::pair<std::size_t, std::size_t>> enab, fire, inhib;
3824 const Matrix<T>& en = tp.enabling[m - 1];
3825 const Matrix<T>& fi = tp.firing[m - 1];
3826 const Matrix<T>& ih = tp.inhibiting[m - 1];
3827 for (std::size_t q = 0; q < en.rows(); ++q)
3828 for (std::size_t r = 0; r < en.cols(); ++r)
3829 if (num_traits<T>::to_double(en(q, r)) > 0)
3830 enab.push_back(std::make_pair(q + 1, r + 1));
3831 for (std::size_t q = 0; q < fi.rows(); ++q)
3832 for (std::size_t r = 0; r < fi.cols(); ++r)
3833 if (num_traits<T>::to_double(fi(q, r)) > 0)
3834 fire.push_back(std::make_pair(q + 1, r + 1));
3835 for (std::size_t q = 0; q < ih.rows(); ++q)
3836 for (std::size_t r = 0; r < ih.cols(); ++r) {
3837 if (std::isinf(num_traits<T>::to_double(ih(q, r)))) continue;
3838 // The de-duplication is against the PLACE, not the
3839 // (place, class) pair: the passive's job is to bring the
3840 // place's marginal into the outcome, and one copy of a
3841 // place carries every class of it.
3842 bool dup = false;
3843 for (std::size_t i = 0; i < enab.size(); ++i)
3844 dup = dup || enab[i].first == q + 1;
3845 for (std::size_t i = 0; i < fire.size(); ++i)
3846 dup = dup || fire[i].first == q + 1;
3847 for (std::size_t i = 0; i < inhib.size(); ++i)
3848 dup = dup || inhib[i].first == q + 1;
3849 if (!dup) inhib.push_back(std::make_pair(q + 1, r + 1));
3850 }
3851 GlobalSync<T> g;
3852 g.active.event = pass == 0 ? EventType::ENABLE : EventType::FIRE;
3853 g.active.node = ind;
3854 g.active.mode = m;
3855 if (pass == 0) {
3856 // An ENABLE only READS the markings, so every passive is
3857 // LOCAL: enabling it is a test, not a token movement. One
3858 // per PLACE here, since a read of a place reads every class.
3859 std::vector<std::size_t> seen;
3860 auto once = [&](std::size_t q, std::size_t r) {
3861 for (std::size_t i = 0; i < seen.size(); ++i)
3862 if (seen[i] == q) return;
3863 seen.push_back(q);
3864 g.passive.push_back(ModeEvent<T>{EventType::LOCAL, q, m, r, one});
3865 };
3866 for (std::size_t i = 0; i < enab.size(); ++i) once(enab[i].first, enab[i].second);
3867 for (std::size_t i = 0; i < inhib.size(); ++i)
3868 once(inhib[i].first, inhib[i].second);
3869 } else {
3870 for (std::size_t i = 0; i < enab.size(); ++i)
3871 g.passive.push_back(ModeEvent<T>{EventType::PRE, enab[i].first, m,
3872 enab[i].second,
3873 en(enab[i].first - 1, enab[i].second - 1)});
3874 for (std::size_t i = 0; i < fire.size(); ++i)
3875 g.passive.push_back(ModeEvent<T>{EventType::POST, fire[i].first, m,
3876 fire[i].second,
3877 fi(fire[i].first - 1, fire[i].second - 1)});
3878 for (std::size_t i = 0; i < inhib.size(); ++i)
3879 g.passive.push_back(ModeEvent<T>{EventType::LOCAL, inhib[i].first, m,
3880 inhib[i].second, one});
3881 }
3882 gsync.push_back(g);
3883 }
3884 }
3885 }
3886 return gsync;
3887}
3888
3889/** What one global event produces: a whole network state per outcome. */
3890template <class T>
3892 std::vector<NetState<T>> space;
3893 std::vector<T> rate, prob;
3894 /**
3895 * True where the outcome is a firing COMPLETION, i.e. one that applied the
3896 * PRE/POST updates. Callers must NOT re-derive this from the markings: a
3897 * transition whose firing returns exactly what its enabling consumed
3898 * leaves every marking invariant yet still completed.
3899 */
3900 std::vector<bool> completion;
3901 bool empty() const { return space.empty(); }
3902};
3903
3904/**
3905 * Port of `State.afterGlobalEvent`: an SPN mode ENABLEs or FIREs.
3906 *
3907 * This is the one handler that rewrites SEVERAL nodes at once, because a
3908 * firing is atomic across all its arcs. The Transition's own row records how
3909 * many servers of each mode are idle, running (and in which firing phase), and
3910 * have just fired; the places are rewritten through the PRE and POST passives.
3911 */
3912template <class T>
3914 const GlobalSync<T>& gl) {
3915 const std::size_t R = sn.nclasses;
3916 const std::size_t ind = gl.active.node;
3917 const std::size_t mode = gl.active.mode;
3918 const T one = num_traits<T>::from_int(1), zero = num_traits<T>::from_int(0);
3920 GlobalOutcome<T> out;
3921 const std::size_t isf = sn.stateful_index(ind);
3922 if (isf == 0) throw InputError("after_global_event: the transition is not stateful");
3923 const typename std::map<std::size_t, TransitionParam<T>>::const_iterator it =
3924 sn.transparam.find(ind);
3925 if (it == sn.transparam.end()) throw InputError("after_global_event: node has no TransitionParam");
3926 const TransitionParam<T>& tp = it->second;
3927
3928 std::vector<std::size_t> fK(tp.nmodes, 1), fKs(tp.nmodes, 0);
3929 std::size_t tot = 0;
3930 for (std::size_t m = 0; m < tp.nmodes; ++m) {
3931 fK[m] = m < tp.firingphases.size() && tp.firingphases[m] > 0 ? tp.firingphases[m] : 1;
3932 fKs[m] = tot;
3933 tot += fK[m];
3934 }
3935 const std::vector<T>& row = glspace.local[isf - 1];
3936 std::vector<T> buf(row.begin(), row.begin() + tp.nmodes);
3937 std::vector<T> srv(row.begin() + tp.nmodes, row.begin() + tp.nmodes + tot);
3938 std::vector<T> fired(row.begin() + tp.nmodes + tot,
3939 row.begin() + 2 * tp.nmodes + tot);
3940 const std::vector<T> var(row.begin() + 2 * tp.nmodes + tot, row.end());
3941
3942 // The marking of every place this mode reads, node-indexed.
3943 std::vector<std::vector<T>> ep(sn.nodes.size() + 1, std::vector<T>(R, zero));
3944 for (std::size_t j = 0; j < gl.passive.size(); ++j) {
3945 const std::size_t pn = gl.passive[j].node;
3946 const std::size_t pisf = sn.stateful_index(pn);
3947 if (pisf == 0) continue;
3948 const std::pair<T, std::vector<T>> mg = to_marginal_aggr(sn, pn, glspace.local[pisf - 1]);
3949 ep[pn] = mg.second;
3950 }
3951
3952 // The enabling DEGREE: how many concurrent firings the marking supports.
3953 // An inhibitor arc disables the mode outright once its threshold is met.
3954 //
3955 // EVERY TEST IS PER (place, class), the elementwise comparison
3956 // `afterGlobalEvent.m:85` makes against `enabling_m`. Summing the marking
3957 // over classes first, as this port did until 2026-08-12, let a Class2 token
3958 // satisfy a Class1 pre-arc: on a net where Mode1 needs two Class1 tokens at
3959 // P1 and Mode2 one Class2 token there, the summed test fires Mode1 off a
3960 // marking that holds no Class1 token at all.
3961 const Matrix<T>& en_m = tp.enabling[mode - 1];
3962 const Matrix<T>& ih_m = tp.inhibiting[mode - 1];
3963 bool inhibited = false;
3964 for (std::size_t q = 0; q < ih_m.rows(); ++q)
3965 for (std::size_t r = 0; r < ih_m.cols() && r < R; ++r) {
3966 const double thr = num_traits<T>::to_double(ih_m(q, r));
3967 if (std::isinf(thr)) continue;
3968 if (num_traits<T>::to_double(ep[q + 1][r]) >= thr) inhibited = true;
3969 }
3970 bool under = false;
3971 for (std::size_t q = 0; q < en_m.rows(); ++q)
3972 for (std::size_t r = 0; r < en_m.cols() && r < R; ++r) {
3973 const double need = num_traits<T>::to_double(en_m(q, r));
3974 if (need <= 0) continue;
3975 if (num_traits<T>::to_double(ep[q + 1][r]) < need) under = true;
3976 }
3977 long mark_degree = 0;
3978 if (!inhibited && !under) {
3979 long d = 1;
3980 for (;;) {
3981 bool ok = true;
3982 for (std::size_t q = 0; q < en_m.rows() && ok; ++q)
3983 for (std::size_t r = 0; r < en_m.cols() && r < R && ok; ++r) {
3984 const double need = num_traits<T>::to_double(en_m(q, r)) * d;
3985 if (need <= 0) continue;
3986 if (num_traits<T>::to_double(ep[q + 1][r]) < need) ok = false;
3987 }
3988 if (!ok) break;
3989 ++d;
3990 }
3991 mark_degree = d - 1;
3992 }
3993 const double svm = mode - 1 < tp.nmodeservers.size() ? tp.nmodeservers[mode - 1] : 1.0;
3994 const long nsrv = std::isfinite(svm) ? static_cast<long>(svm)
3995 : static_cast<long>(GlobalConstants::MaxInt);
3996
3997 if (gl.active.event == EventType::ENABLE) {
3998 long running = 0;
3999 for (std::size_t k = 0; k < fK[mode - 1]; ++k)
4000 running += static_cast<long>(num_traits<T>::to_double(srv[fKs[mode - 1] + k]));
4001 if (inhibited || under) {
4002 // Disabled: every server of this mode returns to the idle pool.
4003 std::vector<T> b2 = buf, s2 = srv;
4004 b2[mode - 1] = num_traits<T>::from_int(nsrv);
4005 for (std::size_t k = 0; k < fK[mode - 1]; ++k) s2[fKs[mode - 1] + k] = zero;
4006 std::vector<T> nr = b2;
4007 nr.insert(nr.end(), s2.begin(), s2.end());
4008 nr.insert(nr.end(), fired.begin(), fired.end());
4009 nr.insert(nr.end(), var.begin(), var.end());
4010 if (nr == row) return out; // already disabled: not a transition
4011 NetState<T> ns = glspace;
4012 ns.local[isf - 1] = nr;
4013 out.space.push_back(ns);
4014 out.rate.push_back(imm);
4015 out.prob.push_back(one);
4016 out.completion.push_back(false);
4017 return out;
4018 }
4019 const long want = std::min(mark_degree, nsrv);
4020 if (running == want) return out; // nothing to do
4021 if (running < want) {
4022 // Start servers, distributing them over the firing phases by the
4023 // entry law; the multinomial weight is the probability of that
4024 // split.
4025 const long nadd = want - running;
4026 std::vector<T> pe(fK[mode - 1], zero);
4027 if (mode - 1 < tp.firingproc.size() && tp.firingproc[mode - 1].D0.rows() ==
4028 static_cast<std::size_t>(fK[mode - 1])) {
4029 mam::Map<T> mp;
4030 mp.D0 = tp.firingproc[mode - 1].D0;
4031 mp.D1 = tp.firingproc[mode - 1].D1;
4032 const std::vector<T> pv = mam::map_pie(mp);
4033 for (std::size_t k = 0; k < fK[mode - 1]; ++k) pe[k] = pv[k];
4034 } else {
4035 pe[0] = one;
4036 }
4037 // Enumerate the splits of nadd over the phases.
4038 std::vector<std::vector<long>> combs;
4039 std::vector<long> cur(fK[mode - 1], 0);
4040 std::function<void(std::size_t, long)> rec = [&](std::size_t k, long left) {
4041 if (k + 1 == fK[mode - 1]) {
4042 cur[k] = left;
4043 combs.push_back(cur);
4044 return;
4045 }
4046 for (long v = left; v >= 0; --v) {
4047 cur[k] = v;
4048 rec(k + 1, left - v);
4049 }
4050 };
4051 rec(0, nadd);
4052 for (std::size_t i = 0; i < combs.size(); ++i) {
4053 std::vector<T> b2 = buf, s2 = srv;
4054 b2[mode - 1] -= num_traits<T>::from_int(nadd);
4055 double logp = std::lgamma(static_cast<double>(nadd) + 1.0);
4056 bool zeroprob = false;
4057 for (std::size_t k = 0; k < fK[mode - 1]; ++k) {
4058 s2[fKs[mode - 1] + k] += num_traits<T>::from_int(combs[i][k]);
4059 const double pk = num_traits<T>::to_double(pe[k]);
4060 if (pk > 0)
4061 logp += combs[i][k] * std::log(pk) -
4062 std::lgamma(static_cast<double>(combs[i][k]) + 1.0);
4063 else if (combs[i][k] > 0)
4064 zeroprob = true;
4065 }
4066 std::vector<T> nr = b2;
4067 nr.insert(nr.end(), s2.begin(), s2.end());
4068 nr.insert(nr.end(), fired.begin(), fired.end());
4069 nr.insert(nr.end(), var.begin(), var.end());
4070 NetState<T> ns = glspace;
4071 ns.local[isf - 1] = nr;
4072 out.space.push_back(ns);
4073 out.rate.push_back(imm);
4074 out.prob.push_back(zeroprob ? zero : num_traits<T>::from_double(std::exp(logp)));
4075 out.completion.push_back(false);
4076 }
4077 return out;
4078 }
4079 // Stop the surplus servers, chosen uniformly across the phases: the
4080 // weight is the multivariate hypergeometric probability of that choice.
4081 const long ndiff = running - want;
4082 std::vector<long> sv(fK[mode - 1], 0);
4083 for (std::size_t k = 0; k < fK[mode - 1]; ++k)
4084 sv[k] = static_cast<long>(num_traits<T>::to_double(srv[fKs[mode - 1] + k]));
4085 std::vector<std::vector<long>> combs;
4086 std::vector<long> cur(fK[mode - 1], 0);
4087 std::function<void(std::size_t, long)> rec = [&](std::size_t k, long left) {
4088 if (k + 1 == fK[mode - 1]) {
4089 if (left > sv[k]) return;
4090 cur[k] = left;
4091 combs.push_back(cur);
4092 return;
4093 }
4094 for (long v = std::min(left, sv[k]); v >= 0; --v) {
4095 cur[k] = v;
4096 rec(k + 1, left - v);
4097 }
4098 };
4099 rec(0, ndiff);
4100 std::vector<double> w(combs.size(), 0.0);
4101 double wmax = -1e300;
4102 for (std::size_t i = 0; i < combs.size(); ++i) {
4103 double lw = 0;
4104 for (std::size_t k = 0; k < fK[mode - 1]; ++k)
4105 lw += std::lgamma(static_cast<double>(sv[k]) + 1.0) -
4106 std::lgamma(static_cast<double>(combs[i][k]) + 1.0) -
4107 std::lgamma(static_cast<double>(sv[k] - combs[i][k]) + 1.0);
4108 w[i] = lw;
4109 wmax = std::max(wmax, lw);
4110 }
4111 double wsum = 0;
4112 for (std::size_t i = 0; i < w.size(); ++i) {
4113 w[i] = std::exp(w[i] - wmax);
4114 wsum += w[i];
4115 }
4116 for (std::size_t i = 0; i < combs.size(); ++i) {
4117 std::vector<T> b2 = buf, s2 = srv;
4118 for (std::size_t k = 0; k < fK[mode - 1]; ++k)
4119 s2[fKs[mode - 1] + k] = num_traits<T>::from_int(sv[k] - combs[i][k]);
4120 b2[mode - 1] += num_traits<T>::from_int(ndiff);
4121 std::vector<T> nr = b2;
4122 nr.insert(nr.end(), s2.begin(), s2.end());
4123 nr.insert(nr.end(), fired.begin(), fired.end());
4124 nr.insert(nr.end(), var.begin(), var.end());
4125 NetState<T> ns = glspace;
4126 ns.local[isf - 1] = nr;
4127 out.space.push_back(ns);
4128 out.rate.push_back(imm);
4129 out.prob.push_back(num_traits<T>::from_double(wsum > 0 ? w[i] / wsum : 0.0));
4130 out.completion.push_back(false);
4131 }
4132 return out;
4133 }
4134
4135 if (gl.active.event != EventType::FIRE) return out;
4136
4137 const bool immediate_mode = mode - 1 < tp.timing.size() &&
4139 const T fw = immediate_mode && mode - 1 < tp.fireweight.size() ? tp.fireweight[mode - 1] : one;
4140 const long en_degree = inhibited ? 0 : std::min(mark_degree, nsrv);
4141 const long imm_servers = immediate_mode ? std::min(mark_degree, nsrv) : 0;
4142
4143 for (std::size_t k = 0; k < fK[mode - 1]; ++k) {
4144 const double in_k = num_traits<T>::to_double(srv[fKs[mode - 1] + k]);
4145 const bool fires = immediate_mode ? (k == 0 && imm_servers >= 1)
4146 : (in_k > 0 && en_degree >= 1);
4147 if (!fires) continue;
4148 T rate = zero;
4149 if (immediate_mode) {
4150 rate = T(imm * fw * num_traits<T>::from_int(imm_servers));
4151 } else {
4152 T d1sum = zero;
4153 if (mode - 1 < tp.firingproc.size())
4154 for (std::size_t j = 0; j < tp.firingproc[mode - 1].D1.cols(); ++j)
4155 d1sum += tp.firingproc[mode - 1].D1(k, j);
4156 rate = T(d1sum * num_traits<T>::from_double(in_k));
4157 // A marking-dependent firing rate g_mode(marking) is exact here,
4158 // because the CTMC evaluates it per enumerated state.
4159 if (mode - 1 < tp.firingdep.size() && tp.firingdep[mode - 1]) {
4160 // the (node, class) marking flattened node-major, MATLAB's ep_space (nnodes x R)
4161 std::vector<T> mk;
4162 for (std::size_t q = 1; q <= sn.nodes.size(); ++q)
4163 for (std::size_t r = 0; r < R; ++r) mk.push_back(ep[q][r]);
4164 rate = T(rate * tp.firingdep[mode - 1](mk));
4165 }
4166 }
4167 if (num_traits<T>::to_double(rate) <= 0) continue;
4168
4169 std::vector<T> b2 = buf, s2 = srv;
4170 if (in_k > 0) {
4171 s2[fKs[mode - 1] + k] -= one; // the firing server leaves execution
4172 b2[mode - 1] += one; // and returns to the idle pool
4173 }
4174 NetState<T> ns = glspace;
4175 std::vector<T> nr = b2;
4176 nr.insert(nr.end(), s2.begin(), s2.end());
4177 nr.insert(nr.end(), fired.begin(), fired.end());
4178 nr.insert(nr.end(), var.begin(), var.end());
4179 ns.local[isf - 1] = nr;
4180
4181 // The arcs fire ATOMICALLY with the mode: PRE consumes from every
4182 // input place and POST produces into every output place, in one
4183 // transition. Splitting them would let the net occupy a state in which
4184 // the tokens have left one place and not arrived at the other.
4185 for (std::size_t j = 0; j < gl.passive.size(); ++j) {
4186 const ModeEvent<T>& pe2 = gl.passive[j];
4187 if (pe2.event != EventType::PRE && pe2.event != EventType::POST) continue;
4188 const std::size_t pisf = sn.stateful_index(pe2.node);
4189 if (pisf == 0) continue;
4190 std::vector<T>& prow = ns.local[pisf - 1];
4191 const double wgt = num_traits<T>::to_double(pe2.weight);
4192 const std::size_t pist = sn.nodes[pe2.node - 1].station;
4193 const SchedStrategy psched =
4194 pist != 0 ? sn.stations[pist - 1].sched : SchedStrategy::INF;
4195 const std::size_t c = pe2.cls;
4196 if (pe2.event == EventType::PRE) {
4197 if (state_detail::buffer_is_class_tag(psched)) {
4198 // An ordered buffer: consume from the head end, matching
4199 // the discipline rather than a count.
4200 long left = static_cast<long>(wgt);
4201 const T tag = num_traits<T>::from_int(static_cast<long>(c));
4202 if (psched == SchedStrategy::LCFS) {
4203 for (std::size_t b = 0; b < prow.size() && left > 0; ++b)
4204 if (prow[b] == tag) { prow[b] = zero; --left; }
4205 } else {
4206 for (std::size_t b = prow.size(); b-- > 0 && left > 0;)
4207 if (prow[b] == tag) { prow[b] = zero; --left; }
4208 }
4209 } else if (prow.size() > R) {
4210 // A Place with a [count | server] split: drain the server
4211 // slot into the count, as the reference does.
4212 const double totc = num_traits<T>::to_double(prow[c - 1]) +
4213 num_traits<T>::to_double(prow[R + c - 1]);
4214 prow[c - 1] = num_traits<T>::from_double(totc - wgt);
4215 prow[R + c - 1] = zero;
4216 } else if (c - 1 < prow.size()) {
4217 prow[c - 1] -= num_traits<T>::from_double(wgt);
4218 }
4219 } else {
4220 if (state_detail::buffer_is_class_tag(psched)) {
4221 for (long q = 0; q < static_cast<long>(wgt); ++q)
4222 prow.insert(prow.begin(), num_traits<T>::from_int(static_cast<long>(c)));
4223 } else if (c - 1 < prow.size()) {
4224 prow[c - 1] += num_traits<T>::from_double(wgt);
4225 }
4226 }
4227 }
4228 out.space.push_back(ns);
4229 out.rate.push_back(rate);
4230 out.prob.push_back(one);
4231 out.completion.push_back(true);
4232 }
4233 return out;
4234}
4235
4236/** One half of a synchronization: an event at a node, in a class. */
4237template <class T>
4239 EventType event = EventType::LOCAL;
4240 std::size_t node = 0; ///< 1-based node index, or `local` for the dummy
4241 std::size_t cls = 0; ///< 1-based class index
4242 T prob = num_traits<T>::from_int(1); ///< routing probability, passive half
4243 /**
4244 * The routing probability is a FUNCTION of the network state, so `prob`
4245 * holds only the state-independent placeholder and the generator must read
4246 * `rt_state(sn, state)(rt_row, rt_col)` instead.
4247 *
4248 * The reference decides this per ACTIVE NODE (`sn.isstatedep(node_a,3)`) and
4249 * then calls whatever `prob` holds, which throws where a node routes one
4250 * class state-dependently and another by probability. Deciding it per
4251 * SYNCHRONIZATION agrees wherever the reference runs at all, and does not
4252 * throw where it would.
4253 */
4254 bool statedep = false;
4255 std::size_t rt_row = 0; ///< (isf-1)*nclasses + (r-1) of the active half
4256 std::size_t rt_col = 0; ///< (jsf-1)*nclasses + (s-1) of this passive half
4257};
4258
4259/**
4260 * One synchronization: an ACTIVE event and the PASSIVE event it drives.
4261 *
4262 * Every transition of the CTMC is one of these. The active half sets the rate;
4263 * the passive half is where the job lands, weighted by the routing probability.
4264 * A LOCAL passive half means the active event moves no job out of its node --
4265 * a phase change, a reneging job leaving the system, a server failing.
4266 */
4267template <class T>
4271
4272/**
4273 * True when a synchronization is an IMMEDIATE-FEEDBACK SELF-LOOP: a departure
4274 * whose passive half is an arrival back at the same station, in a class the
4275 * station holds its server for (`sn.immfeed`, set by
4276 * `Queue.setImmediateFeedback` or `JobClass.setImmediateFeedback`).
4277 *
4278 * The departure half of such a synchronization must run with `no_promote`, so
4279 * the vacated server is not given to a waiting job and the fed-back arrival
4280 * seizes it instead. Every walk of the synchronization list must consult this,
4281 * or it answers a model in which the self-looping job re-queues behind the
4282 * waiting jobs -- the reference's `immfeed_selfloop`.
4283 *
4284 * The class read is the PASSIVE one: after a class switch the job comes back as
4285 * the class it was switched INTO, and `refresh_sync` folds the switch into
4286 * `sn.rt`, so a class-switching self-loop is still ONE synchronization whose
4287 * passive node is its active node.
4288 */
4289template <class T>
4291 if (sy.active.event != EventType::DEP || sy.passive.node != sy.active.node) return false;
4292 if (sy.active.node == 0 || sy.active.node > sn.nodes.size()) return false;
4293 const std::size_t ist = sn.nodes[sy.active.node - 1].station;
4294 if (ist == 0) return false;
4295 const std::size_t cls_p = sy.passive.cls;
4296 if (ist > sn.immfeed.size() || cls_p == 0 || cls_p > sn.immfeed[ist - 1].size()) return false;
4297 return sn.immfeed[ist - 1][cls_p - 1];
4298}
4299
4300/**
4301 * Port of `MNetwork.refreshSync`: the synchronization list.
4302 *
4303 * The ORDER matters as much as the content: the generator adds rates in this
4304 * order, and while addition is commutative in exact arithmetic it is not in
4305 * floating point, so a reordered list perturbs the last digits of every
4306 * reported metric.
4307 *
4308 * @param impatience_classes (station x class) true where reneging is declared
4309 * @param breakdown_nodes 1-based node indices with a server breakdown
4310 * @param sn the refreshed network struct
4311 */
4312template <class T>
4313std::vector<Sync<T>> refresh_sync(
4314 const NetworkStruct<T>& sn,
4315 const std::vector<std::vector<bool>>& impatience_classes = std::vector<std::vector<bool>>(),
4316 const std::vector<std::size_t>& breakdown_nodes = std::vector<std::size_t>()) {
4317 const std::size_t R = sn.nclasses;
4318 const std::size_t local = sn.nodes.size() + 1; // the dummy passive node
4319 const T one = num_traits<T>::from_int(1);
4320 std::vector<Sync<T>> sync;
4321
4322 for (std::size_t ind = 1; ind <= sn.nodes.size(); ++ind) {
4323 const NodeDef& nd = sn.nodes[ind - 1];
4324 const std::size_t ist = nd.station;
4325 for (std::size_t r = 1; r <= R; ++r) {
4326 // A phase-change action exists only for a multi-phase service:
4327 // with one phase there is no internal transition to make.
4328 if (ist != 0 && sn.phases_of(ist, r) > 1) {
4329 Sync<T> s;
4330 s.active = SyncEvent<T>{EventType::PHASE, ind, r, one};
4331 s.passive = SyncEvent<T>{EventType::LOCAL, local, r, one};
4332 sync.push_back(s);
4333 }
4334 // The struct's own reneging declaration emits the action too, so a caller that
4335 // passes no `impatience_classes` no longer drops every RENEGE transition.
4336 if (ist != 0 && ((impatience_classes.size() >= ist &&
4337 impatience_classes[ist - 1].size() >= r &&
4338 impatience_classes[ist - 1][r - 1]) ||
4340 Sync<T> s;
4341 s.active = SyncEvent<T>{EventType::RENEGE, ind, r, one};
4342 s.passive = SyncEvent<T>{EventType::LOCAL, local, r, one};
4343 sync.push_back(s);
4344 }
4345 if (ist != 0) {
4346 const typename std::map<std::size_t, RetrialParam<T>>::const_iterator rit =
4347 sn.retrialparam.find(ist);
4348 if (rit != sn.retrialparam.end() && rit->second.retrial_proc.size() >= r &&
4349 !rit->second.retrial_proc[r - 1].disabled) {
4350 Sync<T> s;
4351 s.active = SyncEvent<T>{EventType::RETRY, ind, r, one};
4352 s.passive = SyncEvent<T>{EventType::LOCAL, local, r, one};
4353 sync.push_back(s);
4354 }
4355 }
4356 // Failure and repair are properties of the SERVER, not of a class,
4357 // so exactly one pair is emitted per station rather than one per
4358 // class -- hence the r == 1 guard.
4359 if (ist != 0 && r == 1) {
4360 bool has_bd = sn.has_breakdown_node(ind);
4361 for (std::size_t b = 0; b < breakdown_nodes.size() && !has_bd; ++b)
4362 if (breakdown_nodes[b] == ind) { has_bd = true; break; }
4363 if (has_bd) {
4364 Sync<T> f, rp;
4365 f.active = SyncEvent<T>{EventType::FAILURE, ind, r, one};
4366 f.passive = SyncEvent<T>{EventType::LOCAL, local, r, one};
4367 sync.push_back(f);
4368 rp.active = SyncEvent<T>{EventType::REPAIR, ind, r, one};
4369 rp.passive = SyncEvent<T>{EventType::LOCAL, local, r, one};
4370 sync.push_back(rp);
4371 }
4372 }
4373 // A polling station needs a SWITCH action per buffer whose
4374 // entering switchover is a real (non-immediate) walk.
4375 if (ist != 0 && sn.stations[ist - 1].sched == SchedStrategy::POLLING) {
4376 const PollingInfo<T> pinfo = polling_info(sn, ind);
4377 if (pinfo.valid && pinfo.has_sw[r - 1]) {
4378 Sync<T> s2;
4379 s2.active = SyncEvent<T>{EventType::SWITCH, ind, r, one};
4380 s2.passive = SyncEvent<T>{EventType::LOCAL, local, r, one};
4381 sync.push_back(s2);
4382 }
4383 }
4384 if (!nd.stateful) continue;
4385 // A stateful Fork emits no departure sync: the atomic multi-branch
4386 // emission is a fork firing synchronization instead.
4387 if (nd.nodetype == NodeType::Fork) continue;
4388
4389 // A CACHE READ IS ITS OWN ACTION, not a routing decision. The read
4390 // consults the contents, rewrites them and switches the job into the
4391 // hit or the miss class, so it moves no job between nodes and its
4392 // passive half is the dummy.
4393 //
4394 // THE READ CLASS THEREFORE EMITS NO DEPARTURE HERE. `refresh_routing`
4395 // resolves its unresolved cache split to a uniform half-half so the
4396 // VISIT equations have a number; the reference leaves the same two
4397 // entries NaN, and `ceil(NaN) > 0` is false, so no departure sync is
4398 // built from them. Reproducing the half-half as a synchronization
4399 // would make the sample path decide hit against miss by a coin
4400 // instead of by reading the cache, which is what it did.
4401 bool cache_read_class = false;
4402 if (nd.nodetype == NodeType::Cache) {
4403 const typename std::map<std::size_t, CacheParam<T>>::const_iterator ci =
4404 sn.nodeparam.find(ind);
4405 if (ci != sn.nodeparam.end()) {
4406 if (r - 1 < ci->second.pread.size() && !ci->second.pread[r - 1].empty()) {
4407 Sync<T> s;
4408 s.active = SyncEvent<T>{EventType::READ, ind, r, one};
4409 s.passive = SyncEvent<T>{EventType::READ, local, r, one};
4410 sync.push_back(s);
4411 }
4412 cache_read_class =
4413 r - 1 < ci->second.hitclass.size() && ci->second.hitclass[r - 1] != 0;
4414 }
4415 }
4416 // A stateful Transition emits one server phase-change action per
4417 // MODE, not per class (the JAR gates the same way on the first
4418 // class); its cls slot carries the mode, as `after_event_transition`
4419 // reads it.
4420 if (nd.nodetype == NodeType::Transition && r == 1) {
4421 const typename std::map<std::size_t, TransitionParam<T>>::const_iterator ti =
4422 sn.transparam.find(ind);
4423 if (ti != sn.transparam.end()) {
4424 for (std::size_t m = 1; m <= ti->second.nmodes; ++m) {
4425 Sync<T> s;
4426 s.active = SyncEvent<T>{EventType::PHASE, ind, m, one};
4427 s.passive = SyncEvent<T>{EventType::LOCAL, local, m, one};
4428 sync.push_back(s);
4429 }
4430 }
4431 }
4432 if (cache_read_class) continue;
4433
4434 const std::size_t isf = sn.stateful_index(ind);
4435 for (std::size_t jnd = 1; jnd <= sn.nodes.size(); ++jnd) {
4436 if (!sn.nodes[jnd - 1].stateful) continue;
4437 const std::size_t jsf = sn.stateful_index(jnd);
4438 for (std::size_t s = 1; s <= R; ++s) {
4439 const T p = sn.rt((isf - 1) * R + (r - 1), (jsf - 1) * R + (s - 1));
4440 if (num_traits<T>::to_double(p) <= 0) continue;
4441 Sync<T> ns;
4442 ns.active = SyncEvent<T>{EventType::DEP, ind, r, one};
4443 ns.passive = SyncEvent<T>{EventType::ARV, jnd, s, p};
4444 // SDR reaches `rt` as the uniform placeholder `refresh_routing`
4445 // writes, so the SUPPORT of the mask is right and the values
4446 // are not: the pair exists exactly where a link does, and the
4447 // generator replaces the probability state by state. This is
4448 // the reference's `rtmask = rtfun(emptystate, emptystate)`,
4449 // which likewise keeps every connected pair. JSQ and SQ(d)
4450 // likewise, keyed on the departing class r: their rows
4451 // never switch class, so r and s agree wherever p > 0.
4452 const RoutingStrategy rsr =
4453 nd.routing.size() >= r ? nd.routing[r - 1] : RoutingStrategy::PROB;
4454 if ((nd.routing.size() >= s && nd.routing[s - 1] == RoutingStrategy::SDR) ||
4455 rsr == RoutingStrategy::JSQ || rsr == RoutingStrategy::SQ) {
4456 ns.passive.statedep = true;
4457 ns.passive.rt_row = (isf - 1) * R + (r - 1);
4458 ns.passive.rt_col = (jsf - 1) * R + (s - 1);
4459 }
4460 sync.push_back(ns);
4461 }
4462 }
4463 }
4464 }
4465 return sync;
4466}
4467
4468/**
4469 * Port of `State.afterFJEvent`: fire ONE entry of the fork firing list.
4470 *
4471 * A fork firing is atomic across several nodes -- it consumes the parent at the
4472 * fork and places one sibling at each branch head in the same instant -- so
4473 * unlike every ordinary transition it cannot be decomposed into an active half
4474 * and a passive half. It therefore takes the whole network state, exactly as an
4475 * SPN global synchronization does.
4476 *
4477 * THE TWO ENABLING CONDITIONS.
4478 *
4479 * 1. The fork holds at least one class-r parent.
4480 *
4481 * 2. This entry's tag is the LOWEST FREE tag for this (fork, class). A tag is
4482 * free when its auxiliary classes have zero occupancy NETWORK-WIDE, which is
4483 * why the test scans every stateful node and not just the branches: a
4484 * sibling in transit is still outstanding. Without the canonical choice
4485 * every firing would produce one successor per free tag, all of them
4486 * relabellings of each other, and the chain would carry a factorial number
4487 * of duplicate states.
4488 *
4489 * The emission is applied SEQUENTIALLY over a growing outcome list rather than
4490 * branch-by-branch into one state, because that is what handles the three cases
4491 * a single pass would get wrong: two branches sharing a head node, `weight > 1`
4492 * repeated emissions on one branch, and a non-exponential sibling service whose
4493 * phase-entry mixture makes one arrival into several outcomes.
4494 */
4495template <class T>
4497 const NetState<T>& gl) {
4498 const std::size_t R = sn.nclasses;
4499 GlobalOutcome<T> out;
4500 const std::size_t isf_f = sn.stateful_index(e.fork);
4501 if (isf_f == 0) return out;
4502 const std::vector<T>& fs = gl.local[isf_f - 1];
4503 if (fs.size() < R) return out;
4504 if (num_traits<T>::to_double(fs[fs.size() - R + e.cls - 1]) < 1) return out;
4505
4506 // Tag occupancy, network-wide.
4507 const std::size_t B = e.auxall.size();
4508 if (B == 0 || e.tag == 0 || e.tag > e.auxall[0].size()) return out;
4509 const std::size_t Tt = e.auxall[0].size();
4510 std::vector<double> nglobal(R, 0.0);
4511 for (std::size_t isf = 1; isf <= sn.stateful_nodes.size(); ++isf) {
4512 const std::pair<T, std::vector<T>> mg =
4513 to_marginal_aggr(sn, sn.stateful_nodes[isf - 1], gl.local[isf - 1]);
4514 for (std::size_t r = 0; r < R; ++r) {
4515 const double v = num_traits<T>::to_double(mg.second[r]);
4516 // A Source encodes its reservoir as an infinite marginal; adding it
4517 // would make every tag look occupied. An auxiliary class is never
4518 // generated by a Source, so skipping the non-finite entries cannot
4519 // hide a real sibling.
4520 if (std::isfinite(v)) nglobal[r] += v;
4521 }
4522 }
4523 std::vector<double> occ(Tt, 0.0);
4524 for (std::size_t t = 0; t < Tt; ++t)
4525 for (std::size_t b = 0; b < B; ++b) occ[t] += nglobal[e.auxall[b][t] - 1];
4526 if (occ[e.tag - 1] > 0) return out; // this tag is in use
4527 for (std::size_t t = 0; t + 1 < e.tag; ++t)
4528 if (occ[t] == 0) return out; // a lower tag is free
4529
4530 NetState<T> seed = gl;
4531 seed.local[isf_f - 1][seed.local[isf_f - 1].size() - R + e.cls - 1] -=
4533
4534 std::vector<NetState<T>> partials(1, seed);
4535 std::vector<T> partprob(1, num_traits<T>::from_int(1));
4536 // The emission list, one entry per sibling. `weightlink` is filled only when
4537 // the fork sends different counts down different links; the interleave below
4538 // reproduces `repmat(1:B,1,w)` exactly in the uniform case, so a plain fork
4539 // walks the order it always did.
4540 std::vector<std::size_t> emissions;
4541 if (e.weightlink.empty()) {
4542 const std::size_t w = e.weight == 0 ? 1 : e.weight;
4543 for (std::size_t rep = 0; rep < w; ++rep)
4544 for (std::size_t b = 0; b < B; ++b) emissions.push_back(b);
4545 } else {
4546 std::size_t wmax = 0;
4547 for (std::size_t b = 0; b < e.weightlink.size(); ++b)
4548 if (e.weightlink[b] > wmax) wmax = e.weightlink[b];
4549 for (std::size_t rep = 1; rep <= wmax; ++rep)
4550 for (std::size_t b = 0; b < B; ++b)
4551 if (b < e.weightlink.size() && e.weightlink[b] >= rep) emissions.push_back(b);
4552 }
4553 for (std::size_t ei = 0; ei < emissions.size(); ++ei) {
4554 const std::size_t b = emissions[ei];
4555 const std::size_t bh = e.branchheads[b];
4556 const std::size_t isf_b = sn.stateful_index(bh);
4557 if (isf_b == 0) return GlobalOutcome<T>();
4558 const std::size_t a = e.auxclasses[b];
4559 std::vector<NetState<T>> nextp;
4560 std::vector<T> nextq;
4561 for (std::size_t pp = 0; pp < partials.size(); ++pp) {
4562 const EventOutcome<T> arv =
4563 after_event(sn, bh, partials[pp].local[isf_b - 1], EventType::ARV, a);
4564 if (arv.space.empty()) return GlobalOutcome<T>(); // blocked: no firing
4565 for (std::size_t io = 0; io < arv.space.size(); ++io) {
4566 NetState<T> ns = partials[pp];
4567 ns.local[isf_b - 1] = arv.space[io];
4568 nextp.push_back(ns);
4569 nextq.push_back(io < arv.prob.size() ? T(partprob[pp] * arv.prob[io])
4570 : partprob[pp]);
4571 }
4572 }
4573 partials.swap(nextp);
4574 partprob.swap(nextq);
4575 }
4576
4577 out.space = partials;
4578 for (std::size_t i = 0; i < partials.size(); ++i) {
4580 out.prob.push_back(T(partprob[i] * e.prob));
4581 out.completion.push_back(true);
4582 }
4583 return out;
4584}
4585
4586} // namespace qn
4587} // namespace line
4588
4589#endif // LINE_LANG_QN_STATE_EVENTS_H
Base error for the multiprecision C++ port.
Definition error.h:73
InputError(const std::string &what)
Definition error.h:105
std::size_t cols() const
Definition matrix.h:90
std::size_t rows() const
Definition matrix.h:89
UnsupportedError(const std::string &what)
Definition error.h:119
A network plus its refreshed NetworkStruct.
The exception types the port throws.
Enumerations and the minimal distribution descriptor shared by the model layer of the C++ port.
Markovian arrival process descriptors: stationary vectors, rate, moments, autocorrelation and the ind...
std::string sn_patience_exp_refusal(const qn::NetworkStruct< T > &sn, std::size_t ist, std::size_t r)
Port of sn_patience_exp_refusal.m: the by-name refusal of a reneging patience that is not EXPONENTIAL...
SchedStrategy
Scheduling disciplines, with the values of MATLAB SchedStrategy.
Definition lang_types.h:185
DropStrategy
Blocking and loss rules, with the values of MATLAB DropStrategy.
Definition lang_types.h:431
@ IMMEDIATE
fires with zero delay, resolved by weight and priority
Definition lang_types.h:370
@ REPLY
completes a synchronous call, releasing a held server
Definition lang_types.h:172
@ CATASTROPHE
removes EVERY job at the station
Definition lang_types.h:174
RoutingStrategy
Routing strategies, with the values of MATLAB RoutingStrategy.
Definition lang_types.h:396
RemovalPolicy
Which job a negative signal removes, with the values of MATLAB RemovalPolicy.
Definition lang_types.h:178
@ FCFS
the oldest waiting job; servers only once nobody waits
Definition lang_types.h:180
@ LCFS
the newest waiting job; servers only once nobody waits
Definition lang_types.h:181
@ RANDOM
uniform over waiting AND in-service jobs
Definition lang_types.h:179
EventType
The events a state can undergo, with the values of MATLAB EventType.
Definition lang_types.h:115
@ KLIMITED
serve at most K per visit (K in pollingPar)
Definition lang_types.h:380
@ EXHAUSTIVE
serve until the queue empties
Definition lang_types.h:379
@ GATED
serve exactly the jobs present at the polling instant
Definition lang_types.h:378
@ DECREMENTING
serve until the queue is one shorter than at arrival
Definition lang_types.h:381
const char * sched_to_text(SchedStrategy s)
Definition lang_types.h:235
std::function< std::vector< T >(const std::vector< T > &)> CdScaling
A class-dependent scaling map, sn.cdscaling.
Definition lang_types.h:736
const char * event_to_text(EventType e)
Definition lang_types.h:141
@ QLRU
q-LRU: LRU with probabilistic admission on a miss
Definition lang_types.h:392
@ FIFO
first in, first out
Definition lang_types.h:387
std::vector< T > map_pie(const Map< T > &m)
Phase distribution seen by an arriving job, pie = pi D1 / (pi D1 e).
Definition map_moment.h:89
std::vector< PoolStart< T > > pool_serve_next(const NetworkStruct< T > &sn, const CtmcPool< T > &pool, SchedStrategy sched, const std::vector< std::size_t > &Ks, const std::vector< T > &buf, const std::vector< T > &srv, std::size_t t)
The freed server of pool t takes the next compatible waiting job, in the discipline's order.
void pool_start(const CtmcPool< T > &pool, const std::vector< std::size_t > &Ks, const std::vector< T > &buf, const std::vector< T > &srv, std::size_t s, std::size_t t, const T &w, std::vector< PoolStart< T > > &out)
Class s starts service on pool t in every entry phase of the pool's block.
std::string state_impatience_unsupported(const NetworkStruct< T > &sn, const std::string &solver)
Port of solver_ctmc_state_supports.m: the impatience laws the state machinery cannot serve,...
std::vector< T > entry_phase_dist(const NetworkStruct< T > &sn, std::size_t ist, std::size_t cls)
The entry-phase distribution pie{ist}{class}: which phase a service STARTS in.
long polling_budget(const PollingInfo< T > &pi, long nbufq)
Port of State.pollingBudget: how many services this visit may perform.
EventOutcome< T > after_event_join(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls)
Port of State.afterEventJoin: an event at a Join node of an FJ-augmented struct.
EventOutcome< T > after_event_station_pas(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls)
Defined below; the ARV and DEP branches divert to it before any slicing.
void tag_last(EventOutcome< T > &out, std::size_t start_cls, std::size_t preempt_cls)
Tag the successor row just appended to OUT: START_CLS begins service on it and PREEMPT_CLS is displac...
void cache_retrieval_class_map(const CacheParam< T > &cp, std::vector< std::size_t > &rc_list, std::vector< std::size_t > &rc_items, std::vector< std::size_t > &rc_orig)
Port of State.cacheRetrievalClassMap: the canonical order of a cache's retrieval classes,...
std::pair< std::vector< std::size_t >, std::vector< T > > signal_batch_pmf(const NetworkStruct< T > &sn, std::size_t cls, std::size_t ntot)
Port of State.signalBatchPMF: the batch size a negative signal removes.
ReplyBlockInfo reply_block_info(const NetworkStruct< T > &sn, std::size_t ind)
Defined below; the departure branch records a server held for a reply.
Marginal< T > to_marginal(const NetworkStruct< T > &sn, std::size_t ist, const std::vector< T > &state_i, const std::vector< std::size_t > &phasesz, const std::vector< std::size_t > &phaseshift, std::size_t nvar=0)
Port of State.toMarginal for a STATION, one state row at a time.
Definition state.h:131
void polling_get(const PollingInfo< T > &pi, const std::vector< T > &var, std::size_t srvclass, std::size_t &pos, std::size_t &swk, long &ctr)
Defined below; the polling branches of ARV, DEP and SWITCH use these.
EventOutcome< T > after_event_station_switch(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls)
Port of the SWITCH branch: a polling server advances its switchover timer.
void rr_advance_row(const NetworkStruct< T > &sn, std::size_t ind, std::size_t cls, std::vector< std::vector< T > > &rows)
Port of State.afterEventStation's dispatch: the successors of one event at one station.
void polling_next(const PollingInfo< T > &pi, std::size_t pos, const std::vector< long > &nbuf, std::size_t R, bool arrived, std::size_t &q, int &mode, long &budget)
Port of State.pollingNext: where the server goes from buffer pos.
bool immfeed_self_loop(const NetworkStruct< T > &sn, const Sync< T > &sy)
True when a synchronization is an IMMEDIATE-FEEDBACK SELF-LOOP: a departure whose passive half is an ...
T station_renege_mu(const NetworkStruct< T > &sn, std::size_t ist, std::size_t cls)
sn.impatienceMu(ist,cls): the rate of an exponential reneging patience, 0 when the class declares non...
std::vector< T > polling_set(const PollingInfo< T > &pi, std::vector< T > var, std::size_t pos, std::size_t swk, long ctr)
Write (pos, swk, ctr) back into the local-variable block.
GlobalOutcome< T > after_global_event(const NetworkStruct< T > &sn, const NetState< T > &glspace, const GlobalSync< T > &gl)
Port of State.afterGlobalEvent: an SPN mode ENABLEs or FIREs.
EventOutcome< T > after_event_station_reply(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls)
Port of State.afterEventStationReply: a REPLY signal completes a synchronous call at the station hold...
EventOutcome< T > after_event_station_arv(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls)
Port of the ARV branch of State.afterEventStation: an arriving class-cls job joins node ind,...
EventOutcome< T > after_event_station_renege(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls, const T &impatience_mu)
Port of the RENEGE branch: a WAITING class-cls job abandons the queue.
EventOutcome< T > after_event_cache(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls)
Port of State.afterEventCache: events at a Cache node.
EventOutcome< T > after_event_station_signal(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls)
Port of State.afterEventStationSignal: a G-network signal arrives.
T station_retrial_mu(const NetworkStruct< T > &sn, std::size_t ist, std::size_t cls)
sn.retrialMu(ist,cls): the rate of the exponential retrial delay, falling back to the scalar retrial_...
bool is_physical_capacity(const NetworkStruct< T > &sn, std::size_t ist, std::size_t cls)
Port of State.isPhysicalCapacity: true when the bound at (ist, class) is a PHYSICAL capacity rather t...
PrioPop< T > prio_pop(const NetworkStruct< T > &sn, std::size_t ist, const Marginal< T > &m, std::size_t cls, double ni, double S)
Compute the *PRIO effective population; a no-op for every other discipline.
T cd_factor(const NetworkStruct< T > &sn, std::size_t ist, const std::vector< T > &nir, std::size_t cls)
Port of State.cdclassfactor: the class-dependence multiplier of a class-cls rate at the per-class pop...
EventOutcome< T > after_event_station_phase(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls)
Port of the PHASE branch of State.afterEventStation: service advances a phase WITHOUT completing.
std::pair< std::vector< T >, std::vector< T > > phase_rates(const NetworkStruct< T > &sn, std::size_t ist, std::size_t cls)
sn.mu and sn.phi for one (station, class), derived as MATLAB's Markovian.getMu / getPhi derive them f...
EventOutcome< T > after_event_transition(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t mode)
Port of State.afterEventTransition, the PHASE arm: one running server of the given mode advances its ...
EventOutcome< T > after_event_router(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls)
Port of State.afterEventRouter: a Router holds a job for the instant it takes to decide where it goes...
T lld_factor(const NetworkStruct< T > &sn, std::size_t ist, double n)
The limited-load-dependent multiplier at population n, 1 when unset.
void pad_tags(EventOutcome< T > &out)
Bring the tag vectors up to one entry per successor, so a caller can index them exactly like space.
void pas_tag_started(EventOutcome< T > &out, const F &mu_fun, const std::vector< std::size_t > &cold, const std::vector< std::size_t > &cnew)
Tag the successor just appended to OUT with the PAS positions that started service on it: those of CN...
std::vector< Sync< T > > refresh_sync(const NetworkStruct< T > &sn, const std::vector< std::vector< bool > > &impatience_classes=std::vector< std::vector< bool > >(), const std::vector< std::size_t > &breakdown_nodes=std::vector< std::size_t >())
Port of MNetwork.refreshSync: the synchronization list.
EventOutcome< T > after_event(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls, bool no_promote=false, const T &aux_rate=num_traits< T >::from_int(0))
Port of State.afterEvent: the successors of one event at one NODE.
std::pair< std::vector< std::size_t >, std::size_t > pass_and_swap(const std::vector< std::size_t > &c, std::size_t p, const std::vector< std::vector< bool > > &G)
Port of State.passAndSwap: the transition a service completion triggers at a pass-and-swap station (D...
std::pair< T, std::vector< T > > to_marginal_aggr(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &state_i)
Port of State.toMarginalAggr: the job counts of one node's state row, without the per-phase detail to...
EventOutcome< T > after_event_fork(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls)
Port of State.afterEventFork: an event at a STATEFUL Fork node.
EventOutcome< T > after_event_station(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls, bool no_promote=false, const T &aux_rate=num_traits< T >::from_int(0))
std::vector< GlobalSync< T > > refresh_global_sync(const NetworkStruct< T > &sn)
Port of MNetwork.refreshGlobalSync: the ENABLE and FIRE synchronizations.
EventOutcome< T > after_event_station_pool(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, EventType event, std::size_t cls)
Port of State.afterEventStationPool: ARV, DEP and PHASE at a station whose heterogeneous server pools...
std::vector< double > pas_increments(const F &mu_fun, const std::vector< std::size_t > &c)
Per-position service rate increments Delta_mu(c1..cp) = mu(c1..cp) - mu(c1..c_{p-1}...
T service_share(const NetworkStruct< T > &sn, std::size_t ist, const Marginal< T > &m, std::size_t cls, double ni, double S)
Defined below; DEP and PHASE must share one definition of the share.
void apply_station_balking(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls, EventOutcome< T > &out)
Port of the QUEUE_LENGTH balking branch of the ARV event: with the probability of the threshold band ...
GlobalOutcome< T > after_fj_event(const NetworkStruct< T > &sn, const FjSync< T > &e, const NetState< T > &gl)
Port of State.afterFJEvent: fire ONE entry of the fork firing list.
bool station_has_reneging(const NetworkStruct< T > &sn, std::size_t ist)
True when station ist declares exponential reneging for some class.
RowLayout< T > row_layout(const NetworkStruct< T > &sn, std::size_t ind, std::size_t width)
EventOutcome< T > after_event_station_dep(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls, bool no_promote=false)
Port of the DEP branch of State.afterEventStation: a class-cls job completes service at station ind.
bool station_retrial_constant(const NetworkStruct< T > &sn, std::size_t ist, std::size_t cls)
sn.retrialPolicy(ist,cls) == CONSTANT: one retry clock for the whole orbit.
PollingInfo< T > polling_info(const NetworkStruct< T > &sn, std::size_t ind)
EventOutcome< T > after_event_station_breakdown(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, bool up, const T &mu)
Port of the FAILURE and REPAIR branches: the server goes down, or comes back.
bool arrival_is_lost(const NetworkStruct< T > &sn, std::size_t ist, std::size_t cls)
Port of State.arrivalIsLost: true when an arrival that finds no room is LOST, false when it must BLOC...
EventOutcome< T > after_event_station_retry(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &inspace, std::size_t cls, const T &retrial_mu, bool constant_policy=false)
Port of the RETRY branch: an ORBITING class-cls job retries entry.
void polling_land(const NetworkStruct< T > &sn, std::size_t ist, const PollingInfo< T > &pi, std::size_t q, int mode, long budget, const std::vector< T > &buf, const std::vector< T > &srv, const std::vector< T > &var, const RowLayout< T > &L, std::vector< std::vector< T > > &rows, std::vector< T > &probs)
Port of State.pollingLand: the states the walk lands in, with weights.
double reply_blocked(const NetworkStruct< T > &sn, std::size_t ind, const std::vector< T > &var)
Defined below; the reply block subtracts held servers in the ARV branch.
Conservation laws of a layered queueing network, enumerated from its structure.
Definition aoi_dist2ph.h:52
A queueing network and its refreshed NetworkStruct.
State.pollingInfo and the controller description it returns.
Port of matlab/src/api/sn/sn_patience_handles.m.
Port of the MATLAB +State package: the encoding that turns a station's state row into marginal job co...
The <kind> part of a LINE:<category>:<kind> identifier (see _kb/17-error-vocabulary....
Definition error.h:37
Matrix< T > D0
The (D0,D1) pair when the type carries one directly.
Definition lang_types.h:863
std::vector< Matrix< T > > Dmark
MMAP per-class D1 blocks / BMAP per-batch-size blocks; empty otherwise.
Definition lang_types.h:873
static constexpr double Immediate
Rate of an Immediate distribution; its mean is 1/Immediate = 1e-8.
Definition lang_types.h:771
A MAP as the pair of matrices (D0, D1).
Definition map_moment.h:53
Matrix< T > D1
Definition map_moment.h:55
Matrix< T > D0
Definition map_moment.h:54
Server breakdown and repair of a station whose server fails and is repaired.
T failure_rate
sn.breakdownMu: 1 / mean failure time
T repair_rate
sn.repairMu: 1 / mean repair time
The parameters of a Cache node, MATLAB's sn.nodeparam{ind} for a Cache.
int retrieval_capacity
Delayed-hit retrieval system (Cache.setRetrievalSystem).
T qlru
q-LRU admission probability; 1 admits every miss (plain LRU).
std::vector< std::vector< Matrix< T > > > accost
(u) x (n) of (h+1)x(h+1), or empty
long max_pending_retrieval
Truncation level of block B: how many secondary requests may be merged onto the in-flight fetches of ...
std::vector< std::vector< std::size_t > > retrieval_classes
(nitems x nclasses), 1-based
std::vector< int > itemcap
std::vector< std::size_t > missclass
std::vector< std::size_t > hitclass
lang::ReplacementStrategy replacestrat
std::vector< std::vector< T > > pread
(u) x (n), empty row = NaN
CTMC pair form of a MAP service at an FCFS station, written by ctmc::ctmc_mapc on the solver's privat...
Matrix< T > V
landing law (-D0)^-1 D1
std::size_t p
phases of the original MAP
std::vector< std::pair< std::size_t, std::size_t > > pairs
0-based (i,j), i-major, V(i,j) > 0
bool single
c = 1: carried phase, no pairs
CTMC bookkeeping of a heterogeneous-server station, written by ctmc::ctmc_pools on the solver's priva...
std::vector< std::vector< std::size_t > > len
offset and length of block k of class r
std::vector< std::vector< std::vector< T > > > alpha
entry vector of block k of class r
std::vector< std::vector< std::vector< T > > > exit
exit rates of block k of class r
std::vector< std::vector< bool > > compat
compat[t-1][r-1]
std::vector< double > count
servers per pool
std::vector< std::size_t > alfsorder
pools by ascending class count (ALFS)
std::vector< std::vector< Matrix< T > > > D0
D0 of block k of class r.
std::vector< std::vector< std::size_t > > pools
pools[r-1]: compatible pools of r, ascending
lang::HeteroSchedPolicy policy
bool rotate
ALIS/FAIRNESS order is part of the state.
std::vector< std::vector< std::size_t > > off
std::size_t perm_index(const std::vector< std::size_t > &order) const
1-based index of order in perms, 0 when absent.
std::vector< std::vector< double > > fsfrate
fsfrate[t-1][r-1] = 1/mean (FSF)
std::vector< std::vector< std::size_t > > perms
every pool order, identity first
What one event produces at one node: the successor rows, their rates and their probabilities,...
std::vector< T > prob
per-row probability of the choice
std::vector< std::vector< T > > space
successor local state rows
std::vector< T > rate
per-row rate, -1 on a passive half
std::vector< std::vector< std::size_t > > start
START annotation: the 1-based classes that BEGIN or RESUME holding a server on each successor row.
std::vector< std::vector< std::size_t > > preempt
PREEMPT annotation: the 1-based classes pushed back into the buffer.
sn.nodeparam{j}.fj: what a Join node needs to fire on identity.
std::vector< std::size_t > origclasses
std::map< std::size_t, std::vector< std::vector< std::size_t > > > auxmatrix
std::map< std::size_t, std::vector< std::size_t > > required
One fork firing synchronization: sn.fjsync{k}.
std::size_t fork
1-based Fork node
std::vector< std::size_t > weightlink
Per-branch tasksPerLink, EMPTY when every branch carries weight.
std::size_t weight
tasksPerLink: siblings emitted per branch
std::vector< std::size_t > branchheads
1-based node per branch
std::size_t cls
1-based ORIGINAL class being forked
std::vector< std::vector< std::size_t > > auxall
(B x T) every auxiliary class of this (fork, class), for the tag scan.
std::vector< std::size_t > auxclasses
the tag's auxiliary class per branch
std::size_t tag
1-based tag this entry allocates
static constexpr double Immediate
Rate of an Immediate distribution; its mean is 1/Immediate = 1e-8.
Definition lang_types.h:771
static constexpr double MaxInt
Stand-in for an unbounded COUNT, MATLAB GlobalConstants.MaxInt.
Definition lang_types.h:776
What one global event produces: a whole network state per outcome.
std::vector< T > rate
std::vector< NetState< T > > space
std::vector< T > prob
std::vector< bool > completion
True where the outcome is a firing COMPLETION, i.e.
A GLOBAL synchronization: an SPN mode event and the place arcs it drives.
ModeEvent< T > active
std::vector< ModeEvent< T > > passive
What State.toMarginal returns for one station and one state row.
Definition state.h:52
std::vector< std::vector< T > > kir
jobs in service per class and phase
Definition state.h:56
std::vector< T > nir
jobs per class
Definition state.h:54
std::vector< T > sir
jobs in service per class
Definition state.h:55
One half of a GLOBAL synchronization: a mode event at a node.
std::size_t mode
1-based mode index
std::size_t node
1-based node index (a Transition, or a place)
T weight
arc multiplicity
std::size_t cls
1-based class the arc moves
One network state: the per-stateful-node local rows it is composed of.
Definition state.h:2734
std::vector< std::vector< T > > local
local[isf] is that node's state row
Definition state.h:2735
A node of the network.
std::vector< RoutingStrategy > routing
sn.routing, per class.
Port of State.pollingInfo: the derived description of a polling controller.
std::vector< bool > has_sw
std::vector< std::size_t > ksw
std::vector< std::vector< T > > sw_pie
std::vector< Matrix< T > > sw_d0
std::vector< Matrix< T > > sw_d1
std::vector< bool > polled
lang::PollingType ptype
The population the *PRIO disciplines actually share the server among.
std::vector< T > nir
nirprio when masked, the plain marginal otherwise
bool served
false when cls is not in the most urgent group
double ni
niprio when masked, the plain total otherwise
bool masked
whether the saturated-station mask was applied
Where node ind keeps its reply-block counters inside the local vars.
std::vector< std::size_t > slot
slot[r-1] = 0-based column, or npos
std::vector< std::size_t > classes
1-based calling classes holding a block
The parameters of a retrial station: MATLAB sn.retrialProc and friends.
std::vector< int > max_attempts
0 = unbounded
std::vector< T > retrial_rate
mu_r, the per-class orbit retry rate
std::vector< lang::Distrib< T > > retrial_proc
retrial_proc[r] is the class-r retrial process; empty = not a retrial class.
How a station's state row splits into [buffer | server | local vars].
std::size_t srvw
total server width
std::size_t bufw
buffer width, the only discipline-dependent part
std::vector< std::size_t > Ks
offset of class r's phase block
std::size_t nvar
local-variable width
std::vector< std::size_t > K
phases per class
One balking threshold: with min_jobs <= n <= max_jobs at the station, an arriving job of the class re...
One station of the network.
std::vector< Distrib< T > > orbit_impatience
Queue.setOrbitImpatience(class, dist): abandonment from the RETRIAL ORBIT, which is a different popul...
std::vector< BalkingParam > balking
std::vector< Distrib< T > > patience
Queue.setPatience(class, dist): the abandonment timer of a WAITING job, with impatience[r] naming whi...
CdScaling< T > jdscaling
sn.jdscaling for this station: MATLAB's Station.ljdScaling, the JOINT dependence map eta_i(n),...
std::vector< lang::ImpatienceType > impatience
CdScaling< T > cdscaling
sn.cdscaling for this station: the class-dependence map, empty when unset.
One half of a synchronization: an event at a node, in a class.
std::size_t cls
1-based class index
T prob
routing probability, passive half
std::size_t rt_row
(isf-1)*nclasses + (r-1) of the active half
std::size_t rt_col
(jsf-1)*nclasses + (s-1) of this passive half
std::size_t node
1-based node index, or local for the dummy
bool statedep
The routing probability is a FUNCTION of the network state, so prob holds only the state-independent ...
One synchronization: an ACTIVE event and the PASSIVE event it drives.
SyncEvent< T > passive
SyncEvent< T > active
The parameters of a Transition node: MATLAB sn.nodeparam{ind} for an SPN transition,...
std::vector< lang::TimingStrategy > timing
immediate or timed
std::vector< lang::Distrib< T > > firingproc
firing distribution per mode
std::vector< double > nmodeservers
servers per mode, may be infinite
std::vector< T > fireweight
weight among simultaneously enabled modes
std::vector< Matrix< T > > firing
firing[m](p,r): class-r tokens mode m moves to/from place p when it fires.
std::vector< Matrix< T > > enabling
enabling[m](p,r): class-r tokens of place p (0-based node) mode m needs.
std::vector< std::function< T(const std::vector< T > &)> > firingdep
Marking-dependent firing-rate multiplier g_m(marking); an empty entry is the unit multiplier.
std::vector< Matrix< T > > inhibiting
inhibiting[m](p,r): class-r tokens of p that BLOCK mode m (Inf = never).
std::vector< std::size_t > firingphases
phase count per mode, 0 when non-Markovian
One successor of a pooled service start: the buffer, the servers, its weight and the class started.