{"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 class=\"wp-block-paragraph\"><a href=\"https:\/\/doi.org\/10.1145\/3392717.3392753\">https:\/\/doi.org\/10.1145\/3392717.3392753<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">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 class=\"wp-block-paragraph\">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 is-layout-flow wp-block-latest-posts-is-layout-flow\"><\/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_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":[28],"tags":[29,30],"class_list":["post-403","post","type-post","status-publish","format-standard","category-graptor","tag-pushpull","tag-simd","czr-hentry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_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}]}}