{"id":544,"date":"2021-08-09T21:07:40","date_gmt":"2021-08-09T20:07:40","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/exploiting-in-hub-temporal-locality-in-spmv-based-graph-processing\/"},"modified":"2024-06-20T16:28:36","modified_gmt":"2024-06-20T15:28:36","slug":"exploiting-in-hub-temporal-locality-in-spmv-based-graph-processing","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/exploiting-in-hub-temporal-locality-in-spmv-based-graph-processing\/","title":{"rendered":"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing &#8211; ICPP&#8217;21"},"content":{"rendered":"<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><a href=\"https:\/\/oaciss.uoregon.edu\/icpp21\/\"><img decoding=\"async\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/ICPP-2021-virutal-background-1.png\" alt=\"ICPP'21\" class=\"wp-image-756\" \/><\/a><\/figure>\n<\/div>\n\n\n<p><strong><a rel=\"noreferrer noopener\" href=\"https:\/\/oaciss.uoregon.edu\/icpp21\/\" target=\"_blank\">50th International Conference on Parallel Processing (ICPP&#8217;21)<\/a><br>August 9-12, 2021<\/strong><br>Acceptance Rate: 26.4%<br><br><a rel=\"noreferrer noopener\" href=\"https:\/\/doi.org\/10.1145\/3472456.3472462\" target=\"_blank\"><strong>DOI<\/strong>:10.1145\/3472456.3472462<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/doi.org\/10.1145\/3472456.3472462\" target=\"_blank\">ACM Digital Library<\/a><br><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/htl_8.pdf\"><strong>PDF Version (Authors&#8217; Copy)<\/strong><\/a><\/p>\n\n\n\n<p class=\"has-text-align-justify\">This paper investigates the implications made by the structure of real-world graphs with power-law degree distribution on the locality of SpMV graph analytics, and by considering the efficacy of locality optimizing graph reordering algorithms (such as <a rel=\"noreferrer noopener\" style=\"color:black\" href=\"https:\/\/ieeexplore.ieee.org\/document\/6807798\" target=\"_blank\">SlashBurn<\/a>, <a rel=\"noreferrer noopener\" style=\"color:black\" href=\"https:\/\/dl.acm.org\/doi\/10.1145\/2882903.2915220\" target=\"_blank\">GOrder<\/a>, and <a rel=\"noreferrer noopener\" style=\"color:black\" href=\"https:\/\/ieeexplore.ieee.org\/document\/7515998\" target=\"_blank\">Rabbit-Order<\/a>) shows that irregular datasets requires special traversals in order to  improve locality for hub vertices that dedicate a large portion of the processing time to themselves.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">We introduce <strong>in-Hub Temporal Locality (iHTL)<\/strong> as a structure-aware and cache-friendly graph traversal that optimizes locality in pull traversal. iHTL identifies different blocks in the adjacency matrix of a graph and applies a suitable traversal direction (push or pull) for each block based on its contents. In other words, iHTL optimizes locality of one traversal of all edges of the graph by:<\/p><p style=\"margin-top:-20px;padding-left:20px\">(1) applying push direction for <strong>flipped blocks<\/strong> containing edges to in-hubs, and<br>(2) applying pull direction for processing <strong>sparse block<\/strong> containing edges to non-hubs.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">Moreover, iHTL introduces a new algorithm to efficiently identify the number of flipped blocks by investigating connection between hub vertices of the graph. This allows iHTL to create flipped blocks as much as the graph structure requires and makes iHTL suitable for a wide range of different real-world graph datasets like social networks and web graphs. <\/p>\n\n\n\n<p class=\"has-text-align-justify\">iHTL is 1.5\u00d7 &#8211; 2.4\u00d7 faster than pull and 4.8\u00d7 &#8211; 9.5\u00d7 faster than push in state-of-the-art graph processing frameworks. More importantly, iHTL is 1.3\u00d7 &#8211; 1.5\u00d7 faster than pull traversal of state-of-the-art locality optimizing reordering algorithms such as SlashBurn, GOrder, and Rabbit-Order while reduces the preprocessing time by 780\u00d7, on average.<\/p>\n\n\n\n<div class=\"wp-block-jetpack-slideshow aligncenter\" data-effect=\"slide\"><div class=\"wp-block-jetpack-slideshow_container swiper-container\"><ul class=\"wp-block-jetpack-slideshow_swiper-wrapper swiper-wrapper\"><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing\" class=\"wp-block-jetpack-slideshow_image wp-image-775\" data-id=\"775\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-01.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : Outline\" class=\"wp-block-jetpack-slideshow_image wp-image-776\" data-id=\"776\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-02.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : Introduction\" class=\"wp-block-jetpack-slideshow_image wp-image-777\" data-id=\"777\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-03.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : Pull vs Push\" class=\"wp-block-jetpack-slideshow_image wp-image-778\" data-id=\"778\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-04.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : Is Pull A Suitable Direction\" class=\"wp-block-jetpack-slideshow_image wp-image-779\" data-id=\"779\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-05.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : iHTL: in-Hub Temporal Locality\" class=\"wp-block-jetpack-slideshow_image wp-image-780\" data-id=\"780\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-06.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : iHTL Graph Structure\" class=\"wp-block-jetpack-slideshow_image wp-image-781\" data-id=\"781\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-07.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : SpMV in iHTL\" class=\"wp-block-jetpack-slideshow_image wp-image-782\" data-id=\"782\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-08.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing : Evaluation\" class=\"wp-block-jetpack-slideshow_image wp-image-783\" data-id=\"783\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-09.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph : Conclusion\" class=\"wp-block-jetpack-slideshow_image wp-image-784\" data-id=\"784\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-10.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph : Thanks\" class=\"wp-block-jetpack-slideshow_image wp-image-785\" data-id=\"785\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-11.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Exploiting in-Hub Temporal Locality in SpMV-based Graph : A Gift From QUB\" class=\"wp-block-jetpack-slideshow_image wp-image-786\" data-id=\"786\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/iHTL-12.png\" \/><\/figure><\/li><\/ul><a class=\"wp-block-jetpack-slideshow_button-prev swiper-button-prev swiper-button-white\" role=\"button\"><\/a><a class=\"wp-block-jetpack-slideshow_button-next swiper-button-next swiper-button-white\" role=\"button\"><\/a><a aria-label=\"Pause Slideshow\" class=\"wp-block-jetpack-slideshow_button-pause\" role=\"button\"><\/a><div class=\"wp-block-jetpack-slideshow_pagination swiper-pagination swiper-pagination-white\"><\/div><\/div><\/div>\n\n\n\n<p><strong>Code Availability<\/strong><br>The  source-code will be published soon.<\/p>\n\n\n\n<p><strong>BibTex<\/strong><br><\/p>\n\n\n\n<pre id=\"block-a1647328-d2c5-49ab-92be-f6b22768ac7f\" class=\"wp-block-code\"><code>\n@INPROCEEDINGS{10.1145\/3472456.3472462,\nauthor = {Koohi Esfahani, Mohsen and Kilpatrick, Peter and Vandierendonck, Hans},\ntitle = {Exploiting In-Hub Temporal Locality In SpMV-Based Graph Processing},\nyear = {2021},\nisbn = {9781450390682},\npublisher = {Association for Computing Machinery},\naddress = {New York, NY, USA},\nurl = {https:\/\/doi.org\/10.1145\/3472456.3472462},\ndoi = {10.1145\/3472456.3472462},\nbooktitle = {50th International Conference on Parallel Processing},\nnumpages = {10},\nlocation = {Lemont, IL, USA},\nseries = {ICPP 2021}\n}<\/code><\/pre>\n\n\n\n<p><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/LaganLighter\"><strong>LaganLighter<\/strong><\/a><\/p>\n\n\n\n<p><strong>Related Posts<\/strong><\/p>\n\n\n<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>\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>50th International Conference on Parallel Processing (ICPP&#8217;21)August 9-12, 2021Acceptance Rate: 26.4% DOI:10.1145\/3472456.3472462ACM Digital LibraryPDF Version (Authors&#8217; Copy) This paper investigates the implications made by the structure of real-world graphs with power-law degree distribution on the locality of SpMV graph analytics, and by considering the efficacy of locality optimizing graph reordering algorithms (such as SlashBurn, GOrder, [&hellip;]<\/p>\n","protected":false},"author":1315,"featured_media":1628,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[40],"tags":[34,43,35,36,37,38,39,26,41,29,42,44],"class_list":{"0":"post-544","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-laganlighter","8":"tag-algorithm-design-and-engineering","9":"tag-algorithm-engineering","10":"tag-graph-processing","11":"tag-graph-relabeling","12":"tag-graph-traversal","13":"tag-high-performance-computing","14":"tag-laganlighter","15":"tag-locality","16":"tag-push-and-pull-locality","17":"tag-pushpull","18":"tag-spmv","19":"tag-structure-aware-algorithms","20":"czr-hentry"},"jetpack_featured_media_url":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-12-1.jpg","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/544","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=544"}],"version-history":[{"count":1,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/544\/revisions"}],"predecessor-version":[{"id":3147,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/544\/revisions\/3147"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media\/1628"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=544"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=544"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=544"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}