Doing more by doing less: how structured partial backpropagation improves deep learning clusters

Adarsh Kumar, Kausik Subramanian, Shivaram Venkataraman, Aditya Akella

TL;DR

This paper introduces Structured Partial Backpropagation (SPB), a novel technique that reduces the computational and memory burden of distributed deep learning training by selectively performing backpropagation on only a portion of the network layers. To fully leverage these savings, they also propose JIGSAW, a scheduler that intelligently packs SPB-aware jobs, leading to significant improvements in cluster efficiency.

What Problem Does This Paper Address?

Training large deep learning models is incredibly resource-intensive, requiring massive compute clusters with accelerators like GPUs and TPUs. This training process consumes significant compute, memory, and network bandwidth. While previous research has focused on reducing these resource demands, they often target only one bottleneck (e.g., network communication) and fail to improve overall cluster utilization, especially in multi-tenant environments. This leaves valuable resources underutilized, leading to long job queues and inefficient cluster operations. The core problem is how to make distributed deep learning training more efficient at the cluster level, not just for individual jobs, without sacrificing model quality.

Methods

The paper introduces two key innovations:

  • Structured Partial Backpropagation (SPB): This technique modifies the standard backpropagation process in distributed training. Instead of computing gradients for all layers of a neural network during the backward pass, SPB selectively computes gradients for a suffix of the layers (e.g., the last few layers). This is possible because computing gradients for a layer requires gradients from subsequent layers. By limiting backpropagation to a subset of layers, SPB simultaneously reduces:
  • Compute: Less computation is performed.
  • Memory: Intermediate outputs for non-backpropagated layers don't need to be stored.
  • Network Bandwidth: Fewer gradients need to be communicated. Crucially, SPB aims to preserve model quality by focusing on the layers that are typically updated more frequently or are more sensitive to changes.

  • JIGSAW Scheduler: SPB creates variable computational loads within a single training iteration (some workers do less work). Traditional schedulers, which treat jobs as fixed-work units and use gang scheduling (all workers in a job must finish an iteration together), cannot exploit these savings. JIGSAW is an SPB-aware scheduler designed to address this. It operates at the iteration level, allowing workers that finish early to be reassigned to other tasks. JIGSAW prioritizes tasks based on resource requirements and aims to minimize makespan (total job completion time) by intelligently packing jobs and considering task dependencies and potential migration overheads.

Datasets

The paper evaluates SPB on various deep learning models across different domains:

  • Computer Vision: Image classification on CIFAR10 and CIFAR100 datasets using models like ResNet (18, 34, 50, 101, 152), VGG (11, 16, 19), and GoogleNet.
  • Natural Language Processing (NLP): Text classification on the MR dataset and language modeling on WikiText using models like CNN-Text and LSTM.

For evaluating JIGSAW, the authors use a large-scale DLT job trace from Microsoft, enriched with profiling data for various models.

Key Insights and Ideas

  • Backpropagation is a Bottleneck: The backward pass is often more computationally and memory-intensive than the forward pass, making it a prime target for optimization.
  • Structured Pruning is Key: Unlike random or top-K gradient dropping (which primarily target network communication), SPB's structured approach to partial backpropagation directly reduces compute and memory, offering broader benefits.
  • Scheduler is Crucial for Cluster Efficiency: The real gains in cluster utilization come not just from optimizing individual jobs (SPB) but from a scheduler (JIGSAW) that understands and exploits these optimizations.
  • Iteration-Level Scheduling Unlocks SPB's Potential: By moving beyond job-level gang scheduling, JIGSAW can dynamically reassign idle workers, significantly improving resource utilization.
  • Minimal Impact on Model Quality: Despite reducing computation, SPB shows minimal degradation in model accuracy, attributed to early layers converging faster and the suffix-based approach.

Key Results

  • SPB:
    • Table 1 shows significant reductions in backward pass time and memory usage for ResNet101 as the percentage of partial backpropagation increases. For example, 20% partial backprop reduces backward pass time by ~70% and memory by ~45%.
  • Table 3 demonstrates that SPB has a minimal impact on model accuracy across various CV and NLP models, with differences typically under 2%.
  • Figure 3 shows that while increasing workers with SPB can lead to more iterations for convergence (consistent with theoretical log(k) factor), the overall convergence is still effective.
  • JIGSAW (with SPB):
    • Figure 4(a) shows JIGSAW improves makespan by approximately 22% over Tiresias and 28% over Gandiva on a 45-GPU cluster.
  • Figure 4(b) shows JIGSAW significantly improves the Cumulative Distribution Function (CDF) of Job Completion Time (JCT) compared to baselines.
  • Figure 4(c) indicates that JIGSAW has low worker migration overheads, even with iteration-level scheduling.
  • The paper claims JIGSAW can improve large-scale cluster efficiency by as high as 28%.

Limitations and Future Work

  • Theoretical Convergence Bound: The theoretical analysis shows that SPB might require a factor of log(k) more iterations to converge compared to full backpropagation, especially for convex functions. While empirical results show minimal impact, this worst-case bound is noted.
  • Warm-up Epochs: For more complex tasks or to potentially close accuracy gaps, the authors suggest using "warm-up epochs" where full backpropagation is used initially.
  • Larger Batch Sizes: The paper notes that with more workers, larger batch sizes might lead to slightly lower maximum accuracy, suggesting further investigation into this interaction.
  • Future Work: The authors implicitly suggest that further exploration of SPB's effectiveness across a wider range of models and tasks, as well as refining JIGSAW's scheduling heuristics, would be beneficial. Investigating how to further close the accuracy gap observed with more workers is also a potential area.

Summary updated

Abstract

Many organizations employ compute clusters equipped with accelerators such as GPUs and TPUs for training deep learning models in a distributed fashion. Training is resource-intensive, consuming significant compute, memory, and network resources. Many prior works explore how to reduce training resource footprint without impacting quality, but their focus on a subset of the bottlenecks (typically only the network) limits their ability to improve overall cluster utilization. In this work, we exploit the unique characteristics of deep learning workloads to propose Structured Partial Backpropagation(SPB), a technique that systematically controls the amount of backpropagation at individual workers in distributed training. This simultaneously reduces network bandwidth, compute utilization, and memory footprint while preserving model quality. To efficiently leverage the benefits of SPB at cluster level, we introduce Jigsaw, a SPB aware scheduler, which does scheduling at the iteration level for Deep Learning Training(DLT) jobs. We find that Jigsaw can improve large scale cluster efficiency by as high as 28%.
BibTeX
@inproceedings{kumar2021doing,
  author = {Adarsh Kumar and Kausik Subramanian and Shivaram Venkataraman and Aditya Akella},
  title = {{Doing more by doing less: how structured partial backpropagation improves deep learning clusters}},
  booktitle = {DistributedML@CoNEXT},
  year = {2021},
  doi = {10.1145/3488659.3493778},
}
Figure