Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
math.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/common/math.hpp
3  *
4  * Part of Project Thrill - http://project-thrill.org
5  *
6  * Copyright (C) 2013-2015 Timo Bingmann <[email protected]>
7  * Copyright (C) 2017 Tim Zeitz <[email protected]>
8  *
9  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
10  ******************************************************************************/
11 
12 #pragma once
13 #ifndef THRILL_COMMON_MATH_HEADER
14 #define THRILL_COMMON_MATH_HEADER
15 
16 #include <algorithm>
17 #include <cassert>
18 #include <cmath>
19 #include <limits>
20 #include <ostream>
21 
22 namespace thrill {
23 namespace common {
24 
25 /******************************************************************************/
26 
27 //! Add x + y but truncate result upwards such that it fits into original
28 //! datatype
29 template <typename IntegerType, unsigned bits = (8 * sizeof(IntegerType))>
30 static inline
31 IntegerType AddTruncToType(const IntegerType& a, const IntegerType& b) {
32  size_t s = static_cast<size_t>(a) + static_cast<size_t>(b);
33  if (s >= (size_t(1) << bits))
34  s = (size_t(1) << bits) - 1;
35  return static_cast<IntegerType>(s);
36 }
37 
38 /******************************************************************************/
39 
40 //! represents a 1 dimensional range (interval) [begin,end)
41 class Range
42 {
43 public:
44  Range() = default;
45  Range(size_t begin, size_t end) : begin(begin), end(end) { }
46 
47  static Range Invalid() {
50  }
51 
52  //! \name Attributes
53  //! \{
54 
55  //! begin index
56  size_t begin = 0;
57  //! end index
58  size_t end = 0;
59 
60  //! \}
61 
62  //! size of range
63  size_t size() const { return end - begin; }
64 
65  //! range is empty (begin == end)
66  bool IsEmpty() const { return begin == end; }
67  //! valid non-empty range (begin < end)
68  bool IsValid() const { return begin < end; }
69 
70  //! swap boundaries, making a valid range invalid.
71  void Swap() { std::swap(begin, end); }
72 
73  //! return shifted Range
74  Range operator + (const size_t& shift) const {
75  return Range(begin + shift, end + shift);
76  }
77 
78  //! true if the Range contains x
79  bool Contains(size_t x) const {
80  return x >= begin && x < end;
81  }
82 
83  //! calculate a partition range [begin,end) by taking the current Range
84  //! splitting it into p parts and taking the i-th one.
85  Range Partition(size_t i, size_t parts) const {
86  assert(i < parts);
87  return Range(CalculateBeginOfPart(i, parts),
88  CalculateBeginOfPart(i + 1, parts));
89  }
90 
91  size_t CalculateBeginOfPart(size_t i, size_t parts) const {
92  assert(i <= parts);
93  return (i * size() + parts - 1) / parts + begin;
94  }
95 
96  //! calculate the partition (ranging from 0 to parts - 1) into which index
97  //! falls
98  size_t FindPartition(size_t index, size_t parts) const {
99  return ((index - begin) * parts) / size();
100  }
101 
102  //! ostream-able
103  friend std ::ostream& operator << (std::ostream& os, const Range& r) {
104  return os << '[' << r.begin << ',' << r.end << ')';
105  }
106 };
107 
108 //! given a global range [0,global_size) and p PEs to split the range, calculate
109 //! the [local_begin,local_end) index range assigned to the PE i.
111  size_t global_size, size_t p, size_t i) {
112  return Range(0, global_size).Partition(i, p);
113 }
114 
115 static inline size_t CalculatePartition(size_t global_size, size_t p, size_t k) {
116  size_t partition = k * p / global_size;
117  assert(k >= CalculateLocalRange(global_size, p, partition).begin);
118  assert(k < CalculateLocalRange(global_size, p, partition).end);
119  return partition;
120 }
121 
122 /******************************************************************************/
123 
124 /*!
125  * Number of rounds in Perfect Matching (1-Factor).
126  */
127 static inline size_t CalcOneFactorSize(size_t n) {
128  return n % 2 == 0 ? n - 1 : n;
129 }
130 
131 /*!
132  * Calculate a Perfect Matching (1-Factor) on a Complete Graph. Used by
133  * collective network algorithms.
134  *
135  * \param r round [0..n-1) of matching
136  * \param p rank of this processor 0..n-1
137  * \param n number of processors (graph size)
138  * \return peer processor in this round
139  */
140 static inline size_t CalcOneFactorPeer(size_t r, size_t p, size_t n) {
141  assert(r < CalcOneFactorSize(n));
142  assert(p < n);
143 
144  if (n % 2 == 0) {
145  // p is even
146  size_t idle = (r * n / 2) % (n - 1);
147  if (p == n - 1)
148  return idle;
149  else if (p == idle)
150  return n - 1;
151  else
152  return (r - p + n - 1) % (n - 1);
153  }
154  else {
155  // p is odd
156  return (r - p + n) % n;
157  }
158 }
159 
160 /******************************************************************************/
161 
162 } // namespace common
163 } // namespace thrill
164 
165 #endif // !THRILL_COMMON_MATH_HEADER
166 
167 /******************************************************************************/
size_t FindPartition(size_t index, size_t parts) const
Definition: math.hpp:98
bool IsEmpty() const
range is empty (begin == end)
Definition: math.hpp:66
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.hpp:226
bool IsValid() const
valid non-empty range (begin < end)
Definition: math.hpp:68
size_t CalculateBeginOfPart(size_t i, size_t parts) const
Definition: math.hpp:91
Range(size_t begin, size_t end)
Definition: math.hpp:45
represents a 1 dimensional range (interval) [begin,end)
Definition: math.hpp:41
static Range Invalid()
Definition: math.hpp:47
static size_t CalcOneFactorPeer(size_t r, size_t p, size_t n)
Calculate a Perfect Matching (1-Factor) on a Complete Graph.
Definition: math.hpp:140
friend std::ostream & operator<<(std::ostream &os, const Range &r)
ostream-able
Definition: math.hpp:103
static Range CalculateLocalRange(size_t global_size, size_t p, size_t i)
Definition: math.hpp:110
bool Contains(size_t x) const
true if the Range contains x
Definition: math.hpp:79
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
list x
Definition: gen_data.py:39
size_t end
end index
Definition: math.hpp:58
static IntegerType AddTruncToType(const IntegerType &a, const IntegerType &b)
Definition: math.hpp:31
static size_t CalculatePartition(size_t global_size, size_t p, size_t k)
Definition: math.hpp:115
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.hpp:217
static size_t CalcOneFactorSize(size_t n)
Number of rounds in Perfect Matching (1-Factor).
Definition: math.hpp:127
Range Partition(size_t i, size_t parts) const
Definition: math.hpp:85
Range operator+(const size_t &shift) const
return shifted Range
Definition: math.hpp:74
size_t begin
begin index
Definition: math.hpp:56
void Swap()
swap boundaries, making a valid range invalid.
Definition: math.hpp:71
size_t size() const
size of range
Definition: math.hpp:63