CS Paper Radar

Pipelining vs. Combining in Aggregation Tasks

Gabriel Marques Domingues, Claire Mathieu, Boaz Patt-Shamir

cs.DC cs.DS ·submitted 2026-10-22 14:52 UTC · v1

Abstract

We study the aggregation task (convergecast) in networks in the case that the values to be aggregated do not fit in a single message. We assume that every node starts with an input value, and there is an aggregation operator that is commutative, associative, and length-preserving, i.e., the result of aggregating two values has the same length as each of the input values. Since values do not fit in a message, they are transferred in a ``train'' of pipelined messages, which must be terminated whenever we want to aggregate values. The goal is to minimize the makespan time of aggregating all values. We present general lower bounds on the problem and optimal algorithms for several prevalent parallel computing architectures, including the hypercube and complete bipartite graphs, under both the splittable and unsplittable flows models. We also present an $O(\log n)$ approximation for general graphs in the unsplittable flows model.

Comment
22 pages; 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Nearly Optimal Min-Cut Algorithm for Dynamic Streams

cs.DS ·2026-10-25 ·Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff
similarity 0.62
Abstract

We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was $\tilde{O}(n/\varepsilon^2)$, due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an $\tilde{O}(n/\varepsilon)$-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general $\pmΔ$ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum $\ell_p$-norm $k$-partitioning for every fixed $k$, weighted correlation-clustering evaluation for two clusters, and for-each cut sketching in balanced directed graphs.

0.46

ETH: Data-Balanced Heterogeneous Pipeline Parallelism for Training Large Models

cs.DC cs.LG ·2026-10-15 ·Mianjie Yu, Zhongmin Zhao, Zizhao Mo, Jianxiong Liao, Wenxuan Li +7 more
publishedcode/data similarity 0.61
Abstract · 19 pages, 14 figures. Accepted at USENIX NSDI 2027

Current heterogeneity-aware training systems for large models balance workloads by assigning unequal numbers of layers across pipeline stages, a strategy aimed at equalizing execution time through a unique pipeline configuration. However, this approach fails to address critical memory constraints and suffers from inherently coarse balancing granularity. In this paper, we propose Heterogeneous Pipeline Parallelism (HPP), a novel approach enabling efficient and fine-grained data balance across heterogeneous pipelines. To address HPP's key challenges, prohibitive search overhead for optimal configurations and high communication overhead from asymmetric All-Reduce, we design the ETH training system. ETH employs a hierarchical workload balance framework that jointly optimizes balance across heterogeneous pipelines and within individual pipeline stages. To mitigate asymmetric communication costs, ETH implements block-wise gradient aggregation. Furthermore, it integrates specialized optimizations that dramatically reduce HPP configuration search overhead. Evaluations demonstrate ETH achieves up to 2x training speedup while reducing configuration generation overhead by up to 56x compared to state-of-the-art systems. The code is available at https://github.com/YuMJie/ETH.

0.42

Para-Pipe: Exploiting Hierarchical Operator Parallelism of ML Computational Graphs on SoCs

cs.DC cs.LGcs.PF ·2026-09-03 ·Yujie Zhang, Huiying Lan, Ehsan Aghapour, Zhiyuan Ning, Peng Zan +3 more
top venue similarity 0.59
Abstract · Accepted to IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

As edge-based deep learning applications become more complex, optimizing performance on heterogeneous System-on-Chips (SoCs) presents unique challenges. Traditional pipelining techniques distributing the computation across different on-chip processing units, while effective for throughput, do not address the latency demands posed by modern neural networks with complex interdependencies and extensive operator parallelism. There is a potential in leveraging operator parallelism to enable concurrent execution across multiple processing units, thereby reducing inference latency. However, prioritizing pipelining or parallel execution often necessitates a compromise, where optimizing one performance metric adversely impacts the other. This paper introduces Para-Pipe, a hierarchical mapping framework that integrates intra- and inter-stage operator parallelism within a pipelined architecture. Para-Pipe navigates the trade-off between throughput and latency by selectively fine-tuning parallelism levels within and across pipeline stages. This strategy can significantly reduce inter-processor communication overhead, significantly improving energy efficiency. Our evaluation demonstrates that Para-Pipe generates multiple Pareto-optimal configurations, achieving a balance between throughput and latency on an Amlogic SoC equipped with ARM big.LITTLE CPUs and GPU, as well as the Black Sesame Technology SoC featuring a deep learning accelerator and two DSPs. More importantly, throughput-optimized configurations under Para-Pipe on Amlogic SoC show an average energy efficiency improvement of 11.0% over purely pipelined strategies and 23.3% relative to non-pipelined parallel execution.

0.39

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

