Detailed Description

Reachability Graph with additional storage in GPU memory.

Methods are provided to copy data from main memory to GPU memory and back.

MERGE and COMBINE methods are scheduled for GPU execution (as OpenCL kernels).

Author: Peter Schäfer

Definition at line 23 of file graph_cl.h.

#include <graph_cl.h>

Public Member Functions
	GraphCL (const GraphCL &that)
	copy constructor More...

	GraphCL (GraphCL &&that)
	move constructor More...

virtual	~GraphCL ()
	destructor; release all memory, including GPU memory More...

GraphCL &	operator= (const GraphCL &that)
	assginment operator More...

GraphCL &	operator= (GraphCL &&that)
	move assignment operator More...

virtual void	synchToGpu () override
	copy adjacancy matrix data to GPU memory More...

virtual void	synchFromGpu () override
	copy adjacancy matrix data back from GPU memory to CPU memory More...

methods delegated to OpenCL kernels.
All methods return immediately. Kernels are scheduled for asynchronous execution. Use OpenCL to wait for execution, then retrieve results with synchFromGpu, or foundDiagonalElement.
virtual void	finalize () override

virtual void	combine (const Graph *P) override
	apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AND oepration: (*this)_VV &= that_VV More...

virtual void	merge2 (const Graph A, const Graph B, MatrixPool *pool) override
	apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (this)_VV = A_VV * *B_VV More...

virtual void	merge3 (const Graph A, const Graph B, MatrixPool *pool) override
	apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: this_HH = A_HV * B_VV * A_VH More...

virtual void	queryDiagonalElement () const override
	find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result of this method, call foundDiagonalElement. (reason: we also want to perform this query asynchronously on a GPU). More...

virtual int	foundDiagonalElement () const override

virtual void	release (Orientation o1, Orientation o2) override
	release memory for one part of the adjacancy matrix More...

virtual void	release (Orientation o1, Orientation o2, MatrixPool *pool) override
	release memory for one part of the adjacancy matrix More...

virtual void	resetConditions () override

Public Member Functions inherited from frechet::reach::Graph
	Graph (const GraphModel &model)

	Graph (const GraphModel &model, Structure &str, int i0)

	Graph (const Graph &)

	Graph (Graph &&)

	~Graph ()

int	vertices () const

int	edges () const

Graph &	operator= (const Graph &)

Graph &	operator= (Graph &&)

Graph &	operator+= (const Graph &)

Graph::ptr	transitiveClosure () const

void	transitiveClosureInPlace ()

void	add_edge (int i, int j)

void	clear ()

	Graph (const Graph &that)
	copy constructor More...

	Graph (Graph &&that)
	move constructor More...

virtual	~Graph ()
	destructor, releases memory More...

void	allocateAll ()
	allocate data for adjacenty matrixes (all four parts) More...

mzd_t *	allocate (Orientation o1, Orientation o2)
	allocate an adjacancy sub-matrix (one of four parts) More...

const IndexRange &	hmask () const
	horizontal range covered by this graph More...

Rect	rect (Orientation o1, Orientation o2) const
	range covered by this graph More...

const GraphModel::ptr	graphModel () const

void	setOriginPlacement (int di, int dj)
	this graph represents a set of valid placements More...

void	setOriginRG (int i)
	this graph represents a reachability graph, it was created from a reachability structure More...

void	setOriginMerge2 (Graph::ptr A, Graph::ptr B)
	this graph is the transitive closure of two other graphs. It is the result of a MERGE operation. More...

void	setOriginMerge3 (Graph::ptr A, Graph::ptr B)
	this graph is the transitive closure of two other graphs. It is the result of a final MERGE operation. More...

void	setOriginCombine (Graph::ptr P)
	a sub-set of valid placements is applied to the graph More...

void	printOrigin (std::ostream &out) const
	debug output More...

Graph &	operator= (const Graph &that)
	assigment operator More...

Graph &	operator= (Graph &&that)
	move assigment operator More...

bool	operator== (const Graph &that) const
	comparison operator More...

void	add_edge (Orientation ori_from, int i_from, Orientation ori_to, int i_to)
	add an edge to the graph More...

void	add_range (IndexRange r_from, IndexRange r_to)
	add a set of edges to the graph, covering a range of nodes More...

bool	contains_edge (Orientation ori_from, int i_from, Orientation ori_to, int i_to) const
	check if an edge is present More...

bool	contains_edge (IndexRange r_from, IndexRange r_to) const
	check a range of edges More...

