Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
parallel.h
Go to the documentation of this file.
1 #ifndef PARALLEL_H
2 #define PARALLEL_H
3 
4 #include <algorithm.h>
5 #include <data/matrix_pool.h>
6 
7 #include <tbb/tbb.h>
8 #include <tbb/combinable.h>
9 #include <tbb/enumerable_thread_specific.h>
10 #include <tbb/flow_graph.h>
11 #include <tbb/task_group.h>
13 
14 namespace frechet { namespace poly {
15 
16 using namespace reach;
17 
18 
25  /*
26  * CRG is an Array of Graph::ptr
27  * */
28 public:
30 
31 protected:
32  virtual reach::Graph::ptr CRG(int i, int j, Triangulation::Edge e = Triangulation::Edge());
33  virtual reach::Graph::ptr create_RG(int i);
34  virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e);
35 
36  virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr A, const reach::Graph::ptr B);
37  virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr A, const reach::Graph::ptr B);
38  virtual void COMBINE(reach::Graph::ptr A, int di, int dj);
39 
40 
41  virtual void calculateReachabilityGraphs() override;
42  virtual void calculateValidPlacements(double epsilon) override;
43  virtual GraphPtr findFeasiblePath() override;
44  virtual bool isSolution(GraphPtr G);
45 
46  virtual void collectCriticalValues_b(const Curve& P, const Curve& Q) override;
47  virtual void collectCriticalValues_c(const Curve& P, const Curve& Q) override;
48  virtual void collectCriticalValues_d() override;
49  virtual void combineCriticalValues() override;
50 
52  bool assertReachabilityGraphs();
53 };
54 
89 private:
90  typedef tbb::enumerable_thread_specific<Triangulation*> LocalTriangulation;
94  std::vector<Segment> c_diagonals_vector;
95 
96  typedef tbb::combinable<CriticalValueList> LocalCriticalValueList;
99 
100  typedef tbb::enumerable_thread_specific<PolygonShortestPathsFS*> LocalSPT;
102  static LocalSPT spt;
103 
104 public:
108  virtual ~AlgorithmMultiCore();
109 
114  virtual void triangulate() override;
115 
116 protected:
117  virtual void calculateReachabilityGraphs() override;
118  virtual void calculateValidPlacements(double epsilon) override;
119  //virtual GraphPtr findFeasiblePath() override;
120 
122  virtual CriticalValueList& currentCriticalValueList();
123  virtual void collectCriticalValues_b(const Curve& P, const Curve& Q) override;
124  virtual void collectCriticalValues_c(const Curve& P, const Curve& Q) override;
125  virtual void collectCriticalValues_d() override;
126 
128  virtual void combineCriticalValues() override;
129 
135  static const CriticalValueList& combine(CriticalValueList& a, const CriticalValueList& b);
137  void clear_qtri();
138 };
139 
140 
168 protected:
171  typedef std::list<Graph::ptr> GraphList;
172  typedef std::vector<GraphList> TopoSort;
179 public:
183  virtual ~AlgorithmTopoSort();
184 
190  virtual reach::Graph::ptr create_RG(int i) override;
196  virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr A, const reach::Graph::ptr B) override;
202  virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr A, const reach::Graph::ptr B) override;
208  virtual void COMBINE(reach::Graph::ptr A, int di, int dj) override;
216  virtual GraphPtr findFeasiblePath() override;
217  virtual bool isSolution(GraphPtr G) override;
218 
219 protected:
222  void addTopoSort(Graph::ptr G);
225  void calculate(Graph::ptr G);
228  void reclaimPredecessors(Graph::ptr G);
230  void reclaim(Graph* G);
232  virtual void cleanup() override;
236  void barrier(bool finish);
237 };
238 
239 
240 } } // namespace frechet::poly
241 
242 #endif // PARALLEL_H
frechet::reach::Graph::ptr GraphPtr
the result of the decision algorithm is a reachability Graph containing a feasible path
Definition: algorithm.h:116
Multi-Core implementaion. Uses Intel TBB to perform some parallel computation.
Definition: parallel.h:88
tbb::combinable< CriticalValueList > LocalCriticalValueList
Definition: parallel.h:96
std::list< Graph::ptr > GraphList
list of tasks, sorted by b-level b-level 0 = leaves = RG's
Definition: parallel.h:171
tbb::enumerable_thread_specific< PolygonShortestPathsFS * > LocalSPT
Definition: parallel.h:100
global definitions for all algorithms.
std::vector< double > CriticalValueList
a list of critical values
Definition: algorithm.h:230
Sequential implementation for a single processor core.
Definition: parallel.h:24
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
implementation with a sorted call-graph.
Definition: parallel.h:167
base class for algorithm for simple polygons.
Definition: algorithm.h:51
GraphList roots
roots of the call graph: this is where the results of the algorithm pop up
Definition: parallel.h:176
static LocalSPT spt
thread-local copies for PolygonShortestPathsFS
Definition: parallel.h:102
std::vector< Segment > c_diagonals_vector
vector of c-diagonals
Definition: parallel.h:94
std::vector< GraphList > TopoSort
Definition: parallel.h:172
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
Definition: types.h:20
MatrixPool pool
recycling pool of matrices
Definition: parallel.h:178
boost::shared_ptr< Graph > ptr
Definition: graph_boost.h:59
memory pool for matrix objects (M4RI matrices mzd_t* and OpenCL matrices clm4rm_t*)
Definition: matrix_pool.h:26
void reclaim(mzd_t *m, MatrixPool *pool)
reclaim an object (i.e. put it into the recycling list)
Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure,...
Definition: graph_boost.h:39
static LocalTriangulation qtri
thread-local copies of Q->triangulation
Definition: parallel.h:92
tbb::enumerable_thread_specific< Triangulation * > LocalTriangulation
Definition: parallel.h:90
static LocalCriticalValueList localCriticalValues
thread-local copies of critical values
Definition: parallel.h:98
TopoSort topo
sorted call graph
Definition: parallel.h:174