The NATIVE LDES engine for LAYERED (LQN) models, the C++ twin of jline/solvers/ldes/handlers/Solver_ssj_ln.java. More...

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <deque>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include "line/lang/lqn/lqn_struct.h"
#include "line/solvers/ldes/ldes_sampler.h"
#include "line/solvers/wrappers/ldes/ldes_options.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for ldes_ln_engine.h:

Classes
struct	line::ldes::engine::LnEvent
	One scheduled event of the layered engine. More...
struct	line::ldes::engine::LnEventLater
struct	line::ldes::engine::LnLine
	One LINE of execution: a point in the activity graph of one invocation. More...
struct	line::ldes::engine::LnInv
	One invocation of an entry: what a call or a reference cycle starts. More...
struct	line::ldes::engine::LnCustomer
	A reference-task customer: it thinks, then starts an invocation. More...
struct	line::ldes::engine::LnCacheState
	Live content of one replica of a cache task, LNCacheState of the Java engine. More...
struct	line::ldes::engine::LnCacheAccess
	One ItemEntry read: its driver activity, its item law and its two branches. More...
struct	line::ldes::engine::LnResult
	The layered result: per element, the mean measures. More...
struct	line::ldes::engine::LnEntryCdf
	One entry's empirical response-time CDF: F[j] = P(R <= t[j]). More...

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

Enumerations
enum class	line::ldes::engine::ThreadState { line::ldes::engine::ACTIVE , line::ldes::engine::DELAYOFF , line::ldes::engine::OFF , line::ldes::engine::SETUP }
	Power state of one task thread, mirroring Solver_ssj_ln's THREAD_* constants. More...
enum class	line::ldes::engine::LnColumn { line::ldes::engine::QLen , line::ldes::engine::Util , line::ldes::engine::RespT , line::ldes::engine::ResidT , line::ldes::engine::Tput }
	A column of the shared layered average table, as line-cli prints it. More...

Functions
std::vector< LnEntryCdf >	line::ldes::engine::ldes_ln_cdf_respt (const LnResult &r, std::size_t nentries)
	The empirical response time CDF of every ENTRY, the getCdfRespTLN of the other codebases: one [F(t), t] table per entry in the LOCAL index space, empty where the run observed nothing.
template<class T>
bool	line::ldes::engine::ln_defined (const lqn::LqnStruct< T > &lsn, const LnResult &r, std::size_t i, LnColumn c)
	Does the element at i HAVE the quantity in column c?
template<class T>
engine::LnResult	line::ldes::ldes_ln_engine_solve (const lqn::LqnStruct< T > &lsn, const LdesOptions &o)
	Simulate a layered model in process.

Variables
static const std::size_t	line::ldes::engine::LN_NONE = static_cast<std::size_t>(-1)
	Index meaning "none" for a line, an invocation or a customer.
static const std::size_t	line::ldes::engine::NOTHR = static_cast<std::size_t>(-1)
	Thread index meaning "no thread held", also used for an infinite-thread task.
static const std::size_t	line::ldes::engine::NOTDRAWN = static_cast<std::size_t>(-1)
	LnJob::calls_left before the repetition count of a call has been drawn.

Detailed Description

The NATIVE LDES engine for LAYERED (LQN) models, the C++ twin of jline/solvers/ldes/handlers/Solver_ssj_ln.java.

IT IS A DIFFERENT SIMULATOR FROM THE FLAT ONE, not a wrapper around it. A layered model has no jobs circulating over a routing matrix: it has REFERENCE TASKS that think and then invoke an entry, ACTIVITIES that consume host demand, and CALLS that suspend the caller until the callee replies. The decomposition into layers that SolverLN performs is an APPROXIMATION; this engine simulates the layered semantics directly and is therefore the reference the layered solvers are checked against.

THE TWO RESOURCES ARE HELD AT ONCE, and that is the whole content of a layered model. An activity needs a THREAD of its task and a SERVER of its host, and it holds the thread across a synchronous call while the callee runs on a different host entirely. Releasing the thread during the call would turn every synchronous call into an asynchronous one and remove the layered contention the model exists to represent – the answer stays plausible and every utilization falls.

WHAT IT COVERS: reference tasks with think time and multiplicity; task multiplicity as a thread semaphore, with setup/delay-off power cycling; host demand on c-server processors under FCFS, LCFS, SIRO, HOL, FCFSPRIO, LCFSPRIO, FCFSPRPRIO, FCFSPIPRIO, LCFSPRPRIO, LCFSPIPRIO, PS, PSPRIO and INF, and task queueing under FCFS, LCFS, SIRO, HOL, FCFSPRIO, LCFSPRIO and INF, each served as Solver_ssj_ln serves it. The priority disciplines order by lsn.prio on the lqns scale, a LARGER number first and the default 0 lowest; HOL and FCFSPRIO are FIFO within a level, the LCFS variants LIFO; the PR/PI variants preempt, resuming the residual work (PR) or drawing a fresh demand (PI); PS is an egalitarian share min(1, c/n) of the c servers and PSPRIO gives the servers to the levels from the top down; INF never queues, whatever the multiplicity. Also synchronous calls with a mean call multiplicity, asynchronous calls and open arrivals (each a request nobody waits on), activity think times (after the demand, before the calls, holding the thread but not the processor), REPLICATION of a processor or a task, one queue per copy, and, as Solver_ssj_ln runs them:

ACTIVITY GRAPHS walked as graphs, not as a list. An entry starts at its bound activity and follows graph: one successor continues, an OR fork or a loop exit draws one branch, an AND fork splits the invocation into concurrent LINES sharing its thread, and an AND join fires on the root line once every PRE_AND input has arrived. A phase-1 activity followed by phase 2 replies early, and the thread is held through phase 2.
CACHE TASKS: one content per task replica, an ItemEntry read drawing an item from its pmf and continuing on the hit or the miss branch, the replacement rules RR/FIFO/SFIFO/LRU/HLRU/CLIMB/QLRU over the level lists, and delayed-hit retrieval (a read of an in-flight item is parked until the fetcher replies, then continues on the hit branch).
ADMISSION CONSTRAINTS A n <= b: a host row blocks a host request outside the processor (thread kept, residence running), a task row blocks a request before the task (counted nowhere), FIFO release on a departure, and a run that stops with a blocked request is reported as a deadlock.
HETEROGENEOUS SERVER POOLS on a processor, served as OI rate sharing: each pool puts its whole capacity count*rate on the first held job it serves.

An activity runs its host demand FIRST, then its think time, then its calls, as LQN2QN builds it and Solver_ssj_ln runs it. An entry's response time is its service time, from taking a thread of its task to its reply: the wait for the thread belongs to the caller's call. Its occupancy runs from the same instant to the end of its last phase.

WHAT IT REFUSES by name: every discipline the Java engine refuses (PS or preemption on a task, which holds threads and does not divide or preempt them, and any weighted discipline anywhere), a setup on an infinite-thread task, server pools on a task, a partial AND-join quorum (the Java engine waits for every input), and a cache read whose ItemEntry has no popularity or no hit/miss pair.

WHAT IT STILL DOES NOT SIMULATE, silently, as before: forwarding.

Definition in file ldes_ln_engine.h.

Classes

Namespaces

Enumerations

Functions

Variables

Detailed Description