Zoltan2 Version of the Day
Zoltan2_AlgBlock.hpp
Go to the documentation of this file.
00001 // @HEADER
00002 //
00003 // ***********************************************************************
00004 //
00005 //   Zoltan2: A package of combinatorial algorithms for scientific computing
00006 //                  Copyright 2012 Sandia Corporation
00007 //
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Karen Devine      (kddevin@sandia.gov)
00039 //                    Erik Boman        (egboman@sandia.gov)
00040 //                    Siva Rajamanickam (srajama@sandia.gov)
00041 //
00042 // ***********************************************************************
00043 //
00044 // @HEADER
00045 #ifndef _ZOLTAN2_ALGBLOCK_HPP
00046 #define _ZOLTAN2_ALGBLOCK_HPP_
00047 
00048 #include <Zoltan2_IdentifierModel.hpp>
00049 #include <Zoltan2_PartitioningSolution.hpp>
00050 
00051 #include <sstream>
00052 #include <string>
00053 #include <bitset>
00054 
00059 typedef zoltan2_partId_t partId_t;
00060 
00061 namespace Zoltan2{
00062 
00065 enum blockParams{
00066   block_balanceCount,            
00067   block_balanceWeight,          
00068   block_minTotalWeight,      
00069   block_minMaximumWeight,  
00070   block_balanceTotalMaximum, 
00071   NUM_BLOCK_PARAMS
00072 };
00073 
00093 template <typename Adapter>
00094 void AlgBlock(
00095   const RCP<const Environment> &env,
00096   const RCP<Comm<int> > &problemComm,
00097   const RCP<const IdentifierModel<typename Adapter::base_adapter_t> > &ids, 
00098   RCP<PartitioningSolution<Adapter> > &solution
00099 ) 
00100 {
00101   using std::string;
00102   using std::ostringstream;
00103   typedef typename Adapter::lno_t lno_t;     // local ids
00104   typedef typename Adapter::gno_t gno_t;     // global ids
00105   typedef typename Adapter::scalar_t scalar_t;   // scalars
00106 
00107   env->debug(DETAILED_STATUS, string("Entering AlgBlock"));
00108 
00109   int rank = env->myRank_;
00110   int nprocs = env->numProcs_;
00111 
00113   // Partitioning problem parameters of interest:
00114   //    objective
00115   //    imbalance_tolerance
00116 
00117   std::bitset<NUM_BLOCK_PARAMS> params;
00118   double imbalanceTolerance=1.1;
00119 
00120   const Teuchos::ParameterList &pl = env->getParameters();
00121 
00122   const Teuchos::ParameterEntry *pe = pl.getEntryPtr("partitioning_objective");
00123 
00124   if (pe){
00125     string po;
00126     po = pe->getValue<string>(&po);
00127     if (po == string("balance_object_count"))
00128       params.set(block_balanceCount);
00129     else if (po == string("multicriteria_minimize_total_weight"))
00130       params.set(block_minTotalWeight);
00131     else if (po == string("multicriteria_minimize_maximum_weight"))
00132       params.set(block_minMaximumWeight);
00133     else if (po == string("multicriteria_balance_total_maximum"))
00134       params.set(block_balanceTotalMaximum);
00135   }
00136   else
00137     params.set(block_balanceWeight);
00138 
00139   pe = pl.getEntryPtr("imbalance_tolerance");
00140 
00141   if (pe)
00142     imbalanceTolerance = pe->getValue<double>(&imbalanceTolerance);
00143 
00145   // From the IdentifierModel we need:
00146   //    the number of gnos
00147   //    number of weights per gno
00148   //    the weights
00149 
00150   size_t numGnos = ids->getLocalNumIdentifiers();
00151 
00152   ArrayView<const gno_t> idList;
00153   typedef StridedData<lno_t, scalar_t> input_t;
00154   ArrayView<input_t> wgtList;
00155   
00156   ids->getIdentifierList(idList, wgtList);
00157 
00158   // If user supplied no weights, we use uniform weights.
00159   Array<input_t> uwArray(1);
00160   if (wgtList.size() == 0)
00161     wgtList = uwArray.view(0,1);
00162 
00163   bool uniformWeights = (wgtList[0].size() == 0);
00164 
00166   // From the Solution we get part information.
00167 
00168   size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
00169 
00170   size_t numLocalParts = solution->getLocalNumberOfParts();
00171 
00172   env->localInputAssertion(__FILE__, __LINE__, 
00173     "can only compute one part per proc",
00174     numLocalParts == 1, BASIC_ASSERTION);
00175   
00177   // The algorithm
00178   //
00179   // Block partitioning algorithm lifted from zoltan/src/simple/block.c
00180   // The solution is:
00181   //    a list of part numbers in gno order
00182   //    an imbalance for each weight 
00183 
00184   scalar_t wtsum(0);
00185 
00186   if (!uniformWeights){
00187     for (size_t i=0; i<numGnos; i++)
00188       wtsum += wgtList[0][i];          // [] operator knows stride
00189   }
00190   else
00191     wtsum = static_cast<scalar_t>(numGnos);
00192 
00193   Array<scalar_t> scansum(nprocs+1, 0);
00194 
00195   Teuchos::gatherAll<int, scalar_t>(*problemComm, 1, &wtsum, nprocs,
00196     scansum.getRawPtr()+1);
00197 
00198   /* scansum = sum of weights on lower processors, excluding self. */
00199 
00200   for (int i=2; i<=nprocs; i++)
00201     scansum[i] += scansum[i-1];
00202 
00203   scalar_t globalTotalWeight = scansum[nprocs];
00204 
00205   /* part_sizes - inclusive sum */
00206 
00207   Array<scalar_t> part_sizes(numGlobalParts);
00208 
00209   if (!solution->criteriaHasUniformPartSizes(0))
00210     for (unsigned int i=0; i<numGlobalParts; i++)
00211       part_sizes[i] = solution->getCriteriaPartSize(0, i);
00212   else
00213     for (unsigned int i=0; i<numGlobalParts; i++)
00214       part_sizes[i] = 1.0 / numGlobalParts;
00215 
00216   for (unsigned int i=1; i<numGlobalParts; i++)
00217     part_sizes[i] += part_sizes[i-1];
00218 
00219   // TODO assertion that last part sizes is about equal to 1.0
00220 
00221   if (env->getDebugLevel() >= VERBOSE_DETAILED_STATUS) {
00222     ostringstream oss("Part sizes: ");
00223     for (unsigned int i=0; i < numGlobalParts; i++)
00224       oss << part_sizes[i] << " ";
00225     oss << "\n";
00226     oss << std::endl << "Weights : ";
00227     for (int i=0; i <= nprocs; i++)
00228       oss << scansum[i] << " ";
00229     oss << "\n";
00230     env->debug(VERBOSE_DETAILED_STATUS, oss.str());
00231   }
00232 
00233   /* Loop over objects and assign partition. */
00234   partId_t part = 0;
00235   wtsum = scansum[rank];
00236   Array<scalar_t> partTotal(numGlobalParts, 0);
00237   ArrayRCP<partId_t> gnoPart= arcp(new partId_t [numGnos], 0, numGnos);
00238 
00239   env->memory("Block algorithm memory");
00240 
00241   for (size_t i=0; i<numGnos; i++){
00242     scalar_t gnoWeight = (uniformWeights ? 1.0 : wgtList[0][i]);
00243     /* wtsum is now sum of all lower-ordered object */
00244     /* determine new partition number for this object,
00245        using the "center of gravity" */
00246     while (unsigned(part)<numGlobalParts-1 && 
00247            (wtsum+0.5*gnoWeight) > part_sizes[part]*globalTotalWeight)
00248       part++;
00249     gnoPart[i] = part;
00250     partTotal[part] += gnoWeight;
00251     wtsum += gnoWeight;
00252   }
00253 
00255   // Done
00256 
00257   ArrayRCP<const gno_t> gnos = arcpFromArrayView(idList);
00258 
00259   solution->setParts(gnos, gnoPart, true);
00260 
00261   env->debug(DETAILED_STATUS, string("Exiting AlgBlock"));
00262 }
00263 
00264 }   // namespace Zoltan2
00265 
00266 #endif