SolverSSA, the para / parallel method: a port of solver_ssa_analyzer_parallel.m. More...

#include <cmath>
#include <cstddef>
#include <limits>
#include <map>
#include <string>
#include <type_traits>
#include <vector>
#include "line/lang/qn/network_struct.h"
#include "line/num/number.h"
#include "line/solvers/ssa/solver_ssa_serial.h"
#include "line/solvers/ssa/ssa_event_cache.h"
#include "line/solvers/ssa/ssa_types.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for solver_ssa_parallel.h:

Classes
struct	line::ssa::SsaParallelOptions
	The replicated engine's knobs: the serial engine's, plus the two the reference reads from options.config on this path. More...
struct	line::ssa::SsaParallelSolution< T >
	What the replicated analyzer returns. More...

Namespaces
namespace	line
namespace	line::ssa

Functions
template<class T>
SsaParallelSolution< T >	line::ssa::solver_ssa_parallel_analyzer (const qn::NetworkStruct< T > &sn, const SsaParallelOptions &opt)
	solver_ssa_analyzer_parallel.m: run R replicas of the serial engine and combine their estimates.
template<class T>
SsaParallelSolution< T >	line::ssa::solver_ssa_parallel (const qn::NetworkStruct< T > &sn, const SsaParallelOptions &opt)
	The para / parallel entry of solver_ssa_analyzer.m.

Detailed Description

SolverSSA, the para / parallel method: a port of solver_ssa_analyzer_parallel.m.

REPLICATION IS NOT A LONGER RUN. This is the whole point of the method and the one thing a reader must take from this file. The budget opt.samples is SPLIT across R independent replicas of ceil(samples/R) firings each, not multiplied by R; each replica is a complete run of the serial engine from the same initial state on its own random stream, and each produces its own time average. What is returned is the MEAN OF THE R REPLICA ESTIMATES, and the quantity that says how good it is, is the spread BETWEEN those R numbers – not the number of firings behind them. Concatenating the R sample paths and time-averaging the whole would give a similar point estimate and an error bar too small by a factor that grows with the autocorrelation of the path, which is precisely the mistake replication exists to avoid. So avg is the replica mean, *_sem is the standard error OF THAT MEAN computed across replicas with R-1 degrees of freedom, and both are reported together.

WORKER-COUNT INVARIANCE. Replica r (0-based) is seeded base_seed + r and given ceil(samples/R) firings, so its result is a function of (base_seed, samples, R) alone. The reference's header dwells on this because its earlier spmd implementation both divided the budget by, and seeded from, the RUNTIME number of workers, so the same script answered differently on two machines. Nothing here can depend on a worker count for a second reason, below.

THERE IS NO THREADING, AND THAT IS A DELIBERATE CHOICE, NOT A GAP. The replicas are run one after another in the loop below. Three reasons, in order of weight: (i) the parallelism is over REPLICAS and each replica's answer is pinned by its seed, so the returned numbers are bit-for-bit the same whether the loop is serial or spread over cores – the concurrency is an implementation detail of how long the call takes and is not part of the answer, which is exactly the property the reference had to work to recover; (ii) nothing else in this port starts a thread and the build declares no threading dependency, so introducing one here would be a build-system change made for a wall-clock gain in a solver whose cost is already the user's chosen sample budget; (iii) SsaSerialEngine holds sn by const reference and mutates nothing shared, so the loop is trivially parallelizable later by whoever wants to pay for the dependency – the estimator does not change.

WHAT THE CACHE WRITE-BACK AVERAGES. The reference averages each Cache node's realized hit and miss probabilities over the replicas with a fixed 1/R weight. That is kept, NaN and all: a replica in which a cache saw no reads reports 0/0 there, and the reference propagates it into the average rather than dropping the replica, which is the honest outcome – the estimate really is undefined when a replica contributes no reads.

DOUBLE ONLY, for the reason solver_ssa_serial.h and solver_ssa_nrm.h both give: the sample path comes out of exponential clocks drawn as -log(u)/rate and the answer's error is Monte Carlo error, not rounding.

Definition in file solver_ssa_parallel.h.

Classes

Namespaces

Functions

Detailed Description