Single-Source Shortest Paths

Problem Description

This benchmark computes the shortest path from a source node to all nodes in a directed graph with non-negative edge weights by using a modified near-far algorithm [1]. This program is generated by the IrGL compiler [2].

[1] https://people.csail.mit.edu/jshun/6886-s18/papers/DBGO14.pdf
[2] https://users.ices.utexas.edu/~sreepai/sree-oopsla2016.pdf

Algorithm

The computation is implemented in a delta-stepping based SSSP algorithm. Worklists are created and managed by Pipe.The Pipe statement implements the invocation of a pipeline of kernels each of which produces a worklist for the next kernel.

  Kernel sssp (...) {
    ...
    if (dst.dsitance <= delta)
      Respawn(dst)
    else
      WL.push(dst)
    ...
  }
  Pipe Once {
    Invoke initialize(graph, src)
    Pipe {
      Invoke sssp(graph, curdelta);
      Invoke remove_dups();
      curdelta += DELTA;
    }
  }

Performance

Graph	Time (ms)
USA-road-d.NY	146
USA-road-d.USA	29315

The above performance is observed on a 1733.500 Mhz GeForce GTX 1080 6000 with 8119 MB of main memory.