ARTSIM

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