Single Source Shortest Path kernel based on Vitis Graph Library L2 - 2023.2 English

Vitis Tutorials: Hardware Acceleration (XD099)
Document ID
XD099
Release Date
2023-11-13
Version
2023.2 English

This tutorial uses the Vitis Graph Library to develop the main kernel for Shortest Path computing.

How does the Graph Library Work?

The Vitis Graph Library provides reference Vitis implementations for a set of graph processing algorithms that fits the Xilinx Alveo™ Series acceleration cards.

  • L3 APIs locate in the Vitis_Libraries/graph/L3/include directory. Pure software APIs are provided to customers who want a fast deployment of graph processing algorithms on Alveo Cards. These APIs provide a series of software designs to efficiently make use of resources in Alveo cards and deliver high-performance graph processing.

  • L2 APIs locate in the Vitis_Libraries/graph/L2/include directory. They are several compute-unit designs running on Alveo cards. These APIs provide a set of compute-unit designs implemented in HLS codes and should be compiled as OpenCL kernels. After the compilation, they will be called OpenCL APIs.

  • L1 APIs locate in the Vitis_Libraries/graph/L1/include directory. They are basic components that are used to compose compute units. The L1 APIs are all well-optimized HLS designs and can fit into various resource constraints.

You can find more information on how the Vitis Graph Library works here.

The L2 APIs located in the Vitis_Libraries/graph/L2/include directory provide a pure FPGA-based graph accelerator. They are used in this tutorial.

You can find more information on the internel design of the SSSP algorithm,including implementation, interface, and profiling here.

Interface in shortest_path.hpp
You can find this information in the L2/include/hw directory. 
  
  
 template 
 void singleSourceShortestPath(ap_uint<32>* config,
                              ap_uint<512>* offsetCSR,
                              ap_uint<512>* indexCSR,
                              ap_uint<512>* weightCSR,

                              ap_uint<512>* queue512,
                              ap_uint<32>* queue32,

                              ap_uint<512>* distance512,
                              ap_uint* distance32,
                              ap_uint<512>* pred512,
                              ap_uint<32>* pred32,
                              ap_uint<8>* info) {
    xf::graph::internal::sssp::pred::shortestPathInner(
        config, offsetCSR, indexCSR, weightCSR, queue512, queue32, distance512, distance32, pred512, pred32, info);
}


template <int WIDTH, int MAXOUTDEGREE>
void singleSourceShortestPath(ap_uint<32>* config,
ap_uint<512>* offsetCSR,
ap_uint<512>* indexCSR,
ap_uint<512>* weightCSR,


                          ap_uint<512>* queue512,
                          ap_uint<32>* queue32,

                          ap_uint<512>* distance512,
                          ap_uint<WIDTH>* distance32,
                          ap_uint<8>* info) {
xf::graph::internal::sssp::nopred::shortestPathInner<WIDTH, MAXOUTDEGREE>(
    config, offsetCSR, indexCSR, weightCSR, queue512, queue32, distance512, distance32, info);





}

Following is an example of kernel codes for calling the API:

extern "C" void shortestPath_top(ap_uint<32>* config,
                                 ap_uint<512>* offset,
                                 ap_uint<512>* column,
                                 ap_uint<512>* weight,

                                 ap_uint<512>* ddrQue512,
                                 ap_uint<32>* ddrQue,

                                 ap_uint<512>* result512,
                                 ap_uint<32>* result,
                                 ap_uint<512>* pred512,
                                 ap_uint<32>* pred,
                                 ap_uint<8>* info) {
    const int depth_E = E;
    const int depth_V = V;

    xf::graph::singleSourceShortestPath<32, MAXOUTDEGREE>(config, offset, column, weight, ddrQue512, ddrQue, result512,result, pred512, pred, info);

}

The Shortest Path test case is located in the Vitis_Libraries/graph/L2/test/shortest_path_float_pred directory. You can run the test case.