LINE Solver (C++)
Templated C++ port of the LINE queueing solver
Loading...
Searching...
No Matches
lqn2qn.h File Reference
Interchange formats

Convert a layered queueing network into a single queueing network in which synchronous call blocking is carried by REPLY signals. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "line/lang/lqn/lqn_reader.h"
#include "line/lang/lqn/lqn_struct.h"
#include "line/lang/lqn/lqn_writer.h"
#include "line/lang/qn/network_builder.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
Include dependency graph for lqn2qn.h:

Go to the source code of this file.

Namespaces

namespace  line
 Conservation laws of a layered queueing network, enumerated from its structure.
namespace  line::io

Functions

template<class T>
qn::Network< T > line::io::lqn2qn (const lqn::LqnModel< T > &lqn, const std::string &replication="auto", const std::string &name="model", std::vector< std::string > *warnings=nullptr)
 Port of MATLAB LQN2QN(lqn, replication): flatten a layered network into a queueing network whose synchronous calls block through REPLY signals.
template<class T>
qn::Network< T > line::io::lqn2qn (const lqn::LqnStruct< T > &lsn, const std::string &replication="auto", const std::string &name="model", std::vector< std::string > *warnings=nullptr)
 LQN2QN over an already flattened LqnStruct.

Detailed Description

Convert a layered queueing network into a single queueing network in which synchronous call blocking is carried by REPLY signals.

Port of matlab/src/io/LQN2QN.m (the reference), mirrored by jar/src/main/java/jline/io/LQN2QN.java and python/line_solver/io/__init__.py. The construction is the reference's, step for step, and so is the order in which nodes and classes are created, so that a model converted here and one converted by MATLAB or Python have the same node and class tables:

  • One station per host processor replica (a Delay when the processor is an infinite server), one Delay per reference task replica for its think time.
  • One class per STEP of the expanded activity graph: an activity, one call stage of an activity, or a merge/trigger step. Reference-task steps are closed classes of population 0, except the think class, which carries the task multiplicity; open-arrival steps are open classes.
  • A synchronous call site that holds its caller's server gets a REPLY signal bound to its class (sn.syncreply); the callee's replying step switches into that signal, which returns to the caller station and releases the server.
  • A call mean m is unrolled into floor(m) mandatory stages plus one stage taken with probability m - floor(m), capped at 20 stages.
  • OR branches and loops follow the graph weights; AND forks become a Fork plus one Router per branch and AND joins a Join, with a PARTIAL strategy when the declared quorum is below the branch count.
  • A CacheTask becomes a Cache node whose read step switches into the hit and the miss class; delayed-hit retrieval adds a PS fetch station per replica.
  • Asynchronous calls are non-blocking visits, forwarding splits the reply exits of the forwarding entry, and the multiplicity of a non-reference task is a thread pool enforced by one finite capacity region with one linear admission row per task replica.
  • Phase-2 activities run after the reply, spawned by the replying step's completions (sn.classspawn) and destroyed at the chain end by a NEGATIVE signal (closed chains) or at the Sink (open chains).
  • Activity think times are steps on a shared ActivityThink delay; setup tasks carry their setup/delay-off pair onto their host station.
  • Replication is materialised (one station and one step-graph copy per replica, calls reaching the fan-out block {(i*f+k) mod r}) or pooled (one station of r times the servers), selected by 'auto', 'materialize' or 'pool' exactly as in the reference.

REPLIES. The reference reads which activity replies to which entry from lsn.replygraph, which holds the EXPLICIT replies plus the implicit ones getStruct.m infers for leaf activities. The C++ LqnStruct keeps no replygraph, so the LqnModel overload recovers it with lqn::detail::reply_activities, the port of that same pass. The LqnStruct overload can only infer the implicit replies: an entry whose reply is declared on a non-leaf activity, which is what a phase-2 activity is, needs the LqnModel overload.

Construction choices that are the reference's own and not yet represented there either (retrieval on a cache read with phase-2 successors, the thread pool of a task with an internal AND-fork, and the others listed in LQN2QN.m) are reported as warnings, exactly where the reference calls line_warning.

Definition in file lqn2qn.h.