#include "convex_hull.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_for.h"
#include "tbb/parallel_reduce.h"
#include "tbb/blocked_range.h"
#include "tbb/concurrent_vector.h"

Include dependency graph for convex_hull_bench.cpp:

Classes
class	FillRNDPointsVector
class	FillRNDPointsVector_buf
class	FindXExtremum
class	SplitByCP
class	SplitByCP_buf
Defines
#define	INIT_ONCE 1
#define	USECONCVEC 1
#define	USETBB 1
Typedefs
typedef util::point< double >	point_t
typedef tbb::concurrent_vector < point_t >	pointVec_t
typedef tbb::blocked_range < size_t >	range_t
Functions
void	appendVector (const point_t *src, size_t srcSize, pointVec_t &dest)
void	appendVector (const pointVec_t &src, pointVec_t &dest)
template<typename BodyType >
point_t	divide (const pointVec_t &P, pointVec_t &P_reduced, const point_t &p1, const point_t &p2)
void	divide_and_conquer (const pointVec_t &P, pointVec_t &H, point_t p1, point_t p2, bool buffered)
template<FindXExtremum::extremumType type>
point_t	extremum (const pointVec_t &P)
template<typename BodyType >
void	initialize (pointVec_t &points)
int	main (int argc, char *argv[])
void	quickhull (const pointVec_t &points, pointVec_t &hull, bool buffered)

Define Documentation

#define INIT_ONCE 1

Definition at line 39 of file convex_hull_bench.cpp.

#define USECONCVEC 1

Definition at line 38 of file convex_hull_bench.cpp.

#define USETBB 1

Definition at line 37 of file convex_hull_bench.cpp.

Typedef Documentation

typedef util::point<double> point_t

Definition at line 35 of file convex_hull_bench.cpp.

typedef tbb::concurrent_vector<point_t> pointVec_t

Definition at line 212 of file convex_hull_bench.cpp.

typedef tbb::blocked_range<size_t> range_t

Definition at line 207 of file convex_hull_bench.cpp.

Function Documentation

void appendVector	(	const point_t *	src,
		size_t	srcSize,
		pointVec_t &	dest
	)

Definition at line 214 of file convex_hull_bench.cpp.

References tbb::concurrent_vector< T, A >::grow_by().

Referenced by divide_and_conquer(), and quickhull().

                                                                        {
    std::copy(src, src + srcSize, dest.grow_by(srcSize));
}

void appendVector	(	const pointVec_t &	src,
		pointVec_t &	dest
	)

Definition at line 218 of file convex_hull_bench.cpp.

References tbb::concurrent_vector< T, A >::begin(), tbb::concurrent_vector< T, A >::end(), tbb::concurrent_vector< T, A >::grow_by(), and tbb::concurrent_vector< T, A >::size().

                                                           {
    std::copy(src.begin(), src.end(), dest.grow_by(src.size()));
}

template<typename BodyType >

point_t divide	(	const pointVec_t &	P,
		pointVec_t &	P_reduced,
		const point_t &	p1,
		const point_t &	p2
	)

Definition at line 500 of file convex_hull_bench.cpp.

References util::OUTPUT, tbb::parallel_reduce(), tbb::concurrent_vector< T, A >::size(), and util::VERBOSE.

Referenced by divide_and_conquer().

                                                    {
    BodyType body(p1, p2, P, P_reduced);
    // Must use simple_partitioner (see the comment in initialize() above)
    tbb::parallel_reduce(range_t(0, P.size(), BodyType::grainSize),
                         body, tbb::simple_partitioner() );

    if(util::VERBOSE) {
        std::stringstream ss;
        ss << P.size() << " nodes in bucket"<< ", "
            << "dividing by: [ " << p1 << ", " << p2 << " ], "
            << "farthest node: " << body.farthestPoint();
        util::OUTPUT.push_back(ss.str());
    }

    return body.farthestPoint();
}

void divide_and_conquer	(	const pointVec_t &	P,
		pointVec_t &	H,
		point_t	p1,
		point_t	p2,
		bool	buffered
	)

Definition at line 518 of file convex_hull_bench.cpp.

References appendVector(), tbb::concurrent_vector< T, A >::begin(), tbb::concurrent_vector< T, A >::end(), tbb::concurrent_vector< T, A >::push_back(), and tbb::concurrent_vector< T, A >::size().

Referenced by divide_and_conquer(), and quickhull().

                                                               {
    if (P.size()<2) {
        H.push_back(p1);
#if USECONCVEC
        appendVector(P, H);
#else // insert into STD::VECTOR
        H.insert(H.end(), P.begin(), P.end());
#endif
    }
    else {
        pointVec_t P_reduced;
        pointVec_t H1, H2;
        point_t p_far;

        if(buffered) {
            p_far = divide<SplitByCP_buf>(P, P_reduced, p1, p2);
        } else {
            p_far = divide<SplitByCP>(P, P_reduced, p1, p2);
        }

        divide_and_conquer(P_reduced, H1, p1, p_far, buffered);
        divide_and_conquer(P_reduced, H2, p_far, p2, buffered);

#if USECONCVEC
        appendVector(H1, H);
        appendVector(H2, H);
#else // insert into STD::VECTOR
        H.insert(H.end(), H1.begin(), H1.end());
        H.insert(H.end(), H2.begin(), H2.end());
#endif
    }
}

