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


Konstantine Karantasis (University of Illinois)

Date Apr 4, 2013
Time 4:00 pm - 5:00 pm  

Central Time


Siebel Center 2405




Illinois-Intel Parallelism Center


Meg Osfar

Views 2915
Originating Calendar I2PC Events

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


                              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


* 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

link for robots only