  Machine learning (ML) models are increasingly trained in clusters with
non-dedicated workers possessing heterogeneous resources. In such scenarios,
model training efficiency can be negatively affected by stragglers -- workers
that run much slower than others. Efficient model training requires eliminating
such stragglers, yet for modern ML workloads, existing load balancing
strategies are inefficient and even infeasible. In this paper, we propose a
novel strategy called semi-dynamic load balancing to eliminate stragglers of
distributed ML workloads. The key insight is that ML workers shall be
load-balanced at iteration boundaries, being non-intrusive to intra-iteration
execution. We develop LB-BSP based on such an insight, which is an integrated
worker coordination mechanism that adapts workers' load to their instantaneous
processing capabilities by right-sizing the sample batches at the
synchronization barriers. We have custom-designed the batch sizing algorithm
respectively for CPU and GPU clusters based on their own characteristics.
LB-BSP has been implemented as a Python module for ML frameworks like
TensorFlow and PyTorch. Our EC2 deployment confirms that LB-BSP is practical,
effective and light-weight, and is able to accelerating distributed training by
up to $54\%$.
