Compendium
Knowledge base
A growing reference for divisible load theory: the model, the vocabulary, the methods and the literature. Pick a section from the menu. Terms defined in the glossary are linked throughout the portal.
Notation & symbols
All solvers and documentation in this portal share the following symbol conventions. Subscript i always refers to processor i (1-indexed); quantities without a subscript are global.
| Symbol | Name | Meaning |
|---|---|---|
| V | Total load | The amount of divisible work to distribute. V is dimensionless in the abstract model, measured in the same units as the computation rates Aᵢ, but maps to byte counts, element counts, or FLOP counts in concrete applications. All load fractions αᵢ must sum to V. |
| m | Processor count | Number of worker processors available to the scheduler. The optimal schedule may activate fewer than m processors: in the startup-free model every additional processor reduces the makespan, but with startup costs there is a crossover threshold m* beyond which adding processors increases the makespan rather than reducing it. |
| αᵢ | Load fraction | The amount of the total load V assigned to processor i. The fractions must sum to V (feasibility) and each must not exceed the memory bound Bᵢ per installment. The scheduler chooses these values, together with the activation order, to minimise the makespan or energy. |
| Sᵢ | Startup latency | A fixed overhead paid once per transfer to processor i, before any data can flow, regardless of the chunk size. It models OS socket setup, MPI handshake, or DMA buffer allocation. Nonzero startup is the primary cause of speedup saturation: each additional processor contributes Sᵢ of unavoidable overhead no matter how small its assigned fraction. |
| Cᵢ | Communication rate | Time to transfer one unit of load across the link to processor i; the inverse of the effective bandwidth on that link. The total transfer time for a chunk αᵢ is Sᵢ + Cᵢ·αᵢ. Setting Cᵢ = 0 models infinite bandwidth, the condition required by the FPTAS schemes. |
| Aᵢ | Computation rate | Time to process one unit of load on processor i; the inverse of its speed. The computation window for chunk αᵢ is Aᵢ·αᵢ. A smaller Aᵢ means a faster processor that should receive a larger share. The ratio Cᵢ / Aᵢ is the communication-to-computation balance and governs whether the network or the processor is the bottleneck. |
| Bᵢ | Memory bound | Maximum load processor i can hold in a single delivery round (installment). When the optimal αᵢ exceeds Bᵢ, the chunk must be split across multiple rounds of at most Bᵢ each. Tight memory bounds increase scheduling complexity, require the multi-installment MILP, and typically increase the makespan. |
| Cmax | Makespan | Completion time of the whole load: the finish time of the last active processor. Minimising Cmax is the primary DLT objective. The simultaneous-finish principle states that the optimal Cmax is achieved when every active processor finishes at exactly the same instant, which turns the optimisation into a linear system. |
| LB | Lower bound | A value provably at or below the optimal makespan, derived analytically from the instance parameters without solving the full scheduling problem. The gap (Cmax − LB) / LB bounds how sub-optimal any heuristic schedule can be: LB = Cmax certifies the schedule is provably optimal. |
| ε(α) | Running energy | Convex piecewise energy consumed by a processor as a function of its assigned chunk size α. In-core computation (α ≤ Bᵢ, data fits in cache) is energy-efficient and has a lower slope; out-of-core computation (α > Bᵢ, data streamed from memory) is steeper due to memory-bus traffic. Used by the energy solvers to trade off makespan against power cost. |