api.lqn

lqn_setup_charge(self, lqn, tidx, S)

C = LQN_SETUP_CHARGE(SELF, LQN, TIDX, S) Mean extra time one request of task TIDX spends because its threads power down, 0 when it declares no setup

A SetupTask powers a thread down when its delay-off countdown expires while it is idle, and a request that finds no warm thread waits for a setup. The task’s thread pool is therefore an M/M/k queue with setup and delayed-off servers (Gandhi, Harchol-Balter and Adan, Performance Evaluation 67(11), 2010), with k the multiplicity and the admission rules of the LDES engine, and it is solved EXACTLY by qbd_setupdelayoff_mmk, at the callers’ population N and complementary delay Z = (N - Q)/X of the layer where TIDX is the server (or at its arrival rate X when a visiting class is open), and at the base service time S of a request, i.e. the sum of the task’s entry services before any charge. The layer serves the pool as a plain M/M/k, so the charge is the EQUIVALENT extra service:

charge = S’ - S, with R_M/M/k(S’) = QN/X (setup, delay-off),

S’ found by bisection. Subtracting the two response times instead counted the queueing behind a setup twice, once in the chain and again in the layer, and ran the one-thread model of test_ln_setup 5.6% below LDES. The result is continuous in the load and exact at any thread count; it replaces a closure that assumed max(1,b) hot threads at offered load b, which dropped the charge to zero above one busy thread and oscillated at the kink (BUG-78).

Called with S, it computes the charge from the current layer solution and stores it in SELF.setupcharge, as updateMetricsDefault does once per iteration; called without, it returns the stored value, so updateThinkTimes and method ‘srvn.ph’ (phSetupProb) charge the same cold start. Before anything has been computed the thread is down when the first request arrives, and the charge is the setup mean.

lqn_ref_routes(lqn, callers, maxpaths, serverSet)

Synchronous call DAG carrying reference-task customers into a layer.

Parameters:

lqn – LayeredNetworkStruct.
callers – Task indices that call the layer’s server.
maxpaths – (Optional) Refuse the layer above this many reference-task routes into it. Default 32. The count is derived, never enumerated.
serverSet – (Optional) Server elements of the layer. A prefix node whose task is one of them is recursion and refuses the layer.

Returns:

R – Struct array, one element per reference task reaching CALLERS. WHY: Non-empty when the layer must fall back to another interlock

method; R is then empty.

[R, WHY] = LQN_REF_ROUTES(LQN, CALLERS, MAXPATHS, SERVERSET)

Resolves, for the caller set of one layer, the synchronous call graph along which reference (REF) task customers descend to those callers, and the mean number of times each entry and each call is invoked per REF cycle.

SolverLN gives every caller of a layer its own client chain, each carrying its own thread pool as a population, so a layer holds one customer per caller even when those callers are the same REF customers arriving by different routes. The caller set of this group, .members, is what has to become ONE chain.

The result carries a single DAG and two readings of it:

.members every caller of the layer on the DAG, in descent order. The
first is the chain head when the REF task is itself a caller.

.prefixPos the entries from the REF task down to, but not past, the first
caller on each path. Below that first caller the layer already holds an activity subgraph, and the descent through it is spliced call by call, so the prefix has nothing left to say.

Nodes are ENTRIES, because the work a hop charges depends on which entry was called. Visits are computed TOPOLOGICALLY, v(u) = sum over parents of v(p)*w(a)*callmean, and routes are COUNTED in the same pass rather than enumerated: the weights a route decomposition would produce are obtainable in one linear pass, and two sources of truth for one quantity is one too many.

Only SYNC calls are followed. An ASYNC call is send-no-reply, so it terminates blocking and the customer below it is not the REF customer; forwarding is already flattened into pseudo-SYNC arcs by lqn_fwd_rendezvous before the layers are built, and any CallType.FWD left in the struct carries no blocking.

R(g) carries:

