IRMA-International.org: Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

Paradigms for Effective Parallelization of Inherently Sequential Graph Algorithms on Multi-Core Architectures

Paradigms for Effective Parallelization of Inherently Sequential Graph Algorithms on Multi-Core Architectures
View Sample PDF
Author(s): Assefaw Gebremedhin (Washington State University, USA), Mostofa Patwary (NVIDIA, USA) and Fredrik Manne (University of Bergen, Norway)
Copyright: 2021
Pages: 22
Source title: Handbook of Research on Methodologies and Applications of Supercomputing
Source Author(s)/Editor(s): Veljko Milutinović (Indiana University, Bloomington, USA) and Miloš Kotlar (University of Belgrade, Serbia)
DOI: 10.4018/978-1-7998-7156-9.ch005

Purchase


Abstract

The chapter describes two algorithmic paradigms, dubbed speculation and iteration and approximate update, for parallelizing greedy graph algorithms and vertex ordering algorithms, respectively, on multicore architectures. The common challenge in these two classes of algorithms is that the computations involved are inherently sequential. The efficacy of the paradigms in overcoming this challenge is demonstrated via extensive experimental study on two representative algorithms from each class and two Intel multi-core systems. The algorithms studied are (1) greedy algorithms for distance-k coloring (for k = 1 and k = 2) and (2) algorithms for two degree-based vertex orderings. The experimental results show that the paradigms enable the design of scalable methods that to a large extent preserve the quality of solution obtained by the underlying serial algorithms.

Related Content

Miloš Kotlar. © 2021. 4 pages.
Ivan Ratković, Miljan Djordjevic. © 2021. 13 pages.
Benjamin Berg, Mor Harchol-Balter. © 2021. 23 pages.
Bryan Donyanavard, Amir M. Rahmani, Axel Jantsch, Onur Mutlu, Nikil Dutt. © 2021. 33 pages.
Assefaw Gebremedhin, Mostofa Patwary, Fredrik Manne. © 2021. 22 pages.
Nenad Korolija, Jovan Popović, Miroslav M. Bojović. © 2021. 10 pages.
Christina Pacher. © 2021. 8 pages.
Body Bottom