A bridging model for parallel computation

By Leslie G. Valiant. 1990

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism (2019, background): “There are two central paradigms for scaling out deep neural network training to numerous hardware accelerators: data parallelism (Valiant, 1990) where a training minibatch is split across multiple workers, and model parallelism in which the memory usage and computation of a model is distributed acro”
GLM-130B: An Open Bilingual Pre-trained Model (2022, methodology): “The data parallelism (Valiant, 1990) and tensor model parallelism (Shoeybi et al.”
PipeDream: Fast and Efficient Pipeline Parallel DNN Training (2018, methodology): “On one end, synchronizing at the end of every minibatch (referred to as bulk synchronous parallel or BSP [42]) reduces the staleness of weights used to compute gradients, ensuring good statistical eﬃciency.”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “, those designed for centralized data, often using a bulk synchronous parallel (BSP) approach (Valiant, 1990)) requires massive amounts of communication.”
Ray: A Distributed Framework for Emerging AI Applications (2017, background): “ch typically requires the use of GPUs. On the other hand, most of the other computations use CPUs. Note that these requirements are not naturally satisﬁed by the Bulk Synchronous Parallel (BSP) model [46], which is implemented by many of today’s popular cluster computing frameworks [18, 50]. With BS”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, background): “Figure 1 shows that GIANT follows the bulk synchronous parallel communication model (Valiant, 1990).”
Piccolo: Building Fast, Distributed Programs with Partitioned Tables (2010, background): “BSP (Bulk Synchronous Parallel) is a high-level communication-oriented model [50].”
Gemini: A Computation-Centric Distributed Graph Processing System (2016, unknown): “Like most recent distributed graph processing systems [3, 11, 12, 16, 17, 23, 26, 32, 41, 43], Gemini follows the Bulk Synchronous Parallel (BSP) model [53].”
3LC: Lightweight and Effective Traffic Compression for Distributed Machine Learning (2018, background): “In vanilla bulk synchronous parallel (BSP), workers train on an identical copy of the model [35].”
Trends in big data analytics (2014, background): “In these cases, bulk-synchronous parallel processing (BSP) [93] of the data works well.”
WTF: the who to follow service at Twitter (2013, methodology): “Beyond MapReduce, Google's Pregel [25] system implements the Bulk Synchronous Parallel model [29]: computations reside at graph vertices and are able to dispatch " messages " to other vertices.”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, methodology): “Pregel and its open-source relatives (e.g., Giraph, 3 Hama, 4 and GPS [60]) use the Bulk Synchronous Parallel (BSP) model [74] with explicit messages to fetch all resources for the vertex computation.”
The Gremlin graph traversal machine and language (invited talk) (2015, methodology): “Distributed Graph Traversals Gremlin’sgraph computertraversal machine was designed to support the distributed execution of a Gremlin traversal via th e bulk synchronous parallel (BSP) model of distributed computing [19].”
A cautionary perspective on cross-layer design (2005, unknown): “The von Neumann architecture for computer systems.”
Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems (1997, methodology): “It should be noted that there are more detailed communication models, such as the BSP model [ 30 ], the Postal model [3], and the LogP model [9], which further take into account that a receiving processor generally completes its receive operation later than the corresponding sending processor finish”
Scalability! But at what COST? (2015, background): “The Bulk Synchronous Parallel model [19] is surprisingly more general than related work sections would have you believe.”