.reftask task index of the REF task at the root .headIsCaller true when the REF task is a caller of this layer .members callers of this layer on the DAG, descent order .entries every DAG entry, topologically ordered, root entries first .etask lqn.parent of each entry .ismember true where that entry’s task is a caller of this layer .vEntry mean invocations of each entry per REF cycle .actweight cell, per entry, [aidx; executions per invocation] .calls [cidx, fromPos, toPos, aidx, vCall] rows, vCall being the

mean invocations of that call per REF cycle

.prefixPos positions in .entries forming the prefix, topological order .prefixTerm true where that prefix position is a first caller .npaths distinct REF-to-caller routes, counted .poolmin min of lqn.maxmult over the DAG tasks. A DIAGNOSTIC: the

chain population is never capped by it.

lqn_ref_thinktime(lqn, tidx)

Z = LQN_REF_THINKTIME(LQN, TIDX)

Declared think time of task TIDX as it enters the thread cycle: the value for a REFERENCE task, zero for any other.

A think time is an attribute of the closed customer population a reference task stands for, and it is what separates one request of that population from the next. On a served task it has no such meaning, and charging it per request throttles the task: lqn_basic’s T3 has 25 threads and a declared think time of 4, and reading it as a per-request delay caps it at 25/(4+0.02) = 6.219 completions per second. Three independent oracles refuse that reading and put the rate at 5 calls per caller request instead – lqsim 66.5, LDES 66.955, lqns 75.6 – so the think time of a non-reference task does not enter the cycle. BOTH SolverLN methods go through this gate: updateThinkTimes and updateThinkTimesPH for the surrogate delay, getTranAvgCoupled for its trajectory, and buildLayersRecursive for the build-time seed. See _kb/06-solver-catalog.md (LN section).

lqn_ph_moments(alpha, T)

[M1, SCV, M2] = LQN_PH_MOMENTS(ALPHA, T)

First two moments of the phase-type law (ALPHA,T) without building a Distribution object, which is what the layered fixed point needs at every iteration for every composed entry law. A defective ALPHA carries an atom at zero and contributes nothing to either moment.

lqn_ph_serial_law(wf)

[ALPHA, T] = LQN_PH_SERIAL_LAW(WF)

Composed law of a workflow in which the branches of an AND fork are SERIAL rather than concurrent, that is, the total work the branches request rather than the elapsed time until the last of them finishes.

This is the law of the PROCESSOR demand of an LQN entry. Two branches of an AND fork are two activity threads of the same task instance: they overlap in time, so the entry response time is the maximum of the branches, but they run on ONE processor, so the demand they place on it is the sum. Composing the host law with Workflow.toPH would charge the processor the maximum and let the layer report a utilization below the true one, which no amount of iterating recovers.

Every other node keeps its own composition rule: an OR fork is a mixture, a loop is a geometric compound, so the correlation within a branch survives.

lqn_nlp_mgrad(f, u)

G = LQN_NLP_MGRAD(F, U)

Gradient of a MULTIVARIATE smooth term F at the real vector U by complex step, one coordinate at a time: exact to machine precision for any analytic F, with no subtraction and so no step size to trade against cancellation. LQN_EXPORT_NLP uses it for the AND-fork closure LQN_NLP_FJ_MAX_EXP. G is a row vector the size of U.

lqn_nlp_lld(src)

[F, WHY] = LQN_NLP_LLD(SRC)

Compile and check a queue-dependent rate multiplier for LQN_EXPORT_NLP.

SRC is an expression in the free variable n, the number of jobs present, written in the small grammar the three codebases share:

expr := term ((‘+’|’-’) term)* term := unary ((‘*’|’/’) unary)* unary := (‘+’|’-’) unary | power power := atom (‘**’ unary)? atom := NUMBER | ‘n’ | FUNC ‘(’ expr ‘)’ | ‘(’ expr ‘)’ FUNC := exp | log | sqrt | sin | cos | tanh, optionally prefixed ‘np.’ or ‘math.’

It is the python form of the exporter (a python expression in n) cut down to what a rate multiplier needs, and it is EVALUATED OVER THE COMPLEX NUMBERS, because the program differentiates every rate by complex step. Three names are kept on purpose so that the check below can refuse them as python does: ‘abs’ evaluates to the REAL modulus (so its complex step is zero and the check reports it as not analytic), and ‘min’ / ‘max’ raise on a complex argument (so the check reports that it rejects one). Any other identifier fails to evaluate with a NameError, and text the grammar does not parse is not a python expression.

