Knowledge base

Glossary

Terms defined here are linked to throughout the portal. Click any term from a cross-link to be brought here directly.

Total load (V)

The total amount of work to be distributed across processors. V is a continuous quantity — it may represent bytes of data, floating-point operations, or any other divisible unit. The scheduler's task is to partition V into fractions α₁, α₂, … αₙ such that Σαᵢ = V and the makespan Cmax is minimised. V does not change during scheduling; it is fixed by the problem instance.

Number of processors (N, m)

The count of available worker processors in the instance. Each processor i ∈ {0, …, N−1} has its own link (Sᵢ, Cᵢ) and compute (Aᵢ, Bᵢ) parameters. Adding more processors does not always reduce the makespan: startup overheads Sᵢ can make an additional processor counterproductive when its fraction αᵢ becomes smaller than what the startup penalty costs. The symbol m is used interchangeably with N in the thesis literature and in the FPTAS internals, where m specifically denotes the count of usable processors after filtering out those with Sᵢ > T or Aᵢ = 0.

Load fraction (αᵢ)

The portion of the total load V assigned to processor i in one installment. αᵢ is a continuous decision variable optimised by the LP for a fixed activation sequence. Processor i spends Sᵢ + Cᵢ·αᵢ time receiving its chunk and then Aᵢ·αᵢ time computing it. At the optimum all active processors finish simultaneously (the simultaneous-finish principle), which uniquely determines each αᵢ once the sequence is fixed.

Deadline (T)

The time limit used in OptV problems: the scheduler must complete as much of the load as possible by time T. T is fixed by the caller and is the primary input to the OptV solver and the FPTAS schemes. It plays the dual role of the makespan Cmax in the primal (min-makespan) problem: OptV with deadline T and OptT with load V are each other's duals — the optimum T of the primal equals the minimum T for which OptV returns V.

Approximation parameter (ε)

The precision control for the FPTAS solvers. A smaller ε gives a tighter guarantee at the cost of longer runtime. For FPTAS OptV the guarantee is Σαᵢ ≥ (1 − ε)·V_OPT: the returned load is within a factor (1 − ε) of the true optimum. For FPTAS OptT the guarantee is T_FPTAS ≤ (1 + ε)·T_OPT. Runtime grows as O(N/ε), so halving ε roughly doubles the work. ε must satisfy 0 < ε < 1; typical values are 0.05–0.1. Note: in the energy model, ε(α) denotes the running-energy function — a separate, unrelated use of the same symbol.

Half-product accumulator (g)

The running value of the half-product objective function f(x) maintained by the FPTAS dynamic program as it processes processors one by one. After selecting a subset x of the first k processors, g equals −Σ pᵢxᵢ + Σ_{i<j} qᵢrⱼ xᵢxⱼ, whose value is the negative of the load achieved by that subset. The DP seeks the representative with the smallest g at the end (most negative = most load). Each step either leaves g unchanged (xₖ = 0) or updates it by −pₖ + rₖ·Q, where Q is the accumulated startup sum.

Accumulated startup sum (Q)

The running sum Σ qᵢxᵢ = Σ Sᵢ over the processors selected so far in the FPTAS dynamic program, where qᵢ = Sᵢ (startup of processor i). Q serves as the bucketing dimension: representatives with similar Q values are grouped into the same geometric bucket and only the best (lowest g) is kept, which is what bounds the DP table size to O(m/ε). When processor k is included, Q grows by Sₖ; when excluded, Q is unchanged.

Bucket width (δ)

The geometric step size used to partition the Q axis into buckets in the FPTAS dynamic program. Defined as δ = (1 + ε)^(1/m) − 1, chosen so that (1 + δ)^m = 1 + ε exactly. Two representatives fall in the same bucket if their Q values lie in the same interval [δʲ, δʲ⁺¹). Keeping only the best representative per bucket introduces a relative error of at most δ per processor; compounded over m processors the total error stays within ε. Smaller ε → smaller δ → more buckets → more work, giving the O(m/ε) table size.

Result fraction (β)

The fraction of each processor's assigned load that must be returned to the originator after computation. If processor i computes αᵢ units, it sends back β·αᵢ units over the same single-port link. β = 0 (the default) means no result return. β > 0 adds a collection phase after all computation: the originator gathers results in installment order, and the makespan extends to include the last return transfer. β is a global instance parameter; all processors use the same fraction.