cs.AI cs.DCcs.DS ·2026-09-07 ·David A. Bader, Adil Chhabra, Ernestine Großmann, Monika Henzinger, Alexander Noe +1 more
benchmarkcode/data similarity 0.58
Abstract

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.

0.27

Distributed Balanced Butterfly Counting in Signed Bipartite Graphs

cs.DC ·2026-09-18 ·Kiran Mekala, Apurba Das, Suman Banerjee
similarity 0.58
Abstract

The balanced butterfly is a fundamental primitive for analyzing signed bipartite graphs and provides a basis for studying higher-order structural properties, such as clustering coefficients and community structure. Despite its importance, existing approaches primarily rely on serial algorithms for balanced butterfly counting, which become inefficient on large-scale graphs. To address this limitation, we propose a distributed algorithm, D-BBC, based on a hybrid MPI+TBB framework that exploits MPI for inter-process communication and Intel TBB for intra-node parallelism. We conduct an experimental assessment of the proposed approach across 15 real-world datasets. Experimental results demonstrate that, on a single-node distributed system, D-BBC achieves average speedups of 1321x and 16.2x over the serial BB2K and multi-core M-BBC implementations, respectively. Furthermore, D-BBC achieves a maximum speedup of 23.58x over the distributed baseline S-Monarch in terms of end-to-end execution time. These results demonstrate the efficiency of the proposed distributed approach and its potential to enable high- performance signed motif analysis on large-scale bipartite graphs.

0.28

Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

cs.DS ·2026-10-23 ·Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
similarity 0.58
Abstract · 101 pages

We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.

0.49

VPP: Virtual Pipeline Parallelism for Efficient Chunked Prefill in Long-Context LLM Inference

cs.DC ·2026-08-27 ·Yan Shi, Xiaochao Wang, Jingchun Gao, Jintao Luo, Xinyi Zhou +5 more
similarity 0.58
Abstract

Chunked prefill pipeline parallelism (CPP) is a key technique for LLM inference. However, equal-size chunks exhibit imbalanced latency, as later chunks attend longer prefix KV caches and incur higher attention costs, leading to pipeline bubbles. Existing approaches mitigate this imbalance through dynamic chunk resizing (Dynamic CPP, DCPP), but our measurements show that this trades scheduling overhead for load balancing, which becomes unfavorable on long sequences. In this study, we propose Virtual Pipeline Parallelism (VPP), which keeps chunk sizes fixed and optimizes the pipeline layout through virtual stages. A V-shaped virtual-stage traversal overlaps each chunk's expensive middle stages with the lighter head and tail stages of its neighbors, while asynchronous communication and pipelined packing further reduce communication stalls and cross-request drain bubbles. We implement VPP in vLLM-Ascend and evaluate it on three MoE-based LLMs with sequences up to 1M tokens on 16 Ascend 910C NPUs. VPP improves throughput by up to 13.1% over DCPP on long sequences and 6.7% on mixed workloads, while preserving performance on short sequences. On a 512K-token DeepSeek-V3.1 prefill workload, VPP reduces the pipeline bubble ratio from 6.4% to 0.1%, achieving a 98.0% reduction compared with DCPP.

0.38

Distributed Datalog at Scale with Worst-Case Optimal Joins

cs.DB ·2026-10-08 ·Kunting Qi, Yihao Sun, Kristopher Micinski, Thomas Gilray, Sidharth Kumar
similarity 0.58
Abstract

Scalable logic-based analytics are frequently dominated by cyclic multi-way joins over large relational datasets. State-of-the-art systems evaluate these joins through chains of binary joins, incurring substantial overhead from large intermediate relations that must be materialized and redistributed across the network. Worst-Case Optimal Joins (WCOJ) offer a provably superior alternative by evaluating joins one variable at a time, eliminating intermediate blowup. However, existing WCOJ implementations target either shared-memory machines or one-shot, non-recursive queries on dataflow and big-data platforms, leaving WCOJ-based recursive evaluation on distributed-memory HPC systems an open problem. We present, to our knowledge, the first distributed-memory Datalog engine that uses WCOJ for recursive fixpoint evaluation. Our design builds on HyperCube partitioning, which hash-partitions relations along variable-aligned grid dimensions and replicates them along missing dimensions, and extends it from a single shuffle to iterative execution: in every semi-naive iteration, only newly derived tuples are repartitioned and re-replicated, using MPI all-to-all collectives and per-dimension all-gathers over subcube communicators, while the same layout is reused across iterations so that all WCOJ intersections remain rank-local. We evaluate our system on the Aurora and Polaris leadership-class supercomputers at Argonne National Laboratory using graph mining and program analysis benchmarks, demonstrating strong scalability, outperforming state-of-the-art Datalog engines on most benchmarks, and characterizing how partition dimensionality trades runtime against memory feasibility.

0.31