Abstract
In this chapter, we consider the applicability of a non-traditional massively multithreaded architecture, the Cray MTA-2 [13], as a platform for graph algorithms. Graph-theoretic problems have emerged as a prominent computational workload in the petascale computing era, and are representative of fundamental kernels in biology, scientific computing, and applications in national security. However, they pose serious challenges on current parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality [35]. We present multithreaded algorithms for two fundamental graph problems – single source shortest paths and connected components – that are designed for processing large-scale, unstructured graph instances.
Kamesh Madduri
Associate Professor
David A. Bader
Distinguished Professor and Director of the Institute for Data Science
David A. Bader is a Distinguished Professor in the Department of Computer Science at New Jersey Institute of Technology.