[Colloquium] Zhou/Dissertation Defense/Apr 6, 2018

[Margaret Jaffey via Colloquium]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Zhixuan Zhou

Date:  Friday, April 6, 2018

Time:  9:00 AM

Place:  Ryerson 255

Title: NEW METHODS FOR GRAPH COMPUTATION ON SINGLE NODES

Abstract:
There has been a recent explosion in specialized graph computing
frameworks with different classes of framework addressing different
niches of requirements. Specifically, some are designed for graphs
that fit in a single machine's memory, but fail when the graph exceeds
memory size. Other frameworks handle extremely large graphs that
exceed a single machine's memory, but achieve worse performance than
simple C programs on small graphs. Thus, the current state-of-the-art
requires users to adopt one programming framework for small graphs and
a completely different framework for large graphs. In this thesis, we
present GraphZ and GraphStone.

GraphZ has two innovations that improve the performance of software
frameworks for out-of-core graph analytics. The first is
\emph{degree-ordered storage}, a new storage format that dramatically
lowers book-keeping overhead when graphs are larger than memory. The
second innovation replaces existing static messages with novel
\emph{ordered dynamic messages} which update their destination
immediately, reducing both the memory required for intermediate
storage and IO pressure. We implement these innovations in a framework
called GraphZ---which we release as open source---and we compare its
performance to two state-of-the-art out-of-core graph frameworks. For
graphs that exceed memory size, GraphZ's harmonic mean performance
improvements are $1.8$--$8.3\times$ over existing state-of-the-art
solutions. In addition, GraphZ's reduced IO greatly reduces power
consumption, resulting in tremendous energy savings.

GraphStone is a unified framework that outperforms current
best-in-class approaches for both in-memory and out-of-core graph
computing. GraphStone's key contribution is an execution model which
combines the best merits of bulk synchronous and asynchronous updates
to achieve the parallelism and streaming data access of bulk
synchronous models with the fast convergence time of asynchronous
models. We implement GraphStone in C++ and compare its performance to
best-in-class approaches for both in-memory and out-of-core computing.
We find that GraphStone programs require no modification when moving
from small to large graphs, yet GraphStone is 2.5$\times$ faster than
a state-of-the-art in-memory approach and 11.6$\times$ faster than a
popular, robust out-of-core approach.

Zhixuan's advisor is Prof. Henry Hoffmann

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#zhixuanzhou

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=