Pregel< MatrixEntryType > Class Template Reference

A Pregel run-time instance. More...

#include <pregel.hpp>

Public Member Functions
template<typename IType >
	Pregel (const size_t _m, const size_t _n, IType _start, const IType _end, const grb::IOMode _mode)
	Constructs a Pregel instance from input iterators over some graph. More...
template<class Op , template< typename > class Id, class Program , typename IOType , typename GlobalProgramData , typename IncomingMessageType , typename OutgoingMessageType >
grb::RC	execute (const Program program, grb::Vector< IOType > &vertex_state, const GlobalProgramData &data, grb::Vector< IncomingMessageType > &in, grb::Vector< OutgoingMessageType > &out, size_t &rounds, grb::Vector< OutgoingMessageType > &out_buffer=grb::Vector< OutgoingMessageType >(0), const size_t max_rounds=0)
	Executes a given vertex-centric program on this graph. More...
const grb::Matrix< MatrixEntryType > &	get_matrix () const noexcept
	Returns the ALP/GraphBLAS matrix representation of the underlying graph. More...
size_t	num_edges () const noexcept
	Queries the number of edges of the graph this Pregel instance has been constructed over. More...
size_t	num_vertices () const noexcept
	Queries the maximum vertex ID for programs running on this Pregel instance. More...

Detailed Description

template<typename MatrixEntryType>
class grb::interfaces::Pregel< MatrixEntryType >

A Pregel run-time instance.

Pregel wraps around graph data and executes computations on said graph. A runtime thus is constructed from graph, and enables running any Pregel algorithm on said graph.

Constructor & Destructor Documentation

Pregel()

Pregel ( const size_t  _m, const size_t  _n, IType  _start, const IType  _end, const grb::IOMode  _mode  )

inline

Constructs a Pregel instance from input iterators over some graph.

Template Parameters

IType

The type of the input iterator.

Parameters

[in]	_m	The maximum vertex ID for excident edges.
[in]	_n	The maximum vertex ID for incident edges.

Note

This is equivalent to the row- and column- size of an input matrix which represents the input graph.

If these values are not known, please scan the input iterators to derive these values prior to calling this constructor. On compelling reasons why such functionality would be useful to provide as a standard factory method, please feel welcome to submit an issue.

Warning

The graph is assumed to have contiguous IDs – i.e., every vertex ID in the range of 0 (inclusive) to the maximum of m and n (exclusive) has at least one excident or at least one incident edge.

Parameters

[in]	_start	An iterator pointing to the start element of an a collection of edges.
[in]	_end	An iterator matching _start in end position.

All edges to be ingested thus are contained within _start and end.

Parameters

[in]

_mode

Whether sequential or parallel I/O is to be used.

The value of _mode only takes effect when there are multiple user processes, such as for example when executing over a distributed-memory cluster. The choice between sequential and parallel I/O should be thus:

• If the edges pointed to by _start and _end correspond to the entire set of edges on each process, then the I/O mode should be grb::SEQUENTIAL;
• If the edges pointed to by _start and _end correspond to different sets of edges on each different process while their union represents the graph to be ingested, then the I/O mode should be grb::PARALLEL.

On errors during ingestion, this constructor throws exceptions.

Member Function Documentation

execute()

grb::RC execute ( const Program  program, grb::Vector< IOType > &  vertex_state, const GlobalProgramData &  data, grb::Vector< IncomingMessageType > &  in, grb::Vector< OutgoingMessageType > &  out, size_t &  rounds, grb::Vector< OutgoingMessageType > &  out_buffer = grb::Vector< OutgoingMessageType >(0), const size_t  max_rounds = 0  )

inline

Executes a given vertex-centric program on this graph.

The program must be a static function that returns void and takes five input arguments:

• a reference to a vertex-defined state. The type of this reference may be defined by the program, but has to match the element type of vertex_state passed to this function.
• a const-reference to an incoming message. The type of this reference may be defined by the program, but has to match the element type of in passed to this function. It must furthermore be compatible with the domains of Op (see below).
• a reference to an outgoing message. The type of this reference may be defined by the program, but has to match the element type of out passed to this function. It must furthermore be compatible with the domains of Op (see below).
• a const-reference to a program-defined type. The function of this argument is to collect global read-only algorithm parameters.
• a reference to an instance of grb::interfaces::PregelState. The function of this argument is two-fold: 1) make available global read- only statistics of the graph the algorithm is executing on, and to 2) control algorithm termination conditions.

