Zoltan2
Loading...
Searching...
No Matches
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
69namespace Zoltan2 {
70
85template <typename Adapter>
87{
88public:
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
244private:
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
313template <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
325template <typename Adapter>
326void 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
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition: Metric.cpp:74
Algorithm defines the base class for all algorithms.
A PartitioningSolution is a solution to a partitioning problem.
const RCP< const Comm< int > > & getCommunicator() const
Remap a new partition for maximum overlap with an input partition.
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.
const RCP< const Environment > & getEnvironment() const
Return the environment associated with the solution.
const gno_t * getRowIdsView() const
Returns list of global row IDs of the nonzeros owned by this process.
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.
const gno_t * getColIdsView() const
Returns list of global column IDs of the nonzeros owned by this process.
Just a placeholder for now.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:18
Created by mbenlioglu on Aug 31, 2020.
@ DETAILED_STATUS
sub-steps, each method's entry and exit
SparseMatrixAdapter_t::part_t part_t