fj_codes_matrices.h File Reference

The state-space construction of FJ_codes, the fork-join response-time-tail approximation of Z. More...

#include <cstddef>
#include <vector>
#include "line/api/fj/fj_dist2fj.h"
#include "line/api/mam/mmap_lambda.h"
#include "line/util/error.h"
#include "line/util/linalg.h"
#include "line/util/matrix.h"

Include dependency graph for fj_codes_matrices.h:

Go to the source code of this file.

Classes
struct	line::fj::FjCodesServiceH
	build_Service_h.m: the two-subtask phase process of one fork-join job. More...
struct	line::fj::FjCodesSA
	build_SA.m: the level-constant generator and the head-of-line jump. More...
struct	line::fj::FjCodesGenService
	generateService.m: the service process seen by a tagged job. More...
struct	line::fj::FjCodesSRK
	constructSRK.m: the extended generator and the busy/idle projectors. More...

Namespaces
namespace	line
namespace	line::fj

Functions
Matrix< double >	line::fj::fj_build_index (std::size_t m, std::size_t cr)
	Port of build_index.m: the compositions of cr into m non-negative parts, one per row, in the reference's own order.
std::size_t	line::fj::fj_vectmatch (const std::vector< double > &row, const Matrix< double > &matrix)
	Port of vectmatch.m: the row of matrix equal to row.
Matrix< double >	line::fj::fj_restart_matrix (const FjDist< double > &service)
	The reference's A = -sum(ST, 2) * tau_st: complete, then restart.
FjCodesServiceH	line::fj::fj_build_service_h (const FjDist< double > &service)
	Port of build_Service_h.m.
FjCodesSA	line::fj::fj_build_sa (const FjDist< double > &service, const FjCodesServiceH &h, std::size_t C)
	Port of build_SA.m.
void	line::fj::fj_busy_to_idle (const FjDist< double > &service, const FjCodesServiceH &h, const Matrix< double > &idle_phases, Matrix< double > &S_long, Matrix< double > &S_last)
	The busy-to-not-busy blocks S_long and S_last, shared verbatim by generateService.m and constructSRK.m.
FjCodesGenService	line::fj::fj_generate_service (const FjDist< double > &service, const FjCodesServiceH &h, std::size_t C, const Matrix< double > &S)
	Port of generateService.m.
Matrix< double >	line::fj::fj_construct_not_all_busy (std::size_t C, const FjDist< double > &service, const FjCodesServiceH &h)
	Port of constructNotAllBusy.m.
FjCodesSRK	line::fj::fj_construct_srk (std::size_t C, const FjDist< double > &service, const FjCodesServiceH &h, const Matrix< double > &S)
	Port of constructSRK.m.

Detailed Description

The state-space construction of 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 build_index.m, vectmatch.m, build_Service_h.m, build_SA.m, generateService.m, constructSRK.m and constructNotAllBusy.m from matlab/lib/thirdparty/FJ_codes. The solve layer is fj_codes.h.

THE STATE SPACE. The algorithm analyses the TWO-node fork-join queue exactly (Section 4 of the paper) and interpolates to K nodes (Section 6). Its phase process tracks, for the job at the head of the two branches, the service phase of the subtask in the LONGER queue and of the subtask in the SHORTER one, together with c, the difference in queue length between the two branches, truncated at C. A phase is therefore a pair of unit count vectors [e_long, e_short] of length m each, and the level is c in 0..C; S is the generator of phase changes at constant c, A_jump collects the transitions on which the head job leaves and the next one enters.

WHY COUNT VECTORS AND NOT PHASE INDICES. The reference indexes every phase by a length-2m vector of counts summing to two (one per branch) and finds the target of a transition with a linear search, vectmatch. For the two-node queue this is a bijection with the pair (i, j), and a direct index would be faster. It is reproduced because the transition builders multiply by countvect(i), the MULTIPLICITY of the source phase, and that factor is where a general-K generalisation of the same code would differ from a pair encoding; dropping the representation would silently drop the factor.

ARITHMETIC. double only, in step with the solve layer: the T matrix needs an ordered real Schur factorization and the two Sylvester equations need Bartels-Stewart, all LAPACK. The construction itself is exact rational arithmetic on the descriptors, but a Matrix<T> construction feeding a double-only solve would only move the conversion one call inwards.

Definition in file fj_codes_matrices.h.