FJ_codes, the fork-join response-time-tail approximation of Z. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <string>
#include <vector>
#include "line/api/fj/fj_codes_matrices.h"
#include "line/api/fj/fj_dist2fj.h"
#include "line/api/mam/mmap_lambda.h"
#include "line/api/mam/mmapph1fcfs.h"
#include "line/util/eig.h"
#include "line/util/error.h"
#include "line/util/linalg.h"
#include "line/util/lstsq.h"
#include "line/util/matrix.h"
#include "line/util/sylvester.h"

Include dependency graph for fj_codes.h:

Classes
struct	line::fj::FjCodesT
	What computeT.m returns. More...
struct	line::fj::FjCodesPi
	What computePi.m returns. More...
struct	line::fj::FjCodesWait
	What returnWait.m returns: the waiting time as a phase-type law. More...
struct	line::fj::FjCodesPercentiles
	One line of mainFJ's output cell: the percentiles of a K-node queue. More...
struct	line::fj::FjCodesRT2
	What returnRT2.m produces, plus the waiting-time law it discards. More...

Namespaces
namespace	line
namespace	line::fj

Enumerations
enum class	line::fj::FjTMode { line::fj::Nare , line::fj::Sylvester }
	Which route computeT.m takes to the T matrix. More...

Functions
FjTMode	line::fj::fj_parse_tmode (const std::string &s)
	Parse the reference's T_Mode string, whose default is 'NARE'.
Matrix< double >	line::fj::fj_compute_t_nare (const Matrix< double > &D0, const Matrix< double > &D1, const Matrix< double > &S, const Matrix< double > &A_jump, double *residual)
	Port of computeT_NARE.m: the T matrix as the stable invariant subspace of.
FjCodesT	line::fj::fj_compute_t (const FjDist< double > &arrival, const FjDist< double > &service, const FjCodesServiceH &h, std::size_t C, FjTMode mode)
	Port of computeT.m.
std::vector< double >	line::fj::fj_boundary_solve (const Matrix< double > &pi0mat, const Matrix< double > &T)
	The boundary solve both branches of computePi.m end with:
FjCodesPi	line::fj::fj_compute_pi (const Matrix< double > &T, const FjDist< double > &arrival, const FjDist< double > &service, const FjCodesServiceH &h, std::size_t C, const Matrix< double > &S, const Matrix< double > &A_jump)
	Port of computePi.m: the all-busy boundary vector and E[n1].
FjCodesWait	line::fj::fj_return_wait (double En1, const std::vector< double > &pi0, const Matrix< double > &T, const std::vector< double > &phi, const std::vector< double > &sum_Ajump)
	Port of returnWait.m: the stationary waiting time as a phase-type law.
std::vector< double >	line::fj::fj_return_per (const std::vector< double > &vec, const Matrix< double > &A, const std::vector< double > &pers)
	Port of returnPer.m: the percentiles of a (possibly defective) phase-type law, by uniformization.
std::vector< double >	line::fj::fj_return_rt1 (const FjDist< double > &arrival, const FjDist< double > &service, const std::vector< double > &pers)
	Port of returnRT1.m: the response-time percentiles of the ONE-node queue, which are exact.
FjCodesRT2	line::fj::fj_return_rt2 (const FjDist< double > &arrival, const FjDist< double > &service, const std::vector< double > &pers, std::size_t C, FjTMode mode)
	Port of returnRT2.m: the response-time percentiles of the TWO-node fork-join queue, under the Section 4 approximation.
std::vector< FjCodesPercentiles >	line::fj::fj_main (const FjDist< double > &arrival, const FjDist< double > &service, const std::vector< double > &pers, const std::vector< std::size_t > &K, const std::vector< std::size_t > &Cs, FjTMode mode)
	Port of mainFJ.m: the response-time percentiles of a K-node fork-join queue, interpolated between the exact one-node and the approximate two-node results in log K.

Detailed Description

FJ_codes, the fork-join response-time-tail approximation of Z.

