Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_MatrixPartitioningSolution.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_MATRIXPARTITIONINGSOLUTION_HPP_
51 #define _ZOLTAN2_MATRIXPARTITIONINGSOLUTION_HPP_
52 
53 // namespace Zoltan2 {
54 // template <typename Adapter>
55 // class PartitioningSolution;
56 // }
57 
58 // #include <Zoltan2_Environment.hpp>
59 // #include <Zoltan2_Solution.hpp>
60 // #include <Zoltan2_GreedyMWM.hpp>
61 // #include <Zoltan2_Algorithm.hpp>
62 // #include <Zoltan2_CoordinatePartitioningGraph.hpp>
63 // #include <cmath>
64 // #include <algorithm>
65 // #include <vector>
66 // #include <limits>
67 
68 
69 namespace Zoltan2 {
70 
85 template <typename Adapter>
87 {
88 public:
89 
90 #ifndef DOXYGEN_SHOULD_SKIP_THIS
91  typedef typename Adapter::gno_t gno_t;
92  typedef typename Adapter::scalar_t scalar_t;
93  typedef typename Adapter::lno_t lno_t;
94  typedef typename Adapter::part_t part_t;
95  typedef typename Adapter::user_t user_t;
96 #endif
97 
113  MatrixPartitioningSolution( const RCP<const Environment> &env,
114  const RCP<const Comm<int> > &comm,
115  const RCP<Algorithm<Adapter> > &algorithm = Teuchos::null);
116 
117 
119  // Information that the algorithm may wish to query.
120 
122  // Method used by the algorithm to set results.
123 
138  void setIDLists(ArrayRCP<part_t> &rowIDs,ArrayRCP<part_t> &colIDs,
139  ArrayRCP<part_t> &domainIDs, ArrayRCP<part_t> &rangeIDs);
140 
142 
143  // TODO: Figure out if I want to do this
144  //
145  // /*! \brief Remap a new partition for maximum overlap with an input partition.
146  // *
147  // * Assumptions for this version:
148  // * input part assignment == processor rank for every local object.
149  // * assuming nGlobalParts <= num ranks
150  // * TODO: Write a version that takes the input part number as input;
151  // * this change requires input parts in adapters to be provided in
152  // * the Adapter.
153  // * TODO: For repartitioning, compare to old remapping results; see Zoltan1.
154  // */
155 
156  // void RemapParts();
157 
158  // ////////////////////////////////////////////////////////////////////
159  // /* Return the weight of objects staying with a given remap.
160  // * If remap is NULL, compute weight of objects staying with given partition
161  // */
162  // long measure_stays(part_t *remap, int *idx, part_t *adj, long *wgt,
163  // part_t nrhs, part_t nlhs)
164  // {
165  // long staying = 0;
166  // for (part_t i = 0; i < nrhs; i++) {
167  // part_t k = (remap ? remap[i] : i);
168  // for (part_t j = idx[k]; j < idx[k+1]; j++) {
169  // if (i == (adj[j]-nlhs)) {
170  // staying += wgt[j];
171  // break;
172  // }
173  // }
174  // }
175  // return staying;
176  // }
177 
179  // Results that may be queried by the user, by migration methods,
180  // or by metric calculation methods.
181  // We return raw pointers so users don't have to learn about our
182  // pointer wrappers.
183 
186  inline const RCP<const Comm<int> > &getCommunicator() const { return comm_;}
187 
190  inline const RCP<const Environment> &getEnvironment() const { return env_;}
191 
192 
195  const gno_t *getRowIdsView() const
196  {
197  if (rowIDs_.size() > 0)
198  return rowIDs_.getRawPtr();
199  else
200  return NULL;
201  }
202 
203 
206  const gno_t *getColIdsView() const
207  {
208  if (colIDs_.size() > 0)
209  return colIDs_.getRawPtr();
210  else
211  return NULL;
212  }
213 
214 
215  // /*! \brief Returns the process list corresponding to the global ID list.
216  // \return The return value is a NULL pointer if part IDs are
217  // synonomous with process IDs.
218  // */
219  // const int *getProcListView() const {
220  // if (procs_.size() > 0) return procs_.getRawPtr();
221  // else return NULL;
222  // }
223 
224 
225  // /*! \brief Get the processes containing a part.
226  // * \param partId a part number from 0 to one less than the global number
227  // * of parts.
228  // * \param procMin on return will be set to minimum proc number
229  // * \param procMax on return will be set to maximum proc number
230  // *
231  // * Normally \c procMin and \c procMax are the same value and a part
232  // * is assigned to one process. But if there are more processes than
233  // * parts, it's possible that a part will be divided across more than
234  // * one process.
235  // */
236  // void getProcsForPart(part_t partId, part_t &procMin, part_t &procMax) const
237  // {
238  // env_->localInputAssertion(__FILE__, __LINE__, "invalid part id",
239  // partId >= 0 && partId < nGlobalParts_, BASIC_ASSERTION);
240 
241  // partToProcsMap(partId, procMin, procMax);
242  // }
243 
244 private:
245 
246 
247  // void setPartDistribution();
248 
249  // void setPartSizes(ArrayView<ArrayRCP<part_t> > reqPartIds,
250  // ArrayView<ArrayRCP<scalar_t> > reqPartSizes);
251 
252  // void computePartSizes(int widx, ArrayView<part_t> ids,
253  // ArrayView<scalar_t> sizes);
254 
255  // void broadcastPartSizes(int widx);
256 
257 
258  RCP<const Environment> env_; // has application communicator
259  const RCP<const Comm<int> > comm_; // the problem communicator
260 
261  // part_t nGlobalParts_;// target global number of parts
262 
264  // The algorithm sets these values upon completion.
265 
266 
267  // There is a decision to made to decide what to store in the solution.
268  // 1. One possibility is to store part numbers for each local id. This
269  // is what was implemented for PartitioninSolution and this was advantageous
270  // for this case since (unlike 2) an extra communication was not needed
271  // after each process assigned its localids a part.
272  // 2. Alternatively, each process can store the set of ids that it owns. For 1D
273  // this would require an additional communication step to place the ids to the
274  // correct processor. This would also complicated the case where number of
275  // parts != number of processes. This is similar to what is needed to build
276  // row or column epetra/tpetra maps.
277  //
278  // However, things are more complicated for 2D Cartesian partitioning (maybe all
279  // of partitioning). In this case, we need to assign matrix nonzeros to both
280  // a process row and a process column. This means that extra communication will
281  // be needed for option #1 in order to determine both of these, which are needed
282  // to determine a part assignment for a given nonzero (or alternatively both the
283  // process rows and column assignments for a 2D block of matrix rows and columns,
284  // although this may complicated part assignment).
285  // This eliminates one of the advantages of method 1 vs. method 2.
286 
287  // For method 2 and 2D, each process would store the set of rowIDs and columnIDs
288  // for which it owns the nonzeros. Method 2 still
289  // has the disadvantage that it becomes more complicated for #parts != #procs.
290  // However, it would have what is needed to build both the row and column ids.
291  // For now, we are going with Method #2.
292 
293  // Need a plan to handle #parts != #procs
294 
295  ArrayRCP<gno_t> rowIDs_; // Row Ids assigned to this process
296  ArrayRCP<gno_t> colIDs_; // Col Ids assigned to this process
297 
298  ArrayRCP<gno_t> domainIDs_; // Domain vector Ids assigned to this process
299  ArrayRCP<gno_t> rangeIDs_; // Range vector Ids assigned to this process
300 
301 
302  bool haveSolution_;
303 
304 
306  // Algorithm used to compute the solution;
307  // Not sure if this is necessary
308  const RCP<Algorithm<Adapter> > algorithm_;
309 };
310 
313 template <typename Adapter>
315  const RCP<const Comm<int> > &comm, const RCP<Algorithm<Adapter> > &algorithm)
316  : env_(env), comm_(comm), rowIDs_(), colIDs_(), haveSolution_(false),
317  algorithm_(algorithm)
318 {
319  env_->memory("After construction of solution");
320 }
322 
325 template <typename Adapter>
326 void MatrixPartitioningSolution<Adapter>::setIDLists(ArrayRCP<part_t> &rowIDs,ArrayRCP<part_t> &colIDs,
327  ArrayRCP<part_t> &domainIDs, ArrayRCP<part_t> &rangeIDs)
328 {
329  env_->debug(DETAILED_STATUS, "Entering setParts");
330 
331  rowIDs_=rowIDs;
332  colIDs_=colIDs;
333  domainIDs_=domainIDs;
334  rangeIDs_=rangeIDs;
335 
336  haveSolution_ = true;
337 
338  env_->memory("After Solution has processed algorithm's answer");
339  env_->debug(DETAILED_STATUS, "Exiting setParts");
340 }
342 
343 
344 
345 
346 } // namespace Zoltan2
347 
348 #endif
Just a placeholder for now.
const RCP< const Comm< int > > & getCommunicator() const
Remap a new partition for maximum overlap with an input partition.
MatrixPartitioningSolution(const RCP< const Environment > &env, const RCP< const Comm< int > > &comm, const RCP< Algorithm< Adapter > > &algorithm=Teuchos::null)
Constructor when part sizes are not supplied.
void setIDLists(ArrayRCP< part_t > &rowIDs, ArrayRCP< part_t > &colIDs, ArrayRCP< part_t > &domainIDs, ArrayRCP< part_t > &rangeIDs)
The algorithm uses setIDLists to set the solution.
sub-steps, each method&#39;s entry and exit
SparseMatrixAdapter_t::part_t part_t
const gno_t * getRowIdsView() const
Returns list of global row IDs of the nonzeros owned by this process.
Algorithm defines the base class for all algorithms.
const gno_t * getColIdsView() const
Returns list of global column IDs of the nonzeros owned by this process.
const RCP< const Environment > & getEnvironment() const
Return the environment associated with the solution.
A PartitioningSolution is a solution to a partitioning problem.
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition: Metric.cpp:74