* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


Design, Implementation, and Optimization of Irregular Graph Algorithms on HPC Platforms

Speaker: George M. Slota
Penn State University

April 11, 2016 - 4:00 p.m. to 5:00 p.m.
Location: DCC 324
Hosted By: Dr. Christopher Carothers (x2930)


Graphs are common, complex, and can be very large, which makes them important to study yet computationally challenging to work with. The extreme irregularity of many real-world graphs make the parallelization of algorithms to analyze such graphs difficult. With the massive parallelism of GPUs, Xeon Phis, and distributed systems, the challenges are even harder for algorithm designers to overcome. I will present my efforts that include the development of several techniques for effective multicore, manycore, and distributed parallelization of graph algorithms. This includes research that has resulted in FASCIA, a subgraph enumeration tool in shared and distributed memory that runs several orders-of-magnitude faster than prior work; Multistep, a method for shared-memory graph connectivity on average 2x faster than the most recent state-of-the-art; manycore optimizations, that accelerate graph algorithms on manycore processors such as GPUs and Xeon Phis up to 3x faster than highly optimized CPU code; and PuLP, a low overhead graph partitioner that scales to networks with trillions of edges. Additionally, I'll present how using techniques derived from these efforts, a suite of distributed graph analytics was imp lemented and applied to study the largest publicly-available web crawl of 3.5 billion pages and 130 billion links, with end-to-end execution of analysis completing in under 20 minutes on only 256 nodes of the Blue Waters system.

At a broad scope, this presentation will discuss my research involving graph algorithm design and implementation in three primary areas: (1) Algorithm design and optimization at the node (shared-memory) level; (2) Algorithm design and optimization at the system (distributed-memory) level; (3) Developing generalized approaches to apply these techniques to real-world problems. My primary research goals are to enable complex analysis of very large graph-structured datasets across a broad range of scientific domains and applications.


George grew up in Pittsburgh and received a B.S. with honors in 2009 from Penn State, where he studied computer engineering, math, physics, and materials science. After graduation, George spent two years working for the Navy at the Naval Undersea Warfare Center. He assisted with research and engineering projects related to unmanned underwater vehicles, human computer interaction, and submarine computer systems. George returned to Penn State in 2012 to complete his PhD. Under advisement of Kamesh Madduri, George has performed research into parallel graph algorithms on HPC systems, with an emphasis on social and biological graph mining applications. In addition, George has been working at Sandia National Labs since 2013, where he has been developing scalable graph and matrix algorithms in support of scientific computing applications.

Last updated: April 1, 2016