parallel.h

Go to the documentation of this file.

#ifndef PARALLEL_H
#define PARALLEL_H

#include <algorithm.h>
#include <data/matrix_pool.h>

#include <tbb/tbb.h>
#include <tbb/combinable.h>
#include <tbb/enumerable_thread_specific.h>
#include <tbb/flow_graph.h>
#include <tbb/task_group.h>
#include <frechet/app/concurrency.h>

namespace frechet { namespace poly {

using namespace reach;


class AlgorithmSingleCore : public Algorithm {
    /*
     *  CRG is an Array of Graph::ptr
     * */
public:
    AlgorithmSingleCore();
    
protected:
    virtual reach::Graph::ptr CRG(int i, int j, Triangulation::Edge e = Triangulation::Edge());
    virtual reach::Graph::ptr create_RG(int i);
    virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e);

    virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr  A, const reach::Graph::ptr  B);
    virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr  A, const reach::Graph::ptr  B);
    virtual void COMBINE(reach::Graph::ptr  A, int di, int dj);


    virtual void calculateReachabilityGraphs() override;
    virtual void calculateValidPlacements(double epsilon) override;
    virtual GraphPtr findFeasiblePath() override;
    virtual bool isSolution(GraphPtr G);

    virtual void collectCriticalValues_b(const Curve& P, const Curve& Q) override;
    virtual void collectCriticalValues_c(const Curve& P, const Curve& Q) override;
    virtual void collectCriticalValues_d() override;
    virtual void combineCriticalValues() override;

    bool assertReachabilityGraphs();
};

class AlgorithmMultiCore : public AlgorithmSingleCore {
private:
    typedef tbb::enumerable_thread_specific<Triangulation*> LocalTriangulation;
    static LocalTriangulation qtri;
    std::vector<Segment> c_diagonals_vector;

    typedef tbb::combinable<CriticalValueList> LocalCriticalValueList;
    static LocalCriticalValueList localCriticalValues;

    typedef tbb::enumerable_thread_specific<PolygonShortestPathsFS*> LocalSPT;
    static LocalSPT spt;

public:
    AlgorithmMultiCore();
    virtual ~AlgorithmMultiCore();

    virtual void triangulate() override;

protected:
    virtual void calculateReachabilityGraphs() override;
    virtual void calculateValidPlacements(double epsilon) override;
    //virtual GraphPtr findFeasiblePath() override;

    virtual CriticalValueList& currentCriticalValueList();
    virtual void collectCriticalValues_b(const Curve& P, const Curve& Q) override;
    virtual void collectCriticalValues_c(const Curve& P, const Curve& Q) override;
    virtual void collectCriticalValues_d() override;

    virtual void combineCriticalValues() override;

    static const CriticalValueList& combine(CriticalValueList& a, const CriticalValueList& b);
    void clear_qtri();
};


class AlgorithmTopoSort : public AlgorithmMultiCore {
protected:
    typedef std::list<Graph::ptr> GraphList;
    typedef std::vector<GraphList> TopoSort;
    TopoSort topo;
    GraphList roots;
    MatrixPool pool;
public:
    AlgorithmTopoSort();
    virtual ~AlgorithmTopoSort();

    virtual reach::Graph::ptr create_RG(int i) override;
    virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr  A, const reach::Graph::ptr  B) override;
    virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr  A, const reach::Graph::ptr  B) override;
    virtual void COMBINE(reach::Graph::ptr  A, int di, int dj) override;
    virtual GraphPtr findFeasiblePath() override;
    virtual bool isSolution(GraphPtr G) override;

protected:
    void addTopoSort(Graph::ptr G);
    void calculate(Graph::ptr G);
    void reclaimPredecessors(Graph::ptr G);
    void reclaim(Graph* G);
    virtual void cleanup() override;
    void barrier(bool finish);
};


} }  // namespace frechet::poly

#endif // PARALLEL_H