  Deep neural networks (DNNs) are becoming progressively large and costly to
train. This paper aims to reduce DNN training costs by leveraging preemptible
instances on modern clouds, which can be allocated at a much lower price when
idle but may be preempted by the cloud provider at any time. Prior work that
supports DNN training on preemptive instances employs a reactive approach to
handling instance preemptions and allocations after their occurrence, which
only achieves limited performance and scalability.
  We present Parcae, a system that enables cheap, fast, and scalable DNN
training on preemptible instances by proactively adjusting the parallelization
strategy of a DNN training job to adapt to predicted resource changes before
instance preemptions and allocations really happen, which significantly reduces
the cost of handling these events. Parcae optimizes liveput, a novel metric
that measures the expected training throughput of a DNN job under various
possible preemption scenarios. Compared to existing reactive,
throughput-optimized systems, Parcae's proactive, live-optimized solution
considers both the throughput of a job and its robustness under preemptions. To
optimize liveput, Parcae supports lightweight instance migration and uses an
availability predictor to forecast future preemptions. It then uses a liveput
optimizer to discover an optimal strategy to parallelize DNN training under
predicted preemptions. We evaluate Parcae on a variety of DNNs and preemption
traces and show that Parcae outperforms existing spot-instance DNN training
systems by up to 10$\times$. More importantly, Parcae achieves near-optimal
performance for training large DNNs under frequent preemptions, in which case
existing approaches cannot make any progress.
