I2PC Events

I2PC Events

skip to events

calendar tabs

  •  All 
  • Grid
  • Month
  • Week
  • Day
  • (Selected tab) Detail

Event Detail Information

Event Detail Information

I2PC Seminar Series - Parallel Reordering: Graph Processing on the Dark Side of BFS

Speaker Konstantine Karantasis (University of Illinois)
Date Apr 4, 2013
Time 4:00 pm - 5:00 pm   Central Time
Location Siebel Center 2405
Cost Free
Sponsor Illinois-Intel Parallelism Center
Contact Meg Osfar
Views 2910

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