Zoltan2
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 namespace Zoltan2{
00060 
00063 enum blockParams{
00064   block_balanceCount,            
00065   block_balanceWeight,          
00066   block_minTotalWeight,      
00067   block_minMaximumWeight,  
00068   block_balanceTotalMaximum, 
00069   NUM_BLOCK_PARAMS
00070 };
00071 
00090 template <typename Adapter>
00091 class AlgBlock {
00092 
00093 private:
00094   const RCP<const Environment> env;
00095   const RCP<Comm<int> > problemComm;
00096   const RCP<const IdentifierModel<typename Adapter::base_adapter_t> > ids;
00097   RCP<PartitioningSolution<Adapter> > solution;
00098 
00099 public:
00100   // Constructor
00101   AlgBlock(
00102     const RCP<const Environment> &env_,
00103     const RCP<Comm<int> > &problemComm_,
00104     const RCP<const IdentifierModel<typename Adapter::base_adapter_t> > &ids_, 
00105     RCP<PartitioningSolution<Adapter> > &solution_
00106   ) : 
00107     env(env_), problemComm(problemComm_), ids(ids_), solution(solution_)
00108   {}
00109 
00110   // Partitioning method
00111   void partition()
00112   {
00113     using std::string;
00114     using std::ostringstream;
00115 
00116     typedef typename Adapter::lno_t lno_t;     // local ids
00117     typedef typename Adapter::gno_t gno_t;     // global ids
00118     typedef typename Adapter::scalar_t scalar_t;   // scalars
00119     typedef typename Adapter::part_t part_t;   // part numbers
00120 
00121     env->debug(DETAILED_STATUS, string("Entering AlgBlock"));
00122 
00123     int rank = env->myRank_;
00124     int nprocs = env->numProcs_;
00125 
00127     // From the IdentifierModel we need:
00128     //    the number of gnos
00129     //    number of weights per gno
00130     //    the weights
00131 
00132     size_t numGnos = ids->getLocalNumIdentifiers();
00133 
00134     ArrayView<const gno_t> idList;
00135     typedef StridedData<lno_t, scalar_t> input_t;
00136     ArrayView<input_t> wgtList;
00137   
00138     ids->getIdentifierList(idList, wgtList);
00139 
00140     // If user supplied no weights, we use uniform weights.
00141     bool uniformWeights = (wgtList.size() == 0);
00142 
00144     // Partitioning problem parameters of interest:
00145     //    objective
00146     //    imbalance_tolerance
00147 
00148     const Teuchos::ParameterList &pl = env->getParameters();
00149     const Teuchos::ParameterEntry *pe;
00150 
00151     pe = pl.getEntryPtr("partitioning_objective");
00152     if (pe) {
00153       string po = pe->getValue<string>(&po);
00154       if (po == string("balance_object_count"))
00155         uniformWeights = true;    // User requests that we ignore weights
00156     }
00157 
00158     double imbalanceTolerance=1.1;
00159     pe = pl.getEntryPtr("imbalance_tolerance");
00160     if (pe) imbalanceTolerance = pe->getValue<double>(&imbalanceTolerance);
00161 
00163     // From the Solution we get part information:
00164     // number of parts and part sizes
00165 
00166     size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
00167 
00168     Array<scalar_t> part_sizes(numGlobalParts);
00169 
00170     if (solution->criteriaHasUniformPartSizes(0))
00171       for (unsigned int i=0; i<numGlobalParts; i++)
00172         part_sizes[i] = 1.0 / numGlobalParts;
00173     else
00174       for (unsigned int i=0; i<numGlobalParts; i++)
00175         part_sizes[i] = solution->getCriteriaPartSize(0, i);
00176 
00177     for (unsigned int i=1; i<numGlobalParts; i++)
00178       part_sizes[i] += part_sizes[i-1];
00179 
00180     // TODO assertion that last part sizes is about equal to 1.0
00181 
00182 
00184     // The algorithm
00185     //
00186     // Block partitioning algorithm lifted from zoltan/src/simple/block.c
00187     // The solution is:
00188     //    a list of part numbers in gno order
00189     //    an imbalance for each weight 
00190 
00191     scalar_t wtsum(0);
00192 
00193     if (!uniformWeights) {
00194       for (size_t i=0; i<numGnos; i++)
00195         wtsum += wgtList[0][i];          // [] operator knows stride
00196     }
00197     else
00198       wtsum = static_cast<scalar_t>(numGnos);
00199 
00200     Array<scalar_t> scansum(nprocs+1, 0);
00201 
00202     Teuchos::gatherAll<int, scalar_t>(*problemComm, 1, &wtsum, nprocs,
00203       scansum.getRawPtr()+1);
00204 
00205     /* scansum = sum of weights on lower processors, excluding self. */
00206 
00207     for (int i=2; i<=nprocs; i++)
00208       scansum[i] += scansum[i-1];
00209 
00210     scalar_t globalTotalWeight = scansum[nprocs];
00211 
00212     if (env->getDebugLevel() >= VERBOSE_DETAILED_STATUS) {
00213       ostringstream oss("Part sizes: ");
00214       for (unsigned int i=0; i < numGlobalParts; i++)
00215         oss << part_sizes[i] << " ";
00216       oss << std::endl << std::endl << "Weights : ";
00217       for (int i=0; i <= nprocs; i++)
00218         oss << scansum[i] << " ";
00219       oss << std::endl;
00220       env->debug(VERBOSE_DETAILED_STATUS, oss.str());
00221     }
00222 
00223     /* Loop over objects and assign part. */
00224     part_t part = 0;
00225     wtsum = scansum[rank];
00226     Array<scalar_t> partTotal(numGlobalParts, 0);
00227     ArrayRCP<part_t> gnoPart= arcp(new part_t[numGnos], 0, numGnos);
00228 
00229     env->memory("Block algorithm memory");
00230 
00231     for (size_t i=0; i<numGnos; i++){
00232       scalar_t gnoWeight = (uniformWeights ? 1.0 : wgtList[0][i]);
00233       /* wtsum is now sum of all lower-ordered object */
00234       /* determine new part number for this object,
00235          using the "center of gravity" */
00236       while (unsigned(part)<numGlobalParts-1 && 
00237              (wtsum+0.5*gnoWeight) > part_sizes[part]*globalTotalWeight)
00238         part++;
00239       gnoPart[i] = part;
00240       partTotal[part] += gnoWeight;
00241       wtsum += gnoWeight;
00242     }
00243 
00245     // Done
00246 
00247     ArrayRCP<const gno_t> gnos = arcpFromArrayView(idList);
00248     solution->setParts(gnos, gnoPart, true);
00249 
00250     env->debug(DETAILED_STATUS, string("Exiting AlgBlock"));
00251   }
00252 };
00253 
00254 }   // namespace Zoltan2
00255 
00256 #endif