Skip to content

Instantly share code, notes, and snippets.

@neoblizz
Last active Mar 27, 2020
Embed
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
}

Random-Walk

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]))
        return;

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

        // 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
        steps_taken[i]++;
        neighbors_seen[i] +=
            (uint64_t)num_neighbors; // Record number of neighbors we've seen
      }
    };

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

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;

GUARD_CU(
    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]))
        return;

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

      return;
    };

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

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

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

Intersection:

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(),
                                                frontier.Next_V_Q(),
                                                oprtr_parameters,
                                                intersect_op));

Scan Statistics:

// First add degrees to scan statistics
GUARD_CU(scan_stats.ForAll(
    [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(),
                                                frontier.Next_V_Q(),
                                                oprtr_parameters,
                                                intersect_op));

Union-Find:

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