CSE Seminar: A Framework for Processing Large Graphs in Shared Memory

*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************

Event Details
  • Date/Time:
    • Friday October 31, 2014 - Saturday November 1, 2014
      2:00 pm - 2:59 pm
  • Location: Atlanta, GA
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    $0.00
  • Extras:
Contact

Della Phinisee

della@cc.gatech.edu

Summaries

Summary Sentence: CSE Seminar with Carnegie Mellon's Julian Shun

Full Summary: No summary paragraph submitted.

Media
  • Julian Shun, Carnegie Mellon - CSE Seminar Julian Shun, Carnegie Mellon - CSE Seminar
    (image/png)

Speaker: Julian Shun, Carnegie Mellon University

Location: MiRC 102A and B

Abstract:

In the first part of the talk, we discuss Ligra, a shared-memory graph processing system that we recently developed. The framework has two very simple routines, one for mapping over edges and one for mapping over vertices. The routines can be applied to any subset of the vertices, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Based on recent ideas used in a very fast algorithm for breadth-first search (BFS), the routines automatically adapt to the density of vertex sets.  We implement several algorithms in this framework, including BFS, betweenness centrality, graph radii estimation, graph connectivity, PageRank and single-source shortest paths.  Our algorithms expressed using this framework are very simple and concise, and perform almost as well as highly optimized code. Furthermore, they get good speedups on a 40-core machine and are sometimes significantly more efficient than previously reported results using graph frameworks on machines with many more cores.

In the second part of the talk, we discuss Ligra+, which integrates graph compression techniques into Ligra.  On average, Ligra+ is able to represent graphs using about half of the space used by Ligra (which stores the graphs uncompressed).  On a 40-core machine, the performance of Ligra+ is usually competitive with or faster than Ligra due to its smaller memory footprint.  Our extensive experimental study shows that Ligra+ is able to support graphs using less memory, or much larger graphs using the same amount of memory, while performing as well as or faster than Ligra. As far as we know, Ligra+ is the first graph processing system to support a reasonably broad set of parallel graph algorithms on compressed graphs.

Bio:

Julian Shun is currently a Ph.D. student in Computer Science at Carnegie Mellon University, and is advised by Guy Blelloch. He is interested in developing large-scale parallel algorithms for graph processing, and parallel string algorithms and data structures. He is also interested in designing methods for writing deterministic parallel programs and benchmarking parallel programs. Julian obtained his undergraduate degree in Computer Science from UC Berkeley.

Additional Information

In Campus Calendar
No
Groups

College of Computing, School of Computational Science and Engineering

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
Carnegie Mellon, graph compression techniques, Ligra, shared-memory graph processing system
Status
  • Created By: Brittany Aiello
  • Workflow Status: Published
  • Created On: Sep 16, 2014 - 11:02am
  • Last Updated: Apr 13, 2017 - 5:21pm