Qiu, J. F. Perez and P. Harrison, "Beyond the Mean in Fork-Join Queues: Efficient Approximation for Response-Time Tails" (IFIP Performance 2015). Third-party, BSD-3-Clause, Copyright 2015 Imperial College London; see THIRD-PARTY-NOTICES.md and python/line_solver/lib/thirdparty/fj/LICENSE.txt.

Port of the solve layer of matlab/lib/thirdparty/FJ_codes: computeT.m, computeT_NARE.m, computePi.m, returnWait.m, returnPer.m, returnRT1.m, returnRT2.m and mainFJ.m. The state-space construction is fj_codes_matrices.h.

THE METHOD IN ONE PARAGRAPH. The response-time percentiles of the ONE-node queue are exact (it is a MAP/PH/1 queue and its sojourn time is a phase-type law). The TWO-node fork-join queue is solved by the approximation of Section 4: the queue-length DIFFERENCE between the two branches is truncated at C, so the all-busy period becomes a finite-phase Markov-modulated fluid whose generator T solves a Riccati equation, and the waiting and response times come out as phase-type laws over that phase space. A K-node queue is then INTERPOLATED (Section 6) as RT_1 + (RT_2 - RT_1) * log(K) / log(2), one percentile at a time. Nothing about K enters the matrices: K appears only in that last line.

WHAT returnRT1 USES HERE. The reference calls Q_CT_MAP_MAP_1 of the QMAM toolbox for the one-node sojourn time. This port calls mmapph1fcfs_stdistr_ph, which returns the same object – the sojourn time of the MAP/PH/1 queue as a phase-type pair (alpha, A) – through BUTools' MMAPPH1FCFS, the route the Java port also takes. Both are exact for this queue, so this is a change of implementation and not of method. The Java port additionally CATCHES a failure of that solve and substitutes the raw SERVICE time PH; that is not reproduced, because a service time reported as a response time is a wrong number rather than a degraded one.

ARITHMETIC. double only. computeT_NARE needs an ORDERED real Schur factorization (the stable invariant subspace of a 2m x 2m Hamiltonian-like pencil), and both Sylvester equations in computePi are of order (C + 1) m^2 ma, which is in the hundreds to low thousands at the default C = 100 – far past what the field-generic Kronecker Sylvester solver can carry. Both are LAPACK, exactly as util/eig.h is. Callers at another arithmetic must refuse by name; solver_mam_fj.h does.

REFERENCE DEFECTS, reproduced unless stated:

mainFJ LOOPS OVER Cs AND KEEPS ONLY THE LAST. percentileRT_1 and percentileRT_2 are overwritten each iteration and only the final C survives, so a vector of accuracies costs the full solve per entry and answers for one of them. Reproduced; LINE passes a scalar.
returnRT1 IS INSIDE THAT LOOP although it does not depend on C. Reproduced, and it is why a two-entry Cs doubles the MAP/PH/1 solve.
returnRT2 COMPUTES percentileWait AND DISCARDS IT. The waiting-time percentiles are a complete result of the same phase-type pair the response time is then built from. NOT reproduced: computing an unused percentile inversion is pure cost, and the inversion is the expensive step. fj_return_rt2 returns the waiting-time PH pair instead, so a caller that wants those percentiles can invert it without a second solve.
returnPer SCANS THE INVERSE CDF ON A FIXED 0.001 GRID downwards from 3 * mean, which quantizes every percentile to a millisecond of model time regardless of the time scale of the model. Reproduced: the grid is the method's resolution and changing it would move every reported number.
returnPer CAN FALL OFF ITS OWN SCAN. If the scan reaches t = 0 without the CDF dropping below the target, temp_percentileRT keeps the value from the PREVIOUS percentile, or is undefined on the first. NOT reproduced: this port reports it by name.
computeT's Sylvester iteration HAS NO ITERATION CAP. NOT reproduced: the loop is capped and a failure to converge is reported by name rather than hanging.
THE RESIDUAL NORMS ARE PRINTED, from computeT and computeT_NARE, on every call. NOT reproduced: they are returned in FjCodesT::residual instead, because a solver that writes to stdout corrupts the CLI's JSON.

Definition in file fj_codes.h.

Classes

Namespaces

Enumerations

Functions

Detailed Description