Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::reach::GraphCL Class Reference

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>

Inherits frechet::reach::Graph.

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...
 
GraphCLoperator= (const GraphCL &that)
 assginment operator More...
 
GraphCLoperator= (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
 
Graphoperator= (const Graph &)
 
Graphoperator= (Graph &&)
 
Graphoperator+= (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 IndexRangehmask () 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...
 
Graphoperator= (const Graph &that)
 assigment operator More...
 
Graphoperator= (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_ttempMatrix (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_tclmtx [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< Graphptr
 
typedef boost::shared_ptr< Graphptr
 
- 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
modelmaps 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
modelmaps reachability intervals to graph nodes
hmaskcolumn 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
modelmaps reachability intervals to graph nodes
stra reachability structure

Definition at line 53 of file graph_cl.cpp.

◆ GraphCL() [4/5]

GraphCL::GraphCL ( const GraphCL that)

copy constructor

Parameters
thatgraph to copy from

Definition at line 61 of file graph_cl.cpp.

◆ GraphCL() [5/5]

GraphCL::GraphCL ( GraphCL &&  that)

move constructor

Parameters
thatgraph 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
Pa 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
thatgraph 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
Aa graph
Banother graph
poolpool 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
Aa graph
Banother graph
poolpool 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
thatgraph 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
thatthat 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
o1horizontal part
o2vertical 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
o1horizontal part
o2vertical part
poola 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
thatgraph 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
rowsnumber of rows
colsnumber of columns
poolpool 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]

◆ 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: