DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs

Dijkstra’s algorithm is a common SSSP algorithm (Dijkstra et al., 1959), and the main optimization methods are priority queue of binary heap and Fibonacci heap (Johnson, 1977; Raman, 1997; Thorup, 2000; Fredman and Tarjan, 1987; Moret and Shapiro, 1992; Chen et al., 2007).

Meyer et al. proposed an optimized Dijkstra’s algorithm, which is a parallel version for a large class of graphs (Meyer and Sanders, 2003). The best parallel version of the $\Delta$-stepping Dijkstra’s algorithm takes $O(D\cdot L\cdot\log n+\log^{2}n)$ time and $O(n+m+D\cdot L\cdot\log n)$ work on average, where $L$ denotes the maximum shortest paths weight from the source node ($s$) to any node reachable from $s$, and $D$ represents the maximum node degree (Meyer and Sanders, 2003).

Scott Beamer et al. proposed a hybrid BFS algorithm that combines a conventional top-down approach with a novel bottom-up approach (Beamer et al., 2012). In the top-down approach, nodes within the active frontier seek unvisited child nodes, whereas in the bottom-up approach, unvisited nodes seek parents within the active frontier. Scott Beamer et al. further optimized the performance of direction-optimized BFS in various application scenarios (Beamer et al., 2013; Buluç et al., 2017), ultimately integrating it into GAP (Graph Algorithm Platform benchmark Suite). GAP is a portable high-performance baseline which includes representative implementations of state-of-the-art performance, and is intended to help graph processing research by standardizing evaluations(Beamer et al., 2015).

Julian Shun and Laxman Dhulipala et al. inspired by the direction-optimized BFS algorithm, achieve close to the same efficiency (time and space) as the optimized BFS of Beamer et. al. and using a much simpler implementation code (Shun and Blelloch, 2013; Shun et al., 2015). Further, they promoted widespread applications of this optimization approach and constructed a high-performance computing framework called GBBS (Graph Based Benchmark Suite) which based on the Ligra/Ligra+/Julienne graph processing frameworks (Shun et al., 2016; Dhulipala et al., 2017; Shun, 2020; Dhulipala et al., 2018), including betweenness centrality, graph radius estimation, graph connectivity, PageRank and single-source shortest paths etc..

The shortest paths algorithm based on matrix squaring multiplication has received extensive attention (Farbey et al., 1967; Takaoka, 1998; Mulmuley and Shah, 2000). The matrix squaring multiplication algorithm reduces the number of matrix multiplications from $n$ to $\log n$, but it requires storing many intermediate matrices. When the graph is large, the algorithm needs to consume a significant amount of space.

Seidel’s algorithm is the APSP algorithm based on matrix multiplication (Seidel, 1995), which is suitable for unweighted undirected graphs and time complexity is $O(\log n\cdot n^{\omega})$. The Seidel’s algorithm requires numerous memory to maintain intermediate matrices, due to reduce the time complexity of GEMM (General Matrix-Matrix multiplication) via divide-and-conquer strategy (Strassen et al., 1969; Coppersmith and Winograd, 1987; Williams, 2012).

Arlazarov et al. proposed the APSP algorithm based on the boolean matrix multiplication on the unweighted graphs (Arlazarov et al., 1970), which has alleviated the issue of excessive memory requirements associated with matrix multiplication-based APSP algorithms to a limited extent.

DAWN relies on the result of matrix multiplication to assist in determining which edge visits can be skipped. However, matrix multiplication is a costly operation, requiring $O(n^{3})$ time and $O(n^{2})$ space.

Our main contribution is the simplification of matrix multiplication, which does not mean that we can compute matrix multiplication faster, but rather that we focus on only a portion of the results of matrix multiplication for the shortest path problem. Specifically, our new approach is able to determine which rows and columns of the matrix multiplication result have an impact on the shortest path problem.

Figure 1 illustrates the correspondence between Boolean matrix operations and shortest path discovery in a graph. The blue markers indicate the result vector, while the red markers indicate a particular row of the adjacency matrix.

