Compressed Coded Distributed Computing

Songze Li, Mohammad Ali Maddah-Ali, Amir Salman Avestimehr

Abstract

Communication overhead is one of the major performance bottlenecks in large-scale distributed computing systems, in particular for machine learning applications. Conventionally, compression techniques are used to reduce the load of communication by combining intermediate results of the same computation task as much as possible. Recently, via the development of coded distributed computing (CDC), it has been shown that it is possible to enable coding opportunities across intermediate results of different computation tasks to further reduce the communication load. We propose a new scheme, named compressed coded distributed computing (in short, compressed CDC), which jointly exploits the above two techniques (i.e., combining the intermediate results of the same computation and coding across the intermediate results of different computations) to significantly reduce the communication load for computations with linear aggregation (reduction) of intermediate results in the final stage that are prevalent in machine learning (e.g., distributed training algorithms where partial gradients are computed distributedly and then averaged in the final stage). In particular, compressed CDC first compresses/combines several intermediate results for a single computation, and then utilizes multiple such combined packets to create a coded multicast packet that is simultaneously useful for multiple computations. We characterize the achievable communication load of compressed CDC and show that it substantially outperforms both combining methods and CDC scheme.

Introduction: Shuffling Less, Computing More

In the world of large-scale machine learning, the bottleneck isn't always how fast your GPUs can crunch numbers—it’s how fast they can talk to each other. Whether you are training a massive ResNet-50 model or running a Hadoop cluster, "data shuffling" (moving intermediate results between nodes) can consume over 30% of total execution time.

A recent paper titled "Compressed Coded Distributed Computing" by researchers from USC and Nokia Bell Labs introduces a clever way to slash this communication overhead. By merging two previously separate strategies—data compression and coded multicasting—the authors propose a "Compressed CDC" scheme that significantly outperforms existing state-of-the-art methods.

The Bottleneck: Data Shuffling in Distributed Systems

In distributed computing frameworks like MapReduce, nodes perform "Map" tasks on local data and then must send intermediate results to other nodes for "Reduce" tasks. This "shuffling" phase is a notorious performance killer.

Two main techniques have historically been used to fight this:

  1. Compression/Combining: If a node has multiple results for the same task, it sums them up before sending. This is an "intra-task" optimization.
  2. Coded Distributed Computing (CDC): This uses redundant computation (storing the same data on multiple nodes) to create "coding opportunities." It allows a node to broadcast a single XOR-ed packet that is simultaneously useful to multiple peers. This is an "inter-task" optimization.

The gap? Traditional CDC doesn't use compression, meaning its communication load scales linearly with the number of input files ($N$). On the other hand, traditional compression doesn't exploit the multicasting benefits of coding.

The Proposed Solution: Compressed CDC

The authors propose Compressed CDC, which works in two main stages to get the "best of both worlds":

  • Repetitive Storage & Map Phase: Files are stored redundantly across nodes according to a specific pattern. Each node computes intermediate values for all functions assigned to it.
  • Stage 1: Intra-task Combining: Before sending anything, a node identifies all intermediate values it has for a single function needed by another node and sums them up into one "pre-combined" packet.
  • Stage 2: Inter-task Coding: The node then takes these pre-combined packets for different functions and jobs, splits them, and performs a bit-wise XOR (coding).
  • Multicasting: This single coded packet is broadcast to multiple nodes. Because each receiving node already has some of the "side information" (from its own local computations), it can "cancel out" what it knows to extract the specific sum it needs.

Comparative Analysis and Key Results

The most significant breakthrough is that by pre-combining results before coding, the communication load becomes independent of the number of input files ($N$). This makes the system highly scalable for truly massive datasets. The scheme specifically targets "linear aggregation" tasks, which is ideal for machine learning where distributed stochastic gradient descent (SGD) requires averaging partial gradients from many nodes.

The authors derive a closed-form expression for the communication load ($L$) of their scheme: $$L_{\text{compressed CDC}} = \frac{(1 - \mu)(\mu K + 1)}{\mu K}$$ Where $\mu$ is the fraction of data stored at each node and $K$ is the number of nodes.

In their motivating example (3 nodes, 6 files, 3 functions), standard CDC and standard compression both resulted in a communication load of 3. Compressed CDC slashed this to 1.5—a 50% reduction. Compared to using only compression, Compressed CDC reduces the load by a factor proportional to the storage size. For "low-end" nodes with small storage, this reduction scales linearly with the network size.

Limitations and Future Outlook

While powerful, the current scheme requires the "Reduce" phase to be linear (commutative and associative, like addition). While this covers many ML use cases, it wouldn't work for non-linear aggregations. Additionally, the results assume a symmetric distribution of tasks and data, which might not always be the case in heterogeneous environments. Future research may explore lower bounds for optimality and strategies to handle "stragglers" (slower nodes) in the network.

Reference: Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2018). Compressed Coded Distributed Computing. arXiv:1805.01993v1.

Summary updated

BibTeX
@inproceedings{li2018compressed,
  author = {Songze Li and Mohammad Ali Maddah-Ali and Amir Salman Avestimehr},
  title = {{Compressed Coded Distributed Computing}},
  booktitle = {ISIT},
  year = {2018},
  url = {https://openreview.net/forum?id=G80ta6DpUKV},
}
Figure