Hierarchical Communication Reduction (HCR) Paradigm
An important category of input graphs exhbit the Power-Law Out-Degree (PLOD) distribution. In such graphs, the majority of vertices have few connections, however, a few vertices (called hubs) may have a huge number of connections (e.g. to 35%-60% of the graph). This distribution is typically exhibited by natural graphs such as social networks, web-graphs, etc.
For these graphs, increasing asynchrony may not be beneficial, since the cost of redundant work for hub vertices may be prohibitive. Therefore, the best course of action is to run it in BSP execution (i.e., k=0). However, in this scenario, the performance of the algorithm becomes bound by the amount of data communicated in the system. We can significantly improve the performance if we reduce the number of bytes communicated, by taking advantage of algorithmic redundancy inherent to many algorithms.
Algorithmic redundancy describes the phenomenon that many graph algorithms tend to send the same data from a vertex to all its neighbors. The knowledge that this data is the same is tied to the distribution of the input graph, and is therefore lost in fine-grained expression of graph algorithms. The communication-reduction paradigm imposes the machine-hierarchy on the input graph, exposing the paths where data can be de-duplicated. Therefore, a single copy of the message is sent to the remote location, and is applied to all neighbors on that location. This can reduce communication by 30% or more1.
To use this paradigm, we need to create a hierarchical graph which is the result of imposing the machine hierarchy on the input graph (note: this is a mutating process, which will mutate the input graph to remove the co-located edges):
auto hierarchy = create_machine_hierarchy(graph);
The created hierarchy can then be plugged-in to the HCR paradigm like so:
h_paradigm(BFSVertexOp(), BFSNeighborOp(), hierarchy, graph);
A variant allows further reduction by aggregating and reducing values on the hub vertices (hubs is another hierarchy of hub vertices only):
h_hubs_paradigm(BFSVertexOp(), BFSNeighborOp(), vertex_reducer(), hierarchy, hubs, graph);
Technical Specification of the HCR Paradigm
- The creation of the hierarchy mutates the input graph.
- Each level of the hierarchy represents a super-graph of the level below it. A super-vertex represents a grouping of vertices in the level below, while a super-edge represents the group of cross-edges between the sets of vertices represented by the two super-vertices which the super-edge connects.
1 Harshvardhan, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, "An Algorithmic Approach to Communication Reduction in Parallel Graph Algorithms," In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), San Francisco, CA, USA, November 2015.