Gunrock Operators

The following are a variety of operators we support within Gunrock (gunrock/gunrock), and a short description explaining the intended use. You can find lots of examples of these operators being used to implement the graph algorithms within the library’s source code (see: gunrock/include/gunrock/algorithms/.)

using namespace gunrock::operators;

Operator	Namespace	Description	Examples
Advance	advance::	An advance operator generates a new frontier from the current frontier by visiting the neighbors of the current frontier. A frontier can consist of either vertices or edges, and an advance step can input and output either kind of frontier. Advance is an irregularly-parallel operation for two reasons: 1) different vertices in a graph have different numbers of neighbors and 2) vertices share neighbors. Thus a vertex in an input frontier map to multiple output items. An efficient advance is the most significant challenge of a GPU implementation.	Breadth-First Search, Single-Source Shortest Path, …	CUDA
Filter	filter::	A filter operator generates a new frontier from the current frontier by choosing a subset of the current frontier based on programmer-specified criteria. Each input item maps to an invalid or one output item.	Breadth-First Search, Single-Source Shortest Path, …	CUDA
Batch	batch::	A batch operator takes in a function and number of jobs as input parameters, and simply runs the function that many times. So far, this is a very barebone implementation of what batching could look like from the host code using CUDA. We can later expand this to account for given resources.	Betweenness Centrality	std::thread
For	parallel_for::	A parallel-for with user-defined computation over each vertex, edge, or weight of the graph, or over each element of the frontier.	Geolocation	CUDA
Neighbor Reduce	neighborreduce::	A neighbor-reduce operator uses the advance operator to visit the neighbor list of each item in the input frontier and performs a segmented reduction over the neighborhood (neighbor list) generated via the advance.	Sparse-Matrix Vector Multiplication	CUDA
Uniquify	uniquify::	A uniquify operator takes in an input frontier and attempts to deduplicate it. If needed, we can achieve 100% deduplication if it is specified using sorting.	Single-Source Shortest Path	CUDA

Operators supported in gunrock/gunrock (and not in gunrock/essentials)

The following is a list of work to port over to gunrock/essentials (now merged to gunrock/gunrock).

using namespace gunrock::oprtr;

Operator	Namespace	Description	Notes	Use Case
Segmented Intersection	intersection::	(misleading description from original gunrock) A segmented intersection operator takes two input node frontiers with the same length, or an input edge frontier, and generates both the number of total intersections and the intersected node IDs as the new frontier.	For essentials, we support intersection as a graph_t method for two vertices instead of a separate operator. A separate operator could be intersecting two frontiers (but that is less useful, and not exactly a segmented intersection).	Triangle Counting	CUDA