ARTSIM

ArtSim Logo
  • GraphSim

  • About us

  • More

    Logo_s.jpg

    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