Knowledge base

What is divisible load scheduling?

A divisible load is work that can be split into arbitrarily-sized independent pieces: scanning a huge file, batch record/image processing, Monte-Carlo runs. A master streams chunks over a network to workers (single-port: one transfer at a time). Each worker must receive its chunk before it can compute it, so communication and computation overlap across workers. The goal: choose who computes how much, and in what order, to minimize the makespan, and optionally the energy.

The model

Each processor i has Sᵢ startup latency, Cᵢ communication time per unit load, Aᵢ computation time per unit load, Bᵢ memory (max load per installment). Total load is V; the makespan is the last processor's finish time. A tight lower bound brackets the optimum, so the gap (Cmax−LB)/LB shows how close a heuristic is.