Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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 
80 namespace Zoltan2{
81 
104 template<typename Adapter>
105 class MatrixPartitioningProblem : public Problem<Adapter>
106 {
107 public:
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;
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 
268 private:
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 
287 template <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 
309 template <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 
383 template <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 HELLO
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
Time an algorithm (or other entity) as a whole.
MatrixPartitioningProblem(Adapter *A, ParameterList *p, const RCP< const Teuchos::Comm< int > > &comm)
Constructor where Teuchos communicator is specified.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
MatrixPartitioningProblem sets up partitioning problems for the user.
MatrixPartitioningProblem(Adapter *A, ParameterList *p)
Constructor where communicator is the Teuchos default.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyDoubleValidator()
Exists to make setting up validators less cluttered.
sub-steps, each method&#39;s entry and exit
SparseMatrixAdapter_t::part_t part_t
Teuchos::ParameterList & getParametersNonConst()
Returns a reference to a non-const copy of the parameters.
A PartitioningSolution is a solution to a partitioning problem.
const PartitioningSolution< Adapter > & getSolution()
Get the solution to the problem.
BaseAdapterType
An enum to identify general types of adapters.
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
Defines the Problem base class.
The user parameters, debug, timing and memory profiling output objects, and error checking methods...
void solve(bool updateInputData=true)
Direct the problem to create a solution.
A PartitioningSolution is a solution to a partitioning problem.
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition: Metric.cpp:74