examples/parallel_reduce/convex_hull/convex_hull.h

   1 /*
   2     Copyright (c) 2005-2019 Intel Corporation
   3
   4     Licensed under the Apache License, Version 2.0 (the "License");
   5     you may not use this file except in compliance with the License.
   6     You may obtain a copy of the License at
   7
   8         http://www.apache.org/licenses/LICENSE-2.0
   9
  10     Unless required by applicable law or agreed to in writing, software
  11     distributed under the License is distributed on an "AS IS" BASIS,
  12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13     See the License for the specific language governing permissions and
  14     limitations under the License.
  15 */
  16
  17 #ifndef __CONVEX_HULL_H__
  18 #define __CONVEX_HULL_H__
  19
  20 #include <cassert>
  21 #include <cstdlib>
  22 #include <iostream>
  23 #include <iomanip>
  24 #include <sstream>
  25 #include <vector>
  26 #include <string>
  27 #include <cstring>
  28 #include <algorithm>
  29 #include <functional>
  30 #include <climits>
  31 #include "tbb/tick_count.h"
  32 #include "tbb/task_scheduler_init.h"
  33 #include "../../common/utility/utility.h"
  34 #include "../../common/utility/fast_random.h"
  35
  36 using namespace std;
  37
  38 namespace cfg {
  39     // convex hull problem user set parameters
  40     long   numberOfPoints  = 5000000; // problem size
  41     utility::thread_number_range threads(tbb::task_scheduler_init::default_num_threads);
  42
  43     // convex hull grain sizes for 3 subproblems. Be sure 16*GS < 512Kb
  44     const size_t generateGrainSize = 25000;
  45     const size_t findExtremumGrainSize  = 25000;
  46     const size_t divideGrainSize   = 25000;
  47 };
  48
  49 namespace util {
  50     bool                     silent = false;
  51     bool                     verbose = false;
  52     vector<string> OUTPUT;
  53
  54     // utility functionality
  55     void ParseInputArgs(int argc, char* argv[]) {
  56         utility::parse_cli_arguments(
  57                 argc,argv,
  58                 utility::cli_argument_pack()
  59                     //"-h" option for displaying help is present implicitly
  60                     .positional_arg(cfg::threads,"n-of-threads",utility::thread_number_range_desc)
  61                     .positional_arg(cfg::numberOfPoints,"n-of-points","number of points")
  62                     .arg(silent,"silent","no output except elapsed time")
  63                     .arg(verbose,"verbose","turns verbose ON")
  64         );
  65         //disabling verbose if silent is specified
  66         if (silent) verbose = false;;
  67     }
  68
  69     template <typename T>
  70     struct point {
  71         T x;
  72         T y;
  73         //According to subparagraph 4 of paragraph 12.6.2 "Initializing bases and members" [class.base.init]
  74         //of ANSI-ISO-IEC C++ 2003 standard, POD members will _not_ be initialized if they are not mentioned
  75         //in the base-member initializer list.
  76
  77         //For more details why this needed please see comment in FillRNDPointsVector_buf
  78         point() {}
  79         point(T _x, T _y) : x(_x), y(_y) {}
  80     };
  81
  82     std::ostream& operator<< (std::ostream& o, point<double> const& p) {
  83         return o << "(" << p.x << "," << p.y << ")";
  84     }
  85
  86     struct rng {
  87         static const size_t max_rand = USHRT_MAX;
  88         utility::FastRandom my_fast_random;
  89         rng (size_t seed):my_fast_random(seed) {}
  90         unsigned short operator()(){return my_fast_random.get();}
  91         unsigned short operator()(size_t& seed){return my_fast_random.get(seed);}
  92     };
  93
  94
  95     template < typename T ,typename rng_functor_type>
  96     point<T> GenerateRNDPoint(size_t& count, rng_functor_type random, size_t rand_max) {
  97         /* generates random points on 2D plane so that the cluster
  98         is somewhat circle shaped */
  99         const size_t maxsize=500;
 100         T x = random()*2.0/(double)rand_max - 1;
 101         T y = random()*2.0/(double)rand_max - 1;
 102         T r = (x*x + y*y);
 103         if(r>1) {
 104             count++;
 105             if(count>10) {
 106                 if (random()/(double)rand_max > 0.5)
 107                     x /= r;
 108                 if (random()/(double)rand_max > 0.5)
 109                     y /= r;
 110                 count = 0;
 111             }
 112             else {
 113                 x /= r;
 114                 y /= r;
 115             }
 116         }
 117
 118         x = (x+1)*0.5*maxsize;
 119         y = (y+1)*0.5*maxsize;
 120
 121         return point<T>(x,y);
 122     }
 123
 124     template <typename Index>
 125     struct edge {
 126         Index start;
 127         Index end;
 128         edge(Index _p1, Index _p2) : start(_p1), end(_p2) {};
 129     };
 130
 131     template <typename T>
 132     ostream& operator <<(ostream& _ostr, point<T> _p) {
 133         return _ostr << '(' << _p.x << ',' << _p.y << ')';
 134     }
 135
 136     template <typename T>
 137     istream& operator >>(istream& _istr, point<T> _p) {
 138         return _istr >> _p.x >> _p.y;
 139     }
 140
 141     template <typename T>
 142     bool operator ==(point<T> p1, point<T> p2) {
 143         return (p1.x == p2.x && p1.y == p2.y);
 144     }
 145
 146     template <typename T>
 147     bool operator !=(point<T> p1, point<T> p2) {
 148         return !(p1 == p2);
 149     }
 150
 151     template <typename T>
 152     double cross_product(const point<T>& start, const point<T>& end1, const point<T>& end2) {
 153         return ((end1.x-start.x)*(end2.y-start.y)-(end2.x-start.x)*(end1.y-start.y));
 154     }
 155
 156     // Timing functions are based on TBB to always obtain wall-clock time
 157     typedef tbb::tick_count my_time_t;
 158
 159     my_time_t gettime() {
 160         return tbb::tick_count::now();
 161     }
 162
 163     double time_diff(my_time_t start, my_time_t end) {
 164         return (end-start).seconds();
 165     }
 166
 167     void WriteResults(int nthreads, double initTime, double calcTime) {
 168         if(verbose) {
 169             cout << " Step by step hull construction:" << endl;
 170             for(size_t i = 0; i < OUTPUT.size(); ++i)
 171                 cout << OUTPUT[i] << endl;
 172         }
 173         if (!silent){
 174             cout
 175                 << "  Number of nodes:" << cfg::numberOfPoints
 176                 << "  Number of threads:" << nthreads
 177                 << "  Initialization time:" << setw(10) << setprecision(3) << initTime
 178                 << "  Calculation time:" << setw(10) << setprecision(3) << calcTime
 179                 << endl;
 180         }
 181     }
 182 };
 183
 184 #endif // __CONVEX_HULL_H__