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