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