908 citations · 2.4k across the 149 of their papers we have counts for
29 papers · 1 filter
LLMQ: Efficient Lower-Precision Pretraining for Consumer GPUs
Erik Schultheis, Dan Alistarh
We present LLMQ, an end-to-end CUDA/C++ implementation for medium-sized language-model training, e.g. 3B to 32B parameters, on affordable, commodity GPUs. These devices are charact…
Game Dynamics and Equilibrium Computation in the Population Protocol Model
Dan Alistarh, Krishnendu Chatterjee, Mehrdad Karrabi +1
We initiate the study of game dynamics in the population protocol model: agents each maintain a current local strategy and interact in pairs uniformly at random. Upon each inte…
PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures
Trevor Brown, William Sigouin, Dan Alistarh
To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained techniques, resulting in efficient and elegant algorithms, w…
Near-Optimal Leader Election in Population Protocols on Graphs
Dan Alistarh, Joel Rybicki, Sasha Voitovych
In the stochastic population protocol model, we are given a connected graph with nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and…
Collecting Coupons is Faster with Friends
Dan Alistarh, Peter Davies
In this note, we introduce a distributed twist on the classic coupon collector problem: a set of collectors wish to each obtain a set of coupons; for this, they can each sa…
CGX: Adaptive System Support for Communication-Efficient Deep Learning
Ilia Markov, Hamidreza Ramezanikebrya, Dan Alistarh
The ability to scale out training workloads has been one of the key performance enablers of deep learning. The main scaling approach is data-parallel GPU-based training, which has…
Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention
Dan Alistarh, Rati Gelashvili, Giorgi Nadiradze
This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registe…
Wait-free approximate agreement on graphs
Dan Alistarh, Faith Ellen, Joel Rybicki
Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to…
Fast Graphical Population Protocols
Dan Alistarh, Rati Gelashvili, Joel Rybicki
Let be a graph on nodes. In the stochastic population protocol model, a collection of indistinguishable, resource-limited nodes collectively solve tasks via pairwise in…
The Splay-List: A Distribution-Adaptive Concurrent Skip-List
Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova +1
The design and implementation of efficient concurrent data structures have seen significant attention. However, most of this work has focused on concurrent data structures providin…
Fast General Distributed Transactions with Opacity using Global Time
Alex Shamis, Matthew Renzelmann, Stanko Novakovic +6
Transactions can simplify distributed applications by hiding data distribution, concurrency, and failures from the application developer. Ideally the developer would see the abstra…
Breaking (Global) Barriers in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging
Shigang Li, Tal Ben-Nun, Giorgi Nadiradze +4
Deep learning at scale is dominated by communication time. Distributing samples across nodes usually yields the best performance, but poses scaling challenges due to global informa…
Robust Comparison in Population Protocols
Dan Alistarh, Martin Töpfer, Przemysław Uznański
There has recently been a surge of interest in the computational and complexity properties of the population model, which assumes anonymous, computationally-bounded nodes, inte…
Relaxed Scheduling for Scalable Belief Propagation
Vitaly Aksenov, Dan Alistarh, Janne H. Korhonen
The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been consi…
Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations
Shigang Li, Tal Ben-Nun, Salvatore Di Girolamo +2
Load imbalance pervasively exists in distributed deep learning training systems, either caused by the inherent imbalance in learned tasks or by the system itself. Traditional synch…
Performance Prediction for Coarse-Grained Locking
Vitaly Aksenov, Dan Alistarh, Petr Kuznetsov
A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data confl…
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen +2
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using pro…
Distributed Learning over Unreliable Networks
Chen Yu, Hanlin Tang, Cedric Renggli +5
Most of today's distributed machine learning systems assume {\em reliable networks}: whenever two machines exchange information (e.g., gradients or models), the network should guar…
The Transactional Conflict Problem
Dan Alistarh, Syed Kamran Haider, Raphael Kübler +1
The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts…
Distributionally Linearizable Data Structures
Dan Alistarh, Trevor Brown, Justin Kopinsky +2
Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications. Despite considerable interest,…
The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
Dan Alistarh, Christopher De Sa, Nikola Konstantinov
Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neu…
SparCML: High-Performance Sparse Communication for Machine Learning
Cedric Renggli, Saleh Ashkboos, Mehdi Aghagolzadeh +2
Applying machine learning techniques to the quickly growing data in science and industry requires highly-scalable algorithms. Large datasets are most commonly processed "data paral…
Space-Optimal Majority in Population Protocols
Dan Alistarh, James Aspnes, Rati Gelashvili
Population protocols are a model of distributed computing, in which agents with limited local state interact randomly, and cooperate to collectively compute global predicates.…
Time-Space Trade-offs in Population Protocols
Dan Alistarh, James Aspnes, David Eisenstat +2
Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational t…