We are happy to announce that Marco’s paper was accepted as Supercomputing 2025, taking place the 16-21 November in St. Louis. Marco will present its research paper on Thursday 20th at 3:30pm in the “Algorithms: Matching System Capabilities” session.<\/p>\n\n\n\n
The Single-Source Shortest Path (SSSP) problem is a fundamental graph problem with an extensive set of real-world applications. State-of-the-art parallel algorithms for SSSP, such as the \u2206-stepping algorithm, create parallelism through priority coarsening. Priority coarsening results in redundant computations that diminish the benefits of parallelization and limit parallel scalability.<\/p>\n\n\n\n
This paper introduces Wasp, a novel SSSP algorithm that reduces parallelism-induced redundant work by utilizing asynchrony and an efficient priority-aware work stealing scheme. Contrary to previous work, Wasp introduces redundant computations only when threads have no high-priority work locally available to execute. This is achieved by a novel priority-aware work stealing mechanism that controls the inefficiencies of indiscriminate priority coarsening.<\/p>\n\n\n\n
Experimental evaluation shows competitive or better performance compared to GAP, GBBS, MultiQueues, Galois, \u2206*-stepping, and \u03c1-stepping on 13 diverse graphs with geometric mean speedups of 2.2x on AMD Zen 3 and 2.1x on Intel Sapphire Rapids using 128 threads.<\/p>\n\n\n\n
The source code is available at: https:\/\/github.com\/DIPSA-QUB\/wasp<\/a> DIPSA presents a research paper at SC’25!<\/p>\n","protected":false},"author":1,"featured_media":3246,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[151],"tags":[34,35,38,66,19],"class_list":["post-3593","post","type-post","status-publish","format-standard","has-post-thumbnail","category-graph-algorithms","tag-algorithm-design-and-engineering","tag-graph-processing","tag-high-performance-computing","tag-real-world-graphs","tag-source-code","czr-hentry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/08\/trees.jpg","_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3593","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=3593"}],"version-history":[{"count":5,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3593\/revisions"}],"predecessor-version":[{"id":3643,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3593\/revisions\/3643"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media\/3246"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=3593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=3593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=3593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
Paper available at: https:\/\/dl.acm.org\/doi\/10.1145\/3712285.3759872<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"