template<FindXExtremum::extremumType type>

point_t extremum ( const pointVec_t & P )

Definition at line 368 of file convex_hull_bench.cpp.

References FindXExtremum::extremeXPoint(), FindXExtremum::grainSize, tbb::parallel_reduce(), and tbb::concurrent_vector< T, A >::size().

                                      {
    FindXExtremum fxBody(P, type);
    tbb::parallel_reduce(range_t(0, P.size(), FindXExtremum::grainSize), fxBody);
    return fxBody.extremeXPoint();
}

template<typename BodyType >

void initialize ( pointVec_t & points )

Definition at line 307 of file convex_hull_bench.cpp.

References tbb::concurrent_vector< T, A >::clear(), cfg::MAXPOINTS, and tbb::parallel_for().

Referenced by main().

                                    {
    points.clear();

    // In the buffered version, a temporary storage for as much as grainSize elements 
    // is allocated inside the body. Since auto_partitioner may increase effective
    // range size which would cause a crash, simple partitioner has to be used.
    tbb::parallel_for(range_t(0, cfg::MAXPOINTS, BodyType::grainSize),
                      BodyType(points), tbb::simple_partitioner());
}

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 569 of file convex_hull_bench.cpp.

References util::gettime(), cfg::NUM_THREADS_END, cfg::NUM_THREADS_START, util::ParseInputArgs(), quickhull(), util::time_diff(), and util::WriteResults().

                                 {
    util::ParseInputArgs(argc, argv);

    pointVec_t      points;
    pointVec_t      hull;
    int             nthreads;
    util::my_time_t tm_init, tm_start, tm_end;
    pointVec_t      tmp_points;

#if USECONCVEC
    std::cout << "Starting TBB unbufferred push_back version of QUICK HULL algorithm" << std::endl;
#else
    std::cout << "Starting STL locked unbufferred push_back version of QUICK HULL algorithm" << std::endl;
#endif // USECONCVEC

    for(nthreads=cfg::NUM_THREADS_START; nthreads<=cfg::NUM_THREADS_END;
        ++nthreads) {
        tbb::task_scheduler_init init(nthreads);
#if INIT_ONCE
        if(nthreads==cfg::NUM_THREADS_START) {
            tm_init = util::gettime();
            initialize<FillRNDPointsVector>(points);
        }
        else /* timing generation for stats, but use original data set */ {
            tm_init = util::gettime();
            initialize<FillRNDPointsVector>(tmp_points);
        }
#else
        tm_init = util::gettime();
        initialize<FillRNDPointsVector>(points);
#endif // INIT_ONCE
        tm_start = util::gettime();
        quickhull(points, hull, false);
        tm_end = util::gettime();

        util::WriteResults(nthreads, util::time_diff(tm_init, tm_start),
            util::time_diff(tm_start, tm_end));
    }

#if USECONCVEC 
    std::cout << "Starting TBB bufferred version of QUICK HULL algorithm" << std::endl;
#else
    std::cout << "Starting STL locked bufferred version of QUICK HULL algorithm" << std::endl;
#endif

    for(nthreads=cfg::NUM_THREADS_START; nthreads<=cfg::NUM_THREADS_END;
        ++nthreads) {
        tbb::task_scheduler_init init(nthreads);
#if INIT_ONCE
        if(nthreads==cfg::NUM_THREADS_START) {
            tm_init = util::gettime();
            initialize<FillRNDPointsVector_buf>(points);
        }
        else /* timing generation for stats, but use original data set */ {
            tm_init = util::gettime();
            initialize<FillRNDPointsVector_buf>(tmp_points);
        }
#else
        tm_init = util::gettime();
        initialize<FillRNDPointsVector_buf>(points);
#endif // INIT_ONCE
        tm_start = util::gettime();
        quickhull(points, hull, true);
        tm_end = util::gettime();

        util::WriteResults(nthreads, util::time_diff(tm_init, tm_start),
            util::time_diff(tm_start, tm_end));
    }    

    return 0;
}

void quickhull	(	const pointVec_t &	points,
		pointVec_t &	hull,
		bool	buffered
	)

Definition at line 552 of file convex_hull_bench.cpp.

References appendVector(), tbb::concurrent_vector< T, A >::clear(), divide_and_conquer(), and tbb::concurrent_vector< T, A >::end().

Referenced by main().

                                                                          {
    hull.clear();

    point_t p_maxx = extremum<FindXExtremum::maxX>(points);
    point_t p_minx = extremum<FindXExtremum::minX>(points);

    pointVec_t H;

    divide_and_conquer(points, hull, p_maxx, p_minx, buffered);
    divide_and_conquer(points, H, p_minx, p_maxx, buffered);
#if USECONCVEC
    appendVector(H, hull);
#else // STD::VECTOR
    hull.insert(hull.end(), H.begin(), H.end());
#endif // USECONCVEC
}

Classes

Defines

Typedefs

Functions

Define Documentation

Typedef Documentation

Function Documentation