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