bool	empty (Orientation o1, Orientation o2) const
	empty test for one of the four sub-graphs More...

bool	zero (Orientation o1, Orientation o2) const
	empty test for one of the four sub-graphs More...

void	releaseIfZero ()
	release memory that is not neeeded (empty sub-graphs) More...

virtual void	release ()
	release memory for all parts of the adjacancy matrix More...

int	find_next1 (Orientation o1, int i, Orientation o2, int j) const
	find the next edge in a sub-graph More...

int	find_next0 (Orientation o1, int i, Orientation o2, int j) const
	find the next missing edge in a sub-graph More...

IndexRange	find_next_range (Orientation o1, int i, Orientation o2, int j) const
	find a range of consecutive edges in a sub-graph More...

Graph::ptr	merge2 (const Graph B, MatrixPool pool=nullptr) const
	apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (result)_VV = (this)_VV * that_VV More...

Graph::ptr	merge3 (const Graph B, MatrixPool pool=nullptr) const
	apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (result)_HH = (this)_HV * that_VV * (*this)_VH More...

double	memory (Orientation ori1, Orientation ori2) const
	compute the memory footprint of an adjacancy matrix More...

double	density (Orientation ori1, Orientation ori2) const
	compute the density (amount of set edges) of an adjacancy matrix More...

double	memory () const

double	density () const

void	clear ()
	remove all edges More...

void	clear (Orientation ori1, Orientation ori2)
	remove all edges of a sub-graph More...

bool	is_upper_triangular (Orientation ori1, Orientation ori2) const

void	print (std::ostream &out, Orientation o1, Orientation o2) const
	print a sub-adjacancy matrix More...

Protected Member Functions
	GraphCL (const GraphModel::ptr model)
	empty constructor More...

	GraphCL (const GraphModel::ptr model, IndexRange hmask)
	constructor with node range More...

	GraphCL (const GraphModel::ptr model, Structure &str)
	constructor from reachability structure More...

clmatrix_t *	tempMatrix (int rows, int cols, MatrixPool *pool) const
	allocate a temporary matrix More...

void	copy (const GraphCL &that)
	copy data More...

void	swap (GraphCL &that)
	swap data More...

Protected Member Functions inherited from frechet::reach::Graph
	Graph (const GraphModel::ptr amodel)
	empty constructor More...

	Graph (const GraphModel::ptr amodel, IndexRange range)
	constructor with column range More...

	Graph (const GraphModel::ptr amodel, Structure &str)
	constructor from reachability structure More...

void	copy (const Graph &that)
	copy graph More...

void	swap (Graph &that)
	swap graph More...

void	copy (const Structure &str, Orientation ori)
	copy reachability info from Structure to Graph More...

Private Attributes
clmatrix_t *	clmtx [2][2]
	data stored on GPU memory More...

std::list< clmatrix_t * >	temps
	temporary matrixes More...

clm4rm_conditions	cond
	cl_events for out-of-order dependencies More...

cl_mem	diagonalElementBuffer
	result of searchDiagonalElement More...

Friends
GraphPtr	frechet::reach::newGraph (const GraphModel::ptr model)

GraphPtr	frechet::reach::newGraph (const GraphModel::ptr model, IndexRange hmask)

GraphPtr	frechet::reach::newGraph (const GraphModel::ptr model, Structure &str)

Additional Inherited Members
Public Types inherited from frechet::reach::Graph
typedef boost::shared_ptr< Graph >	ptr

typedef boost::shared_ptr< Graph >	ptr

Static Public Member Functions inherited from frechet::reach::Graph
static bool	is_adjacent_to (const Graph &A, const Graph &B)

static void	set_bits (mzd_t *M, int row, int i, int j)
	set some bits in a Boolean matrix More...

static bool	has_bits (mzd_t *M, int row, int i, int j)
	query bits in a Boolean matrix More...

static void	clear_row (mzd_t *M, int row)
	clear a row in a Boolean matrix More...

static void	and_row (mzd_t M, int r, mzd_t M2, int r2)
	apply bitwise and of two matrix rows More...

static int	find_next1 (mzd_t *M, int row, int i)
	find next set bit in a Boolean matrix More...

static int	find_next0 (mzd_t *M, int row, int i)
	find next cleared bit in a Boolean matrix More...

static bool	is_upper_triangular (const mzd_t *mzd)

Public Attributes inherited from frechet::reach::Graph
struct frechet::reach::Graph::Origin	origin

Static Protected Member Functions inherited from frechet::reach::Graph
static void	print (std::ostream &out, const mzd_t *M)
	print a Boolean matrix More...

Protected Attributes inherited from frechet::reach::Graph
mzd_t *	mtx [2][2]
	adjacency matrix (M4RI structure) split into four parts to allow for memory savings. More...

IndexRange	mask [2]

const GraphModel::ptr	model

int	diagonalElement
	result of call to searchDiagonalElement More...

Constructor & Destructor Documentation

◆ GraphCL() [1/5]

GraphCL::GraphCL ( const GraphModel::ptr model )

protected

empty constructor

Parameters

model maps reachability intervals to graph nodes

Definition at line 37 of file graph_cl.cpp.

◆ GraphCL() [2/5]

GraphCL::GraphCL	(	const GraphModel::ptr	model,
		IndexRange	hmask
	)

protected

constructor with node range

Parameters

model	maps reachability intervals to graph nodes
hmask	column range covered by the graph

Definition at line 45 of file graph_cl.cpp.

◆ GraphCL() [3/5]

GraphCL::GraphCL	(	const GraphModel::ptr	model,
		Structure &	str
	)

protected

constructor from reachability structure

Parameters

model	maps reachability intervals to graph nodes
str	a reachability structure

Definition at line 53 of file graph_cl.cpp.

◆ GraphCL() [4/5]

GraphCL::GraphCL ( const GraphCL & that )

copy constructor

Parameters

that	graph to copy from

Definition at line 61 of file graph_cl.cpp.

◆ GraphCL() [5/5]

GraphCL::GraphCL ( GraphCL && that )

move constructor

Parameters

that	graph to copy from; empty on return

Definition at line 67 of file graph_cl.cpp.

◆ ~GraphCL()

GraphCL::~GraphCL ( )

virtual

destructor; release all memory, including GPU memory

Definition at line 73 of file graph_cl.cpp.

Member Function Documentation

◆ combine()

void GraphCL::combine ( const Graph * P )

overridevirtual

apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AND oepration: (*this)_VV &= that_VV

Parameters

P	a set of valid placements

Reimplemented from frechet::reach::Graph.

Definition at line 190 of file graph_cl.cpp.

◆ copy()

void GraphCL::copy ( const GraphCL & that )

protected

copy data

Parameters

that	graph to copy from

Definition at line 101 of file graph_cl.cpp.

◆ finalize()

void GraphCL::finalize ( )

overridevirtual

Note: called from multiple threads Fortunately, OpenCL is thread-safe by design.

Reimplemented from frechet::reach::Graph.

Definition at line 134 of file graph_cl.cpp.

◆ foundDiagonalElement()

int GraphCL::foundDiagonalElement ( ) const

overridevirtual

Returns: the result of the last call to queryDiagonalElement. Or -1 if the diagonal is empty.

Reimplemented from frechet::reach::Graph.

Definition at line 315 of file graph_cl.cpp.

◆ merge2()

void GraphCL::merge2	(	const Graph *	A,
		const Graph *	B,
		MatrixPool *	pool
	)

overridevirtual

apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*this)_VV = *A_VV * *B_VV

Parameters

A	a graph
B	another graph
pool	pool of re-cycled matrixes (optional)

Reimplemented from frechet::reach::Graph.

Definition at line 227 of file graph_cl.cpp.

◆ merge3()

void GraphCL::merge3	(	const Graph *	A,
		const Graph *	B,
		MatrixPool *	pool
	)

overridevirtual

apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: this_HH = A_HV * B_VV * A_VH

Parameters

A	a graph
B	another graph
pool	pool of re-cycled matrixes (optional)

Reimplemented from frechet::reach::Graph.

Definition at line 263 of file graph_cl.cpp.

◆ operator=() [1/2]

GraphCL & GraphCL::operator= ( const GraphCL & that )

assginment operator

Parameters

that	graph to copy from

Returns: reference to this, after assignment

Definition at line 89 of file graph_cl.cpp.

◆ operator=() [2/2]

GraphCL & GraphCL::operator= ( GraphCL && that )

move assignment operator

Parameters

that	that graph to copy from; empty on return

Returns: reference to this, after assignment

Definition at line 95 of file graph_cl.cpp.

◆ queryDiagonalElement()

void GraphCL::queryDiagonalElement ( ) const

overridevirtual

find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result of this method, call foundDiagonalElement. (reason: we also want to perform this query asynchronously on a GPU).