SRC may also be a function_handle of one argument, which is checked the same way and must accept a complex argument.

F is a function handle evaluating the expression at a (possibly complex) scalar n; WHY is ‘’ when the expression is usable and otherwise the reason it is not, in the wording of the python exporter’s _check_lld: the values at n = 1, 2.5 and 10 must be real, finite and positive, and the complex-step derivative at 2.5 must agree with a central difference.

lqn_nlp_softmin(a, b, alpha)

Y = LQN_NLP_SOFTMIN(A, B, ALPHA)

Smooth stand-in for min(a,b) used by LQN_EXPORT_NLP as the multiserver rate: (a*e^-alpha*a + b*e^-alpha*b) over the same two exponentials, factored through the smaller argument so nothing overflows. Written to accept a complex argument, since the program differentiates its rate functions through it by complex step: the branch is taken on the REAL parts, and once alpha times the gap exceeds 700 the exponential has underflowed and the smaller argument is returned as is. Twin of the python exporter’s softmin.

lqn_mol(lsn, options)

Method of Layers on the SRVN decomposition of a layered queueing network whose entries carry no activity graph.

A compact, self-contained reimplementation of the layered fixed point that

Parameters:

lsn – LayeredNetworkStruct (from LayeredNetwork.getStruct())
options – optional struct: iter_max (200), iter_tol (1e-6),

Returns:

Index – QN (QLen) host: NaN task: sum of entry T*S entry: T*S activity: T*S

Scope:: Entry-only models. Activity graphs (fork/join, OR-branches, loops, second phases, forwarding), asynchronous calls, caches, setup tasks, admission constraints, replication and open arrivals are REFUSED, not approximated.

Examples

[QN,UN,RN,TN] = lqn_mol(lsn)
[QN,UN,RN,TN,info] = lqn_mol(lsn, options)

Solverln:: runs, restricted to LQNs in which every entry binds exactly one activity and there are no activity precedences. It decomposes the model the way lqns –srvn-layering does – one submodel per processor and one per called task – and sweeps them in the two phases of Rolia-Sevcik’s Method of Layers: all software (task) submodels, then all hardware (processor) ones. Every submodel is a closed multiclass queueing network with ONE station and one class per client task, so it is solved by pfqn_qdamva rather than by building a Network object. The surrogate client delay of @SolverLN collapses into the think-time vector Z of that call. Where this differs from @SolverLN’s srvn.cs: a submodel here carries one class per client TASK with visit-weighted demands, where srvn.cs carries one class per activity and encodes the call multiplicities as routing. On an entry-only model the two agree on the structure and differ only in the aggregation, so the throughputs and processor utilizations track closely while entry response times spread more.

[QN,UN,RN,TN,INFO] = LQN_MOL(LSN, OPTIONS)

lqn_export_nlp(lqn, varargin)

P = LQN_EXPORT_NLP(LQN, ‘lld’, LLD, ‘alpha’, ALPHA, ‘fork’, FORK, ‘name’, NAME)

State a layered queueing network as ONE nonlinear program: linear equality and inequality constraints over the flows, the service-time composition and the closures, plus a nonlinear least-squares objective made of the relations the linear block cannot carry. Its global minimum is zero, attained where

flow X(c) = y(c)*X(a), X(e) = sum_c X(c), X(a) = v(a)*X(e) entry service S(e) = sum_a v(a)*[W(a) + sum_c y(c)*R(c)] host residence W(a)*G(h) = D(a)*(1 + Qbar(h,a)) task residence R(c)*G(t) = S(e)*(1 + Qbar(t,c)) station rate G(i) = r_i(1 + delta_i*sum_j Q_j) queue lengths Q(a) = X(a)*W(a), Qt(c) = X(c)*R(c) busy threads B(c) = X(c)*S(e), z(t)*X(e_t) + B(t) = N(t)

