{{ message }}

Instantly share code, notes, and snippets.

# neoblizz/symph-examples.md

Last active Mar 27, 2020
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;

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>(
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; // 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 {

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 {

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.