{"id":403,"date":"2020-06-05T17:20:00","date_gmt":"2020-06-05T16:20:00","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/graptor-efficient-pull-and-push-style-vectorized-graph-processing\/"},"modified":"2020-06-05T17:20:00","modified_gmt":"2020-06-05T16:20:00","slug":"graptor-efficient-pull-and-push-style-vectorized-graph-processing","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/graptor-efficient-pull-and-push-style-vectorized-graph-processing\/","title":{"rendered":"Graptor: Efficient Pull and Push Style Vectorized Graph Processing"},"content":{"rendered":"\n<p><a href=\"https:\/\/doi.org\/10.1145\/3392717.3392753\">https:\/\/doi.org\/10.1145\/3392717.3392753<\/a><\/p>\n\n\n\n<p>Vectorization seeks to accelerate computation through data-level parallelism. Vectorization has been applied to graph processing, where the graph is traversed either in a push style or a pull style. As it is not well understood which style will perform better, there is a need for both vectorized push and pull style traversals. This paper is the first to present a general solution to vectorizing push style traversal. It more-over presents an enhanced vectorized pull style traversal.<\/p>\n\n\n\n<p>Our solution consists of three components:&nbsp;<em><strong>CleanCut<\/strong><\/em>, a graph partitioning approach that rules out inter-thread race conditions;&nbsp;<em><strong>VectorFast<\/strong><\/em>, a compact graph representation that supports fast-forwarding through the edge stream; and&nbsp;<em><strong>Graptor<\/strong><\/em>, a domain-specific language and compiler for auto-vectorizing and optimizing graph processing codes.<\/p>\n\n\n\n<p>Experimental evaluation demonstrates average speedups of 2.72X over Ligra, 2.46X over GraphGrind, and 2.33X over GraphIt. Graptor outperforms Grazelle, which performs vectorized pull style graph processing, by 4.05 times.<\/p>\n\n\n<ul class=\"wp-block-latest-posts__list has-dates wp-block-latest-posts\"><\/ul>","protected":false},"excerpt":{"rendered":"<p>https:\/\/doi.org\/10.1145\/3392717.3392753 Vectorization seeks to accelerate computation through data-level parallelism. Vectorization has been applied to graph processing, where the graph is traversed either in a push style or a pull style. As it is not well understood which style will perform better, there is a need for both vectorized push and pull style traversals. This paper [&hellip;]<\/p>\n","protected":false},"author":974,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[28],"tags":[29,30],"class_list":{"0":"post-403","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-graptor","7":"tag-pushpull","8":"tag-simd","9":"czr-hentry"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/403","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\/974"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=403"}],"version-history":[{"count":0,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/403\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}