Obviously, we can obtain an expression for all paths,

where $1\leq k_{min}\leq\epsilon(i)$. It is evident that the sum of array is minimized when the first non-zero value of $a_{i,j}^{(k)}$ is encountered.

Theorem 3.2 and Fact 1 state the sufficient condition for breaking the loop and ending it:

1. (1)

   DAWN already found the shortest paths between all pairs of nodes in the graph;

2. (2)

   The distance vector does not change when a loop ends, which means no new paths were found in the loop.

We describe the vector-vector multiplication as follows,

which denotes the collection of path combinations from $i$ to $j$ through any node. Thus, it is unnecessary to consider all possible combinations when determining the presence of a path from i to j; only cases where$a_{i,l}>0\wedge a_{l,j}>0$ can affect the value of $a_{i,j}^{(2)}$. If $a_{i,j}^{(2)}$ represents any value greater than 0, it signifies the existence of a shortest path from node $i$ to $j$. Consequently, we can simplify this formula by utilizing a Boolean data type.

We converted the Formula 2 to a Boolean-type as follows,

which requires $O(n)$ time. Since only the non-zero elements in $\alpha$ and $\beta$ affect the multiplication result, we can compress the vectors by retaining only their non-zero elements, and get Formula 4 as follows,

where $len_{\gamma}$ represents the length of $\gamma$ and $\gamma$ is a compressed version of $\beta$, containing only the indices of non-zero elements.

In Formula 4, if the value of $\alpha[\gamma[l]]$ is 1, the result $a_{i,j}^{(2)}$ will be 1. Once the first element of $true$ is obtained, the sum will always yield a value of $true$ and indicates that the path exists from $i$ to $j$. Hence, we let the loop end at the time. We can ensure that the path we first discover is the shortest path by Theorem 3.2, and skip the computation of any paths ended with $j$ in next operations.

We can extend this vector operation to the CSC format matrix to assist DAWN in reducing neighbor node access and discovering the shortest path. We get the BOVM as the Algorithm 1, where $\alpha$ and $\beta$ are the dense vector, $step$ represents the steps of the shortest paths in the iteration. Line 4 of Algorithm 1 implements the Formula 4, while lines 7-8 implement the stopping criterion provided by Fact 1.

Next, we discuss the time complexity of DAWN based on the BOVM, and the formula as follows,

where $D_{exit}(i,x)$ represents the index value of element in $A[i]$ when DAWN exits the loop $x$, $len[\alpha_{x}]$ is the length of $\alpha$ in the loop $x$ (Refer to Algorithm 1 Line 1 to 5), $p$ represents the average connection probability of graph.

DAWN requires $O(\frac{1+p}{2}\epsilon_{max}\cdot nm)$ and $O(\frac{1+p}{2}\epsilon(i)m)$ time for APSP and SSSP problem, respectively.

The performance of BOVM on sparse graphs, especially those with large diameters, is often limited by the expensive cost of vector-matrix multiplication, making it difficult to outperform BFS. Reducing the number of vector multiplications has become a critical issue in enabling DAWN to be widely used.

We propose the method of SOVM to optimized DAWN on the sparse graphs, which combines graph traversal algorithms with vector-matrix multiplication, limiting the operation to nodes and their neighboring nodes. Specifically, we first obtain the set of neighboring nodes, exclude nodes that have already appeared in the result vector, then calculate the vector multiplication values of these nodes, obtaining paths of length step with target nodes in the neighboring nodes set, and finally update the shortest paths in the result vector.

Although the process is complex, we can simplify it by utilizing the properties of Boolean matrix operations. It is important to note that SOVM operates on CSR matrices, while BOVM operates on CSC matrices. The boolean vector-matrix multiplication is as follows,

If we use matrix $A=\{\beta_{0},\beta_{1},\cdots\beta_{n-2},\beta_{n-1}\}$, we can simplify the boolean vector-matrix multiplication as follows,

where $\beta^{\prime}$ is the compress version of $\beta$. Formula 8 indicates that the BOVM can be achieved by computing multiple inner products of vectors in succession.

