Illinois-Intel Parallelism Center (I2PC) Distinguished Speaker Series

                          http://i2pc.cs.illinois.edu/

Thursday, April 4th, 4-5pm Central Time, Siebel Center 2405

=======================================================

     Parallel Reordering: Graph Processing on the Dark Side of BFS

                              Konstantine Karantasis

                                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:

* http://media.cs.illinois.edu/live/I2PClive.asx

Questions to the speaker for live response can be directed to our chat

moderator:

* http://i2pc.cs.illinois.edu/chat

A complete list of seminars (with archived copies of past talks) is

available here:

* http://i2pc.cs.illinois.edu/seminars.html