Zoltan2
Loading...
Searching...
No Matches
Zoltan2_MatrixPartitioningProblem.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
50#ifndef _ZOLTAN2_MATRIXPARTITIONINGPROBLEM_HPP_
51#define _ZOLTAN2_MATRIXPARTITIONINGPROBLEM_HPP_
52
53#include <Zoltan2_Problem.hpp>
54// #include <Zoltan2_PartitioningAlgorithms.hpp>
57// #include <Zoltan2_EvaluatePartition.hpp>
58// #include <Zoltan2_GraphModel.hpp>
59// #include <Zoltan2_IdentifierModel.hpp>
60// #include <Zoltan2_IntegerRangeList.hpp>
61// #include <Zoltan2_MachineRepresentation.hpp>
62// #include <Zoltan2_AlgSerialGreedy.hpp>
63
64
65// TODO:
66//
67// Currently, we are implementing this matrix partitioning with several
68// constraining assumptions. We should try to relax several of these.
69// In the meantime, we should report errors otherwise
70//
71// Assumptions:
72// 1. 2D Cartesian partitioning (generalize to all 2D, 1D+2D)
73// 2. Number of row processes = number of column processes (eventually relax this)
74// 3. Number of processors is a square number -- follows from 2
75// 4. Number of parts == number of processors
76// 5. Only supports matrix adapter (eventually maybe add graph, hypergraph)
77
78
79
80namespace Zoltan2{
81
104template<typename Adapter>
105class MatrixPartitioningProblem : public Problem<Adapter>
106{
107public:
108
109 typedef typename Adapter::scalar_t scalar_t;
110 typedef typename Adapter::gno_t gno_t;
111 typedef typename Adapter::lno_t lno_t;
112 typedef typename Adapter::part_t part_t;
113 typedef typename Adapter::user_t user_t;
114 typedef typename Adapter::base_adapter_t base_adapter_t;
115
116
117 //TODO FIND WAY TO LIMIT THIS TO ONLY WORK WITH MATRIX ADAPTER FOR NOW
118
120 MatrixPartitioningProblem(Adapter *A, ParameterList *p,
121 const RCP<const Teuchos::Comm<int> > &comm):
122 Problem<Adapter>(A,p,comm), solution_(),
123 inputType_(InvalidAdapterType),
124 algName_()
125 {
126 for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
127 initializeProblem();
128
129
130 }
131
132#ifdef HAVE_ZOLTAN2_MPI
133 typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
136 MatrixPartitioningProblem(Adapter *A, ParameterList *p, MPI_Comm mpicomm):
138 rcp<const Comm<int> >(new Teuchos::MpiComm<int>(
139 Teuchos::opaqueWrapper(mpicomm))))
140 {
141 }
142
143
144 // Problem<Adapter>(A,p,comm), solution_(),
145 // inputType_(InvalidAdapterType),
146 // algName_()
147 // {
148 // for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
149 // initializeProblem();
150 // }
151#endif
152
154 MatrixPartitioningProblem(Adapter *A, ParameterList *p):
155 MatrixPartitioningProblem(A, p, Tpetra::getDefaultComm())
156 {
157
158 }
159
160
164
166 //
167 // \param updateInputData If true this indicates that either
168 // this is the first attempt at solution, or that we
169 // are computing a new solution and the input data has
170 // changed since the previous solution was computed.
171 // By input data we mean coordinates, topology, or weights.
172 // If false, this indicates that we are computing a
173 // new solution using the same input data was used for
174 // the previous solution, even though the parameters
175 // may have been changed.
176 //
177 // For the sake of performance, we ask the caller to set \c updateInputData
178 // to false if he/she is computing a new solution using the same input data,
179 // but different problem parameters, than that which was used to compute
180 // the most recent solution.
181
182 void solve(bool updateInputData=true );
183
185 //
186 // \return a reference to the solution to the most recent solve().
187
189 {
190 return *(solution_.getRawPtr());
191 };
192
195 static void getValidParameters(ParameterList & pl)
196 {
197 // Zoltan2_AlgMJ<Adapter>::getValidParameters(pl);
198 // AlgPuLP<Adapter>::getValidParameters(pl);
199 // AlgPTScotch<Adapter>::getValidParameters(pl);
200 // AlgSerialGreedy<Adapter>::getValidParameters(pl);
201 // AlgForTestingOnly<Adapter>::getValidParameters(pl);
202
203 // This set up does not use tuple because we didn't have constructors
204 // that took that many elements - Tuple will need to be modified and I
205 // didn't want to have low level changes with this particular refactor
206 // TO DO: Add more Tuple constructors and then redo this code to be
207 // Teuchos::tuple<std::string> algorithm_names( "rcb", "multijagged" ... );
208 Array<std::string> algorithm_names(1);
209 algorithm_names[0] = "2D Cartesian";
210 RCP<Teuchos::StringValidator> algorithm_Validator = Teuchos::rcp(
211 new Teuchos::StringValidator( algorithm_names ));
212 pl.set("algorithm", "2D Cartesian", "partitioning algorithm",
213 algorithm_Validator);
214
215
216 // TODO: create set of objectives for matrix partitioning: balance nonzeros, balance rows
217
218 // RCP<Teuchos::StringValidator> partitioning_objective_Validator =
219 // Teuchos::rcp( new Teuchos::StringValidator(
220 // Teuchos::tuple<std::string>( "balance_object_count",
221 // "balance_object_weight", "multicriteria_minimize_total_weight",
222 // "multicriteria_minimize_maximum_weight",
223 // "multicriteria_balance_total_maximum", "minimize_cut_edge_count",
224 // "minimize_cut_edge_weight", "minimize_neighboring_parts",
225 // "minimize_boundary_vertices" )));
226 // pl.set("partitioning_objective", "balance_object_weight",
227 // "objective of partitioning", partitioning_objective_Validator);
228
229 pl.set("imbalance_tolerance", 1.1, "imbalance tolerance, ratio of "
230 "maximum load over average load", Environment::getAnyDoubleValidator());
231
232 // num_global_parts >= 1
233 RCP<Teuchos::EnhancedNumberValidator<int>> num_global_parts_Validator =
234 Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(
235 1, Teuchos::EnhancedNumberTraits<int>::max()) ); // no maximum
236 pl.set("num_global_parts", 1, "global number of parts to compute "
237 "(0 means use the number of processes)", num_global_parts_Validator);
238
239 // num_local_parts >= 0
240 RCP<Teuchos::EnhancedNumberValidator<int>> num_local_parts_Validator =
241 Teuchos::rcp( new Teuchos::EnhancedNumberValidator<int>(
242 0, Teuchos::EnhancedNumberTraits<int>::max()) ); // no maximum
243 pl.set("num_local_parts", 0, "number of parts to compute for this "
244 "process (num_global_parts == sum of all num_local_parts)",
245 num_local_parts_Validator);
246
247 // RCP<Teuchos::StringValidator> partitioning_approach_Validator =
248 // Teuchos::rcp( new Teuchos::StringValidator(
249 // Teuchos::tuple<std::string>( "partition", "repartition",
250 // "maximize_overlap" )));
251 // pl.set("partitioning_approach", "partition", "Partition from scratch, "
252 // "partition incrementally from current partition, of partition from "
253 // "scratch but maximize overlap with the current partition",
254 // partitioning_approach_Validator);
255
256 //TODO do I need new matrix model
257
258 // RCP<Teuchos::StringValidator> model_Validator = Teuchos::rcp(
259 // new Teuchos::StringValidator(
260 // Teuchos::tuple<std::string>( "hypergraph", "graph",
261 // "geometry", "ids" )));
262 // pl.set("model", "graph", "This is a low level parameter. Normally the "
263 // "library will choose a computational model based on the algorithm or "
264 // "objective specified by the user.", model_Validator);
265
266 }
267
268private:
269 void initializeProblem();
270
271 void createPartitioningProblem(bool newData);
272
273 RCP<MatrixPartitioningSolution<Adapter> > solution_;
274
275 BaseAdapterType inputType_;
276
277 bool modelAvail_[MAX_NUM_MODEL_TYPES];
278
279 std::string algName_;
280
281};
283
284
287template <typename Adapter>
288 void MatrixPartitioningProblem<Adapter>::initializeProblem()
289{
290 HELLO;
291
292 this->env_->debug(DETAILED_STATUS, "MatrixPartitioningProblem::initializeProblem");
293
294 inputType_ = this->inputAdapter_->adapterType();
295
296 if(inputType_ != MatrixAdapterType)
297 {
298 // TODO: Better error support
299 std::cerr << "Error: only matrix adapter type supported" << std::endl;
300 return;
301 }
302
303 this->env_->memory("After initializeProblem");
304}
306
309template <typename Adapter>
311{
312 std::cout << "MatrixPartitioningProblem solve " << std::endl;
313
314
315 this->env_->debug(DETAILED_STATUS, "Entering solve");
316
317 // Create the computational model.
318
319 this->env_->timerStart(MACRO_TIMERS, "create problem");
320
321 createPartitioningProblem(updateInputData);
322
323 this->env_->timerStop(MACRO_TIMERS, "create problem");
324
325 // Create the solution. The algorithm will query the Solution
326 // for part and weight information. The algorithm will
327 // update the solution with part assignments and quality metrics.
328
329 // Create the algorithm
330 try
331 {
332
333
334 //TODO NEED to add if statement back once parameters work
335 // if (algName_ == std::string("2D Cartesian"))
336 // {
337
338 // this->algorithm_ = rcp(new AlgMatrix<Adapter>(this->envConst_,
339 // this->comm_,
340 // this->baseInputAdapter_));
341
342
343 this->algorithm_ = rcp(new AlgMatrix<Adapter>(this->envConst_,
344 this->comm_,
345 this->baseInputAdapter_));
346 // }
347 // else {
348 // throw std::logic_error("partitioning algorithm not supported");
349 // }
350 }
352
353 // Create the solution
354 this->env_->timerStart(MACRO_TIMERS, "create solution");
356
357 try{
359 this->envConst_, this->comm_,
360 this->algorithm_);
361 }
363
364 solution_ = rcp(soln);
365
366 this->env_->timerStop(MACRO_TIMERS, "create solution");
367 this->env_->memory("After creating Solution");
368
369 // Call the algorithm
370
371 try
372 {
373 this->algorithm_->partitionMatrix(solution_);
374 }
376
377 this->env_->debug(DETAILED_STATUS, "Exiting solve");
378}
380
383template <typename Adapter>
385{
386 this->env_->debug(DETAILED_STATUS,
387 "MatrixPartitioningProblem::createPartitioningProblem");
388
389 using Teuchos::ParameterList;
390
391 // A Problem object may be reused. The input data may have changed and
392 // new parameters or part sizes may have been set.
393 //
394 // Save these values in order to determine if we need to create a new model.
395
396 // bool prevModelAvail[MAX_NUM_MODEL_TYPES];
397 // for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
398 // {
399 // prevModelAvail[i] = modelAvail_[i];
400 // }
401
402
403 // for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
404 // {
405 // modelAvail_[i] = false;
406 // }
407
408
409 this->env_->debug(DETAILED_STATUS, " parameters");
410 Environment &env = *(this->env_);
411 ParameterList &pl = env.getParametersNonConst();
412 const Teuchos::ParameterEntry *pe;
413 std::string defString("default");
414
415 // Did the user specify a computational model?
416 // Should I allow a model to be created?
417
418 // std::string model(defString);
419 // pe = pl.getEntryPtr("model");
420 // if (pe)
421 // model = pe->getValue<std::string>(&model);
422
423
424 // Did the user specify an algorithm?
425
426 std::string algorithm(defString);
427 pe = pl.getEntryPtr("algorithm");
428 if (pe)
429 algorithm = pe->getValue<std::string>(&algorithm);
430
431 // Possible algorithm requirements that must be conveyed to the model:
432
434 // Determine algorithm, model, and algorithm requirements. This
435 // is a first pass. Feel free to change this and add to it.
436
437 if (algorithm != defString)
438 {
439
440 // Figure out the model required by the algorithm
441 if (algorithm == std::string("2D Cartesian"))
442 {
443 algName_ = algorithm;
444 }
445 else
446 {
447 // Parameter list should ensure this does not happen.
448 throw std::logic_error("parameter list algorithm is invalid");
449 }
450 }
451
452 // Object to be partitioned? (rows, columns, etc)
453
454 // Perhaps should set this
455
456 // std::string objectOfInterest(defString);
457 // pe = pl.getEntryPtr("objects_to_partition");
458 // if (pe)
459 // objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
460
461 this->env_->debug(DETAILED_STATUS, "createPartitioningProblem done");
462
463}
465
466
467} // namespace Zoltan2
468#endif
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
Defines the Problem base class.
#define HELLO
The user parameters, debug, timing and memory profiling output objects, and error checking methods.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyDoubleValidator()
Exists to make setting up validators less cluttered.
Teuchos::ParameterList & getParametersNonConst()
Returns a reference to a non-const copy of the parameters.
MatrixPartitioningProblem sets up partitioning problems for the user.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
MatrixPartitioningProblem(Adapter *A, ParameterList *p)
Constructor where communicator is the Teuchos default.
const PartitioningSolution< Adapter > & getSolution()
Get the solution to the problem.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
MatrixPartitioningProblem(Adapter *A, ParameterList *p, const RCP< const Teuchos::Comm< int > > &comm)
Constructor where Teuchos communicator is specified.
A PartitioningSolution is a solution to a partitioning problem.
A PartitioningSolution is a solution to a partitioning problem.
Problem base class from which other classes (PartitioningProblem, ColoringProblem,...
Created by mbenlioglu on Aug 31, 2020.
@ MAX_NUM_MODEL_TYPES
@ MACRO_TIMERS
Time an algorithm (or other entity) as a whole.
@ DETAILED_STATUS
sub-steps, each method's entry and exit
BaseAdapterType
An enum to identify general types of adapters.
@ InvalidAdapterType
unused value
@ MatrixAdapterType
matrix data