Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
TensorDeviceThreadPool.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2014 Benoit Steiner <benoit.steiner.goog@gmail.com>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#if defined(EIGEN_USE_THREADS) && !defined(EIGEN_TENSOR_TENSOR_DEVICE_THREAD_POOL_H)
12#define EIGEN_TENSOR_TENSOR_DEVICE_THREAD_POOL_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19// An abstract interface to a device specific memory allocator.
20class Allocator {
21 public:
22 virtual ~Allocator() = default;
23 virtual void* allocate(size_t num_bytes) const = 0;
24 virtual void deallocate(void* buffer) const = 0;
25};
26
27// Build a thread pool device on top of an existing pool of threads.
28struct ThreadPoolDevice {
29 // The ownership of the thread pool remains with the caller.
30 ThreadPoolDevice(ThreadPoolInterface* pool, int num_cores, Allocator* allocator = nullptr)
31 : pool_(pool), num_threads_(num_cores), allocator_(allocator) {}
32
33 EIGEN_STRONG_INLINE void* allocate(size_t num_bytes) const {
34 return allocator_ ? allocator_->allocate(num_bytes) : internal::aligned_malloc(num_bytes);
35 }
36
37 EIGEN_STRONG_INLINE void deallocate(void* buffer) const {
38 if (allocator_) {
39 allocator_->deallocate(buffer);
40 } else {
41 internal::aligned_free(buffer);
42 }
43 }
44
45 EIGEN_STRONG_INLINE void* allocate_temp(size_t num_bytes) const { return allocate(num_bytes); }
46
47 EIGEN_STRONG_INLINE void deallocate_temp(void* buffer) const { deallocate(buffer); }
48
49 template <typename Type>
50 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Type get(Type data) const {
51 return data;
52 }
53
54 EIGEN_STRONG_INLINE void memcpy(void* dst, const void* src, size_t n) const {
55#ifdef __ANDROID__
56 ::memcpy(dst, src, n);
57#else
58 // TODO(rmlarsen): Align blocks on cache lines.
59 const size_t kMinBlockSize = 32768;
60 // Pure memory op (zero compute) — the cost model's bandwidth saturation
61 // cap will limit threads appropriately.
62 const size_t num_threads = CostModel::numThreads(n, TensorOpCost(1.0, 1.0, 0), static_cast<int>(numThreads()));
63 if (n <= kMinBlockSize || num_threads < 2) {
64 ::memcpy(dst, src, n);
65 } else {
66 const char* src_ptr = static_cast<const char*>(src);
67 char* dst_ptr = static_cast<char*>(dst);
68 const size_t blocksize = (n + (num_threads - 1)) / num_threads;
69 Barrier barrier(static_cast<int>(num_threads - 1));
70 // Schedule blocks 1..num_threads-1 on worker threads.
71 for (size_t i = 1; i < num_threads; ++i) {
72 pool_->Schedule([n, i, src_ptr, dst_ptr, blocksize, &barrier] {
73 ::memcpy(dst_ptr + i * blocksize, src_ptr + i * blocksize, numext::mini(blocksize, n - (i * blocksize)));
74 barrier.Notify();
75 });
76 }
77 // Run the first block on the calling thread.
78 ::memcpy(dst_ptr, src_ptr, blocksize);
79 barrier.Wait();
80 }
81#endif
82 }
83 EIGEN_STRONG_INLINE void memcpyHostToDevice(void* dst, const void* src, size_t n) const { memcpy(dst, src, n); }
84 EIGEN_STRONG_INLINE void memcpyDeviceToHost(void* dst, const void* src, size_t n) const { memcpy(dst, src, n); }
85
86 EIGEN_STRONG_INLINE void memset(void* buffer, int c, size_t n) const { ::memset(buffer, c, n); }
87
88 template <typename T>
89 EIGEN_STRONG_INLINE void fill(T* begin, T* end, const T& value) const {
90 std::fill(begin, end, value);
91 }
92
93 EIGEN_STRONG_INLINE int numThreads() const { return num_threads_; }
94
95 // Number of threads available in the underlying thread pool. This number can
96 // be different from the value returned by numThreads().
97 EIGEN_STRONG_INLINE int numThreadsInPool() const { return pool_->NumThreads(); }
98
99 EIGEN_STRONG_INLINE size_t firstLevelCacheSize() const { return l1CacheSize(); }
100
101 EIGEN_STRONG_INLINE size_t lastLevelCacheSize() const {
102 // The l3 cache size is shared between all the cores.
103 return l3CacheSize() / num_threads_;
104 }
105
106 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void synchronize() const {
107 // Nothing. Threadpool device operations are synchronous.
108 }
109
110 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE int majorDeviceVersion() const {
111 // Should return an enum that encodes the ISA supported by the CPU
112 return 1;
113 }
114
115 // TODO(rmlarsen): Remove this deprecated interface when all users have been converted.
116 template <class Function, class... Args>
117 EIGEN_STRONG_INLINE void enqueueNoNotification(Function&& f, Args&&... args) const {
118 enqueue(std::forward<Function>(f), std::forward<Args>(args)...);
119 }
120
121 template <class Function, class... Args>
122 EIGEN_STRONG_INLINE void enqueue(Function&& f, Args&&... args) const {
123#if EIGEN_COMP_CXXVER >= 20
124 // C++20 pack-expansion init capture decay-copies args into a lambda
125 // small enough to fit in std::function's SBO for typical arg counts.
126 pool_->Schedule([f = std::forward<Function>(f), ... args = std::forward<Args>(args)]() mutable { f(args...); });
127#else
128 // Pre-C++20 fallback: std::bind decay-copies the arguments so they
129 // outlive the deferred call even when the caller passes temporaries.
130 // The closure exceeds std::function's SBO and forces a heap allocation
131 // that the C++20 path above avoids.
132 pool_->Schedule(std::bind(std::forward<Function>(f), std::forward<Args>(args)...));
133#endif
134 }
135
136 // A nullary function is scheduled as is. This is a separate overload because
137 // a runtime branch would also instantiate Schedule(f) for functions taking args.
138 template <class Function>
139 EIGEN_STRONG_INLINE void enqueue(Function&& f) const {
140 pool_->Schedule(std::forward<Function>(f));
141 }
142
143 // Returns a logical thread index between 0 and pool_->NumThreads() - 1 if
144 // called from one of the threads in pool_. Returns -1 otherwise.
145 EIGEN_STRONG_INLINE int currentThreadId() const { return pool_->CurrentThreadId(); }
146
147 // WARNING: This function is synchronous and will block the calling thread.
148 //
149 // Synchronous parallelFor executes f with [0, n) arguments in parallel and
150 // waits for completion. F accepts a half-open interval [first, last). Block
151 // size is chosen based on the iteration cost and resulting parallel
152 // efficiency. If block_align is not nullptr, it is called to round up the
153 // block size.
154 void parallelFor(Index n, const TensorOpCost& cost, std::function<Index(Index)> block_align,
155 std::function<void(Index, Index)> f) const {
156 if (EIGEN_PREDICT_FALSE(n <= 0)) {
157 return;
158 }
159 // Compute small problems directly in the caller thread.
160 if (n == 1 || numThreads() == 1 || CostModel::numThreads(n, cost, static_cast<int>(numThreads())) == 1) {
161 f(0, n);
162 return;
163 }
164
165 // Compute block size and total count of blocks.
166 ParallelForBlock block = CalculateParallelForBlock(n, cost, block_align);
167
168 // Recursively divide size into halves until we reach block_size.
169 // Division code rounds mid to block_size, so we are guaranteed to get
170 // block_count leaves that do actual computations.
171 Barrier barrier(static_cast<unsigned int>(block.count));
172 if (block.count <= numThreads()) {
173 // Avoid a thread hop by running the root of the tree and one block on the
174 // main thread.
175 handleRange(0, n, block.size, &barrier, pool_, f);
176 } else {
177 // Execute the root in the thread pool to avoid running work on more than
178 // numThreads() threads.
179 pool_->Schedule([this, n, &block, &barrier, &f]() { handleRange(0, n, block.size, &barrier, pool_, f); });
180 }
181
182 barrier.Wait();
183 }
184
185 // Convenience wrapper for parallelFor that does not align blocks.
186 void parallelFor(Index n, const TensorOpCost& cost, std::function<void(Index, Index)> f) const {
187 parallelFor(n, cost, nullptr, std::move(f));
188 }
189
190 // WARNING: This function is asynchronous and will not block the calling thread.
191 //
192 // Asynchronous parallelFor executes f with [0, n) arguments in parallel
193 // without waiting for completion. When the last block finished, it will call
194 // 'done' callback. F accepts a half-open interval [first, last). Block size
195 // is chosen based on the iteration cost and resulting parallel efficiency. If
196 // block_align is not nullptr, it is called to round up the block size.
197 void parallelForAsync(Index n, const TensorOpCost& cost, std::function<Index(Index)> block_align,
198 std::function<void(Index, Index)> f, std::function<void()> done) const {
199 // Compute small problems directly in the caller thread.
200 if (n <= 1 || numThreads() == 1 || CostModel::numThreads(n, cost, static_cast<int>(numThreads())) == 1) {
201 f(0, n);
202 done();
203 return;
204 }
205
206 // Compute block size and total count of blocks.
207 ParallelForBlock block = CalculateParallelForBlock(n, cost, block_align);
208
209 ParallelForAsyncContext* const ctx =
210 new ParallelForAsyncContext(block.count, block.size, pool_, std::move(f), std::move(done));
211
212 if (block.count <= numThreads()) {
213 // Avoid a thread hop by running the root of the tree and one block on the
214 // main thread.
215 handleRangeAsync(ctx, 0, n);
216 } else {
217 // Execute the root in the thread pool to avoid running work on more than
218 // numThreads() threads.
219 pool_->Schedule([ctx, n]() { handleRangeAsync(ctx, 0, n); });
220 }
221 }
222
223 // Convenience wrapper for parallelForAsync that does not align blocks.
224 void parallelForAsync(Index n, const TensorOpCost& cost, std::function<void(Index, Index)> f,
225 std::function<void()> done) const {
226 parallelForAsync(n, cost, nullptr, std::move(f), std::move(done));
227 }
228
229 // Thread pool accessor.
230 ThreadPoolInterface* getPool() const { return pool_; }
231
232 // Allocator accessor.
233 Allocator* allocator() const { return allocator_; }
234
235 private:
236 using CostModel = TensorCostModel<ThreadPoolDevice>;
237
238 static void handleRange(Index firstIdx, Index lastIdx, Index granularity, Barrier* barrier, ThreadPoolInterface* pool,
239 const std::function<void(Index, Index)>& f) {
240 while (lastIdx - firstIdx > granularity) {
241 // Split into halves and schedule the second half on a different thread.
242 const Index midIdx = firstIdx + numext::div_ceil((lastIdx - firstIdx) / 2, granularity) * granularity;
243 pool->Schedule([=, &f]() { handleRange(midIdx, lastIdx, granularity, barrier, pool, f); });
244 lastIdx = midIdx;
245 }
246 // Single block or less, execute directly.
247 f(firstIdx, lastIdx);
248 barrier->Notify();
249 }
250
251 // For parallelForAsync we must keep passed in closures on the heap, and
252 // delete them only after `done` callback finished.
253 struct ParallelForAsyncContext {
254 ParallelForAsyncContext(Index block_count, Index block_size, ThreadPoolInterface* p,
255 std::function<void(Index, Index)> block_f, std::function<void()> done_callback)
256 : count(block_count), granularity(block_size), pool(p), f(std::move(block_f)), done(std::move(done_callback)) {}
257 ~ParallelForAsyncContext() { done(); }
258
259 std::atomic<Index> count;
260 Index granularity;
261 ThreadPoolInterface* pool;
262 std::function<void(Index, Index)> f;
263 std::function<void()> done;
264 };
265
266 // Async counterpart of handleRange: no Barrier, deletes the heap-allocated
267 // context once the final block has run.
268 static void handleRangeAsync(ParallelForAsyncContext* ctx, Index firstIdx, Index lastIdx) {
269 while (lastIdx - firstIdx > ctx->granularity) {
270 const Index midIdx = firstIdx + numext::div_ceil((lastIdx - firstIdx) / 2, ctx->granularity) * ctx->granularity;
271 ctx->pool->Schedule([ctx, midIdx, lastIdx]() { handleRangeAsync(ctx, midIdx, lastIdx); });
272 lastIdx = midIdx;
273 }
274 ctx->f(firstIdx, lastIdx);
275 if (ctx->count.fetch_sub(1) == 1) delete ctx;
276 }
277
278 struct ParallelForBlock {
279 Index size; // block size
280 Index count; // number of blocks
281 };
282
283 // Calculates block size based on (1) the iteration cost and (2) parallel
284 // efficiency. We want blocks to be not too small to mitigate parallelization
285 // overheads; not too large to mitigate tail effect and potential load
286 // imbalance and we also want number of blocks to be evenly dividable across
287 // threads.
288 ParallelForBlock CalculateParallelForBlock(const Index n, const TensorOpCost& cost,
289 const std::function<Index(Index)>& block_align) const {
290 const double block_size_f = 1.0 / CostModel::taskSize(1, cost);
291 const Index max_oversharding_factor = 4;
292 Index block_size = numext::mini(
293 n, numext::maxi<Index>(numext::div_ceil<Index>(n, max_oversharding_factor * numThreads()), block_size_f));
294 const Index max_block_size = numext::mini(n, 2 * block_size);
295
296 if (block_align) {
297 Index new_block_size = block_align(block_size);
298 eigen_assert(new_block_size >= block_size);
299 block_size = numext::mini(n, new_block_size);
300 }
301
302 Index block_count = numext::div_ceil(n, block_size);
303
304 // Calculate parallel efficiency as fraction of total CPU time used for
305 // computations:
306 double max_efficiency =
307 static_cast<double>(block_count) / (numext::div_ceil<Index>(block_count, numThreads()) * numThreads());
308
309 // Now try to increase block size up to max_block_size as long as it
310 // doesn't decrease parallel efficiency.
311 for (Index prev_block_count = block_count; max_efficiency < 1.0 && prev_block_count > 1;) {
312 // This is the next block size that divides size into a smaller number
313 // of blocks than the current block_size.
314 Index coarser_block_size = numext::div_ceil(n, prev_block_count - 1);
315 if (block_align) {
316 Index new_block_size = block_align(coarser_block_size);
317 eigen_assert(new_block_size >= coarser_block_size);
318 coarser_block_size = numext::mini(n, new_block_size);
319 }
320 if (coarser_block_size > max_block_size) {
321 break; // Reached max block size. Stop.
322 }
323 // Recalculate parallel efficiency.
324 const Index coarser_block_count = numext::div_ceil(n, coarser_block_size);
325 eigen_assert(coarser_block_count < prev_block_count);
326 prev_block_count = coarser_block_count;
327 const double coarser_efficiency = static_cast<double>(coarser_block_count) /
328 (numext::div_ceil<Index>(coarser_block_count, numThreads()) * numThreads());
329 if (coarser_efficiency + 0.01 >= max_efficiency) {
330 // Taking it.
331 block_size = coarser_block_size;
332 block_count = coarser_block_count;
333 if (max_efficiency < coarser_efficiency) {
334 max_efficiency = coarser_efficiency;
335 }
336 }
337 }
338
339 return {block_size, block_count};
340 }
341
342 ThreadPoolInterface* pool_;
343 int num_threads_;
344 Allocator* allocator_;
345};
346
347} // end namespace Eigen
348
349#endif // EIGEN_TENSOR_TENSOR_DEVICE_THREAD_POOL_H
Namespace containing all symbols from the Eigen library.