 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
SolverLN: layered decomposition of a layered queueing network. More...
#include "line/util/line_console.h"#include <algorithm>#include <cctype>#include <cmath>#include <functional>#include <limits>#include <map>#include <memory>#include <set>#include <string>#include <vector>#include "line/api/fj/fj_branch_members.h"#include "line/api/fj/fj_quorum_moments.h"#include "line/api/lqn/lqn_boxbounds.h"#include "line/api/mam/aph_convseq.h"#include "line/api/mam/aph_fit.h"#include "line/api/mam/aph_simplify.h"#include "line/api/sn/sn_fj_nodevisits_mmt.h"#include "line/api/sn/sn_compat_rate.h"#include "line/lang/distribution.h"#include "line/lang/lqn/lqn_struct.h"#include "line/lang/qn/qn_layer.h"#include "line/solvers/ctmc/solver_ctmc_waitq.h"#include "line/solvers/fluid/fluid_passage.h"#include "line/solvers/fluid/fluid_runner.h"#include "line/solvers/fluid/solver_fluid.h"#include "line/solvers/mam/mam_dispatch.h"#include "line/api/lqn/lqn_ph.h"#include "line/solvers/ln/lqn_helpers.h"#include "line/solvers/mva/fj_driver.h"#include "line/solvers/mva/fj_mmt.h"#include "line/solvers/mva/solver_mva.h"#include "line/solvers/mva/mva_dispatch.h"#include "line/solvers/nc/nc_dispatch.h"#include "line/solvers/nc/solver_nc_runner.h"#include "line/solvers/sens/solver_sens_table.h"#include "line/solvers/ssa/ssa_dispatch.h"#include "line/util/error.h"#include "line/util/expm.h"#include "line/util/linalg.h"#include "line/util/matrix.h"#include "line/solvers/ln/lqn_analyzers.h"Go to the source code of this file.
Classes | |
| struct | line::ln::LnOptions |
| Options of SolverLN. More... | |
| struct | line::ln::LayerResult< T > |
| Per-layer results of one iteration, the [QN,UN,RN,TN,AN,WN] of getAvg. More... | |
| struct | line::ln::LnSolution< T > |
| The LQN-level answer, indexed by element 1..nidx. More... | |
| struct | line::ln::LnCdf |
| A CDF sampled on a grid, the [F, t] pair MATLAB's evalCDF returns. More... | |
| struct | line::ln::LnTranLayer |
| One layer's block of the layered transient. More... | |
| struct | line::ln::LnLayerBlocks |
| LayeredNetwork.layerBlocks: where each layer's block sits in the aggregate. More... | |
| struct | line::ln::LnTranSolution |
| The layered transient: one block per layer, plus how it was produced. More... | |
| struct | line::ln::LnSensTable< T > |
| getSensitivityTable of the ensemble: the layer tables under a Layer column. More... | |
| struct | line::ln::LnSensTable< T >::Row |
| struct | line::ln::LnStochConfig |
| options.config.stochiter_* of SolverOptions.m, with its defaults. More... | |
| class | line::ln::SolverLN< T > |
| struct | line::ln::LqnCallGroup |
| One routed call group: an activity, the strategy that picks among its targets, and the target ENTRIES in declaration order. More... | |
Namespaces | |
| namespace | line |
| namespace | line::ln |
Typedefs | |
| using | line::ln::FluidRateSched = fluid::FluidOptions::RateSched |
| One (station, class) rate trajectory injected into a layer's closing ODE. | |
Enumerations | |
| enum class | line::ln::CallType |
| Call kinds, with the values of MATLAB CallType. More... | |
| enum class | line::ln::JobClassType |
| Job class kinds, with the values of MATLAB JobClassType. More... | |
| enum class | line::ln::LqnElement |
| LQN element kinds, with the values of MATLAB LayeredNetworkElement. More... | |
| enum class | line::ln::NodeType |
| Node kinds, with the values of MATLAB NodeType. More... | |
| enum class | line::ln::PrecedenceType |
| Activity precedence kinds, with the values of MATLAB ActivityPrecedenceType. More... | |
| enum class | line::ln::RoutingStrategy |
| Routing strategies, with the values of MATLAB RoutingStrategy. More... | |
| enum class | line::ln::SchedStrategy |
| Scheduling disciplines, with the values of MATLAB SchedStrategy. More... | |
Functions | |
| template<class T> | |
| T | line::ln::lqn_overtake_prob_markov (const LqnStruct< T > &lqn, const std::vector< T > &servt, const std::vector< T > &callresidt, const std::vector< T > &tput, std::size_t eidx, const T &xj) |
| Overtaking probability at a server entry, through the LQNS phased-server chain rather than the reduced CTMC above. | |
SolverLN: layered decomposition of a layered queueing network.
Port of the matlab/src/solvers/LN SolverLN class folder – construct, buildLayers, buildLayersRecursive, init, initInterlock, converged, analyze, post, updateMetrics, updatePopulations, updateThinkTimes, updateLayers, updateRoutingProbabilities, getEntryServiceMatrix and getEnsembleAvg – driven by the EnsembleSolver iteration in @EnsembleSolver/iterate.m.
The method is a Picard iteration over a fixed point. Each processor and each software task becomes a closed queueing network (a "layer") in which the element is the server and its callers are the customers; solving all layers gives new residence times, which become the service times of the calls one level up and the think times of the callers one level down, and the layers are re-solved until the queue lengths stop moving.
WHAT IS IMPLEMENTED. Every path a plain layered model takes is here: synchronous calls, entry selection by throughput ratio, multi-entry tasks, reference tasks with think time, infinite-server tasks and processors, server replication, AND-forks and AND-joins, and the LQNS V5 interlock analysis. Forwarding is solved too: construct() runs the lqn_fwd_rendezvous rewrite of lqn_helpers.h (:306), which flattens every forwarding chain into caller-side pseudo rendezvous arcs, so nothing below this point needs a forwarding case. Asynchronous calls and entry open arrivals are solved by giving the layer its own Source/Sink pair and an open chain (build_layer's async_here/open_entries construction, roughly :622-668). Cache tasks and item entries are solved by a Cache node placed in the host layer, with the hit and miss branches switching class at the server (build_layer's iscachelayer path, :591-616 and the read walk at :883-908). Setup tasks with a setup time are solved by charging the cold start to the ENTRY, at the probability the thread was found powered down (setup_charge, added to entry_servt and to the caller's think time); no layer station carries a SetupDelayOffParam. Admission constraints are solved by a Region on the server station, which forces that layer's fixed point through SolverCTMC rather than MVA or fluid (:1051-1096, dispatch at :1753-1760). reject_unsupported() (:433) is kept but empty: every construct the reference LQN model can carry is now accounted for here. A few narrower combinations remain unsupported and are refused where they are discovered instead of up front: a fork sharing a layer with an open stream (:492-496), a fork's fixed point outside layer_solver 'mva' (:1723-1728), and a fluid layer or an AND-join's order-statistic fit under a non-double/non-real arithmetic backend (:120-126, :2198-2201).
WHAT ELSE THIS CLASS ANSWERS, beyond the mean-value table. options.method selects between three DIFFERENT questions rather than three routes to one: default is the mean-based update; moment3 is updateMetricsMomentBased, which fits an APH to each layer's response-time CDF and convolves along the entry's activity sequence, so it additionally reports a per-entry response time DISTRIBUTION through get_cdf_respt(); mwba.upper / mwba.lower report Majumdar-Woodside robust box bounds and never solve a layer at all. get_tran_avg() is the layered transient, decoupled (demands frozen at the fixed point) or coupled (waveform relaxation over time-varying demands injected through the fluid rate schedule). get_sensitivity_table() delegates to each layer's own sensitivity table; every derivative in it is a partial WITHIN its layer, not a total derivative of the layered model.
THE LAYER ENGINE is layer_solver: mva, nc, fluid or ssa, the C++ spelling of the reference's solver FACTORY. They converge to DIFFERENT fixed points, because each feeds different demands back into the next outer sweep. ssa is noisy, so the deterministic convergence test is replaced by LnStochController (Robbins-Monro relaxation, Polyak-Ruppert reporting); running it under the deterministic test would simply reach iter_max.
PHASE-2 ACTIVITIES ARE SOLVED, not refused. servt keeps both phases, so the server's utilization is unchanged, while residt carries the CALLER's view: phase 1 in full plus the phase-2 time the caller is actually overtaken by, with the overtaking probability from lqn_analyzers.h's lqn_overtake_prob_markov. Every phase-2 branch below is gated on has_phase2 and is inert on a single-phase model.
ARITHMETIC. All model quantities are T. Iteration counters, populations, multiplicities and the convergence tolerances are double, matching the reference: they are properties of the algorithm and of the model's integer structure, not quantities whose precision is under study.
Definition in file solver_ln.h.
1.18.0