The program will be called during each round of a Pregel computation. The program is expected to compute something based on the incoming message and vertex-local state, and (optionally) generate an outgoing message. After each round, the outgoing message at all vertices are broadcast to all its neighbours. The Pregel runtime, again for each vertex, reduces all incoming messages into a single message, after which the next round of computation starts, after which the procedure is repeated.

The program terminates in one of two ways:

1. there are no more active vertices; or
2. all active vertices vote to halt.

On program start, i.e., during the first round, all vertices are active. During the computation phase, any vertex can set itself inactive for subsequent rounds by setting grb::interfaces::PregelState::active to false. Similarly, any active vertex can vote to halt by setting grb::interfaces::PregelState::voteToHalt to true.

Reduction of incoming messages to a vertex will occur through an user- defined monoid given by:

Template Parameters

Op	The binary operation of the monoid. This includes its domain.
Id	The identity element of the monoid.

The following template arguments will be automatically inferred:

Template Parameters

Program	The type of the program to-be executed.
IOType	The type of the state of a single vertex.
GlobalProgramData	The type of globally accessible read-only program data.
IncomingMessageType	The type of an incoming message.
OutgoingMessageType	The type of an outgoing message.

The arguments to this function are as follows:

Parameters

[in]

program

The vertex-centric program to execute.

The same Pregel runtime instance hence can be re-used to execute multiple algorithms on the same graph.

Vertex-centric programs have both vertex-local and global state:

Parameters

[in]	vertex_state	A vector that contains the state of each vertex.
[in]	data	Global read-only state for the given program.

The capacity, size, and number of nonzeroes of vertex_state must equal the maximum vertex ID.

Finally, in the ALP spirit which aims to control all relevant performance aspects, the workspace required by the Pregel runtime must be pre- allocated and passed in:

Parameters

[in]	in	Where incoming messages are stored. Any initial values may or may not be ignored, depending on the program behaviour during the first round of computation.
[in]	out	Where outgoing messages are stored. Any initial values will be ignored.

The capacities and sizes of in and out must equal the maximum vertex ID. For sparse vectors in with more than zero nonzeroes, all initial contents will be overwritten by the identity of the reduction monoid. Any initial contents for out will always be ignored as every round of computation starts with the outgoing message set to the monoid identity.

Note

Thus if the program requires some initial incoming messages to be present during the first round of computation, those may be passed as part of a dense vectors in.

The contents of in and out after termination of a vertex-centric function are undefined, including when this function returns grb::SUCCESS. Output of the program should be part of the vertex-centric state recorded in vertex_state.

Some statistics are returned after a vertex-centric program terminates:

Parameters

[out]

rounds

The number of rounds the Pregel program has executed. The initial value to rounds will be ignored.

The contents of this field shall be undefined when this function does not return grb::SUCCESS.

Vertex-programs execute in rounds and could, if the given program does not infer proper termination conditions, run forever. To curb the number of rounds, the following optional parameter may be given:

Parameters

[in]	out_buffer	An optional buffer area that should only be set whenever the config::out_sparsify configuration parameter is not set to config::NONE. If that is the case, then out_buffer should have size and capacity equal to the maximum vertex ID.
[in]	max_rounds	The maximum number of rounds the program may execute. Once reached and not terminated, the program will forcibly terminate.

To turn off termination after a maximum number of rounds, max_rounds may be set to zero. This is also the default.

Executing a Pregel function returns one of the following error codes:

Returns

grb::SUCCESS The program executed (and terminated) successfully.

grb::MISMATCH At least one of vertex_state, in, or out is not of the required size.

grb::ILLEGAL At least one of vertex_state, in, or out does not have the required capacity.

grb::ILLEGAL If vertex_state is not dense.

grb::PANIC In case an unrecoverable error was encountered during execution.

get_matrix()

const grb::Matrix< MatrixEntryType > & get_matrix ( ) const

inlinenoexcept

Returns the ALP/GraphBLAS matrix representation of the underlying graph.

This is useful when an application prefers to sometimes use vertex- centric algorithms and other times prefers direct ALP/GraphBLAS algorithms.

Returns

The underlying ALP/GraphBLAS matrix corresponding to the underlying graph.

num_edges()

size_t num_edges ( ) const

inlinenoexcept

Queries the number of edges of the graph this Pregel instance has been constructed over.

Returns

The number of edges within the underlying graph.

num_vertices()

size_t num_vertices ( ) const

inlinenoexcept

Queries the maximum vertex ID for programs running on this Pregel instance.

Returns

The maximum vertex ID.

---

The documentation for this class was generated from the following file:

• pregel.hpp