Galois
|
Reduction is a fundamental operation used in different graph analytics problems such as bread-first search (BFS), connected components (CC), and PageRank (PR). As such, the Galois runtime provides support for different types of reduction operations such as addition (also known as accumulation).
Data structures that support reductions in Galois are conceptually divided into two classes: reduction of scalar types (e.g., ints and floats) or reduction of container types (e.g., STL vectors and maps).
galois::Reducible is the base class to help reduce values of primitive types or types that are cheap to copy. For example, galois::GAccumulator is for accumulating values of types such as ints.
galois::Reducible is used to reduce mutliple values of type T
to a single value. It is optimized for basic types or types that have low overheads while copying. galois::Reducible takes the type T
of the values to be reduced and a functor MergeFunc
as template parameters, where the MergeFunc
conforms to:
galois::Reducible starts with the default value of type T
. galois::Reducible::update() updates the thread local value by applying the reduction operator to the thread local and provided value. After a parallel region, the final value can be retrieved using galois::Reducible::reduce(). Note, that galois::Reducible::reduce() can only be used outside of parallel regions (e.g., galois::for_each).
The following figure shows the inheritance hierarachy of Galois classes that implement support for scalar reduction operations.
These specialized reducer classes implement support for different types of reduction operations by inheriting from galois::Reducible:
T
has to meet the type requirements of std::max
.T
has to meet the type requirements of std::min
.logical and
of the accumulated values. Type T
has to meet the type requirements of std::logical_and
.logical or
of the accumulated values. Type T
has to meet the type requirements of std::logical_or
.In the following, we show an example of using reduction operations in a common graph analytics application, PageRank. The residual pull-based algorithm for PageRank uses galois::GAccumulator to keep track of whether a node with outgoing neighbors has new PageRank contribution that needs to be propagated. The PageRank computation can terminate if the reduced value across all nodes in the graph is zero (i.e., implying no more work).