Source-linked AI summary
TicTac: Accelerating Distributed Deep Learning with Communication Scheduling
Sayed Hadi Hashemi, Sangeetha Abdu Jyothi, Roy H. Campbell
TL;DR
Distributed deep learning needs better communication scheduling because parameter transfers can arrive in random orders across workers, increasing iteration-time variability. TicTac uses prioritization and critical-path-based heuristics to enforce near-optimal transfer schedules in Parameter Server systems without changing models or developer inputs. The system reports throughput gains of up to 37.7% in inference and 19.2% in training, while reducing straggler effect by up to 2.3×.
Problem
Distributed deep learning iteration time depends on computation, communication, and their overlap, but graph-based systems can receive parameters in random orders across workers.
Method
TicTac uses critical-path analysis, operation priorities, and TIC and TAC heuristics to derive and enforce near-optimal parameter-transfer schedules.
Results
20% improvement in iteration throughput can save significant compute power for typical DNN training jobs running days to weeks.
Takeaways & Limitations
Communication scheduling can provide significant gains across varied workloads, including throughput improvements without model or developer-input changes.
Takeaways & Limitations
The comparison with one prior strategy was excluded because its performance was inconclusive and its order-extraction method could not be reimplemented.
Abstract
from arXiv · showhide
State-of-the-art deep learning systems rely on iterative distributed training to tackle the increasing complexity of models and input data. The iteration time in these communication-heavy systems depends on the computation time, communication time and the extent of overlap of computation and communication. In this work, we identify a shortcoming in systems with graph representation for computation, such as TensorFlow and PyTorch, that result in high variance in iteration time --- random order of received parameters across workers. We develop a system, TicTac, to improve the iteration time by fixing this issue in distributed deep learning with Parameter Servers while guaranteeing near-optimal overlap of communication and computation. TicTac identifies and enforces an order of network transfers which improves the iteration time using prioritization. Our system is implemented over TensorFlow and requires no changes to the model or developer inputs. TicTac improves the throughput by up to $37.7\%$ in inference and $19.2\%$ in training, while also reducing straggler effect by up to $2.3\times$. Our code is publicly available.
1 INTRODUCTION
Distributed deep learning iteration time is shaped by computation, communication, and their overlap, but graph-based systems can receive parameters in arbitrary orders that create blockage and stragglers. TicTac addresses this with resource-aware scheduling, near-optimal transfer heuristics, and TensorFlow enforcement without model changes.
- Distributed training is needed because sophisticated models exceed the capabilities of a single high-end machine and can run for days to weeks.
- Iteration time depends on computation, communication, and their overlap, while parameter dependencies determine whether transfer schedules accelerate or block computation.
- Random parameter-transfer orders in current graph-based systems produce high iteration-time variance and can give workers different schedules, causing synchronized-training stragglers.
- Earlier approaches enforced common transfer orders in layer-by-layer systems, whereas finding an effective order is non-trivial with modern DAG representations.
- TicTac derives near-optimal transfer schedules through critical-path analysis and enforces them with a lightweight TensorFlow mechanism, requiring no model or developer-input changes.
- TicTac contributes a scheduling-efficiency metric and two heuristics, TIC and TAC, for parameter-server computation and communication scheduling.
- 37.7% throughput improvement was achieved with realistic workloads across GPU and high-end CPU environments under DNN training and inference.
2 BACKGROUND AND MOTIVATION
DAG-based distributed deep learning systems suffer from unpredictable parameter-transfer ordering, which can block computation and vary iteration times. TicTac targets predictable communication-computation overlap in Parameter Server systems.
- Scope: TicTac is designed for DAG-based Model Replica training with Parameter Servers and does not address decentralized aggregation systems such as all-reduce or Horovod.
- Opportunity for Optimization: DAG-based TensorFlow and PyTorch systems cannot generally reuse layer-by-layer ordering optimizations because finding effective schedules is non-trivial.
- Network Optimization in DNN training: TicTac focuses on better, predictable communication-computation overlap in Parameter Server systems, while leaving communication-time optimization orthogonal.
- Network Optimization in DNN training: Random parameter-transfer ordering can block computation, underutilize resources, and create straggling through iteration-time variation.
3 SCHEDULING EFFICIENCY
The scheduling problem seeks feasible network-transfer orders that improve overlap and minimize iteration makespan. TicTac evaluates schedules with bounds-based efficiency measures, while device assignment remains outside scope.
- Scheduling Problem: The scheduling objective is to find a network-transfer order that minimizes iteration time by improving communication-computation overlap.
- Scheduling Problem: The scheduler uses priority numbers to restrict execution to feasible topological orders that improve iteration performance.
- Scheduling Problem: Optimal scheduling maps to a dependency-constrained job-shop problem and is NP-hard, motivating an approximate heuristic solution.
- Scheduling Efficiency Metric: Scheduling Efficiency measures scheduling effects and makespan variation relative to upper and lower makespan boundaries.
- Scheduling Efficiency Metric: The upper makespan bound assumes sequential resource use, whereas the practical makespan can be lower when computation and communication run in parallel.
- Scheduling Efficiency Metric: E = 1 indicates perfect ordering, and E = 0 indicates the worst ordering.
- Scheduling Efficiency Metric: Speedup S(G,Time) is the maximum theoretical performance speedup of the best schedule relative to the worst schedule.
- Scheduling Efficiency Metric: S = 0 indicates no scheduling benefit, while S = 1 indicates double the throughput; benefits are limited by a significantly slower bottleneck resource.
4 SCHEDULING ALGORITHMS
TicTac uses DAG dependencies and optional execution-time estimates to prioritize parameter transfers for better communication–computation overlap. TIC ignores operation times, while TAC incorporates them and resolves ordering through a comparator.
- TIC: TIC prioritizes recv ops using only computational-DAG dependencies, treating all operations as having equal cost.It favors transfers that impose the least blocking on computation.
- TAC: TAC prioritizes transfers using both estimated operation times and dependencies in the computational DAG.This targets schedules with greater communication–computation overlap.
- Shared scheduling framework: The algorithms derive communication dependencies by traversing the DAG and update properties for outstanding recv operations.The input includes a partitioned graph, time oracle, communication channels, and outstanding recv set.
- Scheduling properties: Communication time M equals a recv transfer’s duration or, for other operations, the total time of outstanding dependent transfers.These properties quantify how transfer choices affect computation blocking and pending communication.
- Scheduling properties: Directly-Dependent Compute Load P measures computation unlocked by completing one outstanding recv, excluding computation requiring other outstanding recvs.Impending Communication Load M+ estimates the minimum communication needed to activate computation with multiple recv dependencies.
- TIC: TIC uses a generic oracle assigning equal cost to communication operations, whereas its priority is based on impending communication load M+.The resulting schedule is generated without operation timing measurements.
- Comparator: The comparator first favors ordering choices associated with greater overlap and then uses impending transfers to shorten computation blocking when overlap is equal.Its authors note the comparator is an approximate induction, though it is transitive and supports partial ordering.
- Ordering procedure: The ordering algorithm repeatedly updates properties, selects the smallest recv under the comparator, and assigns it higher priority than the remaining transfers.This process continues while outstanding recv operations remain.
5 SYSTEM DESIGN
TicTac separates tracing, timing estimation, ordering, and enforcement to compute and impose worker-specific transfer priorities. It uses offline TIC or TAC schedules and enforces them at the sender before transfers enter TensorFlow’s gRPC layer.
- Architecture: The system comprises tracing, time-oracle estimation, ordering, and enforcement modules.These components form the system design shown in Figure 5.
- Tracing and timing: The tracing module collects runtime statistics that feed the time-oracle estimator.The time oracle estimates each operation’s runtime from execution timing data.
- Ordering: TAC schedules use time-oracle estimates and DAG structure, whereas TIC schedules use the DAG alone.The ordering wizard computes priorities offline, and all iterations follow the same order.
- Enforcement: The enforcement module receives the computed priority list and applies it to network transfers on each worker.Priorities are assigned sequential integers representing how many transfers must complete first.
- Implementation: TicTac implements its components over TensorFlow, including extensions for measuring network-transfer timing and offline TIC and TAC analyzers.The implementation includes TensorFlow tracer, analyzer, and gRPC enforcement changes.
- Transfer path: gRPC uses one channel per worker–parameter-server pair, with transfers serialized so only one transfer is active per channel.A transfer begins after a receiver request and corresponding sender operation become active.
- Enforcement: Enforcement occurs at the sender before gRPC transmission, avoiding conservative DAG dependencies that would prevent pipelining.Ordering recv or send activation alone is insufficient because ordering can change during dataflow.
- Limitation: gRPC occasionally violates queued transfer order; in Inception, this occurred in 0.5% of TIC cases and 0.4% of TAC cases.The paper reports that these occurrences were very few but could affect performance.
6 RESULTS
TicTac improves distributed deep learning performance by scheduling parameter transfers to increase computation–communication overlap and reduce variability from arbitrary transfer orders. Across tested environments and workloads, scheduling improves throughput, efficiency, and straggler behavior, with benefits depending on model and system scale.
- Evaluation setup: TicTac does not alter computational flow or training accuracy, and its heuristics are computed before execution without adding runtime overhead.The evaluation uses ImageNet and reports less than 3% difference between synthetic and real data iteration time on a single machine.
- Throughput: 37.7% throughput speedup is obtained across networks when scaling workers with the parameter-server-to-worker ratio fixed at 1:4.Gains are measured against no scheduling and vary with communication load, computation load, overlap opportunity, and model characteristics.
- Throughput: Higher gains generally occur for larger networks and during inference when scaling the number of parameter servers with eight workers in envG.TicTac remains beneficial even with multiple parameter servers.
- Performance consistency: Scheduling reduces iteration-time variance: with TAC, step time is reduced and variance is minimal, while unscheduled runs show large variance.The baseline's random parameter-transfer order is identified as the main source of iteration-time variation.
- Scheduling efficiency: Scheduling efficiency approaches 1 across models, environments, training, and inference with TIC, indicating near-optimal scheduling.TAC achieves an R^2 score of 0.98 when its efficiency metric predicts step time for Inception v2 training in envC.
- Straggler mitigation: Enforcing any transfer order reduces straggler effects, with larger benefits in bigger DNNs; arbitrary ordering can make workers wait over 50% of an iteration.Stragglers arise from system-level variation and scheduling efficiency on individual workers.
7 CONCLUSION
The paper demonstrates that communication scheduling can produce substantial gains in distributed deep learning. It reports that a 20% improvement in iteration throughput for long-running DNN training can save significant compute power, while motivating broader scheduling research.
- Conclusion: 20% improvement in iteration throughput for DNN training lasting days to weeks can save significant compute power.The conclusion presents this as the practical significance of the reported throughput gains.
- Future work: The study motivates further work on parameter-server scheduling, all-reduce transfer patterns, network-fabric congestion, memory, and storage.These are identified as directions for extending the scheduling approach.
A DNN MODELS
The evaluation uses ten deep learning models characterized by parameter count, parameter size, operation counts for inference and training, and standard batch size.
- Model characteristics: 10 deep learning models are used in the evaluation.Table 1 reports each model's parameter count, aggregate parameter size, inference and training operation counts, and standard batch size.
B TIC VS. TAC
TIC and TAC both provide significant throughput speedups over no scheduling in envC. TIC is comparable to TAC, suggesting current models can benefit without runtime statistics.
- TIC versus TAC: TIC and TAC both offer significant throughput speedup compared with the no-scheduling baseline in envC.The comparison is plotted for both scheduling schemes with and without scheduling.
- TIC versus TAC: TIC performance is comparable to TAC, indicating improved performance without relying on runtime statistics for current models.TIC is selected as the representative cloud-GPU algorithm because of its simplicity.