source: pacpussensors/trunk/Vislab/lib3dv/eigen/Eigen/src/Core/products/GeneralMatrixMatrix.h@ 136

Last change on this file since 136 was 136, checked in by ldecherf, 7 years ago

Doc
File size: 15.9 KB
Line 
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2009 Gael Guennebaud <gael.guennebaud@inria.fr>
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
10#ifndef EIGEN_GENERAL_MATRIX_MATRIX_H
11#define EIGEN_GENERAL_MATRIX_MATRIX_H
12
13namespace Eigen {
14
15namespace internal {
16
17template<typename _LhsScalar, typename _RhsScalar> class level3_blocking;
18
19/* Specialization for a row-major destination matrix => simple transposition of the product */
20template<
21 typename Index,
22 typename LhsScalar, int LhsStorageOrder, bool ConjugateLhs,
23 typename RhsScalar, int RhsStorageOrder, bool ConjugateRhs>
24struct general_matrix_matrix_product<Index,LhsScalar,LhsStorageOrder,ConjugateLhs,RhsScalar,RhsStorageOrder,ConjugateRhs,RowMajor>
25{
26 typedef typename scalar_product_traits<LhsScalar, RhsScalar>::ReturnType ResScalar;
27 static EIGEN_STRONG_INLINE void run(
28 Index rows, Index cols, Index depth,
29 const LhsScalar* lhs, Index lhsStride,
30 const RhsScalar* rhs, Index rhsStride,
31 ResScalar* res, Index resStride,
32 ResScalar alpha,
33 level3_blocking<RhsScalar,LhsScalar>& blocking,
34 GemmParallelInfo<Index>* info = 0)
35 {
36 // transpose the product such that the result is column major
37 general_matrix_matrix_product<Index,
38 RhsScalar, RhsStorageOrder==RowMajor ? ColMajor : RowMajor, ConjugateRhs,
39 LhsScalar, LhsStorageOrder==RowMajor ? ColMajor : RowMajor, ConjugateLhs,
40 ColMajor>
41 ::run(cols,rows,depth,rhs,rhsStride,lhs,lhsStride,res,resStride,alpha,blocking,info);
42 }
43};
44
45/* Specialization for a col-major destination matrix
46 * => Blocking algorithm following Goto's paper */
47template<
48 typename Index,
49 typename LhsScalar, int LhsStorageOrder, bool ConjugateLhs,
50 typename RhsScalar, int RhsStorageOrder, bool ConjugateRhs>
51struct general_matrix_matrix_product<Index,LhsScalar,LhsStorageOrder,ConjugateLhs,RhsScalar,RhsStorageOrder,ConjugateRhs,ColMajor>
52{
53
54typedef typename scalar_product_traits<LhsScalar, RhsScalar>::ReturnType ResScalar;
55static void run(Index rows, Index cols, Index depth,
56 const LhsScalar* _lhs, Index lhsStride,
57 const RhsScalar* _rhs, Index rhsStride,
58 ResScalar* res, Index resStride,
59 ResScalar alpha,
60 level3_blocking<LhsScalar,RhsScalar>& blocking,
61 GemmParallelInfo<Index>* info = 0)
62{
63 const_blas_data_mapper<LhsScalar, Index, LhsStorageOrder> lhs(_lhs,lhsStride);
64 const_blas_data_mapper<RhsScalar, Index, RhsStorageOrder> rhs(_rhs,rhsStride);
65
66 typedef gebp_traits<LhsScalar,RhsScalar> Traits;
67
68 Index kc = blocking.kc(); // cache block size along the K direction
69 Index mc = (std::min)(rows,blocking.mc()); // cache block size along the M direction
70 //Index nc = blocking.nc(); // cache block size along the N direction
71
72 gemm_pack_lhs<LhsScalar, Index, Traits::mr, Traits::LhsProgress, LhsStorageOrder> pack_lhs;
73 gemm_pack_rhs<RhsScalar, Index, Traits::nr, RhsStorageOrder> pack_rhs;
74 gebp_kernel<LhsScalar, RhsScalar, Index, Traits::mr, Traits::nr, ConjugateLhs, ConjugateRhs> gebp;
75
76#ifdef EIGEN_HAS_OPENMP
77 if(info)
78 {
79 // this is the parallel version!
80 Index tid = omp_get_thread_num();
81 Index threads = omp_get_num_threads();
82
83 std::size_t sizeA = kc*mc;
84 std::size_t sizeW = kc*Traits::WorkSpaceFactor;
85 ei_declare_aligned_stack_constructed_variable(LhsScalar, blockA, sizeA, 0);
86 ei_declare_aligned_stack_constructed_variable(RhsScalar, w, sizeW, 0);
87
88 RhsScalar* blockB = blocking.blockB();
89 eigen_internal_assert(blockB!=0);
90
91 // For each horizontal panel of the rhs, and corresponding vertical panel of the lhs...
92 for(Index k=0; k<depth; k+=kc)
93 {
94 const Index actual_kc = (std::min)(k+kc,depth)-k; // => rows of B', and cols of the A'
95
96 // In order to reduce the chance that a thread has to wait for the other,
97 // let's start by packing A'.
98 pack_lhs(blockA, &lhs(0,k), lhsStride, actual_kc, mc);
99
100 // Pack B_k to B' in a parallel fashion:
101 // each thread packs the sub block B_k,j to B'_j where j is the thread id.
102
103 // However, before copying to B'_j, we have to make sure that no other thread is still using it,
104 // i.e., we test that info[tid].users equals 0.
105 // Then, we set info[tid].users to the number of threads to mark that all other threads are going to use it.
106 while(info[tid].users!=0) {}
107 info[tid].users += threads;
108
109 pack_rhs(blockB+info[tid].rhs_start*actual_kc, &rhs(k,info[tid].rhs_start), rhsStride, actual_kc, info[tid].rhs_length);
110
111 // Notify the other threads that the part B'_j is ready to go.
112 info[tid].sync = k;
113
114 // Computes C_i += A' * B' per B'_j
115 for(Index shift=0; shift<threads; ++shift)
116 {
117 Index j = (tid+shift)%threads;
118
119 // At this point we have to make sure that B'_j has been updated by the thread j,
120 // we use testAndSetOrdered to mimic a volatile access.
121 // However, no need to wait for the B' part which has been updated by the current thread!
122 if(shift>0)
123 while(info[j].sync!=k) {}
124
125 gebp(res+info[j].rhs_start*resStride, resStride, blockA, blockB+info[j].rhs_start*actual_kc, mc, actual_kc, info[j].rhs_length, alpha, -1,-1,0,0, w);
126 }
127
128 // Then keep going as usual with the remaining A'
129 for(Index i=mc; i<rows; i+=mc)
130 {
131 const Index actual_mc = (std::min)(i+mc,rows)-i;
132
133 // pack A_i,k to A'
134 pack_lhs(blockA, &lhs(i,k), lhsStride, actual_kc, actual_mc);
135
136 // C_i += A' * B'
137 gebp(res+i, resStride, blockA, blockB, actual_mc, actual_kc, cols, alpha, -1,-1,0,0, w);
138 }
139
140 // Release all the sub blocks B'_j of B' for the current thread,
141 // i.e., we simply decrement the number of users by 1
142 for(Index j=0; j<threads; ++j)
143 {
144 #pragma omp atomic
145 info[j].users -= 1;
146 }
147 }
148 }
149 else
150#endif // EIGEN_HAS_OPENMP
151 {
152 EIGEN_UNUSED_VARIABLE(info);
153
154 // this is the sequential version!
155 std::size_t sizeA = kc*mc;
156 std::size_t sizeB = kc*cols;
157 std::size_t sizeW = kc*Traits::WorkSpaceFactor;
158
159 ei_declare_aligned_stack_constructed_variable(LhsScalar, blockA, sizeA, blocking.blockA());
160 ei_declare_aligned_stack_constructed_variable(RhsScalar, blockB, sizeB, blocking.blockB());
161 ei_declare_aligned_stack_constructed_variable(RhsScalar, blockW, sizeW, blocking.blockW());
162
163 // For each horizontal panel of the rhs, and corresponding panel of the lhs...
164 // (==GEMM_VAR1)
165 for(Index k2=0; k2<depth; k2+=kc)
166 {
167 const Index actual_kc = (std::min)(k2+kc,depth)-k2;
168
169 // OK, here we have selected one horizontal panel of rhs and one vertical panel of lhs.
170 // => Pack rhs's panel into a sequential chunk of memory (L2 caching)
171 // Note that this panel will be read as many times as the number of blocks in the lhs's
172 // vertical panel which is, in practice, a very low number.
173 pack_rhs(blockB, &rhs(k2,0), rhsStride, actual_kc, cols);
174
175 // For each mc x kc block of the lhs's vertical panel...
176 // (==GEPP_VAR1)
177 for(Index i2=0; i2<rows; i2+=mc)
178 {
179 const Index actual_mc = (std::min)(i2+mc,rows)-i2;
180
181 // We pack the lhs's block into a sequential chunk of memory (L1 caching)
182 // Note that this block will be read a very high number of times, which is equal to the number of
183 // micro vertical panel of the large rhs's panel (e.g., cols/4 times).
184 pack_lhs(blockA, &lhs(i2,k2), lhsStride, actual_kc, actual_mc);
185
186 // Everything is packed, we can now call the block * panel kernel:
187 gebp(res+i2, resStride, blockA, blockB, actual_mc, actual_kc, cols, alpha, -1, -1, 0, 0, blockW);
188 }
189 }
190 }
191}
192
193};
194
195/*********************************************************************************
196* Specialization of GeneralProduct<> for "large" GEMM, i.e.,
197* implementation of the high level wrapper to general_matrix_matrix_product
198**********************************************************************************/
199
200template<typename Lhs, typename Rhs>
201struct traits<GeneralProduct<Lhs,Rhs,GemmProduct> >
202 : traits<ProductBase<GeneralProduct<Lhs,Rhs,GemmProduct>, Lhs, Rhs> >
203{};
204
205template<typename Scalar, typename Index, typename Gemm, typename Lhs, typename Rhs, typename Dest, typename BlockingType>
206struct gemm_functor
207{
208 gemm_functor(const Lhs& lhs, const Rhs& rhs, Dest& dest, const Scalar& actualAlpha,
209 BlockingType& blocking)
210 : m_lhs(lhs), m_rhs(rhs), m_dest(dest), m_actualAlpha(actualAlpha), m_blocking(blocking)
211 {}
212
213 void initParallelSession() const
214 {
215 m_blocking.allocateB();
216 }
217
218 void operator() (Index row, Index rows, Index col=0, Index cols=-1, GemmParallelInfo<Index>* info=0) const
219 {
220 if(cols==-1)
221 cols = m_rhs.cols();
222
223 Gemm::run(rows, cols, m_lhs.cols(),
224 /*(const Scalar*)*/&m_lhs.coeffRef(row,0), m_lhs.outerStride(),
225 /*(const Scalar*)*/&m_rhs.coeffRef(0,col), m_rhs.outerStride(),
226 (Scalar*)&(m_dest.coeffRef(row,col)), m_dest.outerStride(),
227 m_actualAlpha, m_blocking, info);
228 }
229
230 protected:
231 const Lhs& m_lhs;
232 const Rhs& m_rhs;
233 Dest& m_dest;
234 Scalar m_actualAlpha;
235 BlockingType& m_blocking;
236};
237
238template<int StorageOrder, typename LhsScalar, typename RhsScalar, int MaxRows, int MaxCols, int MaxDepth, int KcFactor=1,
239bool FiniteAtCompileTime = MaxRows!=Dynamic && MaxCols!=Dynamic && MaxDepth != Dynamic> class gemm_blocking_space;
240
241template<typename _LhsScalar, typename _RhsScalar>
242class level3_blocking
243{
244 typedef _LhsScalar LhsScalar;
245 typedef _RhsScalar RhsScalar;
246
247 protected:
248 LhsScalar* m_blockA;
249 RhsScalar* m_blockB;
250 RhsScalar* m_blockW;
251
252 DenseIndex m_mc;
253 DenseIndex m_nc;
254 DenseIndex m_kc;
255
256 public:
257
258 level3_blocking()
259 : m_blockA(0), m_blockB(0), m_blockW(0), m_mc(0), m_nc(0), m_kc(0)
260 {}
261
262 inline DenseIndex mc() const { return m_mc; }
263 inline DenseIndex nc() const { return m_nc; }
264 inline DenseIndex kc() const { return m_kc; }
265
266 inline LhsScalar* blockA() { return m_blockA; }
267 inline RhsScalar* blockB() { return m_blockB; }
268 inline RhsScalar* blockW() { return m_blockW; }
269};
270
271template<int StorageOrder, typename _LhsScalar, typename _RhsScalar, int MaxRows, int MaxCols, int MaxDepth, int KcFactor>
272class gemm_blocking_space<StorageOrder,_LhsScalar,_RhsScalar,MaxRows, MaxCols, MaxDepth, KcFactor, true>
273 : public level3_blocking<
274 typename conditional<StorageOrder==RowMajor,_RhsScalar,_LhsScalar>::type,
275 typename conditional<StorageOrder==RowMajor,_LhsScalar,_RhsScalar>::type>
276{
277 enum {
278 Transpose = StorageOrder==RowMajor,
279 ActualRows = Transpose ? MaxCols : MaxRows,
280 ActualCols = Transpose ? MaxRows : MaxCols
281 };
282 typedef typename conditional<Transpose,_RhsScalar,_LhsScalar>::type LhsScalar;
283 typedef typename conditional<Transpose,_LhsScalar,_RhsScalar>::type RhsScalar;
284 typedef gebp_traits<LhsScalar,RhsScalar> Traits;
285 enum {
286 SizeA = ActualRows * MaxDepth,
287 SizeB = ActualCols * MaxDepth,
288 SizeW = MaxDepth * Traits::WorkSpaceFactor
289 };
290
291 EIGEN_ALIGN16 LhsScalar m_staticA[SizeA];
292 EIGEN_ALIGN16 RhsScalar m_staticB[SizeB];
293 EIGEN_ALIGN16 RhsScalar m_staticW[SizeW];
294
295 public:
296
297 gemm_blocking_space(DenseIndex /*rows*/, DenseIndex /*cols*/, DenseIndex /*depth*/)
298 {
299 this->m_mc = ActualRows;
300 this->m_nc = ActualCols;
301 this->m_kc = MaxDepth;
302 this->m_blockA = m_staticA;
303 this->m_blockB = m_staticB;
304 this->m_blockW = m_staticW;
305 }
306
307 inline void allocateA() {}
308 inline void allocateB() {}
309 inline void allocateW() {}
310 inline void allocateAll() {}
311};
312
313template<int StorageOrder, typename _LhsScalar, typename _RhsScalar, int MaxRows, int MaxCols, int MaxDepth, int KcFactor>
314class gemm_blocking_space<StorageOrder,_LhsScalar,_RhsScalar,MaxRows, MaxCols, MaxDepth, KcFactor, false>
315 : public level3_blocking<
316 typename conditional<StorageOrder==RowMajor,_RhsScalar,_LhsScalar>::type,
317 typename conditional<StorageOrder==RowMajor,_LhsScalar,_RhsScalar>::type>
318{
319 enum {
320 Transpose = StorageOrder==RowMajor
321 };
322 typedef typename conditional<Transpose,_RhsScalar,_LhsScalar>::type LhsScalar;
323 typedef typename conditional<Transpose,_LhsScalar,_RhsScalar>::type RhsScalar;
324 typedef gebp_traits<LhsScalar,RhsScalar> Traits;
325
326 DenseIndex m_sizeA;
327 DenseIndex m_sizeB;
328 DenseIndex m_sizeW;
329
330 public:
331
332 gemm_blocking_space(DenseIndex rows, DenseIndex cols, DenseIndex depth)
333 {
334 this->m_mc = Transpose ? cols : rows;
335 this->m_nc = Transpose ? rows : cols;
336 this->m_kc = depth;
337
338 computeProductBlockingSizes<LhsScalar,RhsScalar,KcFactor>(this->m_kc, this->m_mc, this->m_nc);
339 m_sizeA = this->m_mc * this->m_kc;
340 m_sizeB = this->m_kc * this->m_nc;
341 m_sizeW = this->m_kc*Traits::WorkSpaceFactor;
342 }
343
344 void allocateA()
345 {
346 if(this->m_blockA==0)
347 this->m_blockA = aligned_new<LhsScalar>(m_sizeA);
348 }
349
350 void allocateB()
351 {
352 if(this->m_blockB==0)
353 this->m_blockB = aligned_new<RhsScalar>(m_sizeB);
354 }
355
356 void allocateW()
357 {
358 if(this->m_blockW==0)
359 this->m_blockW = aligned_new<RhsScalar>(m_sizeW);
360 }
361
362 void allocateAll()
363 {
364 allocateA();
365 allocateB();
366 allocateW();
367 }
368
369 ~gemm_blocking_space()
370 {
371 aligned_delete(this->m_blockA, m_sizeA);
372 aligned_delete(this->m_blockB, m_sizeB);
373 aligned_delete(this->m_blockW, m_sizeW);
374 }
375};
376
377} // end namespace internal
378
379template<typename Lhs, typename Rhs>
380class GeneralProduct<Lhs, Rhs, GemmProduct>
381 : public ProductBase<GeneralProduct<Lhs,Rhs,GemmProduct>, Lhs, Rhs>
382{
383 enum {
384 MaxDepthAtCompileTime = EIGEN_SIZE_MIN_PREFER_FIXED(Lhs::MaxColsAtCompileTime,Rhs::MaxRowsAtCompileTime)
385 };
386 public:
387 EIGEN_PRODUCT_PUBLIC_INTERFACE(GeneralProduct)
388
389 typedef typename Lhs::Scalar LhsScalar;
390 typedef typename Rhs::Scalar RhsScalar;
391 typedef Scalar ResScalar;
392
393 GeneralProduct(const Lhs& lhs, const Rhs& rhs) : Base(lhs,rhs)
394 {
395#if !(defined(EIGEN_NO_STATIC_ASSERT) && defined(EIGEN_NO_DEBUG))
396 typedef internal::scalar_product_op<LhsScalar,RhsScalar> BinOp;
397 EIGEN_CHECK_BINARY_COMPATIBILIY(BinOp,LhsScalar,RhsScalar);
398#endif
399 }
400
401 template<typename Dest> void scaleAndAddTo(Dest& dst, const Scalar& alpha) const
402 {
403 eigen_assert(dst.rows()==m_lhs.rows() && dst.cols()==m_rhs.cols());
404 if(m_lhs.cols()==0 || m_lhs.rows()==0 || m_rhs.cols()==0)
405 return;
406
407 typename internal::add_const_on_value_type<ActualLhsType>::type lhs = LhsBlasTraits::extract(m_lhs);
408 typename internal::add_const_on_value_type<ActualRhsType>::type rhs = RhsBlasTraits::extract(m_rhs);
409
410 Scalar actualAlpha = alpha * LhsBlasTraits::extractScalarFactor(m_lhs)
411 * RhsBlasTraits::extractScalarFactor(m_rhs);
412
413 typedef internal::gemm_blocking_space<(Dest::Flags&RowMajorBit) ? RowMajor : ColMajor,LhsScalar,RhsScalar,
414 Dest::MaxRowsAtCompileTime,Dest::MaxColsAtCompileTime,MaxDepthAtCompileTime> BlockingType;
415
416 typedef internal::gemm_functor<
417 Scalar, Index,
418 internal::general_matrix_matrix_product<
419 Index,
420 LhsScalar, (_ActualLhsType::Flags&RowMajorBit) ? RowMajor : ColMajor, bool(LhsBlasTraits::NeedToConjugate),
421 RhsScalar, (_ActualRhsType::Flags&RowMajorBit) ? RowMajor : ColMajor, bool(RhsBlasTraits::NeedToConjugate),
422 (Dest::Flags&RowMajorBit) ? RowMajor : ColMajor>,
423 _ActualLhsType, _ActualRhsType, Dest, BlockingType> GemmFunctor;
424
425 BlockingType blocking(dst.rows(), dst.cols(), lhs.cols());
426
427 internal::parallelize_gemm<(Dest::MaxRowsAtCompileTime>32 || Dest::MaxRowsAtCompileTime==Dynamic)>(GemmFunctor(lhs, rhs, dst, actualAlpha, blocking), this->rows(), this->cols(), Dest::Flags&RowMajorBit);
428 }
429};
430
431} // end namespace Eigen
432
433#endif // EIGEN_GENERAL_MATRIX_MATRIX_H
Note: See TracBrowser for help on using the repository browser.