Skip to content
This repository has been archived by the owner on Dec 22, 2022. It is now read-only.

Gunrock Operators

Muhammad Osama edited this page Jun 24, 2022 · 14 revisions

The following are a variety of operators we support within Gunrock (gunrock/essentials), 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: essentials/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.

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

Getting Started

Experimentals

Developers

Debugging, Profiling and Testing

Tutorials

Design Choices

Utilities and Tools

Performance Optimizations

Random, weird or fun things

Continuous integration (CI)

Clone this wiki locally