{"id":1286,"date":"2022-06-15T10:12:17","date_gmt":"2022-06-15T09:12:17","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/software-defined-floating-point-number-formats-and-their-application-to-graph-processing\/"},"modified":"2022-06-15T10:12:17","modified_gmt":"2022-06-15T09:12:17","slug":"software-defined-floating-point-number-formats-and-their-application-to-graph-processing","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/software-defined-floating-point-number-formats-and-their-application-to-graph-processing\/","title":{"rendered":"Software-Defined Floating-Point Number Formats and Their Application to Graph Processing &#8211; ICS&#8217;22"},"content":{"rendered":"\n<p><a href=\"http:\/\/doi.org\/10.1145\/3524059.3532360\" data-type=\"URL\" data-id=\"doi.org\/10.1145\/3524059.3532360\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>DOI: <\/strong>10.1145\/3524059.3532360<\/a><\/p>\n\n\n<p><span dir=\"ltr\" role=\"presentation\">This paper proposes software-defined floating-point num<\/span><span dir=\"ltr\" role=\"presentation\">ber formats for graph processing workloads, which can im<\/span><span dir=\"ltr\" role=\"presentation\">prove performance in irregular workloads by reducing cache <\/span><span dir=\"ltr\" role=\"presentation\">misses. Efficient arithmetic on software-defined number for<\/span><span dir=\"ltr\" role=\"presentation\">mats is challenging, even when based on conversion to wider,<\/span> <span dir=\"ltr\" role=\"presentation\">hardware-supported formats. We derive efficient conversion <\/span><span dir=\"ltr\" role=\"presentation\">schemes that are tuned to the IA64 and AVX512 instruc<\/span><span dir=\"ltr\" role=\"presentation\">tion sets. <\/span><\/p>\n<p><span dir=\"ltr\" role=\"presentation\">We demonstrate that: (i) reduced-precision number <\/span><span dir=\"ltr\" role=\"presentation\">formats can be applied to graph processing without loss of<\/span> <span dir=\"ltr\" role=\"presentation\">accuracy; (ii) conversion of floating-point values is possible<\/span><br role=\"presentation\"><span dir=\"ltr\" role=\"presentation\">with minimal instructions; (iii) conversions are most effi<\/span><span dir=\"ltr\" role=\"presentation\">cient when utilizing vectorized instruction sets, specifically <\/span><span dir=\"ltr\" role=\"presentation\">on IA64 processors. <\/span><\/p>\n<p><span dir=\"ltr\" role=\"presentation\">Experiments on twelve real-world graph <\/span><span dir=\"ltr\" role=\"presentation\">data sets demonstrate that our techniques result in speedups<\/span> <span dir=\"ltr\" role=\"presentation\">up to 89% for PageRank and Accelerated PageRank, and up to <\/span><span dir=\"ltr\" role=\"presentation\">35% for Single-Source Shortest Paths. The same techniques<\/span> <span dir=\"ltr\" role=\"presentation\">help to accelerate the integer-based maximal independent <\/span><span dir=\"ltr\" role=\"presentation\">set problem by up to 262%.<\/span><\/p>","protected":false},"excerpt":{"rendered":"<p>DOI: 10.1145\/3524059.3532360 This paper proposes software-defined floating-point number formats for graph processing workloads, which can improve performance in irregular workloads by reducing cache misses. Efficient arithmetic on software-defined number formats is challenging, even when based on conversion to wider, hardware-supported formats. We derive efficient conversion schemes that are tuned to the IA64 and AVX512 instruction [&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":[34,35,37,47,38,30],"class_list":{"0":"post-1286","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-graptor","7":"tag-algorithm-design-and-engineering","8":"tag-graph-processing","9":"tag-graph-traversal","10":"tag-graptor","11":"tag-high-performance-computing","12":"tag-simd","13":"czr-hentry"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1286","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=1286"}],"version-history":[{"count":0,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1286\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=1286"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=1286"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=1286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}