Optimal values (V_OPT, T_OPT)

V_OPT(T) is the maximum load processable within deadline T by the best possible schedule; T_OPT(V) is the minimum makespan to process load V. The two are duals: T_OPT(V_OPT(T)) = T and V_OPT(T_OPT(V)) = V. These values are generally not computable in polynomial time for heterogeneous instances with startups, which is why the FPTAS approximations exist. The FPTAS guarantees are stated relative to them: Σαᵢ ≥ (1 − ε)·V_OPT and T_FPTAS ≤ (1 + ε)·T_OPT.

Activation sequence

The ordered list of processors to which the originator sends load, one per installment. The sequence determines the communication timing: the first processor in the sequence starts receiving immediately, the second starts after the first transfer completes, and so on. For a fixed sequence the optimal load fractions are computed by an LP. The sequence is the combinatorial decision that exact solvers (branch-and-bound, MILP) optimise over; heuristics (GA, best-rate) search or construct sequences without exhaustive enumeration. A processor may appear more than once in multi-installment schedules.

Divisible load

Work that can be partitioned into arbitrarily-sized, independent pieces with no precedence between them, so any fraction can be assigned to any processor without coordination. The divisibility assumption is what allows the scheduler to optimise fraction sizes continuously rather than as a discrete job-assignment problem. Typical examples include pixel-parallel image processing, batch record transformations, Monte-Carlo sampling, and distributed tensor operations where the data can be striped across workers.

Makespan (Cmax)

The moment the last active processor finishes its share of the load. Minimising the makespan is the primary DLT objective and is denoted Cmax in the scheduling literature. The **simultaneous-finish principle** states that the optimal makespan is achieved when every active processor completes at exactly the same instant: any schedule where one processor finishes before the others is sub-optimal, because the finishing processor's fraction could have been redistributed to reduce the overall completion time.

Single-port model

The originator sends data to one worker at a time, so all outbound transfers are serialised through the single network port. Once a worker has received its full chunk it begins computing immediately, so computation on earlier workers overlaps with communication to later ones. This pipelined overlap is the source of the parallel speedup: without it, communication alone would consume the entire makespan. The single-port constraint also means that the activation order (the sequence in which workers are served) is a primary scheduling variable alongside the load fractions.

Startup latency (Sᵢ)

A fixed overhead paid once per transfer to processor i before any load data can flow, independent of the chunk size αᵢ. It models OS socket setup, MPI handshake, DMA buffer allocation, or similar protocol costs. Startup is the primary reason speedup saturates as the number of processors grows: each additional processor contributes Sᵢ of unavoidable overhead even when its assigned fraction αᵢ → 0, eventually making the communication overhead exceed the computation saving and reducing speedup.

Communication rate (Cᵢ)

The time required to transmit one unit of load to processor i; the inverse of the effective bandwidth on that link. The total transfer time for a chunk of size αᵢ is Sᵢ + Cᵢ·αᵢ. Processors on slower links (larger Cᵢ) receive smaller fractions in the optimal schedule, because spending more time on a slow transfer delays all subsequent workers. Setting Cᵢ = 0 models infinite bandwidth. This is the condition required by the FPTAS approximation schemes, which cannot handle non-zero communication time without their polynomial-time guarantees breaking down.

Computation rate (Aᵢ)

The time required to process one unit of load on processor i; the inverse of its computational speed. The computation window for chunk αᵢ is Aᵢ·αᵢ. A faster processor (smaller Aᵢ) will receive a proportionally larger fraction in the optimal schedule, since its computation finishes sooner per unit of load. The ratio Cᵢ / Aᵢ is the communication-to-computation balance. When Cᵢ / Aᵢ is large, the link is the bottleneck and the processor sits idle waiting for data. When it is small, the processor is the bottleneck.

Memory bound (Bᵢ)

