Addressing Algorithmic Bottlenecks in Elastic Machine Learning with Chicle

Michael Kaufmann, Kornilios Kourtis, Celestine Mendler-Dünner, Adrian Schüpbach, Thomas P. ParnellarXiv 2019 · OpenReview

Abstract

Distributed machine learning (ML) training is a cornerstone of modern data center workloads, yet it often competes for resources with other applications. To optimize efficiency and utilization, training frameworks must be elastic—capable of scaling resources dynamically—and load-balanced. However, current elastic frameworks typically rely on "micro-tasks," which force high degrees of parallelism that can severely degrade algorithmic convergence. We introduce Chicle, an elastic distributed training framework that avoids the pitfalls of micro-tasks by utilizing a "uni-task" model combined with mobile data chunks. Our evaluation shows that Chicle maintains the algorithmic efficiency of rigid frameworks while providing the flexibility needed for shared, heterogeneous environments.

The Parallelism Trap in Distributed ML

In multi-tenant data centers, ML training jobs are frequently scaled up or down based on resource availability. Most existing elastic frameworks borrow techniques from general-purpose data processing (like Apache Spark), breaking work into thousands of small, independent "micro-tasks." While this approach provides scheduling flexibility, it creates a "parallelism trap" for ML algorithms like Stochastic Gradient Descent (SGD).

As parallelism increases—for instance, by using larger batch sizes or more data partitions—the model often requires more passes (epochs) over the data to reach the same level of accuracy. This algorithmic penalty means that while the system might process data faster in terms of throughput, the actual time to convergence may increase.

Figure 3: The impact of increased parallelism on convergence. As batch size (left) or number of partitions (right) increases, the number of epochs required to converge grows significantly.

For example, doubling the number of partitions in the CoCoA algorithm on the Criteo dataset can increase the epochs needed for convergence by up to 65%. Micro-tasks force a high degree of parallelism to maintain scheduling granularity, inadvertently slowing down the learning process.

The Chicle Framework

To address these bottlenecks, we developed Chicle (named after the elastic latex in chewing gum). Chicle decouples scheduling granularity from the degree of algorithmic parallelism through three core innovations:

1. Uni-tasks

Instead of many micro-tasks, Chicle runs exactly one multi-threaded "uni-task" per node. This allows the framework to keep the total degree of data parallelism as low as possible for the current cluster size, maximizing the progress made per epoch.

2. Mobile Data Chunks

The unit of scheduling in Chicle is the "data chunk"—a small, fixed-size partition of the training set. By making the data mobile rather than the tasks, Chicle can redistribute work across the cluster without increasing the number of active tasks.

3. Iterative Scheduling and RDMA

ML training is inherently iterative, consisting of local model updates followed by global synchronization. Chicle exploits the natural pauses between these iterations to move data chunks.

Figure 6: The iterative structure of distributed ML training. Chicle uses the gaps between local and global model updates to perform scheduling and data redistribution.

To ensure that moving data doesn't become a bottleneck, Chicle utilizes Remote Direct Memory Access (RDMA). This allows for zero-copy data transfers that bypass CPU overhead, making it feasible to rebalance the cluster between iterations.

Evaluation and Results

We evaluated Chicle across several benchmarks, including HIGGS (SVM), CRITEO (linear models), and CIFAR-10/FASHION-MNIST (CNNs).

  • Algorithmic Efficiency: In "scale-in" scenarios where nodes are removed, Chicle's uni-task approach converged significantly faster than micro-task emulations. Because it could dynamically reduce its batch size, it maintained higher progress per epoch.
  • Dynamic Load Balancing: In heterogeneous clusters with mixed hardware, Chicle's scheduler "learns" node performance and proactively shifts data chunks to faster nodes. This reduced iteration times by approximately 20% compared to static, non-balanced systems.
  • Performance Parity: Despite its flexibility, Chicle remains competitive with "rigid" state-of-the-art frameworks. It achieved convergence rates nearly identical to PyTorch (for CNNs) and Snap ML (for linear models), often with faster wall-clock times due to its efficient C++ implementation.

Conclusion

Chicle demonstrates that elasticity in ML does not have to come at the cost of algorithmic convergence. By moving data instead of tasks and respecting the iterative nature of ML, Chicle provides a path toward highly efficient, shared-resource training. Future work will explore automatic tuning of parallelism levels and mitigating synchronous bottlenecks caused by extreme stragglers.

Summary updated

Abstract

Distributed machine learning training is one of the most common and important workloads running on data centers today, but it is rarely executed alone. Instead, to reduce costs, computing resources are consolidated and shared by different applications. In this scenario, elasticity and proper load balancing are vital to maximize efficiency, fairness, and utilization. Currently, most distributed training frameworks do not support the aforementioned properties. A few exceptions that do support elasticity, imitate generic distributed frameworks and use micro-tasks. In this paper we illustrate that micro-tasks are problematic for machine learning applications, because they require a high degree of parallelism which hinders the convergence of distributed training at a pure algorithmic level (i.e., ignoring overheads and scalability limitations). To address this, we propose Chicle, a new elastic distributed training framework which exploits the nature of machine learning algorithms to implement elasticity and load balancing without micro-tasks. We use Chicle to train deep neural network as well as generalized linear models, and show that Chicle achieves performance competitive with state of the art rigid frameworks, while efficiently enabling elastic execution and dynamic load balancing.
BibTeX
@misc{kaufmann2019addressing,
  author = {Michael Kaufmann and Kornilios Kourtis and Celestine Mendler-Dünner and Adrian Schüpbach and Thomas P. Parnell},
  title = {{Addressing Algorithmic Bottlenecks in Elastic Machine Learning with Chicle}},
  year = {2019},
  eprint = {1909.04885},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.04885},
}
Figure