which is QD-AMVA (Casale, Perez, Wang, PERFORMANCE 2015). r_i(n) is the rate station i serves at with n jobs present: softmin(n, m) for an m-server station, times any declared smooth multiplier, and n at a delay.

This is the MATLAB twin of python’s line_solver.api.lqn.export_nlp. The python function emits the program as a standalone script; this one builds the SAME PROGRAM in memory and returns it as a struct, with the same element numbering, variable layout (Xe,Xa,Xc,W,S,R,Q,Qt,BC,BR,GH,GT,SA), row order of AEQ/AUB and residual order, so a solution vector is comparable component by component across the codebases. Element positions are 1-based here.

LQN is a LayeredNetwork or its LayeredNetworkStruct. Options:

‘lld’ queue-dependent rate multipliers, a struct or containers.Map: {station name: expression in n} (see LQN_NLP_LLD). A tabulated row is refused: its interpolant has a corner at every knot.

‘alpha’ sharpness of the softmin standing in for min(n, m), default 20 ‘fork’ ‘refuse’ (default) declines an AND-fork/join by name; ‘exp’ carries

a well-formed block under the EXPONENTIAL-BRANCH closure (LQN_NLP_FJ_MAX_EXP), an assumption about branch shape

‘name’ model name to record

P carries the parameters and derived index sets under the python names (HOSTS, TASK_MULT, ACTS_OF_HOST, QD_HOSTS, HOST_MAXMULT, OFFSET, NVAR, NRES, AEQ, BEQ, AUB, BUB, …) and these function handles:

residuals(x), jacobian(x), objective(x), initial_point(warm), polish(x), solved(x), solve(warm, maxiter), fallback(x0, maxiter), var_names(), qbar_host(Q,h,a), qd_pop_host(Q,h), qbar_task(Qt,t,c), qd_pop_task(Qt,t), col(block,i), fj_max_exp(m), mgrad(f,u)

solve() runs the Newton root-find on the square system from an escalating warm-start ladder, and falls back to a projected Levenberg-Marquardt descent on the merit ||r||^2 + ||AEQ x - BEQ||^2 + ||max(0, AUB x - BUB)||^2 when no rung reaches a feasible root. That fallback is a documented divergence from python, which uses scipy’s trust-constr there; the Newton path is identical.

A feature the algebraic form cannot express raises LINE:unsupported:NlpExport naming every offending element.

lqn_nlp_fj_max_exp(m)

TOT = LQN_NLP_FJ_MAX_EXP(M)

E[max] of K independent EXPONENTIAL branch completion times of means M, the AND-fork closure of LQN_EXPORT_NLP under nlp_fork=’exp’. The max of exponentials is not exponential, but its mean is a rational function of theirs:

E[max] = sum over nonempty S of (-1)^(|S|+1) / sum_{i in S} 1/m(i)

written here with the reciprocals cleared, so a branch of zero mean contributes zero instead of dividing by it. Two equal branches of mean D give 1.5*D, against the 2*D a sequential sum charges and the D a max of the means would. Homogeneous of degree one. Accepts a complex M, which is how the program differentiates it (LQN_NLP_MGRAD).

THIS IS AN ASSUMPTION ABOUT BRANCH SHAPE: deterministic branches of the same means would give D. It is the closure fj_quorum_moments applies in SolverLN.

lqn_boxbounds(lqn)

Majumdar-Woodside robust box bounds on throughput for a layered queueing network (LQN), computed on the processor-contention model.

Builds a closed multiclass queueing network from a LayeredNetworkStruct in which the stations are the processors (hosts) and the classes are the reference-task call chains, then applies the Majumdar-Woodside robust box bounds (see pfqn_mwrbb). The per-chain demand at each processor is the total host demand executed on that processor during one cycle of the reference task, obtained by traversing the activity/call graph and scaling by the mean number of synchronous calls. The reference-task multiplicity is the class population and the reference-task think time is the class think time.

