pfqn_cntol.h File Reference

Chandy-Neuse population-scaled termination cutoff for approximate MVA. More...

#include <cmath>
#include <vector>
#include "line/num/number.h"

Include dependency graph for pfqn_cntol.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Functions
double	line::pfqn::pfqn_cntol_total (double total_population)
	Termination cutoff at the given total population.
template<class T>
double	line::pfqn::pfqn_cntol (const std::vector< T > &N)
	Termination cutoff at the given population vector.
double	line::pfqn::pfqn_cntol (const std::vector< int > &N)
	Termination cutoff at the given integer population vector.
bool	line::pfqn::is_cntol (double tol)
	True when tol is the sentinel requesting the Chandy-Neuse test.

Detailed Description

Chandy-Neuse population-scaled termination cutoff for approximate MVA.

Templated port of matlab/src/api/pfqn/pfqn_cntol.m. The cutoff 1/(4000 + 16*sum(N)) is published in K. M. Chandy, D. Neuse, "Linearizer: A Heuristic Algorithm for Queuing Network Models of Computing Systems", Commun. ACM 25(2):126-134, 1982, p.129 and appendix. The iteration continues while

max_{i,r} |Q^I(i,r) - Q^{I-1}(i,r)| / N_r > 1/(4000 + 16*|N|),

|N| = sum(N). The paper motivates the scaling with |N|: at large populations removing one job changes the queue lengths very little, so a fixed cutoff would terminate the iteration prematurely. It also notes that the expression stays below 0.00025 even at very small populations.

The same expression is what LQNS uses as its termination test, set in the SchweitzerCommon constructor of libmva/src/mva.cc; that code carries no citation, and the paper above is its source.

The cutoff is a stopping rule, not an algebraic quantity, so it is a double in every arithmetic backend: it is compared against a double residual, and making it exact would not make the fixed point it selects any more exact.

Passing NaN as the tol argument of pfqn_bs / pfqn_egflinearizer selects BOTH this cutoff and the normalized-maximum metric of the paper, which is the published test; passing pfqn_cntol(N) as a plain number selects only the cutoff, with those functions' own convergence metric. NaN is the sentinel because it cannot collide with any legitimate tolerance and it is the one form the MATLAB, Java and Python twins share (MATLAB and Python additionally accept the string "cn").

Definition in file pfqn_cntol.h.