Enterprise: Quick Facts

Enterprise is built to unlock the massive potential of direction optimization for GPU based BFS. After direction optimization, one would immediately notice that direction optimization, by itself, introduces very little benefit for GPU based BFS. The radical reason lies in GPU’s hardware feature: GPU has tremendous amount of simplified threads, leading it highly sensitive to atomic operation and workload imbalance. Only after these two issues are properly addressed, speedup would appear.

Correspondingly, Enterprise introduces streamlined thread scheduling and workload balancing techniques to tackle these two issues, respectively. Further, Enterprise discovers the fundamental cause for direction switching -- Hub Vertex -- too many hub vertices become frontiers thus lead to work explosion and subsequently cause direction switching. As a consequence, we introduce hub vertex based optimizations for Enterprise to further boost its performance.

Medals Enterprise obtained:
  • Graph 500 Ranking No. 43 (June 2014)
  • Green Graph 500 (Small Data Category) Ranking No. 1 (June 2014)

Please do not hesitate to contact me (asherliu@gwu.edu) if you have any questions regarding Enterprise.