TL;DR
This paper introduces OPER, a novel system and algorithm for efficiently parallelizing massive embedding tables (EMTs) in deep learning recommendation models (DLRMs). By intelligently exploring the trade-offs between memory, computation, and communication, OPER achieves significant speedups in both training and inference, outperforming existing state-of-the-art frameworks.
What Problem Does This Paper Address?
Deep learning recommendation models (DLRMs) are crucial for many online services, but they rely on enormous embedding tables (EMTs) that can contain billions of parameters. Training and serving these models efficiently on multi-GPU systems is a major challenge. Existing approaches often parallelize EMTs in a coarse-grained manner, leading to unbalanced workloads and communication bottlenecks. This paper addresses the problem of finding an "optimality-guided" parallelization strategy for EMTs that balances memory consumption, computation, and inter-GPU communication, thereby maximizing performance for large-scale DLRMs.
Methods
OPER employs a two-pronged approach:
- Optimality-Guided Heuristic Algorithm: This algorithm aims to find a near-optimal EMT parallelization strategy. It starts by adaptively partitioning EMTs based on access frequency and memory footprint to reduce the search space. Then, it uses a heuristic hierarchical search to balance model parallelism (distributing partitions across GPUs) and data parallelism (duplicating frequently accessed partitions). This approach is designed to be efficient and approximate the optimal solution.
- System Implementation with Distributed Shared Memory: To support the fine-grained parallelization identified by the algorithm, OPER implements a unified EMT abstraction built on a distributed shared memory architecture (NVSHMEM). This allows for efficient, per-embedding communication and computation. Key system-level optimizations include an "all-in-one" lookup kernel that consolidates operations and a local-remote lookup overlapping technique to hide communication latency. For training, a novel "local-aggregated sparse AllReduce" primitive is introduced to optimize gradient synchronization.
Datasets
The paper evaluates OPER on three widely adopted real-world DLRM datasets:
- Avazu
- Criteo Terabyte
- Criteo Kaggle
Additionally, to test performance on larger-scale, multi-node settings, they generated two synthetic datasets:
- Syn_Small
- Syn_Large
These synthetic datasets are designed to mimic the power-law distribution of embedding access frequencies observed in real-world DLRMs.
Key Insights and Ideas
- Input-Dependent Parallelization is Crucial: The paper highlights that the skewed and input-dependent access patterns of EMTs are the primary reason why coarse-grained parallelization fails. OPER's success stems from its ability to leverage this input information.
- Trade-off Between Granularity and Complexity: Achieving optimal parallelization at the individual embedding level is ideal but computationally prohibitive. OPER finds a "sweet spot" by adaptively partitioning EMTs and using a heuristic search.
- Unified Abstraction Simplifies Fine-Grained Parallelism: The "all-in-one" EMT abstraction, built on distributed shared memory, is key to efficiently managing the complex communication patterns required by fine-grained parallelization.
- Data Parallelism Needs Careful Consideration for Training: While data parallelism can reduce communication, it increases memory usage and requires efficient gradient synchronization. OPER's frequency-aware data parallelism for training addresses this.
Key Results
- Significant Speedups: OPER achieves average speedups of 2.3x in training and 4.0x in inference over state-of-the-art DLRM frameworks.
- Outperforms Baselines: OPER consistently outperforms DLRM, TorchRec, and HugeCTR across various datasets and GPU configurations. For example, it achieves up to 6.6x speedup in inference and 2.4x in training over HugeCTR.
- Balanced Performance: OPER demonstrates near-optimal performance across memory balance, lookup workload balance, and communication balance, a feat not achieved by other methods.
- Efficient Search: The heuristic algorithm finds near-optimal solutions in minutes, significantly faster than MILP solvers which can take hours.
Limitations and Future Work
- Input Distribution Shift: The paper acknowledges that shifts in input data distribution over time could impact the optimality of a pre-generated parallelism plan. They propose that OPER can continuously monitor data distribution and regenerate plans if necessary, a process that is efficient due to their heuristic algorithm.
- Kernel Implementation Choice: The paper discusses two design choices for CUDA kernel implementation (retrieve-based vs. send-based) and opts for retrieve-based to support more general pooling operations. This choice might have implications for specific pooling types.
- Future Work: The paper suggests that OPER's approach is orthogonal to embedding compression techniques and could be combined with them for further optimization. The discussion also touches upon the potential for OPER to adapt to dynamic changes in data distribution.
Summary updated