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.