If we transpose the matrix A to a CSR matrix $A\_CSR=\{\alpha_{0},\alpha_{1},\cdots\alpha_{n-2},\alpha_{n-1}\}$, Formula 8 can be simplified as follows,

and it means that we can use $len_{\beta^{\prime}}$ times of array merges to replace boolean vector-matrix multiplication in the SSSP tasks. We get the optimized method as the Algorithm 2.

Algorithm 2 utilizes a simpler method to merge vectors, and is particularly interested in the newly added elements of $\beta$ after merging these arrays. We aim to skip any duplicate elements since these shortest paths have already been discovered. We only visit the edges and update the shortest path when the element is missing in the $\beta$ array.

Specifically, SOVM starts from the set of neighbor nodes, skips all nodes that have already appeared in the result vector (line 1), finds the target nodes in neighboring nodes set that have not yet appeared in the result vector (line 4), and then updates their shortest paths. Formula 9 provides theoretical support for such operations, and SOVM can automatically exclude the cycles without additional judgment.

Hence, we get the time complexity of DAWN based on SOVM to solve SSSP task of node $i$ is as follows,

where $d^{+}(j)$ is the out-degree of node $j$. $S_{wcc}(i)$ and $E_{wcc}(i)$ denotes the number of nodes and edges included in the largest WCC (Weakly Connected Component) to which node $i$ belongs. The time complexity of DAWN for APSP is determined by the largest WCC in the graph,

where $S_{wcc}$ and $E_{wcc}$ denote the number of nodes and edges included in the largest WCC in graph. The time complexity of DAWN based on the SOVM is $O(S_{wcc}\cdot E_{wcc})$ for APSP tasks.

In summary, DAWN based on SOVM achieves better time complexity, requiring $O(S_{wcc}\cdot E_{wcc})$ and $O(E_{wcc}(i))$ time for APSP and SSSP tasks on the unweighted graphs, compared to BFS which requires $O(nm)$ and $O(m)$, respectively. It is important to note that this complexity improvement only occurs in non-connected graphs, whereas in connected graphs, DAWN and BSF both require $O(nm)$ and $O(m)$ time for APSP and SSSP tasks.

In this section, we elaborate on how DAWN achieves reduced memory usage compared to BFS. Typically, the memory requirements of the BFS algorithm can be divided into three components: CSR matrix, the distance vector, and the priority queue. This implies that BFS cannot operate with less than $4m+8n$ bytes of memory.

DAWN’s memory requirements also consist of three components: the CSR matrix, the distance vector, and two boolean arrays. The two boolean arrays are utilized to store the paths updated in the previous and current iterations (details in Algorithm 2). As DAWN is a backward BFS algorithm, we can maintain a boolean array on the GPU instead of distance vector, with path length updates occurring in memory. The GPU memory is byte-addressable, and even boolean variables are allocated a byte of space.

Therefore, DAWN necessitates a minimum of $4m+3n$ bytes of memory. We can get the formula as follows,

where $D$ represents the average degree of the graph.

For instance, when considering the theoretical minimum memory usage, DAWN requires only 91.58% of the memory used by Gunrock on the graph uk-2005. While the theoretical difference is approximately 8.4%, in experiments conducted under constrained GPU memory conditions, DAWN can solve the BFS task on uk-2005, whereas Gunrock fails to allocate sufficient GPU memory. It is noteworthy that as the sparsity of the graph increases, the memory advantage of DAWN becomes more pronounced.

To further examine the differences between DAWN and BFS, we present the technical details used in these two algorithms. Algorithm 3 describes the general BFS algorithm, and the benchmark implementations from GAP and Gunrock both employed more sophisticated optimization techniques in the experiment, where $pq$ represents the priority queue and $source$ is the source node of the SSSP task.

