Skip to content

Instantly share code, notes, and snippets.

Last active March 27, 2020 21:15
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Symphony Examples

2D Merge-Path Search (by Duane Merrill)

  • Input: Diagonal index, lengths of lists A and B, iterators (pointers) to lists A and B
  • Output: The 2D coordinate (x,y) of the intersection of the merge decision path with the specified grid diagonal
CoordinateT MergePathSearch(int diagonal, int a_len, int b_len, AIteratorT a,
                            BIteratorT b) {
  // Diagonal search range (in x coordinate space)
  int x_min = max(diagonal - b_len, 0);
  int x_max = min(diagonal, a_len);

  // 2D binary-search along the diagonal search range
  while (x_min < x_max) {
    OffsetT pivot = (x_min + x_max) >> 1;

    if (a[pivot] <= b[diagonal - pivot - 1]) {
      // Keep top-right half of diagonal range
      x_min = pivot + 1;

    } else {
      // Keep bottom-left half of diagonal range
      x_max = pivot;
  return CoordinateT(min(x_min, a_len), // x coordinate in A
                     diagonal - x_min); // y coordinate in B


Describes a path that consists of a succession of random steps within a graph. Implemented within Gunrock's generic lambda+for (code).

auto random_walk_op =
    [graph, walks, rand, iteration, walk_length, store_walks, neighbors_seen,
     steps_taken] __host__
    __device__(VertexT * v, const SizeT &i) {
      SizeT write_idx =
          (i * walk_length) + iteration; // Write location in RW array
      if (store_walks) {
        walks[write_idx] = v[i]; // record current position in walk

      if (!util::isValid(v[i]))

      if (iteration < walk_length - 1) {
        SizeT num_neighbors = graph.GetNeighborListLength(v[i]);
        if (num_neighbors == 0) {
          v[i] = util::PreDefinedValues<VertexT>::InvalidValue;

        // Randomly sample neighbor
        SizeT neighbor_list_offset = graph.GetNeighborListOffset(v[i]);
        SizeT rand_offset = (SizeT)round(0.5 + num_neighbors * rand[i]) - 1;
        VertexT neighbor =
            graph.GetEdgeDest(neighbor_list_offset + rand_offset);

        v[i] = neighbor; // Replace vertex w/ neighbor in queue
        neighbors_seen[i] +=
            (uint64_t)num_neighbors; // Record number of neighbors we've seen

curandGenerateUniform(gen, rand.GetPointer(util::DEVICE),
                      graph.nodes *walks_per_node);
GUARD_CU(frontier.V_Q()->ForAll(random_walk_op, frontier.queue_length,

Random Walk is almost always used as a building block to other applications. It was part of one of the HIVE/SDH graph workflows called GraphSearch. Gunrock also has an implementation of Graph Search's lambda within the Random Walk application.

Graph Coloring (Neighbor-Reduce)

Jones-Plassman-Luby (JPL) graph coloring implemented using Gunrock's neighbor reduction (code).

auto advance_op = [graph, iteration, colors, rand] __host__ __device__(
                      const VertexT &src, VertexT &dest, const SizeT &edge_id,
                      const VertexT &input_item, const SizeT &input_pos,
                      SizeT &output_pos) -> ValueT {
  if (util::isValid(colors[dest]))
    return (ValueT)-1;
  return rand[dest];

auto reduce_op = [rand, colors, iteration] __host__ __device__(
                     const ValueT &a, const ValueT &b) -> ValueT {
  return (a < b) ? b : a;

oprtr_parameters.reduce_values_out = &color_predicate;
oprtr_parameters.reduce_values_temp = &color_temp;
oprtr_parameters.reduce_values_temp2 = &color_temp2;
oprtr_parameters.reduce_reset = true;
oprtr_parameters.advance_mode = "ALL_EDGES";

frontier.queue_length = graph.nodes;
frontier.queue_reset = true;
static ValueT Identity = util::PreDefinedValues<ValueT>::MinValue;

    oprtr::NeighborReduce<oprtr::OprtrType_V2V |
                          oprtr::OprtrMode_REDUCE_TO_SRC | oprtr::ReduceOp_Max>(
        graph.csr(), null_ptr, null_ptr, oprtr_parameters, advance_op,
        reduce_op, Identity));

auto reduce_color_op =
    [graph, rand, colors, color_predicate, iteration, colored] __host__
    __device__(VertexT * v_q, const SizeT &pos) {
      if (pos == 0)
        colored[0] = 0; // reset colored ahead-of-time
      VertexT v = v_q[pos];
      if (util::isValid(colors[v]))

      if (color_predicate[v] < rand[v])
        colors[v] = iteration;


GUARD_CU(frontier.V_Q()->ForAll(reduce_color_op, graph.nodes, util::DEVICE,

Set operations: Intersection, Union, Disjoint Set...

Also very useful in graph algorithms. Intersection is used for triangle counting, scan statistics and subgraph matching.


Expected inputs are two arrays of node IDs, each pair of nodes forms an edge. The intersections of each node pair's neighbor lists are computed and returned as a single usnigned int value. Can perform user-defined functors on each of these intersection.

Triangle Counting:

auto intersect_op = [tc_counts] __host__ __device__(VertexT & comm_node,
                                                    VertexT &edge) -> bool {
  atomicAdd(tc_counts + comm_node, 1);

  return true;
frontier.queue_length = graph.edges;
frontier.queue_reset = true;
GUARD_CU(oprtr::Intersect<oprtr::OprtrType_V2V>(graph.csr(), frontier.V_Q(),

Scan Statistics:

// First add degrees to scan statistics
    [scan_stats, row_offsets] __host__ __device__(VertexT *scan_stats_,
                                                  const SizeT &v) {
      scan_stats_[v] = row_offsets[v + 1] - row_offsets[v];
    graph.nodes, target, stream));

// Compute number of triangles for each edge and atomicly add the count to
// each node, then divided by 2 The intersection operation
auto intersect_op = [scan_stats] __host__ __device__(VertexT & comm_node,
                                                     VertexT &edge) -> bool {
  atomicAdd(scan_stats + comm_node, 1);

  return true;
frontier.queue_length = graph.edges;
frontier.queue_reset = true;
GUARD_CU(oprtr::Intersect<oprtr::OprtrType_V2V>(graph.csr(), frontier.V_Q(),


Union Find operator takes list of pairs of sets to merge and returns the list of assignments of elements to the sets. Implemented within Shared Nearest Neighbor. Work-in-progress within Gunrock.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment