| dc.description.abstract | Processing large-scale graphs has increasingly become a critical component in a variety
of fields, from scientific computing to social analytics. The size of graphs of interest
are becoming explosively large, preventing them from fitting into the memory of a single-processor system and highlighting the need for fast and efficient methods to process such
graphs. Because of this, there exists a clear need for distributed data structures and parallel
algorithms to facilitate the processing of these large graphs.
Graph traversals – wherein a computation proceeds from one vertex to another along
the edges of a graph – are an important type of algorithm, as they form the backbone
of several other important graph algorithms (e.g., shortest paths, centrality metrics and
connected components). Improving the performance of traversals therefore in turn benefits
all algorithms dependent on them. Despite receiving a great deal of attention from
many researchers for several decades [1, 2, 3, 4, 5], traversal-based computations remain
notoriously difficult to parallelize effectively.
In this proposal, we will discuss two broad techniques for improving the performance
of graph traversals and general parallel graph algorithms:
1. Asynchrony. Increasing the asynchrony of the algorithm allows one to avoid global
synchronization, while still being mindful of the negatives of unbounded asynchrony
including wasted work.
2. Nested parallelism. Allowing to express graph algorithms in a naturally nested
parallel manner enables us to fully exploit all of the available parallelism inherent
in graph algorithms. | |
