15 papers · ranked by Valyu relevance
Simo Särkkä, Ángel F. García‐Fernández
—This paper presents an experimental evaluation of parallel-in-time Kalman filters and smoothers using graphics processing units (GPUs). In particular, the paper evaluates different all-prefix-sum algorithms, that is, parallel scan algorithms for temporal parallelization of Kalman filters and smoothers in two ways: by…
Michael T. Goodrich, Vinesh Sridhar
Embedded systems and Internet of Things (IoT) applications motivate in-place parallel algorithms, which avoid allocating additional shared memory past the input. Work by Gu, Obeya, and Shun [APOCS '21] defines a family of PIP (parallel in-place) models and parallel algorithms that eschew auxiliary memory at high…
Davide Rucci, Sebastian Parfeniuc, Matteo Mordacchini, Emanuele Carlini + 2 more
—In this paper, we investigate the parallelization of kcore decomposition, a method used in graph analysis to identify cohesive substructures and assess node centrality. Although efficient sequential algorithms exist for this task, the scale of modern networks requires faster, multicore-ready approaches. To this end…
Shridharan Chandramouli
| 1 | | Introduction | | | |---|-----------------------------------------------------|---------------------------------------------------------------------------|----|--| | | 1.1 | Motivation | 1 | | | | 1.2 | Proper Order Multi-Column Graph Structure | 2 | | | | 1.3 | General Maxflow/Mincut Problem Definition | 2 | |…
Accorsi, Luca, Laganà, Demetrio + 6 more
We propose a parallel shared-memory schema to cooperatively optimize the solution of a Capacitated Vehicle Routing Problem instance with minimal synchronization effort and without the need for an explicit decomposition. To this end, we design FILO2 x as a single-trajectory parallel adaptation of the FILO2 algorithm…
Zhixin Ou, Peng Liang, Jianchen Han, Baihui Liu + 1 more
Dynamic sequences with varying lengths have been widely used in the training of Transformer-based large language models (LLMs). However, current training frameworks adopt a pre-defined static parallel strategy for these sequences, causing neither communication-parallelization cancellation on short sequences nor…
Weitian Chen, Shixuan Sun, Cheng Chen, Yongmin Hu + 2 more
Subgraph matching is a core operation in graph analytics, supporting a broad spectrum of applications from social network analysis to bioinformatics. Recent GPU-based approaches accelerate subgraph matching by leveraging parallelism but rely on a coarse-grained execution model that suffers from scalability and…
Shiting Long, Gustavo Ramirez-Hidalgo, Andreas Frommer, Dirk Pleiter
Gauss-Seidel is a well-established iterative method for the solution of linear systems, and multicoloring has been widely used to increase parallelism in iterative solution techniques. Implementing multi-color Gauss-Seidel with conventional divide-and-conquer parallelization strategies, however, may be inefficient due…
Rubén Langarita, Jesús Alastruey-Benedé, Pablo Ibáñez, Santiago Marco‐Sola + 2 more
—Multiple HPC applications are often bottlenecked by compute-intensive kernels implementing complex dependency patterns (data-dependency bound). Traditional general-purpose accelerators struggle to effectively exploit fine-grain parallelism due to limitations in implementing convoluted data-dependency patterns (like…
Guy Blelloch, Andrew Brady, Laxman Dhulipala, Jeremy Fineman + 1 more
We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph is updated with batches of edge insertions/deletions, and for each batch a parallel algorithm updates the maximal independent set to agree…
Marc Becker, Bernd Bischl
Many algorithms in statistics and machine learning can be parallelized in an asynchronous manner where workers need to communicate through shared state rather than execute independent tasks dispatched by a central controller. Especially in modern hyperparameter optimization and parallel black-box optimization with…
Wolfgang Bangerth
Digital elevation models (DEMs) have reached resolutions and sizes that only parallel computaters can efficiently process. One important application of DEMs is predicting how much water flows where, the so-called ``flow routing problem'' (a variation of which is the problem of determining the drainage area upstream of…
Michał Szyfelbein
Consider the classical \textsc{Min-Sum Set Cover} problem: We are given a universe $\mathcal{U}$ of $n$ elements and a collection $\mathcal{S}$ of $k$ subsets of $\mathcal{U}$. Moreover, a cost function is associated with each set. The goal is to find a subsequence of sets in $\mathcal{S}$ that covers all elements in…
Ran Ginosar
I have greatly enjoyed spending many years in studying parallel computing. My journey goes thorough MP-C, PLURAL, Async Plural, HAL, RC64 and more. As a PhD student at Princeton I studied a combination of shared memory and message passing, motivated by algorithms and the ease of programming. While at the Technion, a…
Marco Ronzani, Cristina Silvano
Hypergraph partitioning is a pervasive NP-hard problem, and accelerating its computation on GPU can both slice time-to-solution and raise quality of results. In this work, we implement a multi-level hypergraph partitioning algorithm on GPU targeting a specific set of problem constraints: bounded per-partition size and…