fj_ht.h File Reference

The Heidelberger-Trivedi fork-join transform, options.config.fork_join='ht'. More...

#include <algorithm>
#include <cmath>
#include <limits>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "line/lang/qn/network_struct.h"
#include "line/solvers/mva/fj_mmt.h"
#include "line/util/error.h"

Include dependency graph for fj_ht.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::mva

Functions
template<class T>
FjMmt< T >	line::mva::fj_ht (const qn::NetworkStruct< T > &L)
	Build the H-T transform of L.
template<class T>
FjMmt< T >	line::mva::fj_fork_join_transform (const qn::NetworkStruct< T > &L, const std::string &method)
	options.config.fork_join -> the transform it names.

Detailed Description

The Heidelberger-Trivedi fork-join transform, options.config.fork_join='ht'.

Port of matlab/src/io/@ModelAdapter/ht.m (Heidelberger and Trivedi, "Queueing network models for parallel processing with asynchronous tasks", IEEE TC C-31(11), 1982). It is the second arm of the fork-join fixed point that fj_driver.h drives, beside the MMT transform of fj_mmt.h, and it answers a different question: where MMT keeps the circulating job on ONE branch and carries the remaining branches by auxiliary OPEN classes, H-T sends the circulating job STRAIGHT PAST the branches and gives every branch its own auxiliary CLOSED class, one per (forked class, branch), whose population matches the original's. The four moves are:

1. THE FORK BECOMES A ROUTER, and the ORIGINAL classes are routed from it directly to the join. The original job therefore spends no time on the branches; the whole fork-join span is charged to it as one delay at the join.
2. THE JOIN BECOMES A DELAY. Its service for the original class is the instant the join fires, E[X_(k)] * fanOut, and for an auxiliary class the residual E[X_(k)] - R_branch that branch still waits at the synchronisation point.
3. AN AUXILIARY DELAY IS ADDED PER JOIN, "Auxiliary Delay - <join>". The join routes into it and it routes back to the fork, so an auxiliary token cycles fork -> its own branch -> join -> auxiliary delay -> fork. Its service for an auxiliary class is the response time the ORIGINAL class accumulates OUTSIDE the span, which is what keeps the auxiliary token's cycle time equal to the original's.
4. ONE CLOSED AUXILIARY CLASS PER BRANCH AND PER FORKED CLASS, of the original's population, referencing the auxiliary delay. It carries the original's service demand at every station of its branch, so each branch is loaded by a population equal to the original's, which is what a fork actually generates.

WHAT IT REFUSES, by name and for the same reasons the reference does:

• tasksPerLink > 1. The transform has no way to send w identical tasks down a link, since a branch carries exactly one auxiliary class.
• an OPEN class through the fork. The auxiliary class is a ClosedClass of the original's population, and an open class has none.
• a fork with no join. H-T charges the whole span at the synchronisation point, so without one there is nothing to charge.

The synchronisation delays themselves, and the merge-back of the auxiliary columns, live in fj_driver.h: the reference keeps both arms in one fjFixedPoint, and so does this port.

Definition in file fj_ht.h.