Detailed Description

implementation with a sorted call-graph.

The main loop of Buchin's decision algorithm consists of recursive function calls. We create a call-graph of the recursive function calls. Then the call-graph is sorted topologically from bottom to top. See frechet::reach::Graph how the Graph objects double as placeholders for call-graphs nodes.

Each level of the sorted call-graph consists of independent tasks. Call dependencies exist only between one level and the next level.

This would allow us to distribute the tasks on one level to multiple processor cores. The idea was discarded later because, unfortunately, it interferes with matrix multiplications.

It turns out that matrix multiplications are fine-tuned to make best usage of processor cache memory. Running two multiplications in parallel severely hampers cache performance. That's why the approach had to be dropped: the main loop is still sequential, matrix multiplications are parallelized in inner loops.

However, the call-graph implementation survived because it has one more advantage. After a level of tasks is finished, unneeded data (from lower levels) can be released from the memoisation maps. Thus, this implementation can be used to reduce memory usage, which is indeed an issue with GPGPU memory.

It can be turned on with the command line switch "--gpu --large".

Definition at line 167 of file parallel.h.

#include <parallel.h>

Inherits frechet::poly::AlgorithmMultiCore.

Public Member Functions
	AlgorithmTopoSort ()
	default constructor More...

virtual	~AlgorithmTopoSort ()
	destructor release all memory More...

virtual reach::Graph::ptr	create_RG (int i) override
	re-implements base method; instead of calculating the Graph, we just put a placeholder into the memoisation map. The actual computation is done later. More...

virtual reach::Graph::ptr	MERGE_inner (const reach::Graph::ptr A, const reach::Graph::ptr B) override
	re-implements base method; instead of calculating the result, we just put a placeholder into the memoisation map. The actual computation is done later. More...

virtual reach::Graph::ptr	MERGE_outer (const reach::Graph::ptr A, const reach::Graph::ptr B) override
	re-implements base method; instead of calculating the result, we just put a placeholder into the memoisation map. The actual computation is done later. More...

virtual void	COMBINE (reach::Graph::ptr A, int di, int dj) override
	re-implements base method; instead of calculating the result, we just put a placeholder into the memoisation map. The actual computation is done later. More...

virtual GraphPtr	findFeasiblePath () override
	re-implements the main loop of the decision variant; traverse the call-graph bottom-up and compute the CGRs level by level. Unneeded CRGs are released asap. More...

virtual bool	isSolution (GraphPtr G) override

Public Member Functions inherited from frechet::poly::AlgorithmMultiCore
	AlgorithmMultiCore ()
	default constructor More...

virtual	~AlgorithmMultiCore ()
	destructor More...

virtual void	triangulate () override
	re-implements base class method; stores thread-local copies of Q's triangulation More...

Public Member Functions inherited from frechet::poly::AlgorithmSingleCore
	AlgorithmSingleCore ()

Public Member Functions inherited from frechet::poly::Algorithm
	Algorithm ()
	default constructor More...

virtual	~Algorithm ()
	destructor; releases all memory More...

Status	status () const
	current status of the algorithm More...

