Bounded Asynchrony and Nested Parallelism for Scalable
Graph Processing
Presenter
Event Type
Doctoral Showcase
Applications
Architectures
Graph Algorithms
Heterogeneous Systems
TimeTuesday, November 14th10am -
5:15pm
LocationFour Seasons Ballroom
DescriptionProcessing large-scale graphs has become a critical
component in a variety of fields, from scientific
computing to social analytics. The irregular access
pattern for graph workloads, coupled with complex graph
structures and large data sizes makes efficiently
executing parallel graph workloads challenging. In this
dissertation, we develop two broad techniques for
improving the performance of general parallel graph
algorithms: bounded asynchrony and nested parallelism.
Increasing asynchrony in a bounded manner allows one to
avoid
costly global synchronization at scale, while still avoiding the penalty of unbounded asynchrony including redundant work. Using this technique, we scale a BFS workload to 98,304 cores where traditional methods stop scaling. Additionally, asynchrony enables a new family of approximate algorithms for applications tolerant to fixed amounts of error. Representing graph algorithms in a nested parallel manner enables the full use of available parallelism inherent in graph algorithms, while efficiently managing communication through nested sections.
costly global synchronization at scale, while still avoiding the penalty of unbounded asynchrony including redundant work. Using this technique, we scale a BFS workload to 98,304 cores where traditional methods stop scaling. Additionally, asynchrony enables a new family of approximate algorithms for applications tolerant to fixed amounts of error. Representing graph algorithms in a nested parallel manner enables the full use of available parallelism inherent in graph algorithms, while efficiently managing communication through nested sections.
Presenter
