
Overview
GraphSim is a graph based SSSP algorithm by ArtSim. It is a pre-configured, ready to run image for execution of Dijkstra's shortest path search algorithm on Amazon's FGPA-accelerated F1.
How to run the CLI:
1. login with the "centos" user.
2. Go to ~/GraphSim
3. Run the CLI using the command: sudo ./GraphSim
4. Run the example using the command from the CLI: source runme.cmd
Important commands reference:
load-graph <filename>
Loading a graph to the FPGA. The input file is a CSV with the following format:
source node, destination node,T, weight
sssp <srcID> <dstID>
Find a shortest path between two nodes
dump-result
Dump the results of the last sssp/msssp command to the screen
msssp
Find a shortest path between a list of pairs, loaded with a previous load-pairs command
load-pairs <filename>
Loading pairs from file for an msssp command. The input file is a CSV with the following format: <source node>,<destination node>
Examples:
Under the ~/GraphSim/graphs directory you can find 3 graph examples in the following sizes:
-
10K nodes and 40K edges (file name10K.g)
-
128K nodes and 200K edges (file name128K.g)
-
1M nodes and 2.5M edges (file name1M.g)
You load them by using the following command in the GraphSim’s CLI: load-graph graphs/<file name>
Now you can run the sssp algorithm on any two nodes in the graph (see examples at the end), by using the following command: sssp <start node> <end node>
After the algorithm ran you can see the results using the dump-result command.
Here is an example of the dump-result command output:
Init Cycles: 1 (0.000000 secs)
Calc Cycles: 14405612 (0.057622 secs)
Total Cycles: 14405613 (0.057622 secs)
Path: 101 -> 318
Search Cycles: 14405548 (0.057622 secs)
Node ID Weight
101 0
170 219
217 219
305 237
317 570
318 1040
-
You can find the time that took to calculate the path in the Search Cycles field.
-
The table describe the path from the start node to the end node, where Node ID is the ID of the node in the graph, and the Weight is the weight of the path till that node from the beginning. (“Internal ID” is for internal usage)
Example pairs to try in the graphs:
Start Node End Node
101 318
101 10878
101 219
101 220
101 305
101 532
101 942
101 955
101 1788
101 3095