The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
Paradigms for Effective Parallelization of Inherently Sequential Graph Algorithms on Multi-Core Architectures
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.
|
|
|