- 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]))
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.
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));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.
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));// 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 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.