![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
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 |
![]() | |
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... | |
![]() | |
AlgorithmSingleCore () | |
![]() | |
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 |
![]() | |
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... | |
![]() | |
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... | |
![]() | |
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... | |
![]() | |
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... | |
![]() | |
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 | |
![]() | |
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... | |
![]() | |
void | resetStatus (bool stopping=false) |
reset the status of the algorithm More... | |
![]() | |
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 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 const CriticalValueList & | combine (CriticalValueList &a, const CriticalValueList &b) |
reduce two thread-local lists of critical values; the lists are simply appended More... | |
![]() | |
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... | |
|
protected |
list of tasks, sorted by b-level b-level 0 = leaves = RG's
Definition at line 171 of file parallel.h.
|
protected |
Definition at line 172 of file parallel.h.
AlgorithmTopoSort::AlgorithmTopoSort | ( | ) |
default constructor
Definition at line 389 of file parallel.cpp.
|
virtual |
destructor release all memory
Definition at line 394 of file parallel.cpp.
|
protected |
insert a CGR into the topologically sorted list of calls
G | an empty CGR that acts as placeholder |
Definition at line 521 of file parallel.cpp.
|
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.
|
protected |
finally compute the contents of a CGR
G | a CRG placeholder that will now be filled |
Definition at line 463 of file parallel.cpp.
|
overrideprotectedvirtual |
release all memory
Reimplemented from frechet::poly::Algorithm.
Definition at line 513 of file parallel.cpp.
|
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.
|
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.
|
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.
Reimplemented from frechet::poly::AlgorithmSingleCore.
Definition at line 435 of file parallel.cpp.
|
overridevirtual |
Reimplemented from frechet::poly::AlgorithmSingleCore.
Definition at line 430 of file parallel.cpp.
|
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.
|
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.
|
protected |
reclaim graph memory
Definition at line 504 of file parallel.cpp.
|
protected |
release CGRs that are not needed anymore
G | a CRG whose contents has just been computed; release uneeded predecessor graphs |
Definition at line 490 of file parallel.cpp.
|
protected |
recycling pool of matrices
Definition at line 178 of file parallel.h.
|
protected |
roots of the call graph: this is where the results of the algorithm pop up
Definition at line 176 of file parallel.h.
|
protected |
sorted call graph
Definition at line 174 of file parallel.h.