LINE Solver (C++)
Templated C++ port of the LINE queueing solver
Loading...
Searching...
No Matches
line::infer Namespace Reference

Classes

struct  ConditionEvent
struct  EkfOptions
 MATLAB's OPTIONS struct, with the same defaults infer_lqn_optget supplies. More...
struct  EkfResult
 MATLAB's [ahat, info] return list. More...
struct  EstimatorOptions
struct  GibbsOptions
 MATLAB's hard-coded budgets, exposed with their MATLAB values as defaults. More...
struct  GibbsSlice
 The deterministic content of one coordinate update. More...
struct  GibbsStateProbs
 The empirical state distribution built from the traces. More...
struct  GibbsTrace
 One class's trace. More...
struct  InferLqnOptions
 MATLAB's OPTIONS struct for infer_lqn, with the same defaults the infer_lqn_optget calls supply. More...
struct  InferLqnResult
 MATLAB's INFO struct: the EKF result plus what the driver constructed. More...
struct  JacobianResult
 Mirrors the [H, h0] return list of the MATLAB function. More...
struct  LqnMetrics
 Per-element metric vectors, each aligned with the element name list. More...
struct  LqnObsSpec
 One row of MATLAB's OBSSPEC struct array. More...
struct  LqnParamSpec
 One row of MATLAB's PARAMSPEC struct array. More...
struct  NhppKsResult
 Outcome of the KS test. More...
class  ParamEstimator
class  SampledMetric
struct  VariationalOptions
 Options of infer_variational; a negative box means "derive a default". More...
struct  VariationalResult
 Outcome of infer_variational. More...
struct  VariationalSpec
 Inference problem handed to infer_variational. More...

Enumerations

enum class  LqnMetric { QLen , Util , RespT , Tput }
 The four per-element metrics of a solved LQN, as in getEnsembleAvg. More...
enum class  LqnParamType { HOSTDEM , THINK }
 The two parameter kinds MATLAB's paramSpec(i).type names. More...
enum class  NhppKsMethod { Cu , Lewis }
 Which test to run on the conditional-uniform data. More...
enum class  VariationalSched { INF = 0 , SHARED = 1 , EXTERNAL = 2 }
 Service discipline of a station, as seen by the load factor Upsilon. More...
enum class  SampledFormat { TIMESERIES , TRACE }

Functions

template<class T>
Matrix< T > infer_compute_ql_at_arrival (const std::vector< T > &at, const std::vector< long > &at_jobid, const std::vector< T > &rt, const std::vector< long > &rt_jobid, const std::vector< std::size_t > &cls, std::size_t R)
 Per-class queue lengths seen by each arriving job, reconstructed from arrival and response time samples.
template<class T>
std::vector< Matrix< T > > infer_get_qlen_arrival (const std::vector< std::vector< T > > &at_ms, const std::vector< std::vector< T > > &rt)
 Per-class queue lengths at arrival for the per-class sample format.
