Logarithmic Radix Binning and Vectorized Triangle Counting

Oded Green, James Fox, Alex Watkins, Alok Tripathy, Kasimir Gabert, Euna Kim, Xiaojing An, Kumar Aatish, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations


Triangle counting is a building block for numerous graph applications and given the fact that graphs continue to grow in size, its scalability is important. As such, numerous algorithms have been designed for triangle counting - some of which are compute-bound rather than memory bound. Even for compute-bound algorithms, one of the key challenges is the limited control flow available on the processor. This is in-part due to the high dependency between the control flow, input data, and limited utilization of vector instructions. Not surprising, compilers are not always able to detect these data dependencies and vectorize the algorithms. Using the branch-avoiding model we show to remove control flow restrictions by replacing branches with an equivalent set of arithmetic operations. More so, we show how these can be vectorized using Intel's AVX-512 instruction set and that our new vectorized algorithms are 2×-5× faster than scalar counterparts. We also present a new load balancing method, Logarithmic Radix Binning (LRB) that ensures that threads and the vector data lanes execute a near equal amount of work at any given time. Altogether, our algorithm outperforms several 2017 HPEC Graph Challenge Champions such as the KOKKOS framework and a GPU based algorithm by anywhere from 1.5× and up to 14×.

Original languageEnglish (US)
Title of host publication2018 IEEE High Performance Extreme Computing Conference, HPEC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538659892
StatePublished - Nov 26 2018
Externally publishedYes
Event2018 IEEE High Performance Extreme Computing Conference, HPEC 2018 - Waltham, United States
Duration: Sep 25 2018Sep 27 2018

Publication series

Name2018 IEEE High Performance Extreme Computing Conference, HPEC 2018


Conference2018 IEEE High Performance Extreme Computing Conference, HPEC 2018
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Hardware and Architecture


Dive into the research topics of 'Logarithmic Radix Binning and Vectorized Triangle Counting'. Together they form a unique fingerprint.

Cite this