objectEdgePartition2D extends PartitionStrategy with Product with Serializable
Assigns edges to partitions using a 2D partitioning of the sparse edge adjacency matrix,
guaranteeing a 2 * sqrt(numParts) - 1 bound on vertex replication.
Suppose we have a graph with 12 vertices that we want to partition
over 9 machines. We can use the following sparse matrix representation:
The edge denoted by E connects v11 with v1 and is assigned to processor P6. To get the
processor number we divide the matrix into sqrt(numParts) by sqrt(numParts) blocks. Notice
that edges adjacent to v11 can only be in the first column of blocks (P0, P3,
P6) or the last
row of blocks (P6, P7, P8). As a consequence we can guarantee that v11 will need to be
replicated to at most 2 * sqrt(numParts) - 1 machines.
Notice that P0 has many edges and as a consequence this partitioning would lead to poor work
balance. To improve balance we first multiply each vertex id by a large prime to shuffle the
vertex locations.
One of the limitations of this approach is that the number of machines must either be a
perfect square. We partially address this limitation by computing the machine assignment to
the next
largest perfect square and then mapping back down to the actual number of machines.
Unfortunately, this can also lead to work imbalance and so it is suggested that a perfect
square is used.
Linear Supertypes
Product, Equals, PartitionStrategy, Serializable, Serializable, AnyRef, Any
Assigns edges to partitions using a 2D partitioning of the sparse edge adjacency matrix, guaranteeing a
2 * sqrt(numParts) - 1bound on vertex replication.Suppose we have a graph with 12 vertices that we want to partition over 9 machines. We can use the following sparse matrix representation:
__________________________________ v0 | P0 * | P1 | P2 * | v1 | **** | * | | v2 | ******* | ** | **** | v3 | ***** | * * | * | ---------------------------------- v4 | P3 * | P4 *** | P5 ** * | v5 | * * | * | | v6 | * | ** | **** | v7 | * * * | * * | * | ---------------------------------- v8 | P6 * | P7 * | P8 * *| v9 | * | * * | | v10 | * | ** | * * | v11 | * <-E | *** | ** | ----------------------------------The edge denoted by
Econnectsv11withv1and is assigned to processorP6. To get the processor number we divide the matrix intosqrt(numParts)bysqrt(numParts)blocks. Notice that edges adjacent tov11can only be in the first column of blocks(P0, P3, P6)or the last row of blocks(P6, P7, P8). As a consequence we can guarantee thatv11will need to be replicated to at most2 * sqrt(numParts) - 1machines.Notice that
P0has many edges and as a consequence this partitioning would lead to poor work balance. To improve balance we first multiply each vertex id by a large prime to shuffle the vertex locations.One of the limitations of this approach is that the number of machines must either be a perfect square. We partially address this limitation by computing the machine assignment to the next largest perfect square and then mapping back down to the actual number of machines. Unfortunately, this can also lead to work imbalance and so it is suggested that a perfect square is used.