This generalizes the classical LQN “Type 1 throughput bound” X_ref <= mult/(Z + D_total) (the no-contention upper bound, as computed by lqns -b) by additionally providing the processor-utilization upper bound and the Majumdar-Woodside lower bound (throughput guarantee, Theorem 2).

Scope: processors are the queueing resources; reference-task chains are the classes. Software (finite-thread task) bottlenecks and non-deterministic activity precedence (OR-branch probabilities, loop repetitions) are not modeled here (sequential activity execution is assumed).

Parameters:: lqn – LayeredNetworkStruct (from LayeredNetwork.getStruct())
Returns:: Field – Description refidx: (1 x R) absolute indices of the reference tasks Xlo,Xup: (1 x R) lower/upper throughput bound per reference chain TN_lo,TN_up: (nidx x 1) throughput bound propagated to all elements UN_lo,UN_up: (nidx x 1) processor utilization bound (util law) D: (nhosts x R) per-chain demand at each processor

Examples

out = lqn_boxbounds(lqn)

lqn_entry_workflow(model, lqn, eidx, withCalls)

[WF, ACTIDXOF, CALLIDXOF, EXECS, CALLEXECS] = LQN_ENTRY_WORKFLOW(MODEL, LQN, EIDX, WITHCALLS)

Activity graph of LQN entry EIDX as a Workflow, so that the entry service time can be composed exactly into a phase-type law by the series-parallel reduction of Workflow.toPH.

MODEL is the LayeredNetwork the struct LQN was obtained from; the activity precedences are read from the task object rather than reconstructed from LQN.GRAPH, whose loop back-edges carry probabilities and not counts.

WITHCALLS true expands every synchronous call of an activity into a leaf of its own, placed in series after the activity, so that the call response law and the host demand law stay separable across iterations. WITHCALLS false keeps only the host demands, which is the processor-demand law of the entry: the host is released while a call is outstanding.

Returns:

wf - Workflow whose leaves are the activities (and calls) of EIDX actIdxOf - (nidx,1) workflow activity index of each LQN activity, 0 if absent callIdxOf - (ncalls,1) workflow activity index of each call, 0 if absent execs - (nidx,1) expected executions of each LQN activity per entry

invocation

callexecs - (ncalls,1) expected executions of each call per entry invocation,: not counting the mean number of calls per execution

lqn_act_visits(lqn)

V = LQN_ACT_VISITS(LQN)

Expected number of executions of every activity per invocation of its entry. The activity precedence arcs of a task are a transient Markov chain whose absorbing state is the reply, so the visit counts of the block solve v = e0*(I-P)^-1; a loop back-edge of weight 1-1/count returns count, and an AND-fork row summing above one returns the branching expectation, both of which are what a visit ratio means. Call arcs leave the block and drop out.

V is an lqn.nidx-by-1 vector, nonzero only at activities. Shared by LQN_BALANCE_EQUATIONS and LQN_EXPORT_NLP, so both read the same visits.

lqn_balance_equations(lqn, sol, un)

Enumerate the conservation laws (the “physics”) that any solution of a layered queueing network must satisfy, as symbolic relations over a LayeredNetworkStruct and, optionally, as numeric residuals.

A layered model is not free to report any tuple of throughputs, think times and utilizations: five families of relations tie them together, and every one of them is determined by the STRUCTURE of the model alone. This function walks a LayeredNetworkStruct and emits them, one record per relation, with the index sets to aggregate over, the constant coefficients and a printable form. Nothing is solved here.

The families, with kind as emitted:

little Little’s law on a task’s THREAD POOL. The threads of task t form a closed cycle of one delay stage (the surrogate think time that SolverLN imputes to the task, plus the declared think time of a reference task) and one service stage (holding a request from above). Writing B(t,k) for the mean number of threads of t busy serving caller class k – the per-class utilization expressed in JOB units – the law reads

X(t)*(Z(t) + z(t)) + sum_k B(t,k) = N(t)

