Inspired by prior work by Tian and by Cao and Xu, this paper presents an efficient computer-aided framework to characterize the fundamental limits of coded caching systems under the constraint of linear coding. The proposed framework considers non-Shannon-type inequalities which are valid for representable polymatroids (and hence for linear codes), and leverages symmetric structure and problem-specific constraints of coded caching to reduce the complexity of the linear program. The derived converse bounds are tighter compared to previous known analytic methods, and prove the optimality of some achievable memory-load tradeoff points under the constraint of linear coding placement and delivery. These results seem to indicate that small, structured demand subsets combined with minimal common information constructions may be sufficient to characterize optimal tradeoffs under linear coding.

The rapidly evolving landscape of products, surfaces, policies, and regulations poses significant challenges for deploying state-of-the-art recommendation models at industry scale, primarily due to data fragmentation across domains and escalating infrastructure costs that hinder sustained quality improvements.

This paper presents a new achievable scheme for the K-user Linear Computation Broadcast Channel (K-LCBC). A K-LCBC comprises data stored on a server and$K$users, each aiming to retrieve a desired linear function of the data by leveraging their prior locally available side information in the form of another linear function of the data. The proposed scheme is based on a subspace decomposition derived from representable polymatroid spaces. This decomposition enables the server to effectively design multicast messages that simultaneously benefit multiple users and allow users to eliminate interference using their available side information. This work extends existing results for the 3-LCBC by introducing a linear programming framework to optimize multicast opportunities across an arbitrary number of users. The proposed approach can be used to derive achievable scheme for the K-user coded caching problem with linear coded placement and scalar linear function retrieval, which was our original motivation to investigate the K-LCBC.

Maddah-Ali and Niesen (MAN) showed that coded caching can effectively mitigate peak-time network load by leveraging local caches at the end users. In the MAN model, a server stores multiple files, populates the local caches, and serves single-file requests from cache-aided users via an error-free shared link. The delivered multicast messages in the MAN scheme to serve the users' requests require all users to stay active and expose demand information. To preserve demand privacy and accommodate for offline users, the hotplug caching model with demand privacy against colluding users was introduced and an achievable schemes based on the “privacy keys” idea was proposed at ISIT 2023. This ISIT 2024 paper proposes three new achievable schemes for this model which use Maximum Distance Separable codes coupled with the “virtual users” idea. These new schemes turn out to be exactly optimal under certain conditions, and otherwise optimal to within a constant factor.

Coded caching, introduced by Maddah-Ali and Niesen (MAN), is a model where a server broadcasts multicast packets to users with a local cache that is leveraged so as to reduce the peak network communication load. The original MAN model does not consider missing demands (i.e., some users may not request a file) or privacy issues (i.e., decoding the multicast packets may expose the users’ demands). The former issue was captured by the hotplug model with offline users, where the server starts sending multicast packets after having received a certain number of file requests. The latter issue was addressed by devoting part of the cache to store privacy keys to help users decode their requested file while remaining completely ignorant about the demands of the remaining users. This paper investigates the problem of private demands against colluding users in the hotplug model with offline users. Two achievable schemes are proposed based on Maximum Distance Separable (MDS) codes. They achieve lower subpacketization, and lower load in the small memory regime compared to baseline schemes that trivially include demand privacy or offline users in known schemes.

Deep learning recommendation models (DLRMs) have been used across many business-critical services at Meta and are the single largest AI application in terms of infrastructure demand in its data-centers. In this paper, we present Neo, a software-hardware co-designed system for high-performance distributed training of large-scale DLRMs. Neo employs a novel 4D parallelism strategy that combines table-wise, row-wise, column-wise, and data parallelism for training massive embedding operators in DLRMs. In addition, Neo enables extremely high-performance and memory-efficient embedding computations using a variety of critical systems optimizations, including hybrid kernel fusion, software-managed caching, and quality-preserving compression. Finally, Neo is paired with ZionEX, a new hardware platform co-designed with Neo's 4D parallelism for optimizing communications for large-scale DLRM training. Our evaluation on 128 GPUs using 16 ZionEX nodes shows that Neo outperforms existing systems by up to 40× for training 12-trillion-parameter DLRM models deployed in production.

Coded caching is a technique that leverages locally cached contents at the users to reduce the network’s peak-time communication load. Coded caching achieves significant performance gains compared to uncoded caching schemes and is thus a promising technique to boost performance in future networks. In the original model introduced by Maddah-Ali and Niesen (MAN), a server stores multiple files and is connected to multiple cache-aided users through an error-free shared link; once the local caches have been filled and all users have sent their demand to the server, the server can start sending coded multicast messages to satisfy all users’ demands. A practical limitation of the original MAN model is that it halts if the server does not receive all users’ demands, which is the limiting case of asynchronous coded caching when the requests of some users arrive with infinite delay. This paper formally defines a coded caching system where some users are offline. Achievable and converse bounds are proposed for this novel setting and shown to meet under certain conditions; otherwise, they are within a constant multiplicative gap of two. Interestingly, when optimality can be be shown, the optimal load-memory tradeoff only depends on the number active users, and not on the total (active plus offline) number of users.

Embedding learning is an important technique in deep recommendation models to map categorical features to dense vectors. However, the embedding tables often demand an extremely large number of parameters, which become the storage and efficiency bottlenecks. Distributed training solutions have been adopted to partition the embedding tables into multiple devices. However, the embedding tables can easily lead to imbalances if not carefully partitioned. This is a significant design challenge of distributed systems named embedding table sharding, i.e., how we should partition the embedding tables to balance the costs across devices, which is a non-trivial task because 1) it is hard to efficiently and precisely measure the cost, and 2) the partition problem is known to be NP-hard. In this work, we introduce our novel practice in Meta, namely AutoShard, which uses a neural cost model to directly predict the multi-table costs and leverages deep reinforcement learning to solve the partition problem. Experimental results on an open-sourced large-scale synthetic dataset and Meta's production dataset demonstrate the superiority of AutoShard over the heuristics. Moreover, the learned policy of AutoShard can transfer to sharding tasks with various numbers of tables and different ratios of the unseen tables without any fine-tuning. Furthermore, AutoShard can efficiently shard hundreds of tables in seconds. The effectiveness, transferability, and efficiency of AutoShard make it desirable for production use. Our algorithms have been deployed in Meta production environment. A prototype is available at https://github.com/daochenzha/autoshard

Coded caching aims to minimize the network's peak-time communication load by leveraging the information pre-stored in the users' local cache. The original single file retrieval setting by Maddah-Ali and Niesen has been recently extended to general Scalar Linear Function Retrieval (SLFR) by Wan et al., who proposed a linear scheme that surprisingly achieves the same optimal load (under the constraint of uncoded cache placement) as in single file retrieval. This paper's goal is to characterize the conditions under which a general SLFR linear scheme is optimal and gain practical insights into why the specific choices made by Wan et al. work. This paper shows that the optimal decoding coefficients are necessarily the product of two terms, one only involving the encoding coefficients and the other only the demands. In addition, the relationships among the encoding coefficients are shown to be captured by the cycles of a certain graph. Thus, a general linear scheme for SLFR can be found by solving a spanning tree problem.