 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
SolverENV, the default mean-field path: ENVIRONMENT COMPRESSION. More...
#include <algorithm>#include <cmath>#include <cstddef>#include <limits>#include <memory>#include <string>#include <vector>#include "line/api/mc/ctmc_courtois.h"#include "line/api/mc/ctmc_kms.h"#include "line/api/mc/ctmc_multi.h"#include "line/api/mc/ctmc_solve.h"#include "line/api/mc/ctmc_takahashi.h"#include "line/lang/qn/environment.h"#include "line/lang/qn/network_struct.h"#include "line/num/number.h"#include "line/api/mam/map_cdf.h"#include "line/api/mam/map_moment.h"#include "line/solvers/env/solver_env.h"#include "line/solvers/fluid/fluid_cacheqn.h"#include "line/util/error.h"#include "line/util/matrix.h"Go to the source code of this file.
Classes | |
| struct | line::env::EnvCompressOptions |
| The knobs applyCompression reads out of options.config. More... | |
| struct | line::env::EnvDecomp< T > |
| What SolverENV.ctmc_decompose returns: [p, eps, epsMax, q]. More... | |
| struct | line::env::EnvCompression< T > |
| Everything applyCompression computes, plus the compressed environment. More... | |
| struct | line::env::CacheBlendResult< T > |
| A mean-field solve, with the compression that produced it. More... | |
| struct | line::env::EnvMeanfieldSolution< T > |
Namespaces | |
| namespace | line |
| namespace | line::env |
Typedefs | |
| using | line::env::MacroPartition = std::vector<std::vector<std::size_t>> |
| A partition of the stage indices 0..E-1 into macro-states, MATLAB's MS. | |
Functions | |
| template<class T> | |
| EnvDecomp< T > | line::env::env_ctmc_decompose (const Matrix< T > &Q, const MacroPartition &MS, const EnvCompressOptions &opt) |
| Port of SolverENV.ctmc_decompose: one NCD decomposition, by whichever kernel options.config.da names. | |
| template<class T> | |
| Matrix< T > | line::env::env_rate_matrix (const Environment< T > &e) |
| E0, the environment's rate matrix: E0(e,h) = env{e,h}.getRate(). | |
| template<class T> | |
| MacroPartition | line::env::env_find_best_partition (const Matrix< T > &Eutil, const EnvCompressOptions &opt) |
| Port of findBestPartition, the small-environment search. | |
| template<class T> | |
| MacroPartition | line::env::env_beam_search_partition (const Matrix< T > &Eutil, const EnvCompressOptions &opt) |
| Port of beamSearchPartition, the large-environment search: repeatedly merge two blocks, keeping the beam_width cheapest partitions at each depth. | |
| template<class T> | |
| EnvCompression< T > | line::env::env_compress (const Environment< T > &e0, const EnvCompressOptions &opt) |
| Port of applyCompression: pick a partition, decompose, and build the macro-state environment. | |
| template<class T> | |
| void | line::env::env_apply_macro_probabilities (Environment< T > &e, const EnvCompression< T > &c) |
| probEnv = pMacro and probOrig = newEmbweight, the two quantities applyCompression overwrites on the environment. | |
| template<class T> | |
| EnvMeanfieldSolution< T > | line::env::solver_env_meanfield (Environment< T > &e, const EnvOptions &o) |
| The mean-field solve on the original stages, with no compression. | |
| template<class T> | |
| EnvMeanfieldSolution< T > | line::env::solver_env_meanfield (Environment< T > &e, const EnvOptions &o, const EnvCompressOptions &c) |
| The compressed mean-field solve: aggregate the environment, then run the mean-field fixed point over the macro-states. | |
SolverENV, the default mean-field path: ENVIRONMENT COMPRESSION.
WHAT THIS FILE IS, and what it deliberately is not. The mean-field coupling itself – solver_env_meanfield_analyzer.m, the pre_/analyze_/post_/ finish_/converged_ cycle over per-stage transient means – is ALREADY ported, in solver_env.h. What was missing is the other half of the mean-field path, the half that lives in @@SolverENV/SolverENV.m rather than in the analyzer file: the environment rate matrix E0, its generator Eutil, ctmc_decompose, findBestPartition, beamSearchPartition, computeMacroRate and applyCompression. That is what this header adds, and it composes with SolverEnv<T> instead of duplicating it.
WHAT COMPRESSION BUYS. The mean-field fixed point costs one transient stage solve per stage per iteration, so an environment with many stages is expensive in the number of stages and not in their size. When the environment is NEARLY COMPLETELY DECOMPOSABLE – stages fall into groups that switch rapidly among themselves and rarely across groups – each group behaves, on the slow time scale the network actually feels, like a single stage running at the group's conditionally-averaged rates. Aggregating the groups replaces E stage solves by E' < E of them, and the error is governed by the degree of coupling eps against the admissible epsMAX that the kernels report.
THE KERNELS ARE NOT RE-DERIVED HERE. ctmc_courtois, ctmc_kms, ctmc_takahashi and ctmc_multi are already ported under line/api/mc/, with their reference-defect histories recorded in their own headers; this file is the dispatch SolverENV.ctmc_decompose puts in front of them and nothing more. The same discipline applies downstream: the metrics still come out of SolverEnv<T>, which is the single mean-field implementation, so there is no second copy of the Util computation to drift – the failure mode _kb/06-solver-catalog.md records under "ENV state-vector Util had drifted from the CTMC analyzer".
ONE DELIBERATE DIVERGENCE FROM THE REFERENCE, and it is a correctness fix rather than a preference. applyCompression replaces self.ensemble, self.solvers and self.sn with their E' macro versions but leaves self.envObj at its original E stages, so envObj.proc{e}{h} and envObj.holdTime{e} still describe MICRO transitions while every consumer now indexes them as macro ones. The analyzer's post_ and finish_ weight the macro transients by those stale micro CDFs, silently, and only when E' == E do the two agree. Here env_compress builds a genuinely compressed Environment<T>: E' stages, and arcs carrying the aggregated macro rates, so the holding times the analyzer integrates against are the ones its stages actually have.
WHAT IS PORTED, and what is refused by name: ported E0/Eutil, ctmc_decompose over all four kernels, findBestPartition, beamSearchPartition, computeMacroRate, applyCompression, and the mean-field solve on top of the result ported aggregateCacheMeanfield_ too, as of 2026-08-15: it is a SECOND mean-field fixed point, nested beside the queue-length one and carrying each Cache's own occupancy across a switch by prob_orig, because a cache's state is a per-item occupancy that no marginal queue length encodes. Its per-sweep transient is solver_fld_cacheqn_tran, whose grid runs in PER-REQUEST time – it is divided by the cache's total arrival rate before the holding-time CDF is evaluated on it, or every stage is weighted as though its cache saw the same request rate refused a Cache under a NON-FLUID stage solver (only the fluid stage exposes that RMF transient), compression of a non-exponential environment, and everything solver_env.h already refuses by name
Definition in file solver_env_meanfield.h.
1.18.0