The maximum load processor i can hold in a single delivery round (installment). Physically, it corresponds to the amount of data that fits in processor cache or fast local memory before the computation must spill to main memory. When the optimal fraction αᵢ exceeds Bᵢ, the chunk must be split across multiple smaller installments, each at most Bᵢ in size, delivered in successive rounds. Tight memory bounds force more complex multi-installment scheduling, typically increase the makespan, and are the main motivation for the multi-installment MILP solver.

Installment (single vs multi)

A single round of load delivery to a processor. Single-installment schedules send each worker exactly one chunk. Multi-installment schedules interleave several rounds, enabling a processor to begin computing its first installment while subsequent installments are still being transmitted. Multi-installment scheduling is necessary when memory bounds are binding (αᵢ > Bᵢ), but it is also beneficial when the network is the bottleneck: finer-grained pipelining of communication and computation can reduce the makespan even without memory constraints, at the cost of higher scheduling complexity. Note: the Solver Studio's "Max installments" control is a budget on the total chunk count for the whole schedule, not a per-processor limit — it is automatically raised to at least the number of processors, so requesting fewer than that has no effect.

Originator (master)

The source node that holds the entire load and is responsible for distributing it to workers. In the star topology the originator occupies the centre and maintains direct links to every worker. In chain, tree and graph topologies it is the root from which load flows outward through intermediate nodes. The originator's outbound port is the shared resource that all transfers contend for under the single-port constraint. In most models the originator does not compute (or computes at a separately specified rate), and its scheduling decisions consist of choosing the activation order and the load fractions.

Lower bound (LB)

A value derived analytically from the instance parameters that no feasible schedule can achieve: the optimal makespan is always at least LB. Common DLT lower bounds include the total computation work divided by the aggregate processor capacity (the computation bound), the single-port serialisation time over the total load (the communication bound), and LP relaxations of the activation-order integer program. The closer LB is to the best known schedule, the tighter the proof of near-optimality. When a solver returns both a schedule and a lower bound, the gap between them is a certificate of quality that does not require knowing the true optimum.

Optimality gap

The relative distance of a schedule from the best achievable makespan, approximated as (Cmax − LB) / LB using the lower bound. A gap of zero certifies that the schedule is provably optimal: no other feasible schedule can finish earlier. A gap of 5% means the schedule finishes at most 5% later than the theoretically achievable minimum, regardless of what algorithm produced it. The gap is the standard quality metric reported by the exact solvers and is the benchmark against which heuristics are evaluated.

Energy model

An optional cost layer that equips each worker with a four-state power machine (idle, startup, networking, running) and a convex piecewise running-energy function ε(α). When active, the scheduler can minimise total energy subject to a makespan deadline, or trace the time-energy Pareto front, identifying schedules that balance completion time against power consumption. The out-of-core regime of ε(α) (when chunk size exceeds the memory bound Bᵢ) is steeper, penalising very large chunks and favouring load distribution across more processors even at a makespan cost.

Isoefficiency / isoenergy

Isoefficiency contours are curves in the (V, m) plane along which parallel efficiency E(m) = S(m) / m is constant. They answer the scalability question: how fast must the problem size V grow, as more processors m are added, to hold efficiency above a target threshold? A sub-linear isoefficiency function (V grows slower than m) indicates good scalability. A super-linear one signals that startup overhead dominates at small scales. Isoenergy contours are the analogous curves for constant total energy, identifying the operating regions where adding processors reduces energy rather than increasing it.

Pareto front

The set of non-dominated schedules in the time-energy objective space. A schedule is on the Pareto front if no other feasible schedule achieves a shorter makespan without consuming more energy, and vice versa. A tight makespan deadline forces activation of more processors, raising idle and startup energy even as it reduces computation time; a loose deadline allows consolidation onto fewer, more cache-efficient workers. The Pareto front traces the full range of these tradeoffs, and the operator selects the operating point that best matches their power or thermal budget.

Arborescence

A directed spanning tree rooted at the originator, defining the unique paths along which load flows from the source to every worker node in a graph topology. In a star topology the arborescence is trivial (direct edges from centre to leaves). In a general graph, many distinct arborescences exist, each implying different communication costs and propagation delays. The optimal arborescence is not always the minimum spanning tree (which minimises edge-weight sum), because DLT scheduling is sensitive to the ordering and depth of nodes, not just total edge weight. The graph solver searches for the arborescence that minimises the resulting schedule length.