Distributed BFS

Required Readings

• Course notes

Optional

• Parallel breadth-first search on distributed memory systems

Summary

• Graphs and Adjacency Matrices
• Matrix based BFS
  • 1D Distributed BFS
  • 2D Distributed BFS

Graphs and Adjacency Matrices

To turn a graph into an adjacency matrix:

1. Give each vertex an integer label
2. Create a matrix to represent the graph
3. For any edge going from i to j, A[i][j] = true/1

Matrix for an undirected graph is symmetric

For n vertices and m edges, the array will be of size nxn with 2m non-zeroes

Matrix based BFS

Start with some starting node S, an add all its neighbors to frontier 1. Iterate through frontier 1 and add all of its unvisited neighbors to frontier 2, etc.

For any unvisited node i, there is a given frontier L, if there are any edges from frontier to i, we should update i’s distance.

For any frontier (vector), does i have any 1’s in the corresponding locations, if so, we can update another vector to record this.

$\text{edge } j \rightarrow i \implies a_{ji} = 1$

$u[i] \leftarrow \bigvee_{j=1}^{n}\left( f_j \land a_{ji} \right)$

This is just a boolean matrix-vector product

$u \leftarrow A^T \cdot f$

for-all ui = 1 and di = inf do
  di <- l + 1
  fi <- 1

1D Distributed BFS

1. Partition columns of A and entries of U by p processes
2. Compute $u \leftarrow A^T \cdot f$
3. Update local distances
4. Identify local vertices of the next frontier
5. All-to-all, exchange frontier

$O\left( \alpha \cdot P + \beta \ldots \right)$

2D Distributed BFS

$O\left( \alpha \cdot \sqrt{P} + \beta \ldots \right)$