For Line 15 of Algorithm 2, if no new shortest paths are found in this loop, then exit, according to Fact 1. We utilize step to mark the current node being visited as a neighbor node of the source node at the layer $step$ in DAWN. Lines 4-6 of Algorithm 2 indicate that some edge visitations can be skipped. This means that the nodes that have already been visited in the previous layer do not need to be visited again, as the shortest path has already been determined. The theorem supporting this decision is referred to as Theorem 3.2, which states that the first discovered path from the source node to a reachable node is the shortest path. The processing steps of DAWN is as follows,

1. (1)

   Firstly, DAWN reads the input vector and identifies the single-step reachable nodes from the source node $s$,

2. (2)

   Then, searching for the single-step reachable nodes from the updated nodes which updating in the previous step, while skipping nodes that have already been discovered to have a path from the source node $s$ and reachable nodes with an out-degree of 0,

3. (3)

   Next, DAWN repeats the second step until output vector stabilizes.

4. (4)

   Finally, exit loop and output the result vector.

On the other hand, in BFS, the operations of accessing nodes and edges, and checking whether the path needs to be updated are necessary for every node and edge, refer to Line 6-10 in Algorithm 3.

We illustrate the difference between the BFS algorithm and DAWN through a example in Figure 2. The red color indicates the nodes and edges that are visited in the current step, the blue nodes and edges represent that have already been visited, and the green edges represent that have not yet been visited. The $input$ represents the paths updated in the previous iteration, while the $output$ indicates the paths updated in the current iteration. The $result$ signifies the outcome of the algorithm, specifically denoting the shortest path lengths from the source node to other nodes in the graph.

In the third step of Figure 2, node $5$ has four outbound edges to node $1,4,6,10$. BFS must traverse these edges, and then BFS would note that the destination vertex of these edges had already been visited and the destination vertex would not be in the output frontier. However, DAWN does not traverse these edges. The compressed vector for node 5 is $\{1,2,3,6,10\}$, and $result$ is $\{1,1,1,0,0,0,1,0,0,0\}$. The values of $result[1]$, $result[2]$, $result[3]$, and $result[6]$ are all 1, indicating that DAWN will skip these edges, because the shortest paths of them were already found.

In the SSSP task for node $s$, the BFS algorithm visited a total of 10 nodes and 17 edges, while DAWN visited only 8 nodes and 12 edges, resulting in 2 fewer nodes and 5 fewer edges being visited by DAWN.

Overall, the fundamental difference between DAWN and BFS lies in whether the algorithm relies on a priority queue to prevent revisiting nodes and edges.

In our experimental trials, we leverage a set of 66 general graphs sourced from the SuiteSparse Matrix Collection and the Gunrock benchmark datasets (Davis and Hu, 2011; Wang et al., 2016).

In scenarios where a node is not part of the largest WCC of the graph, but instead resides in a smaller connected component, DAWN has the potential to accomplish the task in constant time, while BFS requires the construction of a priority queue.

Therefore, we have established a randomly generated set comprising 500 nodes, where each node executes the SSSP task 64 times. All computations are conducted within this node-set. It is noteworthy that these nodes are not exclusively part of the largest connected component, and our dataset includes non-connected graphs. We underscore our focus on evaluating the performance of the BFS algorithm across diverse graph types, including connected and non-connected graphs, as well as both generated and real-world graphs.

Performing the task consecutively serves to minimize the influence of external factors on experimental results, such as interference from background processes. We adopted the arithmetic mean as the anticipated value and subjected the sample distribution to a t-distribution test. After eliminating samples that deviated from the assumptions of the t-distribution, and computing the mean of the remaining samples, we get the final result.

The parameters of the test machine are detailed in Table 2. Our comparison includes various versions of the BFS algorithm, and the results are presented in Table 3. We provide accessible links to graphs: [Dataset]. The number of nodes in these graphs ranges up to $139M$, with edges extending up to $921M$. The parameters of the experimental graphs are detailed in Table 4.

Specifically, the results for DAWN running on GPUs were obtained using a thread block size of 1024, a configuration viable on GPUs since the Pascal architecture introduced in 2016. Although the optimal block partitioning scheme depends on several factors (e.g., matrix density, shared memory size, bandwidth, etc.), we adopt a fixed block size to enhance result reproducibility.

