Graph algorithms play a key enabling role in numerous scientific and engineering applications. Thus, there is a need for efficient parallel algorithms and their implementations. However, graph algorithms are challenging to implement on traditional and emerging high performance computing architectures. In this presentation, I will discuss some of the challenges that limit performance and explore solutions using graph matching and coloring as case studies. We will consider traditional multicore as well as non-traditional massively multithreaded (Cray XMT) platforms, and show how architectural features influence the design of parallel algorithms.
Mahantesh Halappanavar is a Research Scientist with the Computational Sciences and Mathematics Division at the Pacific Northwest National Laboratory. He received his MS and PhD degrees in Computer Science from the Old Dominion University in 2003 and 2009 respectively. His work focuses on parallel graph algorithms and spans several application areas including analysis of electric power grids, cyber security, statistical textual analysis, numerical linear algebra, and machine learning. His work explores the interplay of algorithm design, architectural features, and input characteristics targeting massively multithreaded architectures such as the Cray XMT and emerging multicore and manycore platforms.