ldes_ln_engine.h File Reference

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:

Go to the source code of this file.

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::LnJoin
	Progress of one AND join within one invocation, JoinProgress of the Java engine. 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?
Rng	line::ldes::engine::ln_rng (long long seed, long long offset)
	The generator of one LN stream, seeded from a HASH of (run seed, offset).
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::uint64_t	line::ldes::engine::LN_ANYFORK = static_cast<std::uint64_t>(-1)
	Fork instance meaning "any": the late inputs of a join fed by more than one fork instance.
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, or once quorum of them have on a QUORUM join, whose late inputs still run, holding the thread, and are discarded at the join. A phase-1 activity followed by phase 2 replies early, and the thread is held through phase 2; the main line reaching a leaf replies there even while other lines of the invocation still run.
• FORWARDING: an entry that would reply to a synchronous request hands it, with the forwarding probability, to the target entry instead, and the original caller stays blocked until the end of the chain replies.
• 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, except a cold start, which is charged to the request that waited through it. Its occupancy runs from the same instant to the end of its last phase. Task, entry and activity Util are DERIVED as Solver_ssj_ln derives them (throughput times host demand, over the host multiplicity); the measured busy threads are in UThreadLN.

THE RUN IS COUNTED IN ACTIVITY COMPLETIONS and its first 20% are WARMUP, which is Solver_ssj_ln's rule: the budget samples (or events) is a number of activity completions, and at completion floor(0.2*budget) every statistic is reset. A time integral (QLen, Util) restarts from that instant, so a request straddling the reset contributes its part after it. A per-observation measure (a completion, a response time, a host residence, a cache read and its outcome) counts only the observations of the requests whose ROOT began after the reset: a reference cycle or an open arrival started after it, and every call, fork branch, forward and asynchronous request those spawn. A cycle straddling the reset is thus counted nowhere, at its request and at every one of its activities and calls alike, which keeps the flow-balance identities (an activity run once per cycle has the cycle's throughput) exact rather than one cycle off. Every rate is over the measured span.

PROCESSOR UTIL IS THE TOTAL OVER THE REPLICAS, per server of one replica: the busy servers of all copies over the multiplicity, so U = X*D/m with X the total throughput. That is Solver_ssj_ln's table and SolverLN's (which scales one representative replica by REPL), and it exceeds 1 when a replicated processor is more than 1/REPL busy.

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 (both as the Java engine refuses them), a partial-quorum join that the main line of the invocation could reach as a late input, and a cache read whose ItemEntry has no popularity or no hit/miss pair.

Definition in file ldes_ln_engine.h.