Gunrock is a CUDA library for graph-processing designed specifically for the GPU, which achieves a better balance between performance and expressiveness via coupling high-performance GPU computing primitives and optimization strategies, particularly in the area of fine-grained load balancing. (Wang et al., 2017; Osama et al., 2022, 2023; Wang et al., 2016).

We strongly encourage readers to delve into the provided codebase and verify the reported results. The code and more information for our algorithm are available on [GitHub]. In the repository, we offer additional insights into the actual running times and graph details for each proposed solution, accompanied by a description of artifacts and evaluation methodologies. These details are provided to enhance the reproducibility of any results presented in this paper.

It is important to validate DAWN’s feature of high parallelism and scalability. We measure the scalability of DAWN using multi-threading efficiency as follows, simplified from Gustafson-Barsis’s law(Gustafson, 1988),

where $T_{B}$ represents the baseline execution time, $T_{N}$ represents the execution time of the program with $N$ threads, and $N$ is the number of threads. In Table 5 and 6, the multi-threading efficiency for DAWN based on SOVM and BFS API from GAP on the I5-13600KF and EPYC Milan 7T83 are depicted, respectively.

When utilizing up to 32 threads on the EPYC processor, the core frequency remains constant at 3.5 GHz. However, when scaling up to 64 threads, the frequency of all cores diminishes to 2.54 GHz. In contrast, the I5 processor does not experience any reduction in core frequency. It is important to note that the exact performance gains are contingent upon the particular hardware configuration utilized, and considerations such as power and thermal constraints impose limitations on the maximum achievable performance.

The I5 processor integrates a combination of performance and efficiency cores, where the former delivers higher clock speeds, and the latter excels in power efficiency. Hence, DAWN achieves a linear speedup when scaling from 1 thread to 6 threads, but the performance improvement slows down when scaling from 6 to 12 threads due to the performance gap between the two types of cores. Additionally, the I5 processor does not have enough physical cores to achieve significant performance gains beyond 14 threads.

Across diverse hardware configurations, DAWN demonstrates better multi-threading efficiency compared to GAP. Futhurmore, the scalability of the algorithm is influenced by a considerable number of factors, among which the characteristic of the graph is a significant factor.

Figure 3 and 4 illustrate DAWN’s capability for speedup across different thread counts on some of the graphs. Specifically, on the mycielskian16, which is a dense graph with a low-diameter of 2, DAWN exhibits lower thread efficiency compared to other sparse graphs. This phenomenon underscores the impact of multiple factors on the increase or decrease in algorithm performance. For instance, Graph mouse_gene is denser than mycielskian16, and with a diameter of 12, yet DAWN exhibits superior thread efficiency on mouse_gene. Therefore, we emphasize the comprehensive performance of the algorithm across a wider variety of graphs.

In the experiment, DAWN based on SOVM demonstrated remarkable performance and also exhibits high scalability and parallelism. We have included a figure illustrating the distribution of the speedup of DAWN over GAP across all graphs in the test dataset.

In Table 7, the speedup for DAWN based on SOVM over BFS API from GAP on an I5-13600KF is depicted, with the values derived from the mean of repeated experiments, following the methodology outlined in Section 4.1. The first row shows the speedup of DAWN(20) over BFS API from GAP, both on I5-13600KF, and the next row shows the speedup of DAWN on RTX3080TI over BFS API from GAP on I5-13600KF. Due to the significant increase in scalability and parallelism, DAWN based on the SOVM outperformed GAP in most graphs (62 out of 66), achieving an impressive average speedup of 3.769$\times$.

However, the DAWN algorithm demonstrates comparatively lower performance in four specific graphs (coPapersDBLP, com-DBLP, coAuthorsDBLP, coPapersCiteseer), all representing citation and collaboration networks. These graph types are characterized by high clustering coefficients and relatively short average shortest paths. Despite the deployment of a more potent processor, BFS API from Gunrock falls short of surpassing the performance of GAP on these graphs. Nevertheless, in other scale-free graphs such as social networks and the internet, the DAWN algorithm exhibits superior performance.