template<class T>
GibbsStateProbs< T > gibbs_analyse_data (const std::vector< GibbsTrace< T > > &data, std::size_t data_needed)
 Empirical state distribution of the replayed traces (MATLAB's analyseData).
template<class T>
GibbsSlice< T > gibbs_slice (const std::vector< T > &think_time, const std::vector< T > &theta, const Matrix< long > &testset, std::size_t index, const std::vector< T > &N, const T &logG_init, double interval, const T &range_size)
 The deterministic half of one coordinate update: the log normalizing constant along the grid and the normalized slice it implies.
template<class T>
std::vector< T > infer_gibbs (const std::vector< GibbsTrace< T > > &data, const T &nbCores, const GibbsOptions &opts, pfqn::McRng &rng)
 Estimated per-class mean demands.
template<class T>
std::vector< T > infer_gibbs (const std::vector< GibbsTrace< T > > &data, const T &nbCores, double tol, pfqn::McRng &rng)
 MATLAB's three-argument form, with its hard-coded budgets.
template<class T>
InferLqnResult< T > infer_lqn (lqn::LqnStruct< T > &lsn, const std::vector< LqnParamSpec > &spec, const std::vector< LqnObsSpec > &obs, const Matrix< T > &Z, const std::function< LqnMetrics< T >(const lqn::LqnStruct< T > &)> &solve, const InferLqnOptions< T > &opt=InferLqnOptions< T >())
 Identify hidden LQN parameters from measured performance data.
template<class T>
EkfResult< T > infer_lqn_ekf (const std::function< std::vector< T >(const std::vector< T > &)> &hfun, const std::vector< T > &a0, const Matrix< T > &P0, const Matrix< T > &Z, const Matrix< T > &Q, const Matrix< T > &R, const EkfOptions< T > &opts=EkfOptions< T >())
 Extended Kalman Filter for LQN parameter identification.
std::size_t infer_lqn_findbyname (const std::vector< std::string > &names, const std::string &name)
 First element of a named LQN container matching a name.
template<class T>
std::vector< T > infer_lqn_getobs (const std::vector< std::string > &names, const LqnMetrics< T > &metrics, const std::vector< LqnObsSpec > &spec)
 Observation vector of a solved LQN, z = h(a).
template<class T>
JacobianResult< T > infer_lqn_jacobian (const std::function< std::vector< T >(const std::vector< T > &)> &hfun, const std::vector< T > &a, double fd_step=1e-3, double fd_floor=1e-6)
 Forward finite-difference sensitivity matrix of an observation map.
template<class T>
std::vector< T > infer_lqn_getparams (const lqn::LqnStruct< T > &lsn, const std::vector< LqnParamSpec > &spec)
 Read the current values of the parameters named in spec.
template<class T>
void infer_lqn_setparams (lqn::LqnStruct< T > &lsn, const std::vector< LqnParamSpec > &spec, const std::vector< T > &a)
 Set the parameters named in spec to the values in a, in place.
template<class Tv>
NhppKsResult< Tv > infer_nhpp_ks (const std::vector< Tv > &times, const Tv &T, const std::function< Tv(const Tv &)> &cumRate=std::function< Tv(const Tv &)>(), NhppKsMethod method=NhppKsMethod::Lewis, const Tv &T0=num_traits< Tv >::from_int(0))
 Kolmogorov-Smirnov tests for a non-homogeneous Poisson arrival process.
template<class T>
Matrix< T > infer_qmle (const Matrix< T > &Q, const std::vector< T > &N, const std::vector< T > &Z)
 Queue-length-based maximum-likelihood estimator of the service demands of a closed queueing network.
template<class T>
std::vector< T > infer_rps (const std::vector< T > &rt, const std::vector< std::size_t > &cls, const Matrix< T > &ql, long V)
 Regression for Processor Sharing (RPS) demand estimator.
template<class T>
VariationalResult< T > infer_variational (VariationalSpec< T > spec, VariationalOptions< T > opt=VariationalOptions< T >())
 Run the variational inference procedure.

Variables

static const std::size_t GIBBS_NNODES = 2
 The two nodes of the model the estimator assumes: delay, then queue.
static const std::size_t INFER_LQN_NOT_FOUND = static_cast<std::size_t>(-1)
 Returned when no element carries the requested name, MATLAB's [].

Enumeration Type Documentation

◆ LqnMetric

enum class line::infer::LqnMetric
strong

The four per-element metrics of a solved LQN, as in getEnsembleAvg.

Enumerator
QLen 
Util 
RespT 
Tput 

Definition at line 47 of file infer_lqn_getobs.h.

◆ LqnParamType

enum class line::infer::LqnParamType
strong

The two parameter kinds MATLAB's paramSpec(i).type names.

Enumerator
HOSTDEM 
THINK 

Definition at line 55 of file infer_lqn_setparams.h.

◆ NhppKsMethod

enum class line::infer::NhppKsMethod
strong

Which test to run on the conditional-uniform data.

Enumerator
Cu 
Lewis 

Definition at line 52 of file infer_nhpp_ks.h.

◆ SampledFormat

enum class line::infer::SampledFormat
strong
Enumerator
TIMESERIES 
TRACE 

Definition at line 27 of file sampled_metric.h.

◆ VariationalSched

enum class line::infer::VariationalSched
strong

Service discipline of a station, as seen by the load factor Upsilon.

Enumerator
INF 
SHARED 
EXTERNAL 

Definition at line 63 of file infer_variational.h.

Function Documentation

◆ gibbs_analyse_data()

template<class T>
GibbsStateProbs< T > line::infer::gibbs_analyse_data ( const std::vector< GibbsTrace< T > > & data,
std::size_t data_needed )

Empirical state distribution of the replayed traces (MATLAB's analyseData).

Each class contributes one event per sample at the arrival time and one at the arrival plus the response time, so the record is a birth-death walk of the population vector between the delay node and the queue. The population of each class is taken as the largest count the walk ever reaches, which is what makes the delay-node counts non-negative once it is added back.

The state is integer by construction, so it is carried as long and only the holding times are in T: the aggregation over repeated states is then exact in every arithmetic instead of accumulating a rounding per event.

Parameters
dataper-class traces
data_neededevents kept from the END of the record, 0 for all

Definition at line 162 of file infer_gibbs.h.

References gibbs_analyse_data(), GIBBS_NNODES, line::InputError::InputError(), line::infer::GibbsStateProbs< T >::N, line::infer::GibbsStateProbs< T >::N0, line::NumericError::NumericError(), line::infer::GibbsStateProbs< T >::prob, and line::infer::GibbsStateProbs< T >::states.

Referenced by gibbs_analyse_data(), and infer_gibbs().

◆ gibbs_slice()

template<class T>
GibbsSlice< T > line::infer::gibbs_slice ( const std::vector< T > & think_time,
const std::vector< T > & theta,
const Matrix< long > & testset,
std::size_t index,
const std::vector< T > & N,
const T & logG_init,
double interval,
const T & range_size )

The deterministic half of one coordinate update: the log normalizing constant along the grid and the normalized slice it implies.

Parameters
think_time(K) think times of the delay node
theta(K) current demands; theta[index] must lie ON the grid
testset(nt x K*GIBBS_NNODES) sampled states
indexcoordinate being updated
N(K) populations
logG_initrunning log G at the current theta
intervalgrid step
range_sizeupper end of the grid

Definition at line 284 of file infer_gibbs.h.

References line::Matrix< T >::cols(), GIBBS_NNODES, gibbs_slice(), line::infer::GibbsSlice< T >::grid, line::InputError::InputError(), line::infer::GibbsSlice< T >::logG, line::NumericError::NumericError(), line::pfqn::pfqn_bs(), line::infer::GibbsSlice< T >::prob, line::pfqn::AmvaResult< T >::QN, line::infer::GibbsSlice< T >::range_size_dim, and line::Matrix< T >::rows().

Referenced by gibbs_slice(), and infer_gibbs().

◆ infer_compute_ql_at_arrival()

template<class T>
Matrix< T > line::infer::infer_compute_ql_at_arrival ( const std::vector< T > & at,
const std::vector< long > & at_jobid,
const std::vector< T > & rt,
const std::vector< long > & rt_jobid,
const std::vector< std::size_t > & cls,
std::size_t R )

Per-class queue lengths seen by each arriving job, reconstructed from arrival and response time samples.

Parameters
at(n) arrival times
at_jobid(n) job id of each arrival
rt(m) response times, m >= n
rt_jobid(m) job id of each response time
cls(n) class of each arrival, 0-based in [0,R)
Rnumber of classes
Returns
(n x R) queue length at each arrival, in the input order

Definition at line 54 of file infer_compute_ql_at_arrival.h.

References infer_compute_ql_at_arrival(), and line::InputError::InputError().

Referenced by infer_compute_ql_at_arrival(), and infer_get_qlen_arrival().

◆ infer_get_qlen_arrival()

template<class T>
std::vector< Matrix< T > > line::infer::infer_get_qlen_arrival ( const std::vector< std::vector< T > > & at_ms,
const std::vector< std::vector< T > > & rt )

Per-class queue lengths at arrival for the per-class sample format.

Parameters
at_ms(K) per-class arrival times, in milliseconds
rt(K) per-class response times, in seconds
Returns
(K) per-class (n_k x K) queue lengths at arrival

Definition at line 50 of file infer_get_qlen_arrival.h.

References infer_compute_ql_at_arrival(), infer_get_qlen_arrival(), and line::InputError::InputError().

Referenced by infer_get_qlen_arrival(), and line::api::infer_minps_setup().

◆ infer_gibbs() [1/2]

◆ infer_gibbs() [2/2]

template<class T>
std::vector< T > line::infer::infer_gibbs ( const std::vector< GibbsTrace< T > > & data,
const T & nbCores,
double tol,
pfqn::McRng & rng )

MATLAB's three-argument form, with its hard-coded budgets.

Definition at line 568 of file infer_gibbs.h.

References infer_gibbs(), and line::infer::GibbsOptions::tol.

◆ infer_lqn()

template<class T>
InferLqnResult< T > line::infer::infer_lqn ( lqn::LqnStruct< T > & lsn,
const std::vector< LqnParamSpec > & spec,
const std::vector< LqnObsSpec > & obs,
const Matrix< T > & Z,
const std::function< LqnMetrics< T >(const lqn::LqnStruct< T > &)> & solve,
const InferLqnOptions< T > & opt = InferLqnOptions<T>() )

Identify hidden LQN parameters from measured performance data.

Parameters
lsnlayered struct, mutated in place to carry the final estimate
specparameters to identify
obsobservations to read at each step, numel(obs) == Z.rows()
Z(no x nsteps) measurements, one column per step
solveobservation model: given the struct with candidate parameters injected, return the per-element metric vectors
optfilter and covariance options

Definition at line 112 of file infer_lqn.h.

References line::infer::InferLqnResult< T >::a0, line::infer::EkfOptions< T >::a_true, line::infer::EkfOptions< T >::clamp_positive, line::Matrix< T >::cols(), line::infer::InferLqnResult< T >::ekf, line::infer::EkfOptions< T >::fd_floor, line::infer::EkfOptions< T >::fd_step, infer_lqn(), infer_lqn_ekf(), infer_lqn_getobs(), infer_lqn_getparams(), infer_lqn_setparams(), line::InputError::InputError(), line::Matrix< T >::Matrix(), line::lqn::LqnStruct< T >::names, line::num_abs(), line::infer::InferLqnResult< T >::P0, line::infer::InferLqnResult< T >::Q, line::infer::InferLqnResult< T >::R, line::Matrix< T >::rows(), and line::solve().

Referenced by infer_lqn().

◆ infer_lqn_ekf()

template<class T>
EkfResult< T > line::infer::infer_lqn_ekf ( const std::function< std::vector< T >(const std::vector< T > &)> & hfun,
const std::vector< T > & a0,
const Matrix< T > & P0,
const Matrix< T > & Z,
const Matrix< T > & Q,
const Matrix< T > & R,
const EkfOptions< T > & opts = EkfOptions<T>() )

Extended Kalman Filter for LQN parameter identification.

Parameters
hfunobservation map, a parameter vector to an observation vector
a0(np) initial parameter estimate
P0(np x np) initial estimation-error covariance
Z(no x nsteps) measurements, one column per step
Q(np x np) parameter-drift covariance
R(no x no) measurement-error covariance
optsfilter options

Definition at line 108 of file infer_lqn_ekf.h.

References line::infer::EkfResult< T >::ahat, line::Matrix< T >::cols(), line::infer::EkfResult< T >::e, line::infer::EkfResult< T >::Ea, line::infer::EkfResult< T >::Er, line::infer::JacobianResult< T >::H, line::infer::JacobianResult< T >::h0, line::infer::EkfResult< T >::has_Ea, infer_lqn_ekf(), infer_lqn_jacobian(), line::InputError::InputError(), line::lu_factor(), line::lu_solve(), line::Matrix< T >::Matrix(), line::infer::EkfResult< T >::P, line::infer::EkfResult< T >::Phist, line::Matrix< T >::rows(), and line::infer::EkfResult< T >::zpred.

Referenced by infer_lqn(), and infer_lqn_ekf().

◆ infer_lqn_findbyname()

std::size_t line::infer::infer_lqn_findbyname ( const std::vector< std::string > & names,
const std::string & name )
inline

First element of a named LQN container matching a name.

Parameters
namescontainer of element names, in element order
namename to locate
Returns
index of the first match, or INFER_LQN_NOT_FOUND

Definition at line 49 of file infer_lqn_findbyname.h.

References infer_lqn_findbyname(), and INFER_LQN_NOT_FOUND.

Referenced by infer_lqn_findbyname(), and infer_lqn_getobs().

◆ infer_lqn_getobs()

template<class T>
std::vector< T > line::infer::infer_lqn_getobs ( const std::vector< std::string > & names,
const LqnMetrics< T > & metrics,
const std::vector< LqnObsSpec > & spec )

Observation vector of a solved LQN, z = h(a).

Parameters
nameselement names, as in LayeredNetworkStruct.names
metricsper-element metric vectors, indexed like names
specobservations to extract, in order
Returns
(numel(spec)) observation vector

Definition at line 76 of file infer_lqn_getobs.h.

References infer_lqn_findbyname(), infer_lqn_getobs(), INFER_LQN_NOT_FOUND, line::InputError::InputError(), QLen, line::infer::LqnMetrics< T >::QLen, RespT, line::infer::LqnMetrics< T >::RespT, Tput, line::infer::LqnMetrics< T >::Tput, Util, and line::infer::LqnMetrics< T >::Util.

Referenced by infer_lqn(), and infer_lqn_getobs().

◆ infer_lqn_getparams()

template<class T>
std::vector< T > line::infer::infer_lqn_getparams ( const lqn::LqnStruct< T > & lsn,
const std::vector< LqnParamSpec > & spec )

Read the current values of the parameters named in spec.

Parameters
lsnlayered struct to read
specparameters to read, in order
Returns
(numel(spec)) current values

Definition at line 98 of file infer_lqn_setparams.h.

References HOSTDEM, and infer_lqn_getparams().

Referenced by infer_lqn(), and infer_lqn_getparams().

◆ infer_lqn_jacobian()

template<class T>
JacobianResult< T > line::infer::infer_lqn_jacobian ( const std::function< std::vector< T >(const std::vector< T > &)> & hfun,
const std::vector< T > & a,
double fd_step = 1e-3,
double fd_floor = 1e-6 )

Forward finite-difference sensitivity matrix of an observation map.

Parameters
hfunobservation map, a parameter vector to an observation vector
a(np) point at which the sensitivity is taken
fd_steprelative perturbation, MATLAB's default 1e-3
fd_floorminimum absolute perturbation scale, MATLAB's default 1e-6

Definition at line 63 of file infer_lqn_jacobian.h.

References line::infer::JacobianResult< T >::H, line::infer::JacobianResult< T >::h0, infer_lqn_jacobian(), line::InputError::InputError(), line::Matrix< T >::Matrix(), and line::num_abs().

Referenced by infer_lqn_ekf(), and infer_lqn_jacobian().

◆ infer_lqn_setparams()

template<class T>
void line::infer::infer_lqn_setparams ( lqn::LqnStruct< T > & lsn,
const std::vector< LqnParamSpec > & spec,
const std::vector< T > & a )

Set the parameters named in spec to the values in a, in place.

Parameters
lsnlayered struct to mutate
specparameters to set, in order
a(numel(spec)) values, injected as exponential means

Definition at line 118 of file infer_lqn_setparams.h.

References line::lang::Distrib< T >::exp_mean(), HOSTDEM, infer_lqn_setparams(), and line::InputError::InputError().

Referenced by infer_lqn(), and infer_lqn_setparams().

◆ infer_nhpp_ks()

template<class Tv>
NhppKsResult< Tv > line::infer::infer_nhpp_ks ( const std::vector< Tv > & times,
const Tv & T,
const std::function< Tv(const Tv &)> & cumRate = std::function<Tv(const Tv&)>(),
NhppKsMethod method = NhppKsMethod::Lewis,
const Tv & T0 = num_traits<Tv>::from_int(0) )

Kolmogorov-Smirnov tests for a non-homogeneous Poisson arrival process.

Parameters
timesthe arrival times, within [T0,T]
Tthe right end of the observation interval
cumRatethe cumulative rate Lambda(t); a constant rate when empty
methodCu for the plain test, Lewis for the Durbin-transformed one
T0the left end of the observation interval

Definition at line 120 of file infer_nhpp_ks.h.

References Cu, infer_nhpp_ks(), line::InputError::InputError(), Lewis, line::infer::NhppKsResult< T >::n, line::infer::NhppKsResult< T >::pvalue, line::infer::NhppKsResult< T >::statistic, line::infer::NhppKsResult< T >::transformed, and line::infer::NhppKsResult< T >::uniforms.

Referenced by line::lang::dist_is_nhpp(), and infer_nhpp_ks().

◆ infer_qmle()

template<class T>
Matrix< T > line::infer::infer_qmle ( const Matrix< T > & Q,
const std::vector< T > & N,
const std::vector< T > & Z )

Queue-length-based maximum-likelihood estimator of the service demands of a closed queueing network.

Parameters
Q(M x R) mean queue lengths
N(R) population per class
Z(R) think time per class
Returns
(M x R) estimated service demands

Definition at line 50 of file infer_qmle.h.

References line::Matrix< T >::cols(), infer_qmle(), line::InputError::InputError(), line::NumericError::NumericError(), and line::Matrix< T >::rows().

Referenced by infer_qmle().

◆ infer_rps()

template<class T>
std::vector< T > line::infer::infer_rps ( const std::vector< T > & rt,
const std::vector< std::size_t > & cls,
const Matrix< T > & ql,
long V )

Regression for Processor Sharing (RPS) demand estimator.

Parameters
rt(n) response time samples
cls(n) class of each sample, 0-based
ql(n x R) per-class queue lengths at arrival, excluding the arriving job
Vnumber of servers of the PS station
Returns
(max(cls)+1) estimated mean service demands

Definition at line 57 of file infer_rps.h.

References line::Matrix< T >::cols(), infer_rps(), line::InputError::InputError(), line::NumericError::NumericError(), and line::Matrix< T >::rows().

Referenced by line::api::infer_minps(), and infer_rps().

◆ infer_variational()

template<class T>
VariationalResult< T > line::infer::infer_variational ( VariationalSpec< T > spec,
VariationalOptions< T > opt = VariationalOptions<T>() )

Run the variational inference procedure.

Parameters
specthe inference problem
optsolver options; defaults are derived from the specification
Returns
posterior Gamma parameters, the bound trace and the marginals

Conditional rate moments of one transition, and its observation jumps. Fills E[Xi | Y^eta=y] and exp(E[log Xi | Y^eta=y]) on the time grid, both under Q with the transition's own contribution removed.

Definition at line 501 of file infer_variational.h.

References line::infer::VariationalResult< T >::alpha, line::infer::VariationalSpec< T >::alpha0, line::infer::VariationalResult< T >::alpha_trace, line::infer::VariationalSpec< T >::arcparam, line::infer::VariationalSpec< T >::arcrate, line::infer::VariationalSpec< T >::arcs, line::infer::VariationalResult< T >::beta, line::infer::VariationalSpec< T >::beta0, line::infer::VariationalResult< T >::beta_trace, line::infer::VariationalResult< T >::bound, line::infer::VariationalSpec< T >::capacity, line::infer::VariationalResult< T >::converged, line::infer::VariationalSpec< T >::epsilon, EXTERNAL, infer_variational(), line::InputError::InputError(), line::infer::VariationalResult< T >::iter, line::Matrix< T >::Matrix(), line::infer::VariationalResult< T >::mean_service_time, line::infer::VariationalSpec< T >::nservers, line::infer::VariationalResult< T >::nu, line::infer::VariationalSpec< T >::obsData, line::infer::VariationalSpec< T >::obsRange, line::infer::VariationalSpec< T >::obsTimes, line::infer::VariationalResult< T >::qlen, line::infer::VariationalResult< T >::rates, line::infer::VariationalSpec< T >::routeprob, line::infer::VariationalSpec< T >::sched, line::infer::VariationalResult< T >::tailmass, line::infer::VariationalResult< T >::tgrid, line::infer::VariationalSpec< T >::unobserved(), line::infer::VariationalSpec< T >::x0, and line::infer::VariationalResult< T >::Y.

Referenced by infer_variational().

Variable Documentation

◆ GIBBS_NNODES

const std::size_t line::infer::GIBBS_NNODES = 2
static

The two nodes of the model the estimator assumes: delay, then queue.

Definition at line 87 of file infer_gibbs.h.

Referenced by gibbs_analyse_data(), gibbs_slice(), and infer_gibbs().

◆ INFER_LQN_NOT_FOUND

const std::size_t line::infer::INFER_LQN_NOT_FOUND = static_cast<std::size_t>(-1)
static

Returned when no element carries the requested name, MATLAB's [].

Definition at line 40 of file infer_lqn_findbyname.h.

Referenced by infer_lqn_findbyname(), and infer_lqn_getobs().