Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
TensorContractionThreadPool.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#ifndef EIGEN_TENSOR_TENSOR_CONTRACTION_THREAD_POOL_H
12#define EIGEN_TENSOR_TENSOR_CONTRACTION_THREAD_POOL_H
13
14// evaluator for thread pool device
15#ifdef EIGEN_USE_THREADS
16
17// IWYU pragma: private
18#include "./InternalHeaderCheck.h"
19
20namespace Eigen {
21
22template <typename Indices, typename LeftArgType, typename RightArgType, typename OutputKernelType>
23struct TensorEvaluator<const TensorContractionOp<Indices, LeftArgType, RightArgType, OutputKernelType>,
24 ThreadPoolDevice>
25 : public TensorContractionEvaluatorBase<TensorEvaluator<
26 const TensorContractionOp<Indices, LeftArgType, RightArgType, OutputKernelType>, ThreadPoolDevice>> {
27 using Device = ThreadPoolDevice;
28
29 using Self = TensorEvaluator<const TensorContractionOp<Indices, LeftArgType, RightArgType, OutputKernelType>, Device>;
30 using Base = TensorContractionEvaluatorBase<Self>;
31
32 using XprType = TensorContractionOp<Indices, LeftArgType, RightArgType, OutputKernelType>;
33 using Scalar = std::remove_const_t<typename XprType::Scalar>;
34 using Index = typename XprType::Index;
35 using CoeffReturnType = typename XprType::CoeffReturnType;
36 using PacketReturnType = typename PacketType<CoeffReturnType, Device>::type;
37
38 static constexpr int Layout = TensorEvaluator<LeftArgType, Device>::Layout;
39
40 // Most of the code is assuming that both input tensors are ColMajor. If the
41 // inputs are RowMajor, we will "cheat" by swapping the LHS and RHS:
42 // If we want to compute A * B = C, where A is LHS and B is RHS, the code
43 // will pretend B is LHS and A is RHS.
44 using EvalLeftArgType =
45 std::conditional_t<static_cast<int>(Layout) == static_cast<int>(ColMajor), LeftArgType, RightArgType>;
46 using EvalRightArgType =
47 std::conditional_t<static_cast<int>(Layout) == static_cast<int>(ColMajor), RightArgType, LeftArgType>;
48
49 static constexpr int LDims =
50 internal::array_size<typename TensorEvaluator<EvalLeftArgType, Device>::Dimensions>::value;
51 static constexpr int RDims =
52 internal::array_size<typename TensorEvaluator<EvalRightArgType, Device>::Dimensions>::value;
53 static constexpr int ContractDims = internal::array_size<Indices>::value;
54
55 using left_dim_mapper_t = array<Index, LDims>;
56 using right_dim_mapper_t = array<Index, RDims>;
57
58 using contract_t = array<Index, ContractDims>;
59 using left_nocontract_t = array<Index, LDims - ContractDims>;
60 using right_nocontract_t = array<Index, RDims - ContractDims>;
61
62 static constexpr int NumDims = LDims + RDims - 2 * ContractDims;
63
64 using Dimensions = DSizes<Index, NumDims>;
65
66 // typedefs needed in evalTo
67 using LhsScalar = std::remove_const_t<typename EvalLeftArgType::Scalar>;
68 using RhsScalar = std::remove_const_t<typename EvalRightArgType::Scalar>;
69 using Traits = typename internal::gebp_traits<LhsScalar, RhsScalar>;
70
71 using LeftEvaluator = TensorEvaluator<EvalLeftArgType, Device>;
72 using RightEvaluator = TensorEvaluator<EvalRightArgType, Device>;
73
74 TensorEvaluator(const XprType& op, const Device& device) : Base(op, device) {}
75
76 template <int Alignment>
77 void evalProduct(Scalar* buffer) const {
78 evalProductImpl<NoCallback, Alignment>(buffer, NoCallback());
79 }
80
81 template <typename EvalToCallback, int Alignment>
82 void evalProductAsync(Scalar* buffer, EvalToCallback done) const {
83 evalProductImpl<EvalToCallback, Alignment>(buffer, std::move(done));
84 }
85
86 using Base::dispatchContraction;
87
88 template <typename DoneCallback, int Alignment>
89 void evalProductImpl(Scalar* buffer, DoneCallback done) const {
90 // This function computes a lot of heuristics in multiple steps, and it
91 // also has multiple exit points. To keep it sane, readable and all in one
92 // place, sync/async execution decision is made at runtime at the very end.
93 //
94 // (1) In sync mode we allocate Context on the stack, submit computations
95 // to the device thread pool, and block on a barrier until it is
96 // completed.
97 //
98 // (2) In async mode we allocate Context on the heap, and after all tasks
99 // are finished, we call the provided done callback, and delete a
100 // context from the heap.
101 //
102 // (*) EvalParallelContext & EvalShardedByInnerDimContext owns all the state
103 // and temporary buffers, required for executing the tensor contraction.
104 // They are responsible for cleaning it up after contraction is done.
105 static constexpr bool IsEvalInSyncMode = std::is_same<DoneCallback, NoCallback>::value;
106
107 const Index m = this->m_i_size;
108 const Index n = this->m_j_size;
109 const Index k = this->m_k_size;
110 if (m == 0 || n == 0) {
111 EIGEN_IF_CONSTEXPR (!IsEvalInSyncMode) done();
112 return;
113 }
114 if (k == 0) {
115 dispatchContraction(
116 [&](auto lhs_c, auto rhs_c, auto rhs_r) {
117 this->template evalProductSequential<lhs_c(), rhs_c(), rhs_r(), Unaligned>(buffer);
118 },
119 this->m_lhs_inner_dim_contiguous, this->m_rhs_inner_dim_contiguous, this->m_rhs_inner_dim_reordered);
120 EIGEN_IF_CONSTEXPR (!IsEvalInSyncMode) done();
121 return;
122 }
123
124 // Compute a set of algorithm parameters:
125 // - kernel block sizes (bm, bn, bk)
126 // - task grain sizes (number of kernels executed per task: gm, gn)
127 // - number of threads
128 // - sharding by row/column
129 // - parallel packing or first lhs then rhs
130 // and some derived parameters:
131 // - number of tasks (nm, nn, nk)
132 // - number of kernels (nm0, nn0)
133 // Unfortunately, all these parameters are tightly interdependent.
134 // So in some cases we first compute approximate values, then compute other
135 // values based on these approximations and then refine the approximations.
136
137 // There are lots of heuristics here. There is some reasoning behind them,
138 // but ultimately they are just tuned on contraction benchmarks for
139 // different input configurations, thread counts and instruction sets.
140 // So feel free to question any of them.
141
142 // Compute whether we want to shard by row or by column.
143 // This is a first approximation, it will be refined later. Since we don't
144 // know number of threads yet we use 2, because what we are most
145 // interested in at this point is whether it makes sense to use
146 // parallelization at all or not.
147 bool shard_by_col = shardByCol(m, n, 2);
148
149 // First approximation of kernel blocking sizes.
150 // Again, we don't know number of threads yet, so we use 2.
151 Index bm, bn, bk;
152 if (shard_by_col) {
153 internal::TensorContractionBlocking<Scalar, LhsScalar, RhsScalar, Index, internal::ShardByCol> blocking(k, m, n,
154 2);
155 bm = blocking.mc();
156 bn = blocking.nc();
157 bk = blocking.kc();
158 } else {
159 internal::TensorContractionBlocking<Scalar, LhsScalar, RhsScalar, Index, internal::ShardByRow> blocking(k, m, n,
160 2);
161 bm = blocking.mc();
162 bn = blocking.nc();
163 bk = blocking.kc();
164 }
165
166 // Compute optimal number of threads.
167 // Note: we use bk instead of k here because we are interested in amount of
168 // _parallelizable_ computations, and computations are not parallelizable
169 // across k dimension.
170 const TensorOpCost cost = contractionCost(m, n, bm, bn, bk, shard_by_col, false);
171 int num_threads =
172 TensorCostModel<ThreadPoolDevice>::numThreads(static_cast<double>(n) * m, cost, this->m_device.numThreads());
173 int num_threads_by_k = numThreadsInnerDim(m, n, k);
174 if (shardByInnerDim(m, n, k, num_threads, num_threads_by_k)) {
175 // We are in the scenario where it is more effective to shard by the
176 // inner dimension.
177 EIGEN_IF_CONSTEXPR (IsEvalInSyncMode) {
178 EvalShardedByInnerDimContext<DoneCallback> ctx(this, num_threads_by_k, buffer, m, n, k, std::move(done));
179 ctx.template run<Alignment>();
180 } else {
181 auto* ctx =
182 new EvalShardedByInnerDimContext<DoneCallback>(this, num_threads_by_k, buffer, m, n, k, std::move(done));
183 ctx->template runAsync<Alignment>();
184 }
185
186 return;
187 }
188
189 // TODO(dvyukov): this is a stop-gap to prevent regressions while the cost
190 // model is not tuned. Remove this when the cost model is tuned.
191 if (n == 1) num_threads = 1;
192
193 if (num_threads == 1) {
194 dispatchContraction(
195 [&](auto lhs_c, auto rhs_c, auto rhs_r) {
196 this->template evalProductSequential<lhs_c(), rhs_c(), rhs_r(), Unaligned>(buffer);
197 },
198 this->m_lhs_inner_dim_contiguous, this->m_rhs_inner_dim_contiguous, this->m_rhs_inner_dim_reordered);
199 EIGEN_IF_CONSTEXPR (!IsEvalInSyncMode) done();
200 return;
201 }
202
203 // Now that we know number of threads, recalculate sharding and blocking.
204 shard_by_col = shardByCol(m, n, num_threads);
205 if (shard_by_col) {
206 internal::TensorContractionBlocking<Scalar, LhsScalar, RhsScalar, Index, internal::ShardByCol> blocking(
207 k, m, n, num_threads);
208 bm = blocking.mc();
209 bn = blocking.nc();
210 bk = blocking.kc();
211 } else {
212 internal::TensorContractionBlocking<Scalar, LhsScalar, RhsScalar, Index, internal::ShardByRow> blocking(
213 k, m, n, num_threads);
214 bm = blocking.mc();
215 bn = blocking.nc();
216 bk = blocking.kc();
217 }
218
219 // Number of kernels for each dimension.
220 Index nm0 = numext::div_ceil(m, bm);
221 Index nn0 = numext::div_ceil(n, bn);
222 Index nk = numext::div_ceil(k, bk);
223
224 // Calculate task grain size (number of kernels executed per task).
225 // This task size coarsening serves two purposes:
226 // 1. It reduces per-task overheads including synchronization overheads.
227 // 2. It allows to use caches better (reuse the same packed rhs in several
228 // consecutive kernels).
229 Index gm = 1;
230 Index gn = 1;
231 // If we are sharding by column, then we prefer to reduce rows first.
232 if (shard_by_col) {
233 gm = coarsenM(m, n, bm, bn, bk, gn, num_threads, shard_by_col);
234 gn = coarsenN(m, n, bm, bn, bk, gm, num_threads, shard_by_col);
235 } else {
236 gn = coarsenN(m, n, bm, bn, bk, gm, num_threads, shard_by_col);
237 gm = coarsenM(m, n, bm, bn, bk, gn, num_threads, shard_by_col);
238 }
239 // Number of tasks in each dimension.
240 Index nm = numext::div_ceil(nm0, gm);
241 Index nn = numext::div_ceil(nn0, gn);
242
243 // If there is enough concurrency in the sharding dimension, we choose not
244 // to parallelize by the other dimension, and execute all kernels in sync
245 // mode. This reduces parallelism from the nm x nn down to nn
246 // (shard_by_col==true) or nm (shard_by_col==false).
247 const Index sharding_dim_tasks = shard_by_col ? nn : nm;
248 const int num_worker_threads = this->m_device.numThreadsInPool();
249
250 // With small number of threads we want to make sure that we do not reduce
251 // parallelism too much. With large number of threads we trade maximum
252 // parallelism for better memory locality.
253 const float oversharding_factor = num_worker_threads <= 4 ? 8.0
254 : num_worker_threads <= 8 ? 4.0
255 : num_worker_threads <= 16 ? 2.0
256 : num_worker_threads <= 32 ? 1.0
257 : num_worker_threads <= 64 ? 0.8
258 : /* num_worker_threads > 64 */ 0.6;
259
260 const bool parallelize_by_sharding_dim_only = sharding_dim_tasks >= oversharding_factor * num_worker_threads;
261
262 // Last by not least, decide whether we want to issue both lhs and rhs
263 // packing in parallel; or issue lhs packing first, and then issue rhs
264 // packing when lhs packing completes (for !shard_by_col lhs and rhs are
265 // swapped). Parallel packing allows more parallelism (for both packing and
266 // kernels), while sequential packing provides better locality (once
267 // a thread finishes rhs packing it proceed to kernels with that rhs).
268 // First, we are interested in parallel packing if there are few tasks.
269 bool parallel_pack = num_threads >= nm * nn;
270 // Also do parallel packing if all data fits into L2$.
271 if (m * bk * Index(sizeof(LhsScalar)) + n * bk * Index(sizeof(RhsScalar)) <= l2CacheSize() * num_threads)
272 parallel_pack = true;
273 // But don't do it if we will use each rhs only once. Locality seems to be
274 // more important in this case.
275 if ((shard_by_col ? nm : nn) == 1) parallel_pack = false;
276 // Also don't get in the way of parallelize_by_sharding_dim_only
277 // optimization.
278 if (parallelize_by_sharding_dim_only) parallel_pack = false;
279
280 dispatchContraction(
281 [&](auto lhs_c, auto rhs_c, auto rhs_r) {
282 EIGEN_IF_CONSTEXPR (IsEvalInSyncMode) {
283 EvalParallelContext<NoCallback, lhs_c(), rhs_c(), rhs_r()> ctx(
284 this, num_threads, buffer, m, n, k, bm, bn, bk, nm, nn, nk, gm, gn, nm0, nn0, shard_by_col,
285 parallel_pack, parallelize_by_sharding_dim_only, NoCallback());
286 ctx.run();
287 } else {
288 auto* ctx = new EvalParallelContext<DoneCallback, lhs_c(), rhs_c(), rhs_r()>(
289 this, num_threads, buffer, m, n, k, bm, bn, bk, nm, nn, nk, gm, gn, nm0, nn0, shard_by_col,
290 parallel_pack, parallelize_by_sharding_dim_only, std::move(done));
291 ctx->run();
292 }
293 },
294 this->m_lhs_inner_dim_contiguous, this->m_rhs_inner_dim_contiguous, this->m_rhs_inner_dim_reordered);
295 }
296
297 // ------------------------------------------------------------------------ //
298
299 // Dummy struct to represent an empty DoneCallback.
300
301 struct NoCallback {
302 void operator()() const { eigen_assert(false && "NoCallback should never be called"); }
303 };
304
305 // ------------------------------------------------------------------------ //
306
307 template <typename DoneCallback, typename Context>
308 class EvalParallelNotification;
309
310 // Synchronous evaluation notification that blocks caller thread in Wait().
311 template <typename Context>
312 class EvalParallelNotification<NoCallback, Context> {
313 public:
314 EvalParallelNotification(Context*, NoCallback) {}
315 void Notify() { done_.Notify(); }
316 void Wait() { done_.Wait(); }
317
318 private:
319 Eigen::Notification done_;
320 };
321
322 // Asynchronous evaluation notification that does not block in Wait().
323 template <typename DoneCallback, typename Context>
324 class EvalParallelNotification {
325 public:
326 EvalParallelNotification(Context* ctx, DoneCallback done) : ctx_(ctx), done_(std::move(done)) {}
327
328 void Notify() {
329 // Make a copy of done callback, because it will be destructed when we
330 // will delete context in the next line (EvalParallelNotification is a
331 // data member of EvalParallelContext class).
332 DoneCallback done_copy = std::move(done_);
333
334 // Delete parallel evaluation context.
335 delete ctx_;
336
337 // Now safely call the done callback.
338 done_copy();
339 }
340
341 void Wait() {}
342
343 private:
344 Context* ctx_;
345 DoneCallback done_;
346 };
347
348 // Context orchestrates sync/async parallel contraction evaluation. When it is
349 // executed in asynchronous mode, it owns all the shared state that might be
350 // accessible by block packing and kernel tasks.
351
352 template <typename DoneCallback, bool lhs_inner_dim_contiguous, bool rhs_inner_dim_contiguous,
353 bool rhs_inner_dim_reordered>
354 class EvalParallelContext {
355 public:
356 using LhsMapper =
357 internal::TensorContractionInputMapper<LhsScalar, Index, internal::Lhs, LeftEvaluator, left_nocontract_t,
358 contract_t, internal::packet_traits<LhsScalar>::size,
359 lhs_inner_dim_contiguous, false, Unaligned>;
360 using RhsMapper =
361 internal::TensorContractionInputMapper<RhsScalar, Index, internal::Rhs, RightEvaluator, right_nocontract_t,
362 contract_t, internal::packet_traits<RhsScalar>::size,
363 rhs_inner_dim_contiguous, rhs_inner_dim_reordered, Unaligned>;
364
365 using OutputMapper = internal::blas_data_mapper<Scalar, Index, ColMajor>;
366
367 using TensorContractionKernel =
368 internal::TensorContractionKernel<Scalar, LhsScalar, RhsScalar, Index, OutputMapper, LhsMapper, RhsMapper>;
369
370 using LhsBlock = typename TensorContractionKernel::LhsBlock;
371 using RhsBlock = typename TensorContractionKernel::RhsBlock;
372 using BlockMemHandle = typename TensorContractionKernel::BlockMemHandle;
373
374 EvalParallelContext(const Self* self, int num_threads, Scalar* buffer, Index tm, Index tn, Index tk, Index bm,
375 Index bn, Index bk, Index nm, Index nn, Index nk, Index gm, Index gn, Index nm0, Index nn0,
376 bool shard_by_col, bool parallel_pack, bool parallelize_by_sharding_dim_only, DoneCallback done)
377 : created_by_thread_id_(std::this_thread::get_id()),
378 done_(this, std::move(done)),
379 device_(self->m_device),
380 lhs_(self->m_leftImpl, self->m_left_nocontract_strides, self->m_i_strides, self->m_left_contracting_strides,
381 self->m_k_strides),
382 rhs_(self->m_rightImpl, self->m_right_nocontract_strides, self->m_j_strides,
383 self->m_right_contracting_strides, self->m_k_strides),
384 buffer_(buffer),
385 output_(buffer, tm),
386 output_kernel_(self->m_output_kernel),
387 tensor_contraction_params_(self->m_tensor_contraction_params),
388 num_threads_(num_threads),
389 shard_by_col_(shard_by_col),
390 parallel_pack_(parallel_pack),
391 parallelize_by_sharding_dim_only_(parallelize_by_sharding_dim_only),
392 m_(tm),
393 n_(tn),
394 k_(tk),
395 bm_(bm),
396 bn_(bn),
397 bk_(bk),
398 nm_(nm),
399 nn_(nn),
400 nk_(nk),
401 gm_(gm),
402 gn_(gn),
403 nm0_(nm0),
404 nn0_(nn0),
405 kernel_(m_, k_, n_, bm_, bk_, bn_),
406 num_thread_local_allocations_(0),
407 // We reserve 2X more capacity for a thread local values, than the
408 // number of threads in the pool to efficiently handle task stealing
409 // by threads that are not managed by the pool.
410 thread_local_capacity(2 * (parallelize_by_sharding_dim_only_ ? device_.numThreadsInPool() : 0)),
411 // We will use only one of the Lhs/Rhs thread local storage depending
412 // on the shard_by_col value and we parallelize by sharding dim ONLY.
413 lhs_thread_local_blocks_(shard_by_col_ ? 0 : thread_local_capacity, {*this}, {*this}),
414 rhs_thread_local_blocks_(shard_by_col_ ? thread_local_capacity : 0, {*this}, {*this}) {
415 // These two options are mutually exclusive.
416 eigen_assert(!(parallel_pack && parallelize_by_sharding_dim_only));
417
418 for (Index x = 0; x < P; x++) {
419 // Normal number of notifications for k slice switch is
420 // nm_ + nn_ + nm_ * nn_. However, first P - 1 slices will receive only
421 // nm_ + nn_ notifications, because they will not receive notifications
422 // from preceding kernels.
423 state_switch_[x] =
424 x == 0 ? 1 : (parallel_pack_ ? nn_ + nm_ : (shard_by_col_ ? nn_ : nm_)) + (x == P - 1 ? nm_ * nn_ : 0);
425 state_packing_ready_[x] = parallel_pack_ ? 0 : (shard_by_col_ ? nm_ : nn_);
426 state_kernel_[x] = new std::atomic<uint8_t>*[nm_];
427 for (Index m = 0; m < nm_; m++) {
428 state_kernel_[x][m] = new std::atomic<uint8_t>[nn_];
429 // Kernels generally receive 3 notifications (previous kernel + 2
430 // packing), but the first slice won't get notifications from previous
431 // kernels.
432 for (Index n = 0; n < nn_; n++)
433 state_kernel_[x][m][n].store((x == 0 ? 0 : 1) + (parallel_pack_ ? 2 : 1), std::memory_order_relaxed);
434 }
435 }
436
437 // Constructing the packed blocks can throw for scalars that require initialization. The destructor does not run
438 // then, so release what was allocated here, and notify a synchronous waiter so that its destructor accepts it.
439 bool packed_mem_allocated = false;
440 can_use_thread_local_packed_ = nullptr;
441 EIGEN_TRY {
442 // Allocate memory for packed rhs/lhs matrices. With nk_ == 1 and sharding-dim-only parallelism, slice 0 has no
443 // preceding slice to race with, so the sharded operand always packs into thread-local blocks.
444 const bool skip_sharded_global_slice = parallelize_by_sharding_dim_only_ && nk_ == 1;
445 const Index num_global_lhs = (skip_sharded_global_slice && !shard_by_col_) ? 0 : nm0_;
446 const Index num_global_rhs = (skip_sharded_global_slice && shard_by_col_) ? 0 : nn0_;
447 packed_mem_ = kernel_.allocateSlices( //
448 device_, //
449 /*num_lhs=*/num_global_lhs, //
450 /*num_rhs=*/num_global_rhs, //
451 /*num_slices=*/std::min<Index>(nk_, P - 1), //
452 packed_lhs_, packed_rhs_);
453 packed_mem_allocated = true;
454
455 if (parallelize_by_sharding_dim_only_) {
456 const int num_worker_threads = device_.numThreadsInPool();
457
458 if (shard_by_col) {
459 can_use_thread_local_packed_ = new std::atomic<bool>[nn_];
460 for (int i = 0; i < nn_; ++i) can_use_thread_local_packed_[i].store(true, std::memory_order_relaxed);
461
462 Index num_blocks = num_worker_threads * gn_;
463 thread_local_pre_allocated_mem_ = kernel_.allocateSlices( //
464 device_, //
465 /*num_lhs=*/0, //
466 /*num_rhs=*/num_blocks, //
467 /*num_slices=*/1, //
468 /*lhs_blocks=*/nullptr, &rhs_thread_local_pre_allocated_);
469
470 } else {
471 can_use_thread_local_packed_ = new std::atomic<bool>[nm_];
472 for (int i = 0; i < nm_; ++i) can_use_thread_local_packed_[i].store(true, std::memory_order_relaxed);
473
474 Index num_blocks = num_worker_threads * gm_;
475 thread_local_pre_allocated_mem_ = kernel_.allocateSlices( //
476 device_, //
477 /*num_lhs=*/num_blocks, //
478 /*num_rhs=*/0, //
479 /*num_slices=*/1, &lhs_thread_local_pre_allocated_, //
480 /*rhs_blocks=*/nullptr);
481 }
482 }
483 }
484 EIGEN_CATCH(...) {
485 if (packed_mem_allocated) kernel_.deallocate(device_, packed_mem_);
486 delete[] can_use_thread_local_packed_;
487 for (Index x = 0; x < P; x++) {
488 for (Index m = 0; m < nm_; m++) delete[] state_kernel_[x][m];
489 delete[] state_kernel_[x];
490 }
491 EIGEN_IF_CONSTEXPR (std::is_same<DoneCallback, NoCallback>::value) done_.Notify();
492 EIGEN_THROW;
493 }
494 }
495
496 ~EvalParallelContext() {
497 for (Index x = 0; x < P; x++) {
498 for (Index m = 0; m < nm_; m++) delete[] state_kernel_[x][m];
499 delete[] state_kernel_[x];
500 }
501 kernel_.deallocate(device_, packed_mem_);
502 if (parallelize_by_sharding_dim_only_) {
503 kernel_.deallocate(device_, thread_local_pre_allocated_mem_);
504 delete[] can_use_thread_local_packed_;
505 }
506 }
507
508 // The calling thread runs part of the work after tasks are enqueued, and those tasks use this context. A throw here
509 // cannot unwind safely, so it terminates, as a throw on a worker does.
510 void run() noexcept {
511 // Kick off packing of the first slice.
512 signal_switch(0, 1);
513
514 // Wait for overall completion.
515 //
516 // If parallel evaluation is executed in async mode, this is a no-op, and
517 // Wait() will return immediately. In synchronous mode it will block the
518 // caller thread until it will receive notification from last task.
519 //
520 // In async mode, last task when completed will call done callback from
521 // the same thread, and will delete this context.
522 //
523 // TODO(dvyukov): This wait can lead to deadlock if contraction is
524 // evaluated in synchronous mode. If nthreads contractions are
525 // concurrently submitted from worker threads, this wait will block all
526 // worker threads and the system will deadlock.
527 done_.Wait();
528 }
529
530 private:
531 std::thread::id created_by_thread_id_;
532
533 // This notification is specialized on the type of DoneCallback and can be
534 // blocking or non-blocking.
535 EvalParallelNotification<DoneCallback, EvalParallelContext> done_;
536
537 const Device& device_;
538 LhsMapper lhs_;
539 RhsMapper rhs_;
540 Scalar* const buffer_;
541 OutputMapper output_;
542 OutputKernelType output_kernel_;
543 TensorContractionParams tensor_contraction_params_;
544 const int num_threads_;
545 const bool shard_by_col_;
546 const bool parallel_pack_;
547 const bool parallelize_by_sharding_dim_only_;
548 // Matrix sizes.
549 const Index m_;
550 const Index n_;
551 const Index k_;
552 // Block sizes.
553 const Index bm_;
554 const Index bn_;
555 const Index bk_;
556 // Number of tasks.
557 const Index nm_;
558 const Index nn_;
559 const Index nk_;
560 // Task grain sizes (number of kernels executed per task).
561 const Index gm_;
562 const Index gn_;
563 // Number of blocks (this is different from nm_/nn_ because of task size
564 // coarsening).
565 const Index nm0_;
566 const Index nn0_;
567 // Tensor contraction kernel.
568 TensorContractionKernel kernel_;
569
570 // Parallelization strategy.
571 //
572 // Blocks related to the same k block can run in parallel because they write
573 // to different output blocks. So we parallelize within k slices, this
574 // gives us parallelism level of m x n. Before we can start any kernels
575 // related to k-th slice, we need to issue m lhs packing tasks and n rhs
576 // packing tasks.
577 //
578 // However, there is a bottleneck when we are finishing kernels for k-th
579 // slice (at the very end there is only 1 runnable kernel). To mitigate this
580 // bottleneck we allow kernels from k-th and k+1-th slices to run in
581 // parallel. Note that (m, n, k) and (m, n, k+1) kernels write to the same
582 // output block, so they must not run in parallel.
583 //
584 // This gives us the following dependency graph.
585 // On each k slice we have m x n kernel tasks, m lhs packing tasks and n rhs
586 // packing tasks.
587 // Kernel (m, n, k) can start when:
588 // - kernel (m, n, k-1) has finished
589 // - lhs packing (m, k) has finished
590 // - rhs packing (n, k) has finished
591 // Lhs/rhs packing can start when:
592 // - all k-1 packing has finished (artificially imposed to limit amount of
593 // parallel packing)
594 //
595 // On top of that we limit runnable tasks to two consecutive k slices.
596 // This is done to limit amount of memory we need for packed lhs/rhs
597 // (for each k slice we need m*bk + n*bk memory in packed_lhs_/packed_rhs_).
598 //
599 // state_switch_ tracks when we are ready to switch to the next k slice.
600 // state_kernel_[m][n] tracks when we are ready to kick off kernel (m, n).
601 // These variable are rolling over 3 consecutive k slices: first two we are
602 // actively executing + one to track completion of kernels in the second
603 // slice.
604 static constexpr Index P = 3;
605
606 // Handle to the allocated temporary storage for Lhs/Rhs blocks.
607 BlockMemHandle packed_mem_;
608 std::vector<LhsBlock> packed_lhs_[P - 1];
609 std::vector<RhsBlock> packed_rhs_[P - 1];
610
611 // If we choose to parallelize only by the sharding dimension, each thread
612 // will have its own "thread local" (not a C++ thread local storage) memory
613 // for packed_lhs or packed_rhs (shard_by_col = false of true). This memory
614 // can't be passed to a kernel that might execute on a different thread.
615 //
616 // In practice when we are ready to pack memory for the sharding dimension
617 // (rhs if shard_by_col==true) of the K-th slice, all kernels for K-1 slice
618 // already computed (99% of the time), and we can pack data into the thread
619 // local storage, and guarantee that all the kernels will be executed
620 // immediately in the same thread. This significantly increases L1 cache hit
621 // ratio and reduces pressure on the memory bus.
622 //
623 // When nk_ > 1, it is still possible that kernel for the K-th slice will be
624 // ready before completion of the K-1 kernel, so we have to allocate "global"
625 // packed_lhs_ and packed_rhs_ to allow kernels to be executed later on a
626 // thread different from the thread that was used for packing.
627
628 // Handle for pre-allocated thread local memory buffers.
629 BlockMemHandle thread_local_pre_allocated_mem_;
630
631 // Only one of these will be initialized depending on shard_by_col value
632 // (the size will be `num_worker_threads * num_grains_in_the_sharding_dim`).
633 std::vector<LhsBlock> lhs_thread_local_pre_allocated_;
634 std::vector<RhsBlock> rhs_thread_local_pre_allocated_;
635
636 // How many thread local blocks were already allocated.
637 std::atomic<int> num_thread_local_allocations_;
638 const int thread_local_capacity;
639
640 // We will use pre-allocated Lhs/Rhs blocks defined above, if the number of
641 // unique threads in a system is below or equal to the number of threads in
642 // a thread pool. We will fallback on dynamic memory allocation after that.
643
644 // ThreadLocalBlocks is a container for Lhs or Rhs thread local buffers. Its
645 // size is equal to the grain size in Lhs/Rhs sharding dimension.
646 template <typename BlockType>
647 class ThreadLocalBlocks {
648 public:
649 ThreadLocalBlocks() = default;
650
651 ThreadLocalBlocks(BlockType* base, size_t grain_size)
652 : is_pre_allocated_(true), thread_local_pre_allocated_base_(base), grain_size_(grain_size) {}
653
654 ThreadLocalBlocks(BlockMemHandle mem_handle, std::vector<BlockType> blocks)
655 : is_pre_allocated_(false), mem_handle_(std::move(mem_handle)), blocks_(std::move(blocks)) {}
656
657 BlockType& block(int grain_index) {
658 eigen_assert(grain_index >= 0);
659 eigen_assert(static_cast<size_t>(grain_index) < size());
660 return is_pre_allocated_ ? thread_local_pre_allocated_base_[grain_index] : blocks_[grain_index];
661 }
662
663 void Release(EvalParallelContext& ctx) const {
664 if (!is_pre_allocated_) {
665 ctx.kernel_.deallocate(ctx.device_, mem_handle_);
666 }
667 }
668
669 size_t size() const { return is_pre_allocated_ ? grain_size_ : blocks_.size(); }
670
671 private:
672 bool is_pre_allocated_;
673
674 // Reuse pre-allocated thread local buffers.
675 BlockType* thread_local_pre_allocated_base_ = nullptr;
676 size_t grain_size_ = 0;
677
678 // These will be initialized only if `is_pre_allocated == false`.
679 BlockMemHandle mem_handle_{};
680 std::vector<BlockType> blocks_;
681 };
682
683 // ThreadLocalBlocksInitialize callable does custom thread local blocks
684 // initialization, and will reuse pre-allocated buffers if possible, or will
685 // dynamically allocate new memory.
686 //
687 // Lhs/Rhs blocks might be of the same type, so we have to pass explicitly
688 // for what side do we plan to do block allocation.
689 template <typename BlockType, bool is_rhs>
690 class ThreadLocalBlocksInitialize {
691 static constexpr bool kIsLhs = !is_rhs && std::is_same<BlockType, LhsBlock>::value;
692 static constexpr bool kIsRhs = is_rhs && std::is_same<BlockType, RhsBlock>::value;
693 static_assert(kIsLhs || kIsRhs, "Unknown block type");
694
695 using Blocks = ThreadLocalBlocks<BlockType>;
696
697 public:
698 ThreadLocalBlocksInitialize(EvalParallelContext& ctx)
699 : ctx_(ctx), num_worker_threads_(ctx_.device_.numThreadsInPool()) {}
700
701 void operator()(Blocks& blocks) {
702 const int n = ctx_.num_thread_local_allocations_.fetch_add(1, std::memory_order_relaxed);
703
704 if (n >= num_worker_threads_) {
705 ThreadLocalBlocksAllocator<is_rhs>::allocate(ctx_, blocks);
706 } else {
707 ThreadLocalBlocksAllocator<is_rhs>::reuse(ctx_, n, blocks);
708 }
709 }
710
711 private:
712 // Explicit specializations are not allowed at class scope, so EvalCtx is
713 // a dummy template parameter to make these partial specializations.
714 template <bool pack_rhs, typename EvalCtx = EvalParallelContext>
715 struct ThreadLocalBlocksAllocator;
716
717 template <typename EvalCtx>
718 struct ThreadLocalBlocksAllocator</*pack_rhs=*/true, EvalCtx> {
719 static void allocate(EvalCtx& ctx, Blocks& blocks) {
720 std::vector<RhsBlock> rhs_blocks;
721 BlockMemHandle mem_handle = ctx.kernel_.allocateSlices(ctx.device_,
722 /*num_lhs=*/0,
723 /*num_rhs=*/ctx.gn_,
724 /*num_slices=*/1,
725 /*lhs_blocks=*/nullptr, /*rhs_blocks=*/&rhs_blocks);
726 blocks = ThreadLocalBlocks<RhsBlock>(std::move(mem_handle), std::move(rhs_blocks));
727 }
728
729 static void reuse(EvalCtx& ctx, int index, Blocks& blocks) {
730 RhsBlock* ptr = &ctx.rhs_thread_local_pre_allocated_[ctx.gn_ * index];
731 blocks = ThreadLocalBlocks<RhsBlock>(ptr, ctx.gn_);
732 }
733 };
734
735 template <typename EvalCtx>
736 struct ThreadLocalBlocksAllocator</*pack_rhs=*/false, EvalCtx> {
737 static void allocate(EvalCtx& ctx, Blocks& blocks) {
738 std::vector<LhsBlock> lhs_blocks;
739 BlockMemHandle mem_handle = ctx.kernel_.allocateSlices(ctx.device_,
740 /*num_lhs=*/ctx.gm_,
741 /*num_rhs=*/0,
742 /*num_slices=*/1,
743 /*lhs_blocks=*/&lhs_blocks, /*rhs_blocks=*/nullptr);
744 blocks = ThreadLocalBlocks<LhsBlock>(std::move(mem_handle), std::move(lhs_blocks));
745 }
746
747 static void reuse(EvalCtx& ctx, int index, Blocks& blocks) {
748 LhsBlock* ptr = &ctx.lhs_thread_local_pre_allocated_[ctx.gm_ * index];
749 blocks = ThreadLocalBlocks<LhsBlock>(ptr, ctx.gm_);
750 }
751 };
752
753 EvalParallelContext& ctx_;
754 const int num_worker_threads_;
755 };
756
757 template <typename BlockType>
758 class ThreadLocalBlocksRelease {
759 public:
760 using Blocks = ThreadLocalBlocks<BlockType>;
761 ThreadLocalBlocksRelease(EvalParallelContext& ctx) : ctx_(ctx) {}
762 void operator()(Blocks& blocks) { blocks.Release(ctx_); }
763
764 private:
765 EvalParallelContext& ctx_;
766 };
767
768 // ThreadLocalBlocks initialization callables.
769 using ThreadLocalLhsInit = ThreadLocalBlocksInitialize<LhsBlock, /*is_rhs=*/false>;
770 using ThreadLocalRhsInit = ThreadLocalBlocksInitialize<RhsBlock, /*is_rhs=*/true>;
771
772 // ThreadLocalBlocks release callables.
773 using ThreadLocalLhsRelease = ThreadLocalBlocksRelease<LhsBlock>;
774 using ThreadLocalRhsRelease = ThreadLocalBlocksRelease<RhsBlock>;
775
776 // Thread local containers for Lhs/Rhs block packs. In practice only one of
777 // them will be used, depending on the shard_by_col value.
778 Eigen::ThreadLocal<ThreadLocalBlocks<LhsBlock>, ThreadLocalLhsInit, ThreadLocalLhsRelease> lhs_thread_local_blocks_;
779 Eigen::ThreadLocal<ThreadLocalBlocks<RhsBlock>, ThreadLocalRhsInit, ThreadLocalRhsRelease> rhs_thread_local_blocks_;
780
781 // After a particular shard for Kth slice missed thread local execution
782 // opportunity (K-1 slice didn't complete kernels execution), we can no
783 // longer schedule K+1 and following slices in thread local mode, because
784 // there is no more guarantee that previous kernels were executed
785 // sequentially in the same thread (size is nn_ or nm_).
786 std::atomic<bool>* can_use_thread_local_packed_;
787
788 std::atomic<uint8_t>** state_kernel_[P];
789 // state_switch_ is frequently modified by worker threads, while other
790 // fields are read-only after constructor. Let's move it to a separate cache
791 // line to reduce cache-coherency traffic.
792 char pad_[128];
793 std::atomic<Index> state_packing_ready_[P];
794 std::atomic<Index> state_switch_[P];
795
796 LhsBlock& packed_lhs(Index m, Index k, Index m1, bool use_thread_local) {
797 if (use_thread_local) {
798 eigen_assert(!shard_by_col_);
799 ThreadLocalBlocks<LhsBlock>& blocks = lhs_thread_local_blocks_.local();
800
801 Index grain_index = m1 - m * gm_;
802 return blocks.block(
803 internal::convert_index<int>(grain_index)); // FIXME: Consider making ThreadLocalBlocks use Eigen::Index.
804 } else {
805 return packed_lhs_[k % (P - 1)][m1];
806 }
807 }
808
809 RhsBlock& packed_rhs(Index n, Index k, Index n1, bool use_thread_local) {
810 if (use_thread_local) {
811 eigen_assert(shard_by_col_);
812 ThreadLocalBlocks<RhsBlock>& blocks = rhs_thread_local_blocks_.local();
813
814 Index grain_index = n1 - n * gn_;
815 return blocks.block(
816 internal::convert_index<int>(grain_index)); // FIXME: Consider making ThreadLocalBlocks use Eigen::Index.
817 } else {
818 return packed_rhs_[k % (P - 1)][n1];
819 }
820 }
821
822 // In following two methods (pack_lhs and pack_rhs), if we know for sure
823 // that we'll be able to immediately call a kernel with packed data, and do
824 // not submit it to the thread pool, we can use thread local memory for
825 // packed data.
826 //
827 // We can only reliably check it if we are running all kernels in sync mode
828 // (parallelize only by sharding dim). If kernel for m==0 (n==0) is ready to
829 // run, it's guaranteed that all kernels with larger values of m (n) are
830 // also ready, because we execute them in the same order for all K slices.
831
832 void pack_lhs(Index m, Index k) {
833 bool use_thread_local = false;
834
835 if (parallelize_by_sharding_dim_only_ && !shard_by_col_ &&
836 can_use_thread_local_packed_[m].load(std::memory_order_relaxed)) {
837 if (state_kernel_[k % P][m][0].load(std::memory_order_relaxed) == 1) {
838 use_thread_local = true;
839 } else {
840 // If we can't guarantee that all kernels in `k` slice will be
841 // executed sequentially in current thread, it's no longer safe to use
842 // thread local memory in following slices along the k dimensions.
843 eigen_assert(k > 0);
844 can_use_thread_local_packed_[m].store(false, std::memory_order_relaxed);
845 }
846 }
847
848 const Index mend = m * gm_ + gm(m);
849 for (Index m1 = m * gm_; m1 < mend; m1++)
850 kernel_.packLhs(&packed_lhs(m, k, m1, use_thread_local), lhs_.getSubMapper(m1 * bm_, k * bk_), bk(k), bm(m1));
851
852 if (!parallel_pack_ && shard_by_col_) {
853 eigen_assert(!use_thread_local);
854 signal_packing(k);
855 } else {
856 signal_switch(k + 1);
857 for (Index n = nn_ - 1; n >= 0; n--) {
858 bool sync = parallelize_by_sharding_dim_only_ || n == 0;
859 signal_kernel(m, n, k, sync, use_thread_local);
860 }
861 }
862 }
863
864 void pack_rhs(Index n, Index k) {
865 bool use_thread_local = false;
866
867 if (parallelize_by_sharding_dim_only_ && shard_by_col_ &&
868 can_use_thread_local_packed_[n].load(std::memory_order_relaxed)) {
869 if (state_kernel_[k % P][0][n].load(std::memory_order_relaxed) == 1) {
870 use_thread_local = true;
871 } else {
872 // If we can't guarantee that all kernels in `k` slice will be
873 // executed sequentially in current thread, it's no longer safe to use
874 // thread local memory in following slices along the k dimensions.
875 eigen_assert(k > 0);
876 can_use_thread_local_packed_[n].store(false, std::memory_order_relaxed);
877 }
878 }
879
880 const Index nend = n * gn_ + gn(n);
881 for (Index n1 = n * gn_; n1 < nend; n1++) {
882 EIGEN_IF_CONSTEXPR (!TensorContractionKernel::HasBeta) {
883 if (k == 0) {
884 // Zero the output memory in parallel, only if contraction kernel does
885 // not support `beta`. Otherwise we will pass beta 0.0 to the first
886 // call to the `TensorContractionKernel::invoke()`.
887 //
888 // On 10000x2x10000 mm zeroing can easily take half of time. Zero (bn
889 // x m) row. Safe to do here because all kernels that will write to
890 // this memory depend on completion of this task. Note: don't call
891 // device_.fill() here. device_.fill() blocks on thread pool
892 // worker thread, which can lead to underutilization and deadlocks.
893 std::fill_n(buffer_ + n1 * bn_ * m_, bn(n1) * m_, Scalar(0));
894 }
895 }
896 kernel_.packRhs(&packed_rhs(n, k, n1, use_thread_local), rhs_.getSubMapper(k * bk_, n1 * bn_), bk(k), bn(n1));
897 }
898
899 if (parallel_pack_ || shard_by_col_) {
900 signal_switch(k + 1);
901 for (Index m = nm_ - 1; m >= 0; m--) {
902 bool sync = parallelize_by_sharding_dim_only_ || m == 0;
903 signal_kernel(m, n, k, sync, use_thread_local);
904 }
905 } else {
906 eigen_assert(!use_thread_local);
907 signal_packing(k);
908 }
909 }
910
911 void kernel(Index m, Index n, Index k, bool use_thread_local) {
912 // Note: order of iteration matters here. Iteration over m is innermost
913 // because we want to reuse the same packed rhs in consecutive tasks
914 // (rhs fits into L2$ while lhs only into L3$).
915 const Index nend = n * gn_ + gn(n);
916 const Index mend = m * gm_ + gm(m);
917
918 // NOTE: output = alpha * LHS * RHS + beta * output.
919 const Scalar alpha = Scalar(1);
920 const Scalar beta = (TensorContractionKernel::HasBeta && k == 0) ? Scalar(0) : Scalar(1);
921
922 if (shard_by_col_) {
923 for (Index n1 = n * gn_; n1 < nend; n1++) {
924 for (Index m1 = m * gm_; m1 < mend; m1++) {
925 const auto output_mapper = output_.getSubMapper(m1 * bm_, n1 * bn_);
926 kernel_.invoke(output_mapper, packed_lhs(m, k, m1, !shard_by_col_ && use_thread_local),
927 packed_rhs(n, k, n1, shard_by_col_ && use_thread_local), bm(m1), bk(k), bn(n1), alpha, beta);
928
929 // We are done with the last task for the [m1, n1] block.
930 if (k + 1 == nk_) {
931 output_kernel_(output_mapper, tensor_contraction_params_, m1 * bm_, n1 * bn_, bm(m1), bn(n1));
932 }
933 }
934 }
935 } else {
936 for (Index m1 = m * gm_; m1 < mend; m1++)
937 for (Index n1 = n * gn_; n1 < nend; n1++) {
938 const auto output_mapper = output_.getSubMapper(m1 * bm_, n1 * bn_);
939 kernel_.invoke(output_mapper, packed_lhs(m, k, m1, !shard_by_col_ && use_thread_local),
940 packed_rhs(n, k, n1, shard_by_col_ && use_thread_local), bm(m1), bk(k), bn(n1), alpha, beta);
941
942 // We are done with the last task for the [m1, n1] block.
943 if (k + 1 == nk_) {
944 output_kernel_(output_mapper, tensor_contraction_params_, m1 * bm_, n1 * bn_, bm(m1), bn(n1));
945 }
946 }
947 }
948 signal_kernel(m, n, k + 1, /*sync=*/false, /*use_thread_local=*/false);
949 signal_switch(k + 2);
950 }
951
952 void signal_packing(Index k) {
953 eigen_assert(!parallel_pack_);
954 Index s = state_packing_ready_[k % P].fetch_sub(1);
955 eigen_assert(s > 0);
956 if (s != 1) return;
957 state_packing_ready_[k % P] = shard_by_col_ ? nm_ : nn_;
958 enqueue_packing(k, shard_by_col_);
959 }
960
961 void signal_kernel(Index m, Index n, Index k, bool sync, bool use_thread_local) {
962 std::atomic<uint8_t>* state = &state_kernel_[k % P][m][n];
963 Index s = state->load();
964 eigen_assert(s > 0);
965 if (s != 1 && state->fetch_sub(1) != 1) {
966 eigen_assert(!use_thread_local);
967 return;
968 }
969 state->store(parallel_pack_ ? 3 : 2, std::memory_order_relaxed);
970 if (sync) {
971 kernel(m, n, k, use_thread_local);
972 } else {
973 eigen_assert(!use_thread_local);
974 device_.enqueue([this, m, n, k, use_thread_local]() { kernel(m, n, k, use_thread_local); });
975 }
976 }
977
978 void signal_switch(Index k, Index v = 1) {
979 Index s = state_switch_[k % P].fetch_sub(v);
980 eigen_assert(s >= v);
981 if (s != v) return;
982
983 // Ready to switch to the next k slice.
984 // Reset counter for the next iteration.
985 state_switch_[k % P] = (parallel_pack_ ? nm_ + nn_ : (shard_by_col_ ? nn_ : nm_)) + nm_ * nn_;
986 if (k < nk_) {
987 // Issue lhs/rhs packing. Their completion will in turn kick off
988 // kernels.
989 if (parallel_pack_) {
990 enqueue_packing(k, !shard_by_col_);
991 enqueue_packing(k, shard_by_col_);
992 } else if (shard_by_col_) {
993 enqueue_packing(k, false);
994 } else {
995 enqueue_packing(k, true);
996 }
997
998 // Termination handling.
999 // Because kernel completion signals k + 2 switch, we need to finish nk
1000 // + 2 slices without issuing any tasks on nk + 1 slice. So here we
1001 // pretend that all nk + 1 packing tasks just finish instantly; so that
1002 // nk + 2 switch only waits for completion of nk kernels.
1003 } else if (k == nk_) {
1004 signal_switch(k + 1, parallel_pack_ ? nm_ + nn_ : (shard_by_col_ ? nn_ : nm_));
1005 } else {
1006 done_.Notify();
1007 }
1008 }
1009
1010 // Enqueue all rhs/lhs packing for k-th slice.
1011 void enqueue_packing(Index k, bool rhs) { enqueue_packing_helper(0, rhs ? nn_ : nm_, k, rhs); }
1012
1013 void enqueue_packing_helper(Index start, Index end, Index k, bool rhs) {
1014 if (end - start == 1) {
1015 if (rhs)
1016 pack_rhs(start, k);
1017 else
1018 pack_lhs(start, k);
1019 } else {
1020 while (end - start > 1) {
1021 Index mid = (start + end) / 2;
1022 device_.enqueue([this, mid, end, k, rhs]() { enqueue_packing_helper(mid, end, k, rhs); });
1023 end = mid;
1024 }
1025
1026 // Decide if we want to run first packing task (start == 0) in
1027 // async mode if we parallelize only by sharding dim:
1028 // (1) pack_lhs and pack_rhs call signal_switch before completing
1029 // all calls to signal_kernel, which in sync mode might lead
1030 // to the execution of the first kernel of the k+1 slice, before
1031 // completing a call to the last kernel of the k slice.
1032 // (2) all pack tasks for sharded dim must be executed in a thread
1033 // pool to get pre-allocated thread local buffers.
1034 bool pack_async = (start == 0) && (parallelize_by_sharding_dim_only_ && shard_by_col_ == rhs) &&
1035 (k > 0 || std::this_thread::get_id() == created_by_thread_id_);
1036
1037 if (pack_async) {
1038 device_.enqueue([this, start, end, k, rhs]() { enqueue_packing_helper(start, end, k, rhs); });
1039 } else {
1040 enqueue_packing_helper(start, end, k, rhs);
1041 }
1042 }
1043 }
1044
1045 // Block sizes with accounting for potentially incomplete last block.
1046 Index bm(Index m) const { return m + 1 < nm0_ ? bm_ : m_ + bm_ - bm_ * nm0_; }
1047 Index bn(Index n) const { return n + 1 < nn0_ ? bn_ : n_ + bn_ - bn_ * nn0_; }
1048 Index bk(Index k) const { return k + 1 < nk_ ? bk_ : k_ + bk_ - bk_ * nk_; }
1049 // Task grain sizes accounting for potentially incomplete last task.
1050 Index gm(Index m) const { return m + 1 < nm_ ? gm_ : nm0_ + gm_ - gm_ * nm_; }
1051 Index gn(Index n) const { return n + 1 < nn_ ? gn_ : nn0_ + gn_ - gn_ * nn_; }
1052
1053 EvalParallelContext(const EvalParallelContext&) = delete;
1054 void operator=(const EvalParallelContext&) = delete;
1055 };
1056
1057 // ------------------------------------------------------------------------ //
1058
1059 // EvalShardedByInnerDimContext orchestrates sync/async contraction
1060 // evaluation, when we shard by inner dimension. When it is executed in
1061 // asynchronous mode, it owns all the shared state that might be accessible by
1062 // block processing tasks.
1063
1064 template <typename DoneCallback>
1065 struct EvalShardedByInnerDimContext {
1066 EvalShardedByInnerDimContext(const Self* self, int num_threads, Scalar* result_buffer, Index m_size, Index n_size,
1067 Index k_size, DoneCallback done_callback)
1068 : evaluator(self),
1069 m_lhs_inner_dim_contiguous(evaluator->m_lhs_inner_dim_contiguous),
1070 m_rhs_inner_dim_contiguous(evaluator->m_rhs_inner_dim_contiguous),
1071 m_rhs_inner_dim_reordered(evaluator->m_rhs_inner_dim_reordered),
1072 result(result_buffer),
1073 m(m_size),
1074 n(n_size),
1075 k(k_size),
1076 done(std::move(done_callback)),
1077 buffer_size_bytes(m * n * sizeof(Scalar)),
1078 block_size(innerDimBlockSize(k, num_threads)),
1079 num_blocks(numext::div_ceil<Index>(k, block_size)),
1080 num_pending_blocks(internal::convert_index<int>(num_blocks)),
1081 l0_ranges(numext::div_ceil<Index>(num_blocks, l0_size)),
1082 l0_state(l0_ranges),
1083 block_buffers(num_blocks) {
1084 // Keep count of pending gemm tasks for each l0 range.
1085 for (int i = 0; i < l0_ranges; ++i) {
1086 const Index num_pending_tasks = actualRangeSize(l0_ranges, l0_size, i);
1087 l0_state.emplace_back(internal::convert_index<int>(num_pending_tasks));
1088 }
1089
1090 // Allocate temporary buffers for each block. The destructor does not run if this throws, so release them here.
1091 EIGEN_TRY {
1092 for (Index block_idx = 0; block_idx < num_blocks; ++block_idx) {
1093 block_buffers.emplace_back(block_idx == 0 ? result : allocateBlockBuffer());
1094 }
1095 }
1096 EIGEN_CATCH(...) {
1097 releaseBlockBuffers();
1098 EIGEN_THROW;
1099 }
1100 }
1101
1102 ~EvalShardedByInnerDimContext() { releaseBlockBuffers(); }
1103
1104 Scalar* allocateBlockBuffer() const {
1105 Scalar* buf = static_cast<Scalar*>(evaluator->m_device.allocate(buffer_size_bytes));
1106 EIGEN_IF_CONSTEXPR (NumTraits<Scalar>::RequireInitialization) {
1107 EIGEN_TRY { internal::default_construct_elements_of_array(buf, m * n); }
1108 EIGEN_CATCH(...) {
1109 evaluator->m_device.deallocate(buf);
1110 EIGEN_THROW;
1111 }
1112 }
1113 return buf;
1114 }
1115
1116 void releaseBlockBuffers() {
1117 for (size_t i = 1; i < block_buffers.size(); ++i) {
1118 EIGEN_IF_CONSTEXPR (NumTraits<Scalar>::RequireInitialization) {
1119 internal::destruct_elements_of_array(block_buffers[i], m * n);
1120 }
1121 evaluator->m_device.deallocate(block_buffers[i]);
1122 }
1123 }
1124
1125 template <int Alignment>
1126 void run() {
1127 Barrier barrier(internal::convert_index<int>(num_blocks));
1128 evalBlocks<Alignment>(barrier);
1129
1130 // Aggregate partial sums from l0 ranges.
1131 aggregateL0Blocks<Alignment>();
1132
1133 // Apply output kernel.
1134 applyOutputKernel();
1135 }
1136
1137 // The calling thread evaluates a block after tasks are enqueued, and those tasks use this context and the barrier.
1138 // A throw here cannot unwind safely, so it terminates, as a throw on a worker does.
1139 template <int Alignment>
1140 void evalBlocks(Barrier& barrier) noexcept {
1141 eval<Alignment>(barrier, 0, num_blocks);
1142 barrier.Wait();
1143 }
1144
1145 template <int Alignment>
1146 void runAsync() noexcept {
1147 evalAsync<Alignment>(0, num_blocks);
1148 }
1149
1150 private:
1151 const Self* evaluator; // TensorContraction evaluator
1152
1153 // These fields cache values from the evaluator for use in processBlock dispatch.
1154 bool m_lhs_inner_dim_contiguous;
1155 bool m_rhs_inner_dim_contiguous;
1156 bool m_rhs_inner_dim_reordered;
1157
1158 Scalar* result;
1159
1160 Index m;
1161 Index n;
1162 Index k;
1163
1164 DoneCallback done;
1165
1166 // ----------------------------------------------------------------------//
1167 // Algorithm parameters.
1168
1169 // We will compute partial results into the buffers of this size.
1170 Index buffer_size_bytes;
1171
1172 Index block_size;
1173 Index num_blocks;
1174
1175 // Keep track of pending tasks when evaluate in async mode.
1176 std::atomic<int> num_pending_blocks;
1177
1178 // We compute partial gemm results in parallel, and to get the final result
1179 // we need to add them all together. For the large number of threads (>= 48)
1180 // this adds a very expensive sequential step at the end.
1181 //
1182 // We split the [0, num_blocks) into small ranges, and when a task for the
1183 // block finishes its partial gemm computation, it checks if it was the last
1184 // gemm in the range, and if so, it will add all blocks of the range.
1185 //
1186 // After all tasks done, we need to add only these pre-aggregated blocks.
1187
1188 // For now we use just a single level of ranges to compute pre-aggregated
1189 // partial sums, but in general we can use more layers to compute tree
1190 // aggregation in parallel and reduce the size of the sequential step.
1191 //
1192 // TODO(ezhulenev): Add multilevel tree aggregation? Probably will make
1193 // sense only if number of threads >= ~128?
1194 static constexpr Index l0_size = 4;
1195 Index l0_ranges;
1196
1197 // Keep count of pending gemm tasks for each l0 range.
1198 MaxSizeVector<std::atomic<int>> l0_state; // [0, l0_ranges)
1199
1200 // Buffers allocated for each temporary block computation.
1201 MaxSizeVector<Scalar*> block_buffers; // [0, num_blocks)
1202
1203 template <int Alignment>
1204 void processBlock(Index block_idx, Index begin, Index end) {
1205 Scalar* buf = block_buffers[block_idx];
1206
1207 dispatchContraction(
1208 [&](auto lhs_c, auto rhs_c, auto rhs_r) {
1209 evaluator->template evalGemmPartialWithoutOutputKernel<lhs_c(), rhs_c(), rhs_r(), Alignment>(
1210 buf, begin, end, /*num_threads=*/internal::convert_index<int>(num_blocks));
1211 },
1212 m_lhs_inner_dim_contiguous, m_rhs_inner_dim_contiguous, m_rhs_inner_dim_reordered);
1213
1214 // Check if it was the last task in l0 range.
1215 const Index l0_index = block_idx / l0_size;
1216 const int v = l0_state[l0_index].fetch_sub(1);
1217 eigen_assert(v >= 1);
1218
1219 // If we processed the last block of the range, we can aggregate all
1220 // partial results into the first block of the range.
1221 if (v == 1) {
1222 const Index rng_size = actualRangeSize(l0_ranges, l0_size, l0_index);
1223 const Index dst_block_idx = l0_index * l0_size;
1224
1225 if (rng_size == l0_size) {
1226 addAllToBuffer<Alignment>(m * n,
1227 /*src_buf0=*/block_buffers[dst_block_idx + 1],
1228 /*src_buf1=*/block_buffers[dst_block_idx + 2],
1229 /*src_buf2=*/block_buffers[dst_block_idx + 3],
1230 /*dst_buf= */ block_buffers[dst_block_idx]);
1231 } else {
1232 // Aggregate blocks of potentially incomplete last range.
1233 for (int i = 1; i < rng_size; ++i) {
1234 addToBuffer<Alignment>(m * n,
1235 /*src_buf=*/block_buffers[dst_block_idx + i],
1236 /*tgt_buf=*/block_buffers[dst_block_idx]);
1237 }
1238 }
1239 }
1240 }
1241
1242 // Aggregate partial sums from l0 ranges.
1243 template <int Alignment>
1244 void aggregateL0Blocks() const {
1245 Index l0_index = 1;
1246
1247 for (; l0_index + 2 < l0_ranges; l0_index += 3) {
1248 addAllToBuffer<Alignment>(m * n,
1249 /*src_buf0=*/block_buffers[(l0_index + 0) * l0_size],
1250 /*src_buf1=*/block_buffers[(l0_index + 1) * l0_size],
1251 /*src_buf2=*/block_buffers[(l0_index + 2) * l0_size],
1252 /*dst_buf= */ block_buffers[0]);
1253 }
1254
1255 for (; l0_index < l0_ranges; ++l0_index) {
1256 addToBuffer<Alignment>(m * n, block_buffers[l0_index * l0_size], block_buffers[0]);
1257 }
1258 }
1259
1260 void applyOutputKernel() const {
1261 using OutputMapper = internal::blas_data_mapper<Scalar, Index, ColMajor>;
1262 evaluator->m_output_kernel(OutputMapper(result, m), evaluator->m_tensor_contraction_params,
1263 static_cast<Eigen::Index>(0), static_cast<Eigen::Index>(0), m, n);
1264 }
1265
1266 // Compute block size with accounting for potentially incomplete last block.
1267 Index actualBlockSize(Index block_idx) const {
1268 return block_idx + 1 < num_blocks ? block_size : k + block_size - block_size * num_blocks;
1269 }
1270
1271 // Compute range size with accounting for potentially incomplete last range.
1272 Index actualRangeSize(Index num_ranges, Index range_size, Index range_idx) const {
1273 eigen_assert(range_idx < num_ranges);
1274 return range_idx + 1 < num_ranges ? range_size : num_blocks + range_size - range_size * num_ranges;
1275 }
1276
1277 template <int Alignment>
1278 EIGEN_STRONG_INLINE static void addToBuffer(size_t n, const Scalar* src_buf, Scalar* tgt_buf) {
1279 const int output_packet_size = internal::unpacket_traits<PacketReturnType>::size;
1280 size_t i = 0;
1281 const size_t num_packets = n / output_packet_size;
1282 for (; i < output_packet_size * num_packets; i += output_packet_size) {
1283 const PacketReturnType src_val = internal::pload<PacketReturnType>(src_buf + i);
1284 const PacketReturnType tgt_val = internal::ploadt<PacketReturnType, Alignment>(tgt_buf + i);
1285 const PacketReturnType sum = internal::padd(src_val, tgt_val);
1286 internal::pstoret<Scalar, PacketReturnType, Alignment>(tgt_buf + i, sum);
1287 }
1288 for (; i < n; ++i) {
1289 tgt_buf[i] += src_buf[i];
1290 }
1291 }
1292
1293 template <int Alignment>
1294 EIGEN_STRONG_INLINE static void addAllToBuffer(size_t n, const Scalar* src_buf0, const Scalar* src_buf1,
1295 const Scalar* src_buf2, Scalar* dst_buf) {
1296 using ::Eigen::internal::padd;
1297 using ::Eigen::internal::pload;
1298 using ::Eigen::internal::ploadt;
1299 using ::Eigen::internal::pstoret;
1300
1301 const int output_packet_size = internal::unpacket_traits<PacketReturnType>::size;
1302
1303 size_t i = 0;
1304 const size_t num_packets = n / output_packet_size;
1305 for (; i < output_packet_size * num_packets; i += output_packet_size) {
1306 const auto src_val0 = pload<PacketReturnType>(src_buf0 + i);
1307 const auto src_val1 = pload<PacketReturnType>(src_buf1 + i);
1308 const auto src_val2 = pload<PacketReturnType>(src_buf2 + i);
1309
1310 const auto dst_val = ploadt<PacketReturnType, Alignment>(dst_buf + i);
1311 const auto sum = padd(padd(dst_val, src_val0), padd(src_val1, src_val2));
1312
1313 pstoret<Scalar, PacketReturnType, Alignment>(dst_buf + i, sum);
1314 }
1315 for (; i < n; ++i) {
1316 dst_buf[i] += src_buf0[i] + src_buf1[i] + src_buf2[i];
1317 }
1318 }
1319
1320 template <int Alignment>
1321 void eval(Barrier& barrier, Index start_block_idx, Index end_block_idx) {
1322 while (end_block_idx - start_block_idx > 1) {
1323 Index mid_block_idx = (start_block_idx + end_block_idx) / 2;
1324 evaluator->m_device.enqueue([this, &barrier, mid_block_idx, end_block_idx]() {
1325 eval<Alignment>(barrier, mid_block_idx, end_block_idx);
1326 });
1327 end_block_idx = mid_block_idx;
1328 }
1329
1330 Index block_idx = start_block_idx;
1331 Index block_start = block_idx * block_size;
1332 Index block_end = block_start + actualBlockSize(block_idx);
1333
1334 processBlock<Alignment>(block_idx, block_start, block_end);
1335 barrier.Notify();
1336 }
1337
1338 template <int Alignment>
1339 void evalAsync(Index start_block_idx, Index end_block_idx) {
1340 while (end_block_idx - start_block_idx > 1) {
1341 Index mid_block_idx = (start_block_idx + end_block_idx) / 2;
1342 evaluator->m_device.enqueue(
1343 [this, mid_block_idx, end_block_idx]() { evalAsync<Alignment>(mid_block_idx, end_block_idx); });
1344 end_block_idx = mid_block_idx;
1345 }
1346
1347 Index block_idx = start_block_idx;
1348
1349 Index block_start = block_idx * block_size;
1350 Index block_end = block_start + actualBlockSize(block_idx);
1351
1352 processBlock<Alignment>(block_idx, block_start, block_end);
1353
1354 int v = num_pending_blocks.fetch_sub(1);
1355 eigen_assert(v >= 1);
1356
1357 if (v == 1) {
1358 // Aggregate partial sums from l0 ranges.
1359 aggregateL0Blocks<Alignment>();
1360
1361 // Apply output kernel.
1362 applyOutputKernel();
1363
1364 // NOTE: If we call `done` callback before deleting this (context),
1365 // it might deallocate Self* pointer captured by context, and we'll
1366 // fail in destructor trying to deallocate temporary buffers.
1367
1368 // Move done call back from context before it will be destructed.
1369 DoneCallback done_copy = std::move(done);
1370
1371 // We are confident that we are the last one who touches context.
1372 delete this;
1373
1374 // Now safely call the done callback.
1375 done_copy();
1376 }
1377 }
1378
1379 EvalShardedByInnerDimContext(const EvalShardedByInnerDimContext&) = delete;
1380 void operator=(const EvalShardedByInnerDimContext&) = delete;
1381 };
1382
1383 // ------------------------------------------------------------------------ //
1384
1385 // Below are the function used by evalProductImpl heuristics, trying to select
1386 // optimal parameters for parallelization algorithm.
1387
1388 // Decide whether we want to shard m x n contraction by columns or by rows.
1389 static bool shardByCol(Index m, Index n, Index num_threads) {
1390 // Note: we are comparing both n and m against Traits::nr, it is not
1391 // a mistake. We are trying to figure out how both n and m will fit into
1392 // the main sharding dimension.
1393
1394 // Sharding by column is the default
1395 // ... unless there is enough data for vectorization over rows
1396 if (m / num_threads >= Traits::nr &&
1397 // and not enough data for vectorization over columns
1398 (n / num_threads < Traits::nr ||
1399 // ... or barely enough data for vectorization over columns,
1400 // but it is not evenly dividable across threads
1401 (n / num_threads < 4 * Traits::nr && (n % (num_threads * Traits::nr)) != 0 &&
1402 // ... and it is evenly dividable across threads for rows
1403 ((m % (num_threads * Traits::nr)) == 0 ||
1404 // .. or it is not evenly dividable for both dimensions but
1405 // there is much more data over rows so that corner effects are
1406 // mitigated.
1407 (m / n >= 6)))))
1408 return false;
1409 // Wait, or if matrices are just substantially prolonged over the other
1410 // dimension.
1411 if (n / num_threads < 16 * Traits::nr && m > n * 32) return false;
1412 return true;
1413 }
1414
1415 Index coarsenM(Index m, Index n, Index bm, Index bn, Index bk, Index gn, int num_threads, bool shard_by_col) const {
1416 Index gm = 1;
1417 Index gm1 = 1;
1418 Index nm0 = numext::div_ceil(m, bm);
1419 Index nm1 = nm0;
1420 for (;;) {
1421 // Find the next candidate for m grain size. It needs to result in
1422 // different number of blocks. E.g. if we have 10 kernels, we want to try
1423 // 5 and 10, but not 6, 7, 8 and 9.
1424 while (gm1 <= nm0 && nm1 == numext::div_ceil(nm0, gm1)) gm1++;
1425 if (gm1 > nm0) break;
1426 // Check the candidate.
1427 int res = checkGrain(m, n, bm, bn, bk, gm1, gn, gm, gn, num_threads, shard_by_col);
1428 if (res < 0) break;
1429 nm1 = numext::div_ceil(nm0, gm1);
1430 if (res == 0) continue;
1431 // Commit new grain size.
1432 gm = gm1;
1433 }
1434 return gm;
1435 }
1436
1437 Index coarsenN(Index m, Index n, Index bm, Index bn, Index bk, Index gm, int num_threads, bool shard_by_col) const {
1438 Index gn = 1;
1439 Index gn1 = 1;
1440 Index nn0 = numext::div_ceil(n, bn);
1441 Index nn1 = nn0;
1442 for (;;) {
1443 while (gn1 <= nn0 && nn1 == numext::div_ceil(nn0, gn1)) gn1++;
1444 if (gn1 > nn0) break;
1445 int res = checkGrain(m, n, bm, bn, bk, gm, gn1, gm, gn, num_threads, shard_by_col);
1446 if (res < 0) break;
1447 nn1 = numext::div_ceil(nn0, gn1);
1448 if (res == 0) continue;
1449 gn = gn1;
1450 }
1451 return gn;
1452 }
1453
1454 // checkGrain checks whether grain (gm, gn) is suitable and is better than
1455 // (oldgm, oldgn).
1456 int checkGrain(Index m, Index n, Index bm, Index bn, Index bk, Index gm, Index gn, Index oldgm, Index oldgn,
1457 int num_threads, bool shard_by_col) const {
1458 const TensorOpCost cost = contractionCost(bm * gm, bn * gn, bm, bn, bk, shard_by_col, true);
1459 double taskSize = TensorCostModel<ThreadPoolDevice>::taskSize(static_cast<double>(bm) * gm * bn * gn, cost);
1460 // If the task is too small, then we agree on it regardless of anything
1461 // else. Otherwise synchronization overheads will dominate.
1462 if (taskSize < 1) return 1;
1463 // If it is too large, then we reject it and all larger tasks.
1464 if (taskSize > 2) return -1;
1465 // Now we are in presumably good task size range.
1466 // The main deciding factor here is parallelism. Consider that we have 12
1467 // kernels and 4 threads. Grains of 2, 3 and 4 all yield good task sizes.
1468 // But 2/4 yield 6/3 tasks, which gives us parallelism of 0.75 (at most 3/4
1469 // of cores will be busy). While grain size 3 gives us 4 tasks, which gives
1470 // us parallelism of 1 (we can load all cores).
1471 Index nm0 = numext::div_ceil(m, bm);
1472 Index nn0 = numext::div_ceil(n, bn);
1473 Index new_tasks = numext::div_ceil(nm0, gm) * numext::div_ceil(nn0, gn);
1474 double new_parallelism =
1475 static_cast<double>(new_tasks) / (numext::div_ceil<Index>(new_tasks, num_threads) * num_threads);
1476 Index old_tasks = numext::div_ceil(nm0, oldgm) * numext::div_ceil(nn0, oldgn);
1477 double old_parallelism =
1478 static_cast<double>(old_tasks) / (numext::div_ceil<Index>(old_tasks, num_threads) * num_threads);
1479 if (new_parallelism > old_parallelism || new_parallelism == 1) return 1;
1480 return 0;
1481 }
1482
1483 TensorOpCost contractionCost(Index m, Index n, Index bm, Index bn, Index bk, bool shard_by_col,
1484 bool prepacked) const {
1485 const int packed_size = std::min<int>(PacketType<LhsScalar, Device>::size, PacketType<RhsScalar, Device>::size);
1486 const int output_packet_size = internal::unpacket_traits<PacketReturnType>::size;
1487 const double kd = static_cast<double>(bk);
1488 double compute_bandwidth = computeBandwidth(bm, bn, bk);
1489 // Computations.
1490 TensorOpCost cost = TensorOpCost(0, 0, kd * compute_bandwidth, true, packed_size);
1491 // Output stores.
1492 cost += TensorOpCost(0, sizeof(CoeffReturnType), 0, true, output_packet_size);
1493 if (prepacked) {
1494 // Packing and kernels are executed in different tasks. When we calculate
1495 // task grain size we look only at kernel cost assuming that kernel
1496 // is more expensive than packing.
1497 return cost;
1498 }
1499 // Lhs/rhs loads + computations.
1500 TensorOpCost lhsCost = this->m_leftImpl.costPerCoeff(true) * (kd / n);
1501 TensorOpCost rhsCost = this->m_rightImpl.costPerCoeff(true) * (kd / m);
1502 // Lhs packing memory cost does not contribute considerably to overall
1503 // execution time because lhs is prefetched early and accessed sequentially.
1504 if (shard_by_col)
1505 lhsCost.dropMemoryCost();
1506 else
1507 rhsCost.dropMemoryCost();
1508 return cost + lhsCost + rhsCost;
1509 }
1510
1511 // Decide whether we want to shard m x k x n contraction over the inner
1512 // (contraction) dimension (k).
1513 static bool shardByInnerDim(Index m, Index n, Index k, int num_threads, int num_threads_by_k) {
1514 std::ptrdiff_t bufsize = m * n * sizeof(Scalar);
1515 bool shard_by_k = false;
1516 if (n == 1 || // If mat*vec or...
1517 num_threads_by_k < 2 || // running single threaded or...
1518 num_threads_by_k < num_threads || // sharding by k gives less parallelism or...
1519 bufsize > l3CacheSize() / num_threads_by_k || // need more buffer space
1520 // than L3 cache or...
1521 k / num_threads_by_k < 2 * Traits::nr) { // k per thread is tiny.
1522 shard_by_k = false;
1523 } else if (numext::maxi(m, n) / num_threads < Traits::nr || // both other dimensions are tiny or...
1524 // k per thread is not small and...
1525 (k / num_threads_by_k > 8 * Traits::nr &&
1526 // one of the outer dimensions is tiny or sharding by k offers
1527 // more parallelism.
1528 (numext::mini(m, n) < 2 * Traits::nr || num_threads_by_k > num_threads))) {
1529 shard_by_k = true;
1530 }
1531 return shard_by_k;
1532 }
1533
1534 // Steps along the inner dimension in each block of a contraction sharded by that dimension for num_threads
1535 // threads. Cost model doesn't capture well the cost associated with constructing tensor contraction mappers and
1536 // computing loop bounds in gemm_pack_lhs and gemm_pack_rhs, so we specify minimum desired block size.
1537 static Index innerDimBlockSize(Index k, int num_threads) {
1538 // The underlying GEMM kernel assumes that k is a multiple of
1539 // the packet size and subtle breakage occurs if this is violated.
1540 const Index packet_size = internal::packet_traits<RhsScalar>::size;
1541 const auto round_up = [=](Index index) -> Index {
1542 const Index kmultiple = packet_size <= 8 ? 8 : packet_size;
1543 return numext::div_ceil<Index>(index, kmultiple) * kmultiple;
1544 };
1545
1546 const Index target_block_size = round_up(numext::div_ceil<Index>(k, num_threads));
1547 const Index desired_min_block_size = 12 * packet_size;
1548
1549 return numext::mini<Index>(k, numext::maxi<Index>(desired_min_block_size, target_block_size));
1550 }
1551
1552 // Estimated cycles for one step along the inner dimension of a contraction sharded by that dimension: packing
1553 // one lhs column and one rhs row, then m * n multiply-adds in the kernel.
1554 double contractionCostPerInnerDim(Index m, Index n) const {
1555 using CostModel = TensorCostModel<ThreadPoolDevice>;
1556 const int output_packet_size = internal::unpacket_traits<PacketReturnType>::size;
1557 // computeBandwidth() compares a kernel block with the register block (mr x nr). Here m and n are whole
1558 // dimensions, and the kernel loses its peak rate only when a lhs column is shorter than a packet.
1559 const double bandwidth = (m < output_packet_size) ? shortBlockComputeBandwidth() : peakComputeBandwidth();
1560 const TensorOpCost kernel_cost(0, 0, (bandwidth * m) * n, true, output_packet_size);
1561 // Packing loads and stores every coefficient once. The kernel amortizes a packed lhs column over only n
1562 // columns, so when n is small, packing costs as much as the kernel does.
1563 TensorOpCost pack_cost = this->m_leftImpl.costPerCoeff(true) * m + this->m_rightImpl.costPerCoeff(true) * n;
1564 pack_cost +=
1565 TensorOpCost(0, static_cast<double>(m) * sizeof(LhsScalar) + static_cast<double>(n) * sizeof(RhsScalar), 0);
1566 // Packing and the kernel run one after the other, so their times add.
1567 return CostModel::totalCost(1, kernel_cost) + CostModel::totalCost(1, pack_cost);
1568 }
1569
1570 // Number of blocks, each one a task, into which to shard a contraction by its inner dimension; 1 if sharding by
1571 // that dimension does not pay.
1572 int numThreadsInnerDim(Index m, Index n, Index k) const {
1573 using CostModel = TensorCostModel<ThreadPoolDevice>;
1574 const int output_packet_size = internal::unpacket_traits<PacketReturnType>::size;
1575 const double total_parallel_cost = k * contractionCostPerInnerDim(m, n);
1576 // Cost of reduction step accumulating the m*n per-thread buffers into the
1577 // result.
1578 const double reduction_cost = CostModel::totalCost(m * n, TensorOpCost(2, 1, 1, true, output_packet_size));
1579 // As in TensorCostModel::numThreads(), each thread needs at least kPerThreadCycles of work. It also needs more
1580 // than 8 * nr steps, or shardByInnerDim() rejects the sharding instead of using fewer threads.
1581 const double max_threads_by_work = total_parallel_cost / CostModel::kPerThreadCycles;
1582 const double max_threads_by_steps = static_cast<double>(k / (8 * Traits::nr + 1));
1583 const int max_threads = static_cast<int>(numext::mini<double>(
1584 this->m_device.numThreads(), numext::mini<double>(max_threads_by_work, max_threads_by_steps)));
1585 int num_threads = 1;
1586 double min_cost = total_parallel_cost;
1587 for (int nt = 2; nt <= max_threads; nt += 2) {
1588 // innerDimBlockSize() rounds the block size up and bounds it from below, so nt threads can get fewer than nt
1589 // blocks. Cost the blocks that run and return their number.
1590 const int num_blocks = internal::convert_index<int>(numext::div_ceil<Index>(k, innerDimBlockSize(k, nt)));
1591 const double parallel_cost =
1592 total_parallel_cost / num_blocks + CostModel::kStartupCycles + num_blocks * reduction_cost;
1593 if (parallel_cost < min_cost) {
1594 num_threads = num_blocks;
1595 min_cost = parallel_cost;
1596 }
1597 }
1598 return num_threads;
1599 }
1600
1601 static double peakComputeBandwidth() {
1602#ifdef EIGEN_VECTORIZE_FMA
1603 return 0.5;
1604#else
1605 // Bandwidth of all of VFMA/MULPS/ADDPS is 0.5 on latest Intel processors.
1606 // However for MULPS/ADDPS we have dependent sequence of 2 such
1607 // instructions,
1608 // so overall bandwidth is 1.0.
1609 return 1.0;
1610#endif
1611 }
1612
1613 // Bandwidth of a kernel block with too little data to vectorize, determined experimentally.
1614 static double shortBlockComputeBandwidth() { return 2.0; }
1615
1616 double computeBandwidth(Index bm, Index bn, Index bk) const {
1617 // Peak VFMA bandwidth is 0.5. However if we have not enough data for
1618 // vectorization bandwidth drops. The 4.0 and 2.0 bandwidth is determined
1619 // experimentally.
1620 if (bk == 1) return 4.0;
1621 if (bn < Traits::nr || bm < Traits::mr) return shortBlockComputeBandwidth();
1622 return peakComputeBandwidth();
1623 }
1624};
1625
1626} // end namespace Eigen
1627
1628#endif // EIGEN_USE_THREADS
1629#endif // EIGEN_TENSOR_TENSOR_CONTRACTION_THREAD_POOL_H
Definition TensorContraction.h:418
Namespace containing all symbols from the Eigen library.
The tensor evaluator class.
Definition TensorEvaluator.h:47