xgboost
threading_utils.h
Go to the documentation of this file.
1 
6 #ifndef XGBOOST_COMMON_THREADING_UTILS_H_
7 #define XGBOOST_COMMON_THREADING_UTILS_H_
8 
9 #include <vector>
10 #include <algorithm>
11 
12 namespace xgboost {
13 namespace common {
14 
15 // Represent simple range of indexes [begin, end)
16 // Inspired by tbb::blocked_range
17 class Range1d {
18  public:
19  Range1d(size_t begin, size_t end): begin_(begin), end_(end) {
20  CHECK_LT(begin, end);
21  }
22 
23  size_t begin() {
24  return begin_;
25  }
26 
27  size_t end() {
28  return end_;
29  }
30 
31  private:
32  size_t begin_;
33  size_t end_;
34 };
35 
36 
37 // Split 2d space to balanced blocks
38 // Implementation of the class is inspired by tbb::blocked_range2d
39 // However, TBB provides only (n x m) 2d range (matrix) separated by blocks. Example:
40 // [ 1,2,3 ]
41 // [ 4,5,6 ]
42 // [ 7,8,9 ]
43 // But the class is able to work with different sizes in each 'row'. Example:
44 // [ 1,2 ]
45 // [ 3,4,5,6 ]
46 // [ 7,8,9]
47 // If grain_size is 2: It produces following blocks:
48 // [1,2], [3,4], [5,6], [7,8], [9]
49 // The class helps to process data in several tree nodes (non-balanced usually) in parallel
50 // Using nested parallelism (by nodes and by data in each node)
51 // it helps to improve CPU resources utilization
53  public:
54  // Example of space:
55  // [ 1,2 ]
56  // [ 3,4,5,6 ]
57  // [ 7,8,9]
58  // BlockedSpace2d will create following blocks (tasks) if grain_size=2:
59  // 1-block: first_dimension = 0, range of indexes in a 'row' = [0,2) (includes [1,2] values)
60  // 2-block: first_dimension = 1, range of indexes in a 'row' = [0,2) (includes [3,4] values)
61  // 3-block: first_dimension = 1, range of indexes in a 'row' = [2,4) (includes [5,6] values)
62  // 4-block: first_dimension = 2, range of indexes in a 'row' = [0,2) (includes [7,8] values)
63  // 5-block: first_dimension = 2, range of indexes in a 'row' = [2,3) (includes [9] values)
64  // Arguments:
65  // dim1 - size of the first dimension in the space
66  // getter_size_dim2 - functor to get the second dimensions for each 'row' by row-index
67  // grain_size - max size of produced blocks
68  template<typename Func>
69  BlockedSpace2d(size_t dim1, Func getter_size_dim2, size_t grain_size) {
70  for (size_t i = 0; i < dim1; ++i) {
71  const size_t size = getter_size_dim2(i);
72  const size_t n_blocks = size/grain_size + !!(size % grain_size);
73  for (size_t iblock = 0; iblock < n_blocks; ++iblock) {
74  const size_t begin = iblock * grain_size;
75  const size_t end = std::min(begin + grain_size, size);
76  AddBlock(i, begin, end);
77  }
78  }
79  }
80 
81  // Amount of blocks(tasks) in a space
82  size_t Size() const {
83  return ranges_.size();
84  }
85 
86  // get index of the first dimension of i-th block(task)
87  size_t GetFirstDimension(size_t i) const {
88  CHECK_LT(i, first_dimension_.size());
89  return first_dimension_[i];
90  }
91 
92  // get a range of indexes for the second dimension of i-th block(task)
93  Range1d GetRange(size_t i) const {
94  CHECK_LT(i, ranges_.size());
95  return ranges_[i];
96  }
97 
98  private:
99  void AddBlock(size_t first_dimension, size_t begin, size_t end) {
100  first_dimension_.push_back(first_dimension);
101  ranges_.emplace_back(begin, end);
102  }
103 
104  std::vector<Range1d> ranges_;
105  std::vector<size_t> first_dimension_;
106 };
107 
108 
109 // Wrapper to implement nested parallelism with simple omp parallel for
110 template<typename Func>
111 void ParallelFor2d(const BlockedSpace2d& space, const int nthreads, Func func) {
112  const size_t num_blocks_in_space = space.Size();
113 
114  #pragma omp parallel num_threads(nthreads)
115  {
116  size_t tid = omp_get_thread_num();
117  size_t chunck_size = num_blocks_in_space / nthreads + !!(num_blocks_in_space % nthreads);
118 
119  size_t begin = chunck_size * tid;
120  size_t end = std::min(begin + chunck_size, num_blocks_in_space);
121  for (auto i = begin; i < end; i++) {
122  func(space.GetFirstDimension(i), space.GetRange(i));
123  }
124  }
125 }
126 
127 } // namespace common
128 } // namespace xgboost
129 
130 #endif // XGBOOST_COMMON_THREADING_UTILS_H_
void ParallelFor2d(const BlockedSpace2d &space, const int nthreads, Func func)
Definition: threading_utils.h:111
BlockedSpace2d(size_t dim1, Func getter_size_dim2, size_t grain_size)
Definition: threading_utils.h:69
size_t GetFirstDimension(size_t i) const
Definition: threading_utils.h:87
size_t Size() const
Definition: threading_utils.h:82
Definition: threading_utils.h:17
size_t begin()
Definition: threading_utils.h:23
namespace of xgboost
Definition: base.h:102
Definition: threading_utils.h:52
size_t end()
Definition: threading_utils.h:27
Range1d GetRange(size_t i) const
Definition: threading_utils.h:93
Range1d(size_t begin, size_t end)
Definition: threading_utils.h:19