Zoltan2
Loading...
Searching...
No Matches
Zoltan2_AlgBlock.hpp
Go to the documentation of this file.
1// @HEADER
2//
3// ***********************************************************************
4//
5// Zoltan2: A package of combinatorial algorithms for scientific computing
6// Copyright 2012 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Karen Devine (kddevin@sandia.gov)
39// Erik Boman (egboman@sandia.gov)
40// Siva Rajamanickam (srajama@sandia.gov)
41//
42// ***********************************************************************
43//
44// @HEADER
45#ifndef _ZOLTAN2_ALGBLOCK_HPP_
46#define _ZOLTAN2_ALGBLOCK_HPP_
47
48#include <Zoltan2_Algorithm.hpp>
51
52#include <bitset>
53#include <sstream>
54#include <string>
55
60namespace Zoltan2{
61
71};
72
90template <typename Adapter>
91class AlgBlock : public Algorithm<Adapter>
92{
93
94private:
95 const RCP<const Environment> env;
96 const RCP<const Comm<int> > problemComm;
97 const RCP<const typename Adapter::base_adapter_t > adapter;
98
99public:
100 typedef typename Adapter::lno_t lno_t; // local ids
101 typedef typename Adapter::gno_t gno_t; // global ids
102 typedef typename Adapter::scalar_t scalar_t; // scalars
103 typedef typename Adapter::part_t part_t; // part numbers
104
105 // Constructor
107 const RCP<const Environment> &env_,
108 const RCP<const Comm<int> > &problemComm_,
109 const RCP<const typename Adapter::base_adapter_t > &adapter_
110 ) :
111 env(env_), problemComm(problemComm_), adapter(adapter_)
112 {}
113
114 // Partitioning method
115 void partition(const RCP<PartitioningSolution<Adapter> > &solution)
116 {
117 env->debug(DETAILED_STATUS, std::string("Entering AlgBlock"));
118
119 int rank = env->myRank_;
120 int nprocs = env->numProcs_;
121
123 // From the IdentifierModel we need:
124 // the number of gnos
125 // number of weights per gno
126 // the weights
127
128 modelFlag_t modelFlag;
129 IdentifierModel<typename Adapter::base_adapter_t> ids(adapter, env, problemComm, modelFlag);
130 size_t numGnos = ids.getLocalNumIdentifiers();
131
132 ArrayView<const gno_t> idList;
133 typedef StridedData<lno_t, scalar_t> input_t;
134 ArrayView<input_t> wgtList;
135
136 ids.getIdentifierList(idList, wgtList);
137
138 // If user supplied no weights, we use uniform weights.
139 bool uniformWeights = (wgtList.size() == 0);
140
142 // Partitioning problem parameters of interest:
143 // objective
144 // imbalance_tolerance
145
146 const Teuchos::ParameterList &pl = env->getParameters();
147 const Teuchos::ParameterEntry *pe;
148
149 pe = pl.getEntryPtr("partitioning_objective");
150 if (pe) {
151 std::string po = pe->getValue<std::string>(&po);
152 if (po == std::string("balance_object_count"))
153 uniformWeights = true; // User requests that we ignore weights
154 }
155
156 double imbalanceTolerance=1.1;
157 pe = pl.getEntryPtr("imbalance_tolerance");
158 if (pe) imbalanceTolerance = pe->getValue<double>(&imbalanceTolerance);
159
161 // From the Solution we get part information:
162 // number of parts and part sizes
163
164 size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
165
166 Array<scalar_t> part_sizes(numGlobalParts);
167
168 if (solution->criteriaHasUniformPartSizes(0))
169 for (unsigned int i=0; i<numGlobalParts; i++)
170 part_sizes[i] = 1.0 / numGlobalParts;
171 else
172 for (unsigned int i=0; i<numGlobalParts; i++)
173 part_sizes[i] = solution->getCriteriaPartSize(0, i);
174
175 for (unsigned int i=1; i<numGlobalParts; i++)
176 part_sizes[i] += part_sizes[i-1];
177
178 // TODO assertion that last part sizes is about equal to 1.0
179
180
182 // The algorithm
183 //
184 // Block partitioning algorithm lifted from zoltan/src/simple/block.c
185 // The solution is:
186 // a list of part numbers in gno order
187 // an imbalance for each weight
188
189 scalar_t wtsum(0);
190
191 if (!uniformWeights) {
192 for (size_t i=0; i<numGnos; i++)
193 wtsum += wgtList[0][i]; // [] operator knows stride
194 }
195 else
196 wtsum = static_cast<scalar_t>(numGnos);
197
198 Array<scalar_t> scansum(nprocs+1, 0);
199
200 Teuchos::gatherAll<int, scalar_t>(*problemComm, 1, &wtsum, nprocs,
201 scansum.getRawPtr()+1);
202
203 /* scansum = sum of weights on lower processors, excluding self. */
204
205 for (int i=2; i<=nprocs; i++)
206 scansum[i] += scansum[i-1];
207
208 scalar_t globalTotalWeight = scansum[nprocs];
209
210 if (env->getDebugLevel() >= VERBOSE_DETAILED_STATUS) {
211 std::ostringstream oss("Part sizes: ");
212 for (unsigned int i=0; i < numGlobalParts; i++)
213 oss << part_sizes[i] << " ";
214 oss << std::endl << std::endl << "Weights : ";
215 for (int i=0; i <= nprocs; i++)
216 oss << scansum[i] << " ";
217 oss << std::endl;
218 env->debug(VERBOSE_DETAILED_STATUS, oss.str());
219 }
220
221 /* Loop over objects and assign part. */
222 part_t part = 0;
223 wtsum = scansum[rank];
224 Array<scalar_t> partTotal(numGlobalParts, 0);
225 ArrayRCP<part_t> gnoPart= arcp(new part_t[numGnos], 0, numGnos);
226
227 env->memory("Block algorithm memory");
228
229 for (size_t i=0; i<numGnos; i++){
230 scalar_t gnoWeight = (uniformWeights ? 1.0 : wgtList[0][i]);
231 /* wtsum is now sum of all lower-ordered object */
232 /* determine new part number for this object,
233 using the "center of gravity" */
234 while (unsigned(part)<numGlobalParts-1 &&
235 (wtsum+0.5*gnoWeight) > part_sizes[part]*globalTotalWeight)
236 part++;
237 gnoPart[i] = part;
238 partTotal[part] += gnoWeight;
239 wtsum += gnoWeight;
240 }
241
243 // Done
244
245 solution->setParts(gnoPart);
246
247 env->debug(DETAILED_STATUS, std::string("Exiting AlgBlock"));
248 }
249};
250
251} // namespace Zoltan2
252
253#endif
Defines the IdentifierModel interface.
Defines the PartitioningSolution class.
Adapter::part_t part_t
AlgBlock(const RCP< const Environment > &env_, const RCP< const Comm< int > > &problemComm_, const RCP< const typename Adapter::base_adapter_t > &adapter_)
Adapter::gno_t gno_t
Adapter::scalar_t scalar_t
void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
Adapter::lno_t lno_t
Algorithm defines the base class for all algorithms.
IdentifierModel defines the interface for all identifier models.
size_t getIdentifierList(ArrayView< const gno_t > &Ids, ArrayView< input_t > &wgts) const
A PartitioningSolution is a solution to a partitioning problem.
The StridedData class manages lists of weights or coordinates.
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
@ DETAILED_STATUS
sub-steps, each method's entry and exit
@ VERBOSE_DETAILED_STATUS
include more detail about sub-steps
blockParams
The boolean parameters of interest to the Block algorithm.
@ block_balanceTotalMaximum
@ block_minMaximumWeight