
16 Large Scale and Big Data
parallelism and graph parallelism. Graph parallelism is widely used in many domains
such as machine learning, data mining, physics, and electronic circuit designs, among
others. Many problems in these domains can be modeled as graphs in which verti-
ces represent computations and edges encode data dependencies or communications.
Recall that a graph G is a pair (V, E), where V is a nite set of vertices and E is a nite
set of pairwise relationships, E ⊂ V × V, called edges. Weights can be associated with
vertices and edges to indicate the amount of work per each vertex and the communica-
tion data per each edge. To e ...