Event Detail Information
Event Detail Information
I2PC Seminar Series - Parallel Reordering: Graph Processing on the Dark Side of BFS
Illinois-Intel Parallelism Center (I2PC) Distinguished Speaker Series
Thursday, April 4th, 4-5pm Central Time, Siebel Center 2405
Parallel Reordering: Graph Processing on the Dark Side of BFS
University of Illinois
ABSTRACT: Reordering of sparse matrices and graphs are standard preprocessing procedures for a plethora of applications, most notably those for sparse linear algebra. Many heuristic algorithms have been proposed for addressing this computationally hard problem. Since these algorithms have been considered efficient in comparison to subsequent computations, such as factorization, little work has gone into creating parallel implementations. However the introduction of highly parallel numerical methods for sparse matrices as well as the demand for applying reordering to increasingly large graphs are rendering reordering algorithms a potential bottleneck.
In this talk, I'll present the first parallel implementations of two widely used reordering algorithms: Reverse Cuthill-McKee (RCM) and Sloan. These algorithms are based on performing specific graph traversals. Recent work has successfully parallelized breadth-first search (BFS), a less constrained graph traversal than either RCM or Sloan. We evaluated our parallelizations on multicore systems and with large matrices from several domains. Our implementations present significant performance improvements compared to a state-of-the-art sequential library, without compromising the quality of reordering. Our results demonstrate that it is possible to achieve parallel speedup for several graph traversal-based reordering algorithms beyond BFS, even for highly constrained ones such as RCM and Sloan.
BIO: Konstantine Karantasis is a visiting lecturer in ECE at the University of Illinois, Urbana-Champaign and a postdoctoral research associate in Coordinated Science Lab. He received his PhD in Computer Engineering at the University of Patras, Greece in 2011. His ongoing research focuses in runtime, compiler and system optimizations that improve the performance of irregular algorithms and accelerate applications of big data requirements.
The talk will be streamed live at this link:
Questions to the speaker for live response can be directed to our chat
A complete list of seminars (with archived copies of past talks) is