ctmc_state_space_logsize.h File Reference

Worst-case log-size of the CTMC state space induced by a NetworkStruct. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <string>
#include <limits>
#include <vector>
#include "line/lang/lang_types.h"
#include "line/lang/qn/network_struct.h"

Include dependency graph for ctmc_state_space_logsize.h:

Go to the source code of this file.

Classes
struct	line::mc::CtmcSizeOptions
	Options the estimator reads; only the cutoff matters. More...

Namespaces
namespace	line
namespace	line::mc

Functions
double	line::mc::log_ordered_joint (const std::vector< std::vector< int > > &caps_per, const std::vector< double > &cap_tot, const std::vector< int > &njobs, std::size_t m_rem)
	Log count of (placement, ordering) configurations over ALL order-preserving stations at once, POPULATION CONSERVED.
template<class T>
double	line::mc::ctmc_state_space_logsize (const qn::NetworkStruct< T > &sn, const CtmcSizeOptions &opt=CtmcSizeOptions())
	Worst-case log state-space size of sn.

Variables
constexpr double	line::mc::kOrderGridMax = 1.0e6
	Largest (m_1..m_K) box the exact ordered-buffer DP will walk.

Detailed Description

Worst-case log-size of the CTMC state space induced by a NetworkStruct.

Port of matlab/src/api/mc/ctmc_state_space_logsize.m. The estimate is the product of four factors, summed in log space:

1. job placements: stars-and-bars C(n_k+M-1, M-1) per class over the stations that keep no ordered buffer, with an open class truncated at the cutoff;
2. buffer orderings: a station outside the share family keeps the CLASS SEQUENCE of the jobs it holds, so with K>1 classes one occupancy vector is as many states as its sequences;
3. service phases: the phase count raised to the number of jobs that can be in service concurrently at the station;
4. routing state: one pointer over the outgoing links per (node, class) routed RROBIN or WRROBIN.

It is computed in LOG space throughout because the quantity it exists to detect overflows a double: the intractableCTMC fixture (8 PS stations, N=400, Erlang-5) sits at exp(200), and a linear-space estimator would report inf for everything above exp(709) and lose the ability to rank one intractable model against another.

This is the quantity fed to ctmc_memory_gate. It is separate from the gate so a caller such as SolverAUTO can screen CTMC out of a ranking without building the chain.

Definition in file ctmc_state_space_logsize.h.