fj_tag.h File Reference

Port of matlab/src/api/fj/sn_fj_validate.m and matlab/src/io/@@ModelAdapter/fjtag.m: the model-to-model transform that makes a closed fork-join network EXACTLY solvable by a Markov chain. More...

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

Include dependency graph for fj_tag.h:

Go to the source code of this file.

Classes
struct	line::qn::FjTagged< T >
	The augmented struct and everything needed to read its results back. More...

Namespaces
namespace	line
namespace	line::qn

Functions
template<class T>
void	line::qn::sn_fj_validate (const NetworkStruct< T > &sn)
	Port of sn_fj_validate: is this fork-join model inside the exact solver's reach?
template<class T>
std::string	line::qn::sn_fj_supports (const NetworkStruct< T > &sn)
	Can the exact fork-join construction be asked for this model?
template<class T>
FjTagged< T >	line::qn::fj_tag (const NetworkStruct< T > &sn)
	Port of ModelAdapter.fjtag.

Detailed Description

Port of matlab/src/api/fj/sn_fj_validate.m and matlab/src/io/@@ModelAdapter/fjtag.m: the model-to-model transform that makes a closed fork-join network EXACTLY solvable by a Markov chain.

WHY A TRANSFORM AND NOT A JOIN HANDLER. A join must release one parent job once ALL siblings of THAT parent have arrived. A per-class count vector at the join cannot express "of that parent": with two parents outstanding and two branches, the counts (1,1) are consistent both with one sibling from each parent (nothing may join) and with both siblings of one parent (a join must fire). Any solver that reads only counts has to guess, and guessing is what makes a join an approximation.

WHAT THE TRANSFORM DOES. For each (fork f, class r) with matched join j, each branch b = 1..B and each TAG t = 1..T, it mints an auxiliary closed class A(f,r,b,t) with population 0. The tag names the parent job. A fork firing consumes one parent held at the fork and emits one sibling per branch in the classes of ONE tag – the lowest free one – and the join fires only when every branch of some tag is present. Identity matching is then exact even when siblings overtake one another, and the price is B*T extra classes per (fork, class): the state space grows accordingly, which is why this is the exact solver's route and fj_mmt remains the mean-value one.

WHY T IS THE CHAIN POPULATION AND NOT THE CLASS POPULATION. Class switching OUTSIDE the fork-join section can concentrate the whole chain in class r – a class switch on the edge into the fork does exactly that – so the number of concurrently outstanding forked jobs is bounded by the chain, not by the declared population of r.

WHY THE LOWEST FREE TAG. Tags are interchangeable, so without a canonical choice each firing would produce T! equivalent successors and the chain would carry a permutation group's worth of duplicate states. Allocating the lowest free tag makes exactly one fjsync entry enabled per (fork, class) in any state.

HOW THIS DIFFERS FROM THE REFERENCE'S ROUTE. fjtag.m copies the Network OBJECT, adds ClosedClass objects, re-links it and calls getStruct. Here the transform is applied to the refreshed NetworkStruct directly, as tag_chain and fj_mmt already are: the auxiliary routing is written into P and one refresh_struct() re-derives the chains, capacities and rt. The post-edits that follow are the reference's own – it overrides the visits and the auxiliary capacities after getStruct for the same reason, because the engines read them only as a zero-versus-nonzero support gate.

Definition in file fj_tag.h.