Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_MappingProblem.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_MAPPINGPROBLEM_HPP_
51 #define _ZOLTAN2_MAPPINGPROBLEM_HPP_
52 
53 #include <Zoltan2_Standards.hpp>
54 
55 #include <Zoltan2_Problem.hpp>
59 
61 #include <Zoltan2_TaskMapping.hpp>
62 #include <string>
63 
64 namespace Zoltan2{
65 
67 
80 template<typename Adapter,
81  typename MachineRep = // Default MachineRep type
82  MachineRepresentation<typename Adapter::scalar_t,
83  typename Adapter::part_t> >
84 class MappingProblem : public Problem<Adapter>
85 {
86 public:
87 
88  typedef typename Adapter::scalar_t scalar_t;
89  typedef typename Adapter::gno_t gno_t;
90  typedef typename Adapter::lno_t lno_t;
91  typedef typename Adapter::user_t user_t;
92  typedef typename Adapter::part_t part_t;
94 
97 
100  virtual ~MappingProblem() {};
101 
104  MappingProblem(Adapter *A_, Teuchos::ParameterList *p_,
105  const Teuchos::RCP<const Teuchos::Comm<int> > &ucomm_,
106  partsoln_t *partition_ = NULL, MachineRep *machine_ = NULL) :
107  Problem<Adapter>(A_, p_, ucomm_)
108  {
109  HELLO;
110  createMappingProblem(partition_, machine_);
111  };
112 
113 #ifdef HAVE_ZOLTAN2_MPI
114 
116  MappingProblem(Adapter *A_, Teuchos::ParameterList *p_,
117  MPI_Comm mpicomm_,
118  partsoln_t *partition_ = NULL, MachineRep *machine_ = NULL) :
119  MappingProblem(A_, p_,
120  rcp<const Comm<int> >(new Teuchos::MpiComm<int>(
121  Teuchos::opaqueWrapper(mpicomm_))),
122  partition_, machine_)
123  {}
124 #endif
125 
127  //
128  // \param updateInputData If true this indicates that either
129  // this is the first attempt at solution, or that we
130  // are computing a new solution and the input data has
131  // changed since the previous solution was computed.
132  // If false, this indicates that we are computing a
133  // new solution using the same input data was used for
134  // the previous solution, even though the parameters
135  // may have been changed.
136  //
137  // For the sake of performance, we ask the caller to set \c updateInputData
138  // to false if he/she is computing a new solution using the same input data,
139  // but different problem parameters, than that which was used to compute
140  // the most recent solution.
141 
142  void solve(bool updateInputData=true);
143 
146  static void getValidParameters(ParameterList & pl)
147  {
149  RCP<Teuchos::StringValidator> mapping_algorithm_Validator =
150  Teuchos::rcp( new Teuchos::StringValidator(
151  Teuchos::tuple<std::string>( "geometric", "default", "block" )));
152  pl.set("mapping_algorithm", "default", "mapping algorithm",
153  mapping_algorithm_Validator);
154 
155 
156  // bool parameter
157  pl.set("distributed_input_adapter", true,
158  "Whether the input adapter for mapping is distributed over processes or not",
160 
161  // bool parameter
162  pl.set("divide_prime_first", false,
163  "When partitioning into-non power of two, whether to partition for nonpowers of two at the beginning, or at the end",
165 
166  //TODO: This should be positive integer validator.
167  pl.set("ranks_per_node", 1,
168  "The number of MPI ranks per node",
170  pl.set("reduce_best_mapping", true,
171  "If true, nodes will calculate different mappings with rotations, and best one will be reduced. If not, the result will be the one with longest dimension partitioning.",
173  }
174 
176  //
177  // \return the solution to the most recent solve().
178 
179  mapsoln_t *getSolution() { return soln.getRawPtr(); };
180  Teuchos::RCP<MachineRep> getMachine(){return machine; }
181 private:
182  void createMappingProblem(partsoln_t *partition_, MachineRep *machine_);
183 
184  Teuchos::RCP<mapsoln_t> soln;
185 
186  Teuchos::RCP<partsoln_t> partition;
187  Teuchos::RCP<MachineRep> machine;
188 };
189 
191 // createMappingProblem
192 // Method with common functionality for creating a MappingProblem.
193 // Individual constructors do appropriate conversions of input, etc.
194 // This method does everything that all constructors must do.
195 
196 template <typename Adapter, typename MachineRep>
197 void MappingProblem<Adapter, MachineRep>::createMappingProblem(
198  partsoln_t *partition_,
199  MachineRep *machine_)
200 {
201  HELLO;
202 
203  // Save pointer to user's partitioning solution. If not provided, create one.
204 
205  if (partition_) {
206  // User provided a partitioning solution; use it.
207  partition = Teuchos::rcp(partition_, false);
208  }
209  else {
210  // User did not provide a partitioning solution;
211  // Use input adapter to create a "fake" solution with the input partition.
212 
213  partition = rcp(new partsoln_t(this->env_, this->comm_,
214  this->inputAdapter_->getNumWeightsPerID()));
215  size_t nLocal = this->inputAdapter_->getLocalNumIDs();
216 
217  const part_t *inputPartsView = NULL;
218  this->inputAdapter_->getPartsView(inputPartsView);
219  if (nLocal && inputPartsView == NULL) {
220  // User has not provided input parts in input adapter
221  int me = this->comm_->getRank();
222  ArrayRCP<part_t> inputParts = arcp(new part_t[nLocal], 0, nLocal, true);
223  for (size_t i = 0; i < nLocal; i++) inputParts[i] = me;
224  partition->setParts(inputParts);
225  }
226  else {
227  // User has provided input parts; use those.
228  ArrayRCP<part_t> inputParts = arcp(const_cast<part_t *>(inputPartsView),
229  0, nLocal, false);
230  partition->setParts(inputParts);
231  }
232  }
233 
234  // Save pointer to user's machine. If not provided, create one.
235  if (machine_)
236  machine = Teuchos::rcp(machine_, false);
237  else {
238  try {
239  Teuchos::ParameterList pl = this->env_->getParameters();
240 
241  machine = Teuchos::rcp(new MachineRep(*(this->comm_), pl));
242  }
244  }
245 }
246 
248 template <typename Adapter, typename MachineRep>
250 {
251  HELLO;
252 
253 
254  // Determine which algorithm to use based on defaults and parameters.
255  std::string algName("block");
256 
257  Teuchos::ParameterList pl = this->env_->getParametersNonConst();
258  const Teuchos::ParameterEntry *pe = pl.getEntryPtr("mapping_algorithm");
259  if (pe) algName = pe->getValue<std::string>(&algName);
260 
261  try {
262  if (algName == "default") {
263  throw(NotImplemented(__FILE__, __LINE__, __func__zoltan2__));
264 #ifdef KDDKDD_NOT_READH
265  this->algorithm_ = rcp(new AlgDefaultMapping<Adapter,MachineRep>(
266  this->comm_, machine,
267  this->inputAdapter_,
268  partition, this->envConst_));
269  this->soln = rcp(new mapsoln_t(this->env_, this->comm_, this->algorithm_));
270  this->algorithm_->map(this->soln);
271 #endif
272  }
273  else if (algName == "block") {
274  this->algorithm_ = rcp(new AlgBlockMapping<Adapter,MachineRep>(
275  this->comm_, machine,
276  this->inputAdapter_,
277  partition, this->envConst_));
278  this->soln = rcp(new mapsoln_t(this->env_, this->comm_, this->algorithm_));
279  this->algorithm_->map(this->soln);
280  }
281  else if (algName == "geometric") {
282 
283  bool is_input_distributed = true;
284  const Teuchos::ParameterEntry *pe_input_adapter = pl.getEntryPtr("distributed_input_adapter");
285  if (pe_input_adapter) is_input_distributed = pe_input_adapter->getValue<bool>(&is_input_distributed);
286 
287 
288  int ranks_per_node = 1;
289  pe_input_adapter = pl.getEntryPtr("ranks_per_node");
290  if (pe_input_adapter) ranks_per_node = pe_input_adapter->getValue<int>(&ranks_per_node);
291 
292  bool divide_prime_first = false;
293  pe_input_adapter = pl.getEntryPtr("divide_prime_first");
294  if (pe_input_adapter) divide_prime_first = pe_input_adapter->getValue<bool>(&divide_prime_first);
295 
296  bool reduce_best_mapping = true;
297  pe_input_adapter = pl.getEntryPtr("reduce_best_mapping");
298  if (pe_input_adapter) reduce_best_mapping = pe_input_adapter->getValue<bool>(&reduce_best_mapping);
299 
300 
301 
302  this->algorithm_ =
303  rcp(new CoordinateTaskMapper<Adapter,part_t>(this->comm_,
304  machine,
305  this->inputAdapter_,
306  partition,
307  this->envConst_,
308  is_input_distributed, ranks_per_node, divide_prime_first, reduce_best_mapping));
309  this->soln = rcp(new mapsoln_t(this->env_, this->comm_, this->algorithm_));
310  this->algorithm_->map(this->soln);
311 
312  }
313  else {
314  // Add other mapping methods here
315  throw std::logic_error("specified mapping_algorithm not supported");
316  }
317  }
319 }
320 
321 } //namespace Zoltan2
322 
323 #endif
324 
325 #ifdef KDDKDD
326 Case 1
327 MappingProblem(
328  InputAdapter
329  partitioningSolution
330  MachineRepresentation=NULL
331 // KDD Don't know how to properly template MachineRepresentation. Proper types
332 // KDD probably depend on how it is to be used. I imagine MJ needs
333 // KDD pcoord_t to be scalar_t, right? But how does user know that at the
334 // KDD time he calls this constructor?
335 )
336 {
337  // Create MachineRepresentation if not provided
338  // User would have called partitioning problem and provides a solution
339  // Mapping vertices are the parts from the partitioning solution
340  // Create MappingSolution that can return getRankForPart(part)
341 }
342 
343 
344 Case 2
345 MappingProblem(
346  InputAdapter
347  MachineRepresentation=NULL
348 )
349 {
350  // Create MachineRepresentation if not provided
351  // Compute mapping vertices based on InputAdapter's partition
352  // Assuming input adapter's partition should be used.
353  // KDD would use with Exodus/Nemesis input files or PamGen meshes
354 
355 }
356 
357 
358 Case 3
359 MappingProblem(
360  InputAdapter
361  MachineRepresentation=NULL
362 )
363 {
364  // Create MachineRepresentation if not provided
365  // Call a partitioning algorithm to get mapping vertices that are the parts
366  // Mapping vertices are computed from this internal partitioning solution
367  // Maybe relevant models can be shared.
368  // Similar to what's in PartitioningProblem now and to what LibTopoMap does
369 
370 }
371 
372 
373 Case 4
374 MappingProblem(
375  InputAdapter
376  MachineRepresentation=NULL
377 )
378 {
379  // Create MachineRepresentation if not provided
380  // Call mapping with mapping vertices == IDs from the input adapter.
381  // Similar in spirit to previous case, but runs more slowly since current
382  // task mapping is done in serial.
383  // Mehmet has done experiments with Scotch, comparing case 3 with 4.
384  // Case 3 is faster; case 4 has higher quality.
385 
386 
387 }
388 
389 
390 In general, the applyPartitioningSolution method should take an
391 optional MappingSolution.
392 
393 Should MappingSolution provide a re-numbered communicator reflecting the new mapping?
394 
395 #endif
#define HELLO
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
PartitionMapping maps a solution or an input distribution to ranks.
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
Adapter::base_adapter_t base_adapter_t
void solve(bool updateInputData=true)
Direct the problem to create a solution.
Defines the PartitioningSolution class.
Define a simple mapping of parts to processors assuming parts.
mapsoln_t * getSolution()
Get the solution to the problem.
SparseMatrixAdapter_t::part_t part_t
MappingProblem(Adapter *A_, Teuchos::ParameterList *p_, const Teuchos::RCP< const Teuchos::Comm< int > > &ucomm_, partsoln_t *partition_=NULL, MachineRep *machine_=NULL)
Constructor that takes an Teuchos communicator.
A PartitioningSolution is a solution to a partitioning problem.
Exception thrown when a called base-class method is not implemented.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
Defines the Problem base class.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
MachineRepresentation Class Base class for representing machine coordinates, networks, etc.
MappingSolution< Adapter > mapsoln_t
Defines the MappingSolution class.
Gathering definitions used in software development.
PartitioningSolution< Adapter > partsoln_t
MappingProblem enables mapping of a partition (either computed or input) to MPI ranks.
Teuchos::RCP< MachineRep > getMachine()
virtual ~MappingProblem()
Destructor.
#define __func__zoltan2__
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition: Metric.cpp:74