| 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 |
| 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 |
| 81 |
point() {} |
| 82 |
point(T _x, T _y) : x(_x), y(_y) {} |
| 83 |
}; |
| 84 |
|
| 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; |
| 92 |
rng(std::size_t seed) : my_fast_random(seed) {} |
| 93 |
unsigned short operator()() { |
| 94 |
return my_fast_random.get(); |
| 95 |
} |
| 96 |
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> |
| 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; |
| 134 |
edge(Index _p1, Index _p2) : start(_p1), end(_p2){}; |
| 135 |
}; |
| 136 |
|
| 137 |
template <typename T> |
| 138 |
std::ostream& operator<<(std::ostream& _ostr, point<T> _p) { |
| 139 |
return _ostr << '(' << _p.x << ',' << _p.y << ')'; |
| 140 |
} |
| 141 |
|
| 142 |
template <typename T> |
| 143 |
std::istream& operator>>(std::istream& _istr, point<T> _p) { |
| 144 |
return _istr >> _p.x >> _p.y; |
| 145 |
} |
| 146 |
|
| 147 |
template <typename T> |
| 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> |
| 153 |
bool operator!=(point<T> p1, point<T> p2) { |
| 154 |
return !(p1 == p2); |
| 155 |
} |
| 156 |
|
| 157 |
template <typename T> |
| 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 |
|
| 165 |
my_time_t gettime() { |
| 166 |
return oneapi::tbb::tick_count::now(); |
| 167 |
} |
| 168 |
|
| 169 |
double time_diff(my_time_t start, my_time_t end) { |
| 170 |
return (end - start).seconds(); |
| 171 |
} |
| 172 |
|
| 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 */ |