Numerous well-established studies have presented evidence that the eccentricity of the real graphs is $\log n$ (Bollobás, 1981; Albert et al., 1999; Cohen and Havlin, 2003; Riordan et al., 2004; Ganesh and Xue, 2007; Takes and Kosters, 2011). Therefore, we get the small-world graphs (23 out of 66) which the average shortest path in the graph is less than $\log n$, includes the citation and collaboration networks mentioned before.

The Direction-Optimizing BFS algorithm will achieve the speedups when the active frontier is a substantial fraction of the total graph, which commonly occurs in small-world graphs (Beamer et al., 2012). However, DAWN outperforms GAP on the most small-world graphs (19 out of 23) and achieves an average speedup of 2.332$\times$. Furthermore, in other real graph with a high-diameter such as road networks, DAWN achieves an average speedup of 4.483$\times$ over GAP.

Figure 5 shows the running time for DAWN(20) and GAP. The y-axis represents the average running time, with each marker representing the running time on a graph. GAP instances are indicated by blue markers, while DAWN instances are represented by black markers.

In Table 8, the first row shows the speedup of DAWN(20) on an I5-13600KF over BFS API from Gunrock on RTX3080TI. The next rows shows the speedup of DAWN over BFS API from Gunrock, both on RTX3080TI. Figure 6 illustrates the running time for DAWN and BFS API from Gunrock. Red markers correspond to DAWN, while green markers represent Gunrock. Impressively, DAWN outperformed Gunrock in the majority of graphs (63 out of 66), achieving an average speedup of 9.410$\times$. On the Graphs uk-2005 and arabic-2005, Gunrock encountered an out-of-memory error, thus preventing the acquisition of runtime data for these two graphs. The testing machine equipped with 12GB of physical GPU memory, with 9.7GB available. The available GPU memory for both DAWN and Gunrock is identical, indicating that when executing similar tasks, DAWN requires less GPU memory compared to Gunrock.

Apart from the aforementioned two graphs, DAWN demonstrates performance inferior to that of Gunrock on the Graph web-BerkStan, and also falls short compared to DAWN(20) and GAP running on CPU. This phenomenon may be attributed to the scale-free nature of web-BerkStan, leading to load imbalance during computation and significantly impacting algorithm performance. Gunrock, possessing robust load balancing capabilities, holds an advantage in such scenarios. It is crucial to note that DAWN does not prioritize load balancing as the primary focus of our investigation. Nonetheless, despite these challenges, DAWN outperforms Gunrock on the majority of graphs due to algorithmic optimizations.

The differences in the speedup distribution of DAWN compared to different algorithms are attributed to the nature of the graphs, such as the number of nodes and the average shortest path length. Therefore, we will proceed to compare the performance of DAWN on the different platforms. Figure 7 illustrates the performance gap of DAWN between CPU and GPU. Light purple bars indicate cases where DAWN’s performance on CPU is inferior to that on GPU, while dark purple bars represent the opposite scenario.

In more than half of the graphs (37 out of 66), DAWN(20) exhibits superior performance compared to DAWN. For instance, on web graphs, DAWN(20) and the GAP algorithm achieved enhanced performance, which demonstrates that the powerful single-core performance of CPUs provide better acceleration for algorithms.

However, this single-core performance acceleration has its limitations. Once the graph size exceeds one million nodes, the advantage of single-core performance can no longer compensate for the performance disparity induced by a greater number of cores. Furthermore, on graphs with a smaller number of nodes, the communication overhead between the CPU and GPU appears more costly than computational expenses, leading to inferior performance compared to algorithms running on CPU.

DAWN(20) achieved performance superiority on graphs with an average of 0.209 million nodes and 5.854 million edges (considering undirected edges as two directed edges). On the other hand, DAWN demonstrated performance superiority on graphs with an average of 13.820 million nodes and 146.592 million edges.

In summary, DAWN is more efficient and yielding a higher speedup when compared to Gunrock and GAP.