Documentation
Library manual
Reference for the self-contained C++20 divisible-load scheduling library that powers this portal: what it is for, what it covers, how to build and use it, and how it is licensed. Concepts and notation are defined in the Knowledge base. This manual is a living document and will grow as new problem classes and solvers are added.
Instance format
Instance files are line-oriented text. Lines beginning with # are comments.
A V <value> line sets the total load and must appear first.
Each subsequent processor is one space-separated row of up to nine numbers (the last five are optional and default to zero).
Optional power, energy, and
pieces lines immediately follow the processor row they annotate and are
ignored by solvers that do not use the energy model.
The energy <a,b> ... line defines the convex piecewise
running-energy function ε(α) as a list of (intercept, slope) pairs. Each pair contributes the linear piece
intercept + slope·α; the function value at α is the maximum over all pieces. For a two-regime memory model
with in-core slope k₁ and out-of-core slope k₂ > k₁, the two pieces cross at α = B (the memory bound):
the out-of-core piece has intercept l₂ = (k₁ − k₂)·B so that l₂ + k₂·B = k₁·B.
# star-model instance: 3 workers, total load 1000 units V 1000 # β = result-return fraction; 0 = results NOT sent back to master (default) beta 0.0 # originator power: P^N = 8 W while sending, P^I = 2 W after dispatch originator 8 2 # S C A B p r d f l # start comm comp mem cst rel ddl fix lin 0.10 0.11 0.52 4000 0 0 0 0 0 # power: P^I idle P^S startup P^N network power 3 5 10 # energy ε(α): in-core piece (0 + 2·α) + out-of-core piece (−8000 + 4·α) # the two pieces cross at α = B = 4000, the cache boundary energy 0,2 -8000,4 0.20 0.21 0.22 5000 0 0 0 0 0 power 3 5 10 energy 0,2 -10000,4 0.30 0.31 0.32 1500 0 0 0 0 0 power 3 5 10 energy 0,1.5 -2250,3
Column reference
# Column reference for the processor rows # # S commStartup fixed startup latency per transfer (seconds) # C commRate transfer time per unit of load (s / unit) # A computeRate compute time per unit of load (s / unit) # B memoryLimit max load per installment; 0 or omitted = unbounded # p computeStup computation startup time per installment (s) # r releaseTime processor unavailable before this time # d deadline processor-local completion deadline; 0 = none # f fixedCost fixed cost for activating this processor # l linearCost cost per unit of load; also the default energy slope # # Lines "power i s n" and "energy a,b ..." follow the processor row # they annotate and are optional. Lines beginning with '#' are comments.
Non-star topology formats
Chain, tree and graph instances use a different format with
node and edge directives.
Node 0 is always the source. For chains and trees the load propagates from parent to children;
for graphs the solver first finds the best arborescence.
# chain: node <A> <C> (node 0 = source; its C field is unused) V 100 node 0.20 0 node 0.30 0.10 node 0.25 0.12 # tree: node <A> <C> <parent> (node 0 = root, parent = -1) V 100 node 0.20 0 -1 node 0.30 0.10 0 node 0.25 0.12 0 node 0.28 0.08 1 # graph: node <A> then edge <u> <v> <rate> (node 0 = source) V 100 node 0.20 node 0.30 node 0.25 edge 0 1 0.10 edge 0 2 0.08 edge 1 2 0.15