We were discussing the parallel Breadth-First-Search using the 2D partitioning approach.
This is the latter case of two highly tuned parallel approaches for BFS on large parallel systems:
1) a level synchronous strategy that relies on a simple vertex based graph partitioning and
2) a two-dimensional sparse matrix partitioning-based approach that mitigates parallel communication overhead.
In the second approach, the idea is that with each BFS iteration is equivalent to a sparse matrix -sparse vector multiplication. The adjacencies can only be atmost N nodes so the vector can only have N dimensions and not all of them are used.
The algorithm computes the breadth first spanning tree by returning a dense parents array. The inner loop performs a single level traversal
The exploration of level k in BFS is equivalent to transposing the adjacency matrix and performing a matrix vector multiplication on an element wise multiplication of a complement to dense parents array. Since the parents array is a boolean array, a complement operation inverts it elementwise. The algorithm always picks the parent with the vertex as the highest label.
All vectors and input matrix are distributed 2D wise. For example, f which is an initially sparse vector. Each n/p sized piece of the vector takes a progressive section of the adjacency matrix. Notice the algorithm is written in a gather-appy-scatter strategy Since the matrix and the vectors are distributed, the algorithm proceeds parallely.
There are two distinct communication phases in a BFS algorithm- an expand phase over the processor column and a fold phase over the processor row.
In any parallelization, we have partition of tasks and communication overhead. If we have non-overlapped partition through out the algorithm, we can have least communication. This works for batch processing map-Reduce method in Big Data. For BFS algorithm there is a tradeoff that needs to be struck between the partitioning and the communication. This approach cited here made the communication efficient but there are other ways to tune a hybrid approach.
This is the latter case of two highly tuned parallel approaches for BFS on large parallel systems:
1) a level synchronous strategy that relies on a simple vertex based graph partitioning and
2) a two-dimensional sparse matrix partitioning-based approach that mitigates parallel communication overhead.
In the second approach, the idea is that with each BFS iteration is equivalent to a sparse matrix -sparse vector multiplication. The adjacencies can only be atmost N nodes so the vector can only have N dimensions and not all of them are used.
The algorithm computes the breadth first spanning tree by returning a dense parents array. The inner loop performs a single level traversal
The exploration of level k in BFS is equivalent to transposing the adjacency matrix and performing a matrix vector multiplication on an element wise multiplication of a complement to dense parents array. Since the parents array is a boolean array, a complement operation inverts it elementwise. The algorithm always picks the parent with the vertex as the highest label.
All vectors and input matrix are distributed 2D wise. For example, f which is an initially sparse vector. Each n/p sized piece of the vector takes a progressive section of the adjacency matrix. Notice the algorithm is written in a gather-appy-scatter strategy Since the matrix and the vectors are distributed, the algorithm proceeds parallely.
There are two distinct communication phases in a BFS algorithm- an expand phase over the processor column and a fold phase over the processor row.
In any parallelization, we have partition of tasks and communication overhead. If we have non-overlapped partition through out the algorithm, we can have least communication. This works for batch processing map-Reduce method in Big Data. For BFS algorithm there is a tradeoff that needs to be struck between the partitioning and the communication. This approach cited here made the communication efficient but there are other ways to tune a hybrid approach.
No comments:
Post a Comment