Reimplemented from frechet::reach::Graph.

Definition at line 302 of file graph_cl.cpp.

◆ release() [1/2]

virtual void frechet::reach::GraphCL::release	(	Orientation	o1,
		Orientation	o2
	)

overridevirtual

release memory for one part of the adjacancy matrix

Parameters

o1	horizontal part
o2	vertical part

Reimplemented from frechet::reach::Graph.

◆ release() [2/2]

virtual void frechet::reach::GraphCL::release	(	Orientation	o1,
		Orientation	o2,
		MatrixPool *	pool
	)

overridevirtual

release memory for one part of the adjacancy matrix

Parameters

o1	horizontal part
o2	vertical part
pool	a pool of re-cycled matrix data

Reimplemented from frechet::reach::Graph.

◆ resetConditions()

void GraphCL::resetConditions ( )

overridevirtual

After a barrier, we can assume that all pre-conditions are met. We need not explicitly track them.

Reimplemented from frechet::reach::Graph.

Definition at line 142 of file graph_cl.cpp.

◆ swap()

void GraphCL::swap ( GraphCL & that )

protected

swap data

Parameters

that	graph to swap with

Definition at line 112 of file graph_cl.cpp.

◆ synchFromGpu()

void GraphCL::synchFromGpu ( )

overridevirtual

copy adjacancy matrix data back from GPU memory to CPU memory

Reimplemented from frechet::reach::Graph.

Definition at line 173 of file graph_cl.cpp.

◆ synchToGpu()

void GraphCL::synchToGpu ( )

overridevirtual

copy adjacancy matrix data to GPU memory

Reimplemented from frechet::reach::Graph.

Definition at line 147 of file graph_cl.cpp.

◆ tempMatrix()

clmatrix_t * GraphCL::tempMatrix	(	int	rows,
		int	cols,
		MatrixPool *	pool
	)		const

protected

allocate a temporary matrix

Parameters

rows	number of rows
cols	number of columns
pool	pool for re-cycled matrix data

Returns: a Boolean matrix

Definition at line 331 of file graph_cl.cpp.

Friends And Related Function Documentation

◆ frechet::reach::newGraph [1/3]

GraphPtr frechet::reach::newGraph ( const GraphModel::ptr model )

friend

◆ frechet::reach::newGraph [2/3]

GraphPtr frechet::reach::newGraph	(	const GraphModel::ptr	model,
		IndexRange	hmask
	)

friend

◆ frechet::reach::newGraph [3/3]

GraphPtr frechet::reach::newGraph	(	const GraphModel::ptr	model,
		Structure &	str
	)

friend

Member Data Documentation

◆ clmtx

clmatrix_t* frechet::reach::GraphCL::clmtx[2][2]

private

data stored on GPU memory

Definition at line 26 of file graph_cl.h.

◆ cond

clm4rm_conditions frechet::reach::GraphCL::cond

mutableprivate

cl_events for out-of-order dependencies

Definition at line 30 of file graph_cl.h.

◆ diagonalElementBuffer

cl_mem frechet::reach::GraphCL::diagonalElementBuffer

mutableprivate

result of searchDiagonalElement

Definition at line 32 of file graph_cl.h.

◆ temps

std::list<clmatrix_t*> frechet::reach::GraphCL::temps

mutableprivate

temporary matrixes

Definition at line 28 of file graph_cl.h.

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

include/frechet/reachability/graph_cl.h
src/frechet/reachability/graph_cl.cpp

Detailed Description

Public Member Functions

Protected Member Functions

Private Attributes

Friends

Additional Inherited Members

Constructor & Destructor Documentation

◆ GraphCL() [1/5]

◆ GraphCL() [2/5]

◆ GraphCL() [3/5]

◆ GraphCL() [4/5]

◆ GraphCL() [5/5]

◆ ~GraphCL()

Member Function Documentation

◆ combine()

◆ copy()

◆ finalize()

◆ foundDiagonalElement()

◆ merge2()

◆ merge3()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ queryDiagonalElement()

◆ release() [1/2]

◆ release() [2/2]

◆ resetConditions()

◆ swap()

◆ synchFromGpu()

◆ synchToGpu()

◆ tempMatrix()

Friends And Related Function Documentation

◆ frechet::reach::newGraph [1/3]

◆ frechet::reach::newGraph [2/3]

◆ frechet::reach::newGraph [3/3]

Member Data Documentation

◆ clmtx

◆ cond

◆ diagonalElementBuffer

◆ temps