Kokkos Node API and Local Linear Algebra Kernels Version of the Day
TbbTsqr_Partitioner.hpp
00001 //@HEADER
00002 // ************************************************************************
00003 // 
00004 //          Kokkos: Node API and Parallel Node Kernels
00005 //              Copyright (2008) Sandia Corporation
00006 // 
00007 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00008 // the U.S. Government retains certain rights in this software.
00009 // 
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00038 // 
00039 // ************************************************************************
00040 //@HEADER
00041 
00042 #ifndef __TSQR_TBB_Partitioner_hpp
00043 #define __TSQR_TBB_Partitioner_hpp
00044 
00045 #include <Tsqr_MatView.hpp>
00046 
00047 #include <cstring> // size_t
00048 #include <sstream>
00049 #include <stdexcept>
00050 #include <utility>
00051 #include <vector>
00052 
00055 
00056 namespace TSQR {
00057   namespace TBB {
00058 
00059     template< class Ordinal, class Scalar >
00060     class Partitioner {
00061     private:
00062       bool
00063       should_split (const Ordinal nrows,
00064         const Ordinal ncols,
00065         const size_t num_partitions) const
00066       {
00067   using std::invalid_argument;
00068   using std::ostringstream;
00069 
00070   if (nrows < ncols)
00071     {
00072       ostringstream os;
00073       os << "Partitioner::should_split: nrows (= " << nrows 
00074          << ") < ncols (= " << ncols << ")";
00075       throw invalid_argument (os.str());
00076     }
00077   else if (num_partitions == 0)
00078     {
00079       ostringstream os;
00080       os << "Partitioner::should_split: nrows (= " << nrows 
00081          << ") < ncols (= " << ncols << ")";
00082       throw invalid_argument (os.str());
00083     }
00084   // FIXME (mfh 11 Jul 2010) Need more overflow checks here.
00085   return static_cast<size_t>(nrows) / num_partitions >= static_cast<size_t>(ncols);
00086       } 
00087 
00088     public:
00092       template< class MatrixViewType >
00093       std::pair< MatrixViewType, MatrixViewType >
00094       split (const MatrixViewType& A,
00095        const size_t P_first,
00096        const size_t P_mid,
00097        const size_t P_last,
00098        const bool contiguous_cache_blocks) const
00099       {
00100   typedef typename MatrixViewType::ordinal_type ordinal_type;
00101   typedef typename MatrixViewType::pointer_type pointer_type;
00102 
00103   const size_t num_partitions_top = P_mid - P_first + 1;
00104   //const size_t num_partitions_bottom = P_last - P_mid;
00105   const size_t num_partitions = P_last - P_first + 1;
00106   const ordinal_type nrows = A.nrows();
00107   const ordinal_type ncols = A.ncols();
00108   
00109   if (! should_split (nrows, ncols, num_partitions))
00110     return std::make_pair (MatrixViewType(A), MatrixViewType());
00111   else
00112     {
00113       const ordinal_type num_rows_partition = nrows / num_partitions;
00114       const ordinal_type remainder = nrows % num_partitions;
00115       
00116       // Top partition gets the remainder rows.  Doing the
00117       // multiplication before the division might make it more
00118       // likely to avoid truncating the fraction, but may cause
00119       // overflow of ordinal_type.  
00120       const ordinal_type num_rows_top = 
00121         num_rows_partition * num_partitions_top + remainder;
00122       const ordinal_type num_rows_bot = nrows - num_rows_top;
00123 
00124       // We don't call (Const)MatView::split_top(), because that
00125       // is for splitting off a single cache block.  Each half
00126       // of the split may contain more than one cache block.
00127       if (contiguous_cache_blocks)
00128         {
00129     pointer_type A_bot_ptr = A.get() + num_rows_top * ncols;
00130     MatrixViewType A_top (num_rows_top, ncols, A.get(), num_rows_top);
00131     MatrixViewType A_bot (num_rows_bot, ncols, A_bot_ptr, num_rows_bot);
00132     return std::make_pair (A_top, A_bot);
00133         }
00134       else
00135         {
00136     pointer_type A_bot_ptr = A.get() + num_rows_top;
00137     MatrixViewType A_top (num_rows_top, ncols, A.get(), A.lda());
00138     MatrixViewType A_bot (num_rows_bot, ncols, A_bot_ptr, A.lda());
00139     return std::make_pair (A_top, A_bot);
00140         }
00141     }
00142       }
00143     }; // class Partitioner
00144   } // namespace TBB
00145 } // namespace TSQR
00146 
00147 #endif // __TSQR_TBB_Partitioner_hpp
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends