Composable Parallelism in Graph Processing

2026
OriginalPaper
Chapter

Published in:

Authors: Vladimir Bakhtin; Nikita Kataev; Alexander Kolganov; Dmitry Zakharov; Alexander Smirnov; Anton Malahov
Published in: Parallel Computing Technologies
Publisher: Springer Nature Switzerland

Read first chapter Log in

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This chapter explores the concept of composable parallelism in graph processing, focusing on its application to algorithms like Breadth-First Search (BFS) and Single Source Shortest Path (SSSP). It discusses the challenges of nested parallelism and the limitations of native OpenMP implementations, particularly in handling oversubscription and synchronization overhead. The authors propose a solution using an intermediate abstraction layer based on oneTBB, which maps user-level threads to OS threads, thereby improving performance and scalability. The chapter also delves into the implementation of synchronization primitives for user-level threads and compares the performance of different OpenMP runtimes. Experimental results demonstrate significant improvements in performance when using the proposed composable runtime, especially in nested parallelism scenarios. The study concludes that the proposed approach can achieve up to a 43% performance improvement compared to native OpenMP implementations, highlighting the potential of composable parallelism in optimizing graph processing tasks.

AI Generated

This summary of the content was generated with the help of AI.

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Business + Economics & Engineering + Technology"

Online-Abonnement

Springer Professional "Business + Economics & Engineering + Technology" gives you access to:

more than 102.000 books
more than 537 journals

from the following subject areas:

Automotive
Construction + Real Estate
Business IT + Informatics
Electrical Engineering + Electronics
Energy + Sustainability
Finance + Banking
Management + Leadership
Marketing + Sales
Mechanical Engineering + Materials
Insurance + Risk

Secure your knowledge advantage now!

inform now

Springer Professional "Engineering + Technology"

Online-Abonnement

Springer Professional "Engineering + Technology" gives you access to:

more than 67.000 books
more than 390 journals

from the following specialised fileds:

Automotive
Business IT + Informatics
Construction + Real Estate
Electrical Engineering + Electronics
Energy + Sustainability
Mechanical Engineering + Materials

Secure your knowledge advantage now!

inform now

Springer Professional "Business + Economics"

Online-Abonnement

Springer Professional "Business + Economics" gives you access to:

more than 67.000 books
more than 340 journals

from the following specialised fileds:

Construction + Real Estate
Business IT + Informatics
Finance + Banking
Management + Leadership
Marketing + Sales
Insurance + Risk

Secure your knowledge advantage now!

inform now

previous chapter Efficient OLAP Support of Hierarchical Data Almost in Real-Time

next chapter Brahma.FSharp: Power of Functional Programming to Create Portable GPGPU-Enabled .NET Applications

Metadata
Literature

Title: Composable Parallelism in Graph Processing
Authors: Vladimir Bakhtin
Nikita Kataev
Alexander Kolganov
Dmitry Zakharov
Alexander Smirnov
Anton Malahov
Publisher: Springer Nature Switzerland
Book: Parallel Computing Technologies
Print ISBN: 978-3-032-06750-0

Electronic ISBN: 978-3-032-06751-7

Copyright Year: 2026
DOI: https://doi.org/10.1007/978-3-032-06751-7_3

This content is only visible if you are logged in and have the appropriate permissions.