which is the update SolverLN.updateThinkTimes iterates on. In the [0,1]-normalized utilization LINE reports for a queueing station, B(t,k) = N(t)*U(t,k) and the law is the familiar X(t)*(Z(t)+z(t)) = N(t)*(1 - sum_k U(t,k)); at an infinite server LINE’s utilization is already a job count, so B = U. The caller classes k are the CALLS that target an entry of t – the in-edges of t in the call graph – plus each entry of t that carries an OPEN ARRIVAL, a stream that holds a thread exactly as a call does and that a task can have alongside its callers. Both are structural neighbours of t, which makes the whole relation node-local. termisentry says which of the two a term is.

callflow Throughput conservation across one call: X(c) = X(src(c))*y(c), with y(c) the mean number of calls and src(c) the dispatching activity (the dispatching ENTRY for a forwarding call).
entryflow The requests an entry serves are the calls that reach it plus its open-arrival stream: X(e) = sum_c X(c) + lambda(e).
actflow An activity executes v(a) times per invocation of its entry: X(a) = X(e)*v(a). The visit counts v come from the activity precedence graph and are returned in out.visits. An AND-JOIN is the one place where flow does not add up – its target executes once per fork, not once per branch – so the arcs into a join are scaled by 1/(number of joined branches); see lqn_act_visits.
hostutil The utilization law at a processor: the host demand executed there per unit time equals its busy servers, sum_a X(a)*D(a) = m(h)*U(h) (again m(h)*U(h) is a job count, and the factor m(h) drops at an infinite server).

Together these close the system: little alone is one equation per task and admits the all-zero solution, so a physics-informed loss built on it should carry the flow and utilization families as well.

Parameters:

lqn – LayeredNetworkStruct (from LayeredNetwork.getStruct())
sol – optional; a solved SolverLN, or any struct exposing the same
UN – optional; the REPORTED utilization per element, the second

Returns:

Field – Description eqs: (1 x M) struct array of relations; see below text: cellstr, the printable report visits: (nidx x 1) activity visit count per invocation of its entry A_little: sparse (ntasks x ncalls) 1 where call c is a caller class of task t A_flow: sparse (ncalls x nidx) call-to-source incidence, weighted by y(c) A_host: sparse (nhosts x nidx) host-to-activity incidence, weighted by D(a) maxresidual: largest absolute residual over the non-degenerate records, NaN without sol

Reference-task, forwarding and open-arrival tasks:

A reference task has no layer above, so its cycle closes on its OWN entries, which enter K(t) as entry classes. A forwarding target and an entry-arrival target are driven by a rate pinned outside the task, but the shape of the relation is identical. All four cases therefore share one template, and the branch field says which one produced the record; what it selects is only the label and whether the utilization is a job count.

Conventions (also returned in out.convention):

Rates and populations in a little record are PER REPLICA, matching SolverLN.updateThinkTimes: X per replica is tput/repl and N is the declared multiplicity of one copy. Utilizations and throughputs elsewhere are as the solver reports them, i.e. totalled over replicas – which is why the server count in hostutil is mult and not mult*repl.
N(t) is lqn.mult. SolverLN instead iterates on njobs, which carries the interlocking corrections and, under replication, may be maxmult; both are returned per record so a caller can substitute.
A task whose multiplicity is infinite has no finite thread pool, so its little record is emitted with const = Inf and degenerate set. The sustainable multiplicity maxmult is the finite surrogate SolverLN uses.
S(k) is the entry SERVICE time servt (phase 1 plus phase 2), the time a thread is held, not the residence time residt the caller waits for. The difference is the phase-2 tail, and corr.phase2 marks the tasks that have one. corr.setup marks a task that pays a setup charge, which lands on Z.

Saturation:

SolverLN clamps the think time at zero, so the little equality is an INEQUALITY at a saturated task: when sum_k U(t,k) -> 1 the right-hand side reaches zero and Z can no longer absorb the imbalance. Records carry clamped once instantiated, true when the equality is not attainable. A loss built on these relations should use a one-sided (hinge) form there.

Examples

out = lqn_balance_equations(lqn)            % symbolic only
out = lqn_balance_equations(lqn, sol)       % also numeric residuals
out = lqn_balance_equations(lqn, sol, UN)   % including the host utilization law
lqn_balance_equations(lqn)                  % print the report