92 COMMUNICATIONS OF THE ACM | AUGUST 2018 | VOL. 61 | NO. 8 would allow for fast network analysis and serve as a building block for more complicated programs.

Acknowledgments

The work depicted in this article was partially sponsored by Defense Advanced Research Projects Agency (DARPA) under agreement #HR0011-13-2-0001. The content, views and conclusions presented in this document do not necessarily reflect the position or the policy of DARPA or the U.S. government, no official endorsement should be inferred. Distribution Statement A: “Approved for public release; distribution is unlimited.” This work was also partially sponsored by NSF Grant ACI-1339745 (XScala). This research used resources of the Keeneland Computing Facility at the Georgia Institute of Technology, which is supported by the National Science Foundation under Contract OCI- 0910735. Special thanks to Jeff Young for his assistance with running experiments on KIDS. Finally, we would also like to thank NVIDIA Corporation for their donation of a GeForce GTX Titan GPU.

© 2018 ACM 0001-0782/18/8 $15.00

6840 (2001), 907–908.

14. Madduri, K., Ediger, D., Jiang, K., Bader, D., Chavarria-Miranda, D. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. In IEEE International Symposium on Parallel

& Distributed Processing (IPDPS)

(May 2009), 1–8.

15. McLaughlin, A., Bader, D. Revisiting edge and node parallelism for dynamic GPU graph analytics. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPS W) (2014).

16. McLaughlin, A., Bader, D.A. Scalable and high performance betweenness centrality on the GPU. In Proceedings of the 26th ACM/IEEE International Conference on High Performance Computing, Networking, Storage, and Analysis (SC) (2014).

17. Mendez-Lojo, M., Burtscher, M., Pingali, K. A GPU implementation of inclusion-based points-to analysis.

In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ‘ 12 (New York, NY, USA, 2012).

ACM, 107–116.

18. Merrill, D. CUDA Unbound. 2013. https://nvlabs.github.io/cub/ (accessed April 11, 2014).

19. Merrill, D., Garland, M., Grimshaw, A.

Scalable GPU graph traversal.

In Proceedings of the 17th ACM
SIGPLAN Symposium on Principles
and Practice of Parallel Programming,
PPoPP ‘ 12 (New York, NY, USA, 2012).
ACM, 117–128.

20. Porta, S., Latora, V., Wang, F., Strano, E., Cardillo, A., Scellato, S., Iacoviello, V., Messora, R. Street centrality and densities of retail and services in Bologna, Italy. Environment and Planning B: Planning and design 36, 3 (2009), 450–465.

21. Sariyüce, A.E., Saule, E., Kaya, K., Çatalyürek, Ü. Regularizing graph centrality computations. J, Parallel Distrib. Comput. (JPDC) (2014).

22. Shi, Z., Zhang, B. Fast network centrality analysis using GPUs.

BMC Bioinformatics 12, 1

(2011), 149.

23. Soman, J., Narang, A. Fast community detection algorithm with GPUs and multicore architectures. In International Parallel & Distributed Processing Symposium (IPDPS) (IEEE, 2011), 568–579.

24. Vetter, J.S., Glassbrook, R., Dongarra, J., Schwan, K., Loftis, B., McNally, S., Meredith, J., Rogers, J., Roth, P., Spafford, K., Yalamanchili, S. Keeneland: Bringing heterogeneous GPU computing to the computational science community. Comput. Sci. & Engineering 13, 5 (2011), 90–95.

25. Watts, D.J., Strogatz, S.H. Collective dynamics of ‘Small-World’ networks. Nature 393, 6684 (1998), 440–442.

Figure 6. Multi-GPU scaling by number of nodes for various graph structures. Each node contains three GPUs.

Number of nodes
S
pee
du
p
o
ve
r1
n
o
de
S
pee
du
p
o
ve
r1
n
o
de
Scale 16
Scale 17
Scale 18

(a) rgg
Number of nodes
Scale 10

Scale 12 Scale 14 Scale 16 Scale 18 Scale 20

(b) delaunay

0 10 20 30 40 50 60 0 10 20 30 40 50 60 0 10 20 30 40 50 60 0

10 20 30 40 50 60

0 10 20 30 40 50 60

0 10 20 30 40 50 60

Number of nodes Scale 16

Scale 19

(c) kron

References

1. Bader, D. A., Meyerhenke, H., Sanders, P., Wagner, D. (eds) Graph Partitioning and Graph Clustering—10th DIMACS Implementation Challenge, volume 588 of Contemporary Mathematics

(2013).

2. Barabási, A.-L., Albert, R. Emergence of scaling in random networks.

Science 286, 5439 (1999),

509–512.

3. Brandes, U. A faster algorithm for betweenness centrality. J. Math.

Sociol. 25 (2001), 163–177.

4. Brandes, U. On variants of shortest-path betweenness centrality and their generic computation. Social Networks

30, 2 (2008), 136–145.

5. Bullmore, E., Sporns, O. Complex brain networks: Graph theoretical analysis of structural and functional systems. Nat. Rev. Neurosci. 10, 3

(2009), 186–198.

6. Davidson, A.A., Baxter, S., Garland, M., Owens, J.D. Work-efficient parallel GPU methods for single-source shortest paths. In International Parallel and Distributed Processing Symposium 28 (2014).

7. Davis, T. A., Hu, Y. The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1 (Dec. 2011),

1:1–1: 25.

8. Freeman, L. C. A set of measures of centrality based on betweenness.

Sociometry (1977), 35–41.

9. Hoberock, J., Bell, N. Thrust: A Parallel Template Library. Online at: http://thrust.googlecode. com, 42: 43

(2010).

10. Jia, Y., Lu, V., Hoberock, J., Garland, M.,
Hart, J. C. Edge v. node parallelism
for graph centrality metrics. GPU
Computing Gems 2 (2011), 15–30.

11. Jin, S., Huang, Z., Chen, Y., Chavarria-Miranda, D., Feo, J., Wong, P. C. A novel application of parallel betweenness centrality to power grid contingency analysis. In IEEE International Symposium on Parallel Distributed Processing (IPDPS) (2010), 1–7.

12. Leskovec, J., Krevl, A. SNAP datasets: Stanford large network dataset collection. http://snap.stanford.edu/ data, June 2014.

13. Liljeros, F., Edling, C. R., Amaral, L.A., Stanley, H. E., Aberg, Y. The web of human sexual contacts. Nature 411,

Adam McLaughlin (adam27x@gatech. edu), School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA, USA.

David A. Bader ( [e-mail]. edu), School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA, USA.