{"id":3355,"date":"2025-01-15T19:32:09","date_gmt":"2025-01-15T19:32:09","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/?p=3355"},"modified":"2025-09-18T06:57:33","modified_gmt":"2025-09-18T05:57:33","slug":"on-optimizing-locality-of-graph-transposition-on-modern-architectures","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/on-optimizing-locality-of-graph-transposition-on-modern-architectures\/","title":{"rendered":"On Optimizing Locality of Graph Transposition on Modern Architectures"},"content":{"rendered":"\n<p><a href=\"https:\/\/doi.org\/10.48550\/arXiv.2501.06872\" target=\"_blank\" rel=\"noreferrer noopener\">DOI: 10.48550\/arXiv.2501.06872<\/a><br><a href=\"https:\/\/arxiv.org\/pdf\/2501.06872\"><strong>PDF version<\/strong><\/a><\/p>\n\n\n\n<p>This paper investigates the shared-memory Graph Transposition (GT) problem, a fundamental graph algorithm that is widely used in graph analytics and scientific computing.<\/p>\n\n\n\n<p><br>Previous GT algorithms have significant memory requirements that are proportional to the number of vertices and threads which obstructs their use on large graphs. Moreover, atomic memory operations have become comparably fast on recent CPU architectures, which creates new opportunities for improving the performance of concurrent atomic accesses in GT.<br><\/p>\n\n\n\n<p>We design <strong>PoTra<\/strong>, a GT algorithm which leverages graph structure and processor and memory architecture to optimize locality and performance. PoTra limits the size of additional data structures close to CPU cache sizes and utilizes the skewed degree distribution of graph datasets to optimize locality and performance. We present the performance model of PoTra to explain the connection between cache and memory response times and graph locality.<\/p>\n\n\n\n<p><br>Our evaluation of PoTra on three CPU architectures and 20 real-world and synthetic graph datasets with up to 128 billion edges demonstrates that PoTra achieves up to 8.7 times speedup compared to previous works and if there is a performance loss it remains limited to 15.7%, on average.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Source code<\/h2>\n\n\n\n<p>The source code of PoTra is available on <a href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/laganlighter-source-code\/\" data-type=\"post\" data-id=\"1437\" target=\"_blank\" rel=\"noreferrer noopener\">LaganLighter repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">BibTex<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>@misc{PoTra,\n     title={On Optimizing Locality of Graph Transposition on Modern Architectures}, \n     author={Mohsen {Koohi Esfahani} and Hans Vandierendonck},\n     year={2025},\n     eprint={2501.06872},\n     archivePrefix={arXiv},\n     primaryClass={cs.DC},\n     url={https:\/\/arxiv.org\/abs\/2501.06872},\n     doi={10.48550\/arXiv.2501.06872} \n} <\/code><\/pre>\n\n\n\n<p class=\"has-medium-font-size\"><br><strong><a href=\"\/DIPSA\/LaganLighter\">LaganLighter<\/a><\/strong><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\"><ul class=\"wp-block-latest-posts__list has-dates wp-block-latest-posts\"><li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2025\/01\/potra-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/on-optimizing-locality-of-graph-transposition-on-modern-architectures\/\">On Optimizing Locality of Graph Transposition on Modern Architectures<\/a><time datetime=\"2025-01-15T19:32:09+00:00\" class=\"wp-block-latest-posts__post-date\">15 January 2025<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/08\/cones2-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/random-vertex-relabelling-in-laganlighter\/\">Random Vertex Relabelling in LaganLighter<\/a><time datetime=\"2024-08-21T12:37:52+01:00\" class=\"wp-block-latest-posts__post-date\">21 August 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/08\/trees-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/minimum-spanning-forest-of-ms-biographs\/\">Minimum Spanning Forest of MS-BioGraphs<\/a><time datetime=\"2024-08-09T14:11:36+01:00\" class=\"wp-block-latest-posts__post-date\">9 August 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/08\/affinity-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/topology-based-thread-affinity-setting-thread-pinning-in-openmp\/\">Topology-Based Thread Affinity Setting (Thread Pinning) in OpenMP<\/a><time datetime=\"2024-08-03T18:07:31+01:00\" class=\"wp-block-latest-posts__post-date\">3 August 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/02\/loriini-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/paragrapher-integrated-to-laganlighter\/\">ParaGrapher Integrated to LaganLighter<\/a><time datetime=\"2024-02-16T08:29:26+00:00\" class=\"wp-block-latest-posts__post-date\">16 February 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/Squirrel-Dima-Solomin-Unsplash-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/on-designing-structure-aware-high-performance-graph-algorithms-phd-thesis\/\">On Designing Structure-Aware High-Performance Graph Algorithms (PhD Thesis)<\/a><time datetime=\"2022-12-08T10:00:00+00:00\" class=\"wp-block-latest-posts__post-date\">8 December 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/cactus-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/laganlighter-source-code\/\">LaganLighter Source Code<\/a><time datetime=\"2022-11-14T13:17:17+00:00\" class=\"wp-block-latest-posts__post-date\">14 November 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/Mastiff-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/mastiff-structure-aware-minimum-spanning-tree-forest\/\">MASTIFF: Structure-Aware Minimum Spanning Tree\/Forest &#8211; ICS&#8217;22<\/a><time datetime=\"2022-06-28T20:17:30+01:00\" class=\"wp-block-latest-posts__post-date\">28 June 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/White-Stork-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/sapco-sort-optimizing-degree-ordering-for-power-law-graphs\/\">SAPCo Sort: Optimizing Degree-Ordering for Power-Law Graphs &#8211; ISPASS&#8217;22 (Poster)<\/a><time datetime=\"2022-05-23T11:56:43+01:00\" class=\"wp-block-latest-posts__post-date\">23 May 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/lotus-1000x288-1-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/lotus-locality-optimizing-triangle-counting\/\">LOTUS: Locality Optimizing Triangle Counting &#8211; PPOPP&#8217;22<\/a><time datetime=\"2022-04-05T15:50:00+01:00\" class=\"wp-block-latest-posts__post-date\">5 April 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-19-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/locality-analysis-of-graph-reordering-algorithms\/\">Locality Analysis of Graph Reordering Algorithms &#8211; IISWC&#8217;21<\/a><time datetime=\"2021-11-08T08:19:00+00:00\" class=\"wp-block-latest-posts__post-date\">8 November 2021<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/michael-mahood-N_WK99xI9hU-unsplash-2-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/thrifty-label-propagation-fast-connected-components-for-skewed-degree-graphs\/\">Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs &#8211; IEEE CLUSTER&#8217;21<\/a><time datetime=\"2021-09-09T16:34:43+01:00\" class=\"wp-block-latest-posts__post-date\">9 September 2021<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-12-1-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/exploiting-in-hub-temporal-locality-in-spmv-based-graph-processing\/\">Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing &#8211; ICPP&#8217;21<\/a><time datetime=\"2021-08-09T21:07:40+01:00\" class=\"wp-block-latest-posts__post-date\">9 August 2021<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-11-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/how-do-graph-relabeling-algorithms-improve-memory-locality-ispass21\/\">How Do Graph Relabeling Algorithms Improve Memory Locality? ISPASS&#8217;21 (Poster)<\/a><time datetime=\"2021-03-28T08:00:00+01:00\" class=\"wp-block-latest-posts__post-date\">28 March 2021<\/time><\/li>\n<\/ul><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>DOI: 10.48550\/arXiv.2501.06872PDF version This paper investigates the shared-memory Graph Transposition (GT) problem, a fundamental graph algorithm that is widely used in graph analytics and scientific computing. Previous GT algorithms have significant memory requirements that are proportional to the number of vertices and threads which obstructs their use on large graphs. Moreover, atomic memory operations have [&hellip;]<\/p>\n","protected":false},"author":1315,"featured_media":3360,"comment_status":"open","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[40],"tags":[35,133,38,64,44],"class_list":{"0":"post-3355","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-laganlighter","8":"tag-graph-processing","9":"tag-graph-transposition","10":"tag-high-performance-computing","11":"tag-high-performance-graph-processing","12":"tag-structure-aware-algorithms","13":"czr-hentry"},"jetpack_featured_media_url":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2025\/01\/potra.jpg","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3355","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\/1315"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=3355"}],"version-history":[{"count":6,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3355\/revisions"}],"predecessor-version":[{"id":3569,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3355\/revisions\/3569"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media\/3360"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=3355"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=3355"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=3355"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}