The Grainger College of Engineering
Parallel Programming Laboratory

Fine-grained Graph Algorithms

We are developing techniques to speed up graph algorithms at scale. In particular, we are interested in fine-grained, communication-bound algorithms.

Our first target is the single-source shortest paths (SSSP) problem. In SSSP, the input is a weighted, directed graph. One vertex is selected as the source, and the output is a list of distances from the source to each vertex in the graph. Traditional parallel SSSP approaches either focus on maximizing work efficiency at the cost of synchronization (delta-stepping) or maximizing asynchronous communication at the cost of unnecessary distance updates (parallel Bellman-Ford). We propose a new approach that is work efficient and completely asynchronous. This is based on a framework called ACIC (Asynchronous Continuous Introspection and Control). We start executing SSSP with a parallel Bellman-Ford approach: when a vertex receives a distance update, if the update reduces the distance to the root, new updates are generated and sent to each neighbor. As this executes, a concurrent system of broadcasts and reductions monitors the creation, processing, and flow of updates by collecting statistics from each PE (such as the number of created updates and the weight distribution of pending updates). Based on this information, a periodic broadcast to all PEs provides thresholds that control which updates are immediately sent to their destinations and which ones are held back.

Our SSSP algorithm uses tramlib, a message aggregation library designed for programs that are distributed and with multithreaded processes. Tramlib reduces the cost of communication by combining multiple small messages (updates in SSSP) into a single message sent over an interconnect, reducing per-message overheads. When ACIC broadcasts thresholds in SSSP, two thresholds are sent. One threshold determines if a message is immediately sent via tramlib or is held back in an application-level buffer. The second threshold is a receiver-side threshold. All PEs store pending updates in a priority queue, and the priority queue threshold prevents updates above that threshold from being pulled from the priority queue. The goal of both thresholds is to minimize the generation of updates by prioritizing the flow of smaller-weighted updates, which are more likely to be the actual shortest path value for a vertex. 

While ACIC was first designed for SSSP, our intention is to apply ACIC to a class of similar graph algorithms where message flows can be controlled based on priorities. For more on this, see the attached paper.

People

Papers / Talks