bool	canDecidePoly () const
	check if we can execute the decision variant on simple polygons (Buchin et al.'s algorithm) More...

bool	canOptimisePoly () const
	check if we can execute the optimisation variant on simple polygons (Buchin et al.'s algorithm) More...

bool	canOptimiseCurve () const
	check if we can execute the optimisation variant on curves (Alt and Godau's algorithm) More...

const Segments &	c_diagonals () const
	the c-diagonals More...

bool	is_c_diagonal (int di, int dj) const
	check, whether a diagonal is a c-diagonal More...

bool	is_c_diagonal (Segment s) const
	check, whether a diagonal is a c-diagonal More...

Triangulation &	PTriangulation ()
	the triangulation of P More...

Triangulation &	QTriangulation ()
	the triangulation of Q More...

Triangulation &	displayPTriangulation ()
	a complete triangulation for P (only needed for visualisation More...

const Curve &	Pcurve () const
	the first input curve P More...

const Curve &	Qcurve () const
	the first input curve Q More...

PolygonUtilities *	polygonUtilities (bool primary)
	helper object for polygon analysis More...

Status	setup (Curve &aP, Curve &aQ, bool fixOrientation=false)
	Initialize input curves and perform some basic sanity checks. More...

bool	decompose (bool optimal)
	decompose polygons into convex parts More...

void	swap ()
	swap input curves. The algorithm by Buchin et al. chooses the smalled convex decompositioin as P. More...

GraphPtr	decidePolygon (FreeSpace::ptr fs, reach::FSPath::ptr path, double epsilon, bool update_status)
	execute the decision variant for simple polygons (Buchin et al.'s algorithm) More...

double	optimisePolygon (reach::FSPath::ptr path, double approximation=0.0)
	execute the optimisaion variant for simple polygons. (Buchin et al.'s algorithm) The result value is broadcast by signal optimisationResult(double epsilon). More...

reach::Pointer	decideCurve (FreeSpace::ptr fs, reach::FSPath::ptr path, double ignored, bool update_status)
	execute the decision variant for curves. (Alt and Godau's algorithm) More...

double	optimiseCurve (double approximation=0.0)
	execute the optimisation variant for curves. (Alt and Godau's algorithm) More...

void	collectCriticalValues (bool a, bool b, bool c, bool d)
	compute a set of critical values for the optimisation variant More...

template<typename R >
int	binarySearch (const std::vector< double > &values, int lo, int hi, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)

template<typename R >
double	intervalSearch (double lower_bound, double upper_bound, double precision, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)

template<typename Float >
Float	segment_distance (const QLineF &segment, const Point &q1)

template<typename Float >
Float	bisector_distance (const Float &p1x, const Float &p1y, const Float &p2x, const Float &p2y, const Float &q1x, const Float &q1y, const Float &q2x, const Float &q2y, const Float &tolerance)

template<typename Float >
Float	bisector_distance (const Point &q1, const Point &q2, const QLineF &segment, Float tolerance)

Protected Types
typedef std::list< Graph::ptr >	GraphList
	list of tasks, sorted by b-level b-level 0 = leaves = RG's More...

typedef std::vector< GraphList >	TopoSort

Protected Types inherited from frechet::poly::Algorithm
typedef tbb::concurrent_unordered_map< int, GraphPtr >	PlacementMap
	hash map for reachability graphs More...

typedef std::vector< reach::Placements >	PlacementVector
	list of valid placements More...

typedef tbb::concurrent_unordered_map< int, reach::Graph::ptr >	GraphMap
	used to store intermediate (memo-ized) reachability graphs More...

typedef std::vector< double >	CriticalValueList
	a list of critical values More...

Protected Member Functions
void	addTopoSort (Graph::ptr G)
	insert a CGR into the topologically sorted list of calls More...

void	calculate (Graph::ptr G)
	finally compute the contents of a CGR More...

void	reclaimPredecessors (Graph::ptr G)
	release CGRs that are not needed anymore More...

void	reclaim (Graph *G)
	reclaim graph memory More...

virtual void	cleanup () override
	release all memory More...

void	barrier (bool finish)
	put up a memory barrier between each level of the call graph (necessary for OpenCL implementation) More...

Protected Member Functions inherited from frechet::poly::AlgorithmMultiCore
virtual void	calculateReachabilityGraphs () override

virtual void	calculateValidPlacements (double epsilon) override
	calculate all valid placements More...

virtual CriticalValueList &	currentCriticalValueList ()
	thread-local copy of critical values More...

virtual void	collectCriticalValues_b (const Curve &P, const Curve &Q) override
	compute critical values of type (b) More...

virtual void	collectCriticalValues_c (const Curve &P, const Curve &Q) override
	compute critical values of type (c) More...

virtual void	collectCriticalValues_d () override
	compute critical values for diagonals and reflex vertices More...

virtual void	combineCriticalValues () override
	reduce thread-local lists to a global list, then sort it More...

void	clear_qtri ()
	release thread-local variables More...

Protected Member Functions inherited from frechet::poly::AlgorithmSingleCore
virtual reach::Graph::ptr	CRG (int i, int j, Triangulation::Edge e=Triangulation::Edge())
	get a memoised Combined Reachabilty Graph. This is one of the steps in Buchin et al.'s decision algorithm. More...

virtual reach::Graph::ptr	create_CRG (int i, int j, Triangulation::Edge e)
	compute a Combined Reachabilty Graph. More...

bool	assertReachabilityGraphs ()
	debug assertion; check if the CRGs are correctyl aligned More...

Protected Member Functions inherited from frechet::poly::Algorithm
GraphPtr	getValidPlacements (int di, int dj)
	get valid placements for a given pair of diagonal end points; compute them, if necssary. Subsequent calls retrieve the memo-ized result. More...

GraphPtr	calculate_RG (int i)
	get a Reachability Graph; compute it, if necessary. Subsequent calls retrieve the memo-ized result. More...

int	mapKey (int di, int dj)
	hash key for memo-ized maps More...

GraphPtr	createValidPlacementGraph (int di, int dj)
	compute an adjacancy matrix of valid placements for one pair of diagonal end points More...

void	calculateValidPlacements (poly::PolygonShortestPathsFS &spt, double epsilon, int di, int dj)
	calculate valid placements for a pair of diagonal end points More...

Triangulation::Edge	diagonalEdge (int i) const
	a diagonal edge of the triangulation of P More...

int	l () const
	number of diagonal end points More...

int	k () const
	number of c-diagonals More...

int	d (int i) const
	map a diagonal end-point to a vertex in P More...

int	partitions () const
	number of convex partitions (components) More...

void	calculatePlacements (int i, frechet::reach::Placements &result)
	calculate free-space placements More...

Status	setStatus (Status)
	set current status More...

Status	setInitialStatus (Status)
	set initial status (after pre-processing input data) More...

void	updatePath (reach::FSPath::ptr path, GraphPtr result, double epsilon)
	compute a feasible path from the result of (Buchin et al.'s) decision algorithm More...

void	updatePath (reach::FSPath::ptr path, reach::Pointer startPointer, double epsilon)
	compute a feasible path from the result of (Alt and Godau's) decision algorithm More...

void	collectCriticalValues_a ()
	compute critical values of type (a) More...

void	collectCriticalValues_b (const Point &p, const Curve &Q)
	compute critical values of type (b) More...

void	collectCriticalValues_c (const QLineF &pseg, const Curve &Q)
	compute critical values of type (c) More...

void	collectCriticalValues_d (const QLineF &diagonal)
	compute critical values for diagonals and reflex vertices More...

virtual void	collectCriticalValue (const accurate_float &x)
	store a critical value. Duplicates are accepted but removed later. More...

void	removeDuplicates (CriticalValueList &vector)
	remove duplicates from a sorted list of critical values More...

template<typename R >
int	binarySearch (const std::vector< double > &values, int lo, int hi, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)
	perform a binary search on a list of critical values. For each step of the binary search, perform the decision variant. More...

template<typename R >
double	intervalSearch (double lower_bound, double upper_bound, double precision, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)
	perform a nested interval search. For each step of the search, perform the decision variant. More...

void	testCancelFlag ()
	poll cancelFlag More...

Protected Attributes
TopoSort	topo
	sorted call graph More...

GraphList	roots
	roots of the call graph: this is where the results of the algorithm pop up More...

MatrixPool	pool
	recycling pool of matrices More...

Protected Attributes inherited from frechet::poly::Algorithm
enum Status	_status
	current status of the algorithm More...

enum Status	initial_status
	initial status of the algorithm (before or after processing input data) More...

struct frechet::poly::Algorithm::CurveData *	P

struct frechet::poly::Algorithm::CurveData *	Q

FreeSpace::ptr	fs
	current Free-Space diagram (passed to the decision variant) More...

PlacementVector	_placements
	list of placements (for each end point of diagonals) More...

PlacementMap	_validPlacements
	map of valid placements (as adjacency matrices, for each c-diagonal) More...

reach::GraphModel::ptr	graphModel
	map free-space interval to nodes of the reachability graph More...

GraphMap	CRG_map
	a map of memo-ized Combined Reachability Graphs More...

FreeSpace::ptr	local_fs
	Free-Space used during binary searches (optimisation variant) More...

CriticalValueList	criticalValues
	the list of critical values (optimisation variant) More...

volatile bool *	cancelFlag
	indicates user interruption More...

Additional Inherited Members
Public Types inherited from frechet::poly::Algorithm
enum	Status : int8_t { RUNNING = -2, RUNNING_DECIDE_POLY =-8, RUNNING_OPT_POLY =-7, RUNNING_APPROX_POLY =-6, RUNNING_DECIDE_CURVE =-5, RUNNING_OPT_CURVE =-4, RUNNING_APPROX_CURVE =-3, YES =0, NO, NOT_SET_UP, SET_UP, P_EMPTY, Q_EMPTY, P_NOT_CLOSED, Q_NOT_CLOSED, P_NOT_SIMPLE, Q_NOT_SIMPLE, P_NOT_COUNTER_CLOCKWISE, Q_NOT_COUNTER_CLOCKWISE, P_CONVEX, Q_CONVEX }
	indicates the current status of the algorithm. Negative values indicate that the algorithm is currently computing. Positive values indicate the result and also conditions of input data. More...

typedef frechet::reach::Graph::ptr	GraphPtr
	the result of the decision algorithm is a reachability Graph containing a feasible path More...

typedef boost::shared_ptr< Algorithm >	ptr
	(smart) pointer to an Algorithm object More...

Public Slots inherited from frechet::poly::Algorithm
void	resetStatus (bool stopping=false)
	reset the status of the algorithm More...

Signals inherited from frechet::poly::Algorithm
void	statusChanged ()
	emitted whenever the status of the algorithm changes. More...

void	pathUpdated (bool valid)
	emitted when a feasible path has been found More...

void	optimisationResult (double epsilon)
	emitted when the optimisation (or approximation) algorithm finds a result More...

Static Public Member Functions inherited from frechet::poly::Algorithm
static double	pickIntervalPoint (const Interval &j, int m=INT_MAX)
	pick a point from a free-space interval. Helper function for creating feasible paths. More...

Static Protected Member Functions inherited from frechet::poly::AlgorithmMultiCore
static const CriticalValueList &	combine (CriticalValueList &a, const CriticalValueList &b)
	reduce two thread-local lists of critical values; the lists are simply appended More...

Static Protected Member Functions inherited from frechet::poly::Algorithm
template<typename Float >
static Float	bisector_distance (const Float &p1x, const Float &p1y, const Float &p2x, const Float &p2y, const Float &q1x, const Float &q1y, const Float &q2x, const Float &q2y, const Float &tolerance)
	compute the distance between a bisector and a polygon segment More...

template<typename Float >
static Float	segment_distance (const QLineF &segment, const Point &q1)
	compute the distance between a polygon segment and a point More...

template<typename Float >
static Float	bisector_distance (const Point &q1, const Point &q2, const QLineF &segment, Float tolerance=0.0)
	compute the distance between a bisector and a polygon segment More...

Member Typedef Documentation

◆ GraphList

typedef std::list<Graph::ptr> frechet::poly::AlgorithmTopoSort::GraphList

protected

list of tasks, sorted by b-level b-level 0 = leaves = RG's

Definition at line 171 of file parallel.h.

◆ TopoSort

typedef std::vector<GraphList> frechet::poly::AlgorithmTopoSort::TopoSort

protected

Definition at line 172 of file parallel.h.

Constructor & Destructor Documentation

◆ AlgorithmTopoSort()

AlgorithmTopoSort::AlgorithmTopoSort ( )

default constructor

Definition at line 389 of file parallel.cpp.

◆ ~AlgorithmTopoSort()

AlgorithmTopoSort::~AlgorithmTopoSort ( )

virtual

destructor release all memory

Definition at line 394 of file parallel.cpp.

Member Function Documentation

◆ addTopoSort()

void AlgorithmTopoSort::addTopoSort ( Graph::ptr G )

protected

insert a CGR into the topologically sorted list of calls

Parameters

G	an empty CGR that acts as placeholder

Definition at line 521 of file parallel.cpp.

◆ barrier()

void AlgorithmTopoSort::barrier ( bool finish )

protected

put up a memory barrier between each level of the call graph (necessary for OpenCL implementation)

finish

Definition at line 527 of file parallel.cpp.

◆ calculate()

void AlgorithmTopoSort::calculate ( Graph::ptr G )

protected

finally compute the contents of a CGR

Parameters

G	a CRG placeholder that will now be filled

Definition at line 463 of file parallel.cpp.

◆ cleanup()

void AlgorithmTopoSort::cleanup ( )

overrideprotectedvirtual

release all memory

Reimplemented from frechet::poly::Algorithm.

Definition at line 513 of file parallel.cpp.

◆ COMBINE()

void AlgorithmTopoSort::COMBINE	(	reach::Graph::ptr	A,
		int	di,
		int	dj
	)

overridevirtual

re-implements base method; instead of calculating the result, we just put a placeholder into the memoisation map. The actual computation is done later.

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 423 of file parallel.cpp.

◆ create_RG()

reach::Graph::ptr AlgorithmTopoSort::create_RG ( int i )

overridevirtual

re-implements base method; instead of calculating the Graph, we just put a placeholder into the memoisation map. The actual computation is done later.

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 397 of file parallel.cpp.

◆ findFeasiblePath()

GraphPtr AlgorithmTopoSort::findFeasiblePath ( )

overridevirtual

re-implements the main loop of the decision variant; traverse the call-graph bottom-up and compute the CGRs level by level. Unneeded CRGs are released asap.

Returns: resulting CRG, or nullptr

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 435 of file parallel.cpp.

◆ isSolution()

bool AlgorithmTopoSort::isSolution ( GraphPtr G )

overridevirtual

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 430 of file parallel.cpp.

◆ MERGE_inner()

reach::Graph::ptr AlgorithmTopoSort::MERGE_inner	(	const reach::Graph::ptr	A,
		const reach::Graph::ptr	B
	)

overridevirtual

re-implements base method; instead of calculating the result, we just put a placeholder into the memoisation map. The actual computation is done later.

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 406 of file parallel.cpp.

◆ MERGE_outer()

reach::Graph::ptr AlgorithmTopoSort::MERGE_outer	(	const reach::Graph::ptr	A,
		const reach::Graph::ptr	B
	)

overridevirtual

re-implements base method; instead of calculating the result, we just put a placeholder into the memoisation map. The actual computation is done later.

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 414 of file parallel.cpp.

◆ reclaim()

void AlgorithmTopoSort::reclaim ( Graph * G )

protected

reclaim graph memory

Definition at line 504 of file parallel.cpp.

◆ reclaimPredecessors()

void AlgorithmTopoSort::reclaimPredecessors ( Graph::ptr G )

protected

release CGRs that are not needed anymore

Parameters

G	a CRG whose contents has just been computed; release uneeded predecessor graphs

Definition at line 490 of file parallel.cpp.

Member Data Documentation

◆ pool

MatrixPool frechet::poly::AlgorithmTopoSort::pool

protected

recycling pool of matrices

Definition at line 178 of file parallel.h.

◆ roots

GraphList frechet::poly::AlgorithmTopoSort::roots

protected

roots of the call graph: this is where the results of the algorithm pop up

Definition at line 176 of file parallel.h.

◆ topo

TopoSort frechet::poly::AlgorithmTopoSort::topo

protected

sorted call graph

Definition at line 174 of file parallel.h.

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

include/frechet/poly/parallel.h
src/frechet/poly/parallel.cpp

Detailed Description

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Member Typedef Documentation

◆ GraphList

◆ TopoSort

Constructor & Destructor Documentation

◆ AlgorithmTopoSort()

◆ ~AlgorithmTopoSort()

Member Function Documentation

◆ addTopoSort()

◆ barrier()

◆ calculate()

◆ cleanup()

◆ COMBINE()

◆ create_RG()

◆ findFeasiblePath()

◆ isSolution()

◆ MERGE_inner()

◆ MERGE_outer()

◆ reclaim()

◆ reclaimPredecessors()

Member Data Documentation

◆ pool

◆ roots

◆ topo