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].



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)
  Pipe Once {
    Invoke initialize(graph, src)
    Pipe {
      Invoke sssp(graph, curdelta);
      Invoke remove_dups();
      curdelta += DELTA;


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.