Heterogeneous resource matching

Why does shape mismatch cap utilization, and why does the costliest resource set the objective?

This is multi-dimensional vector packing: each task is a vector (CPU, memory, GPU, ...) and each machine a vector of capacities. Its key property is that it caps utilization by arithmetic alone.

Accelerators: the limiting case

A GPU is indivisible, and it can cost an order of magnitude or more than the rest of the host. When one resource carries most of the price, the packing objective collapses: keeping that one resource busy is the objective, and every other dimension becomes a rounding error. That is why GPU clusters will happily strand CPU and memory. It is also why:

• fractionalization (time-slicing a GPU, or partitioning it into smaller slices) is worth its complexity;
• gang scheduling and topology-aware placement (placing the tasks of one job on GPUs that are linked by fast interconnects) became mandatory rather than optional.

What the scheduler cannot name

What the scheduler allocates is only what it can name. Memory bandwidth, last-level cache and network-card queue depth are consumed but not requested, so the vector it packs is not the vector that contends, and the gap is the noisy neighbour.

Utilization is bounded by shape mismatch before it is bounded by policy. The priciest indivisible resource dictates the objective for everything around it.