Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_AlgQuotient.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 #ifndef _ZOLTAN2_ALGQUOTIENT_HPP_
46 #define _ZOLTAN2_ALGQUOTIENT_HPP_
47 
49 #include <Zoltan2_Algorithm.hpp>
51 #include <Zoltan2_Util.hpp>
52 
53 
56 //
57 // This algorithm
58 // - creates a CommGraphModel (communication graph model)
59 // - partitions the CommGraphModel using ParMETIS, and
60 // - transfers the solution (which is only stored on active ranks of
61 // CommGraphModel) to all MPI ranks.
62 //
63 // Please see model/Zoltan2_CommGraphModel.hpp for more details.
65 
66 namespace Zoltan2 {
67 
68 template <typename Adapter>
69 class AlgQuotient : public Algorithm<Adapter>
70 {
71 public:
73  typedef typename Adapter::part_t part_t;
74  typedef typename Adapter::user_t user_t;
75  typedef typename Adapter::userCoord_t userCoord_t;
77 
78 
86  AlgQuotient(const RCP<const Environment> &env__,
87  const RCP<const Comm<int> > &problemComm__,
88  const RCP<const IdentifierAdapter<user_t> > &adapter__,
89  const modelFlag_t& graphFlags_) :
90  env(env__), problemComm(problemComm__), adapter(adapter__), graphFlags(graphFlags_)
91  {
92  std::string errStr = "cannot build CommGraphModel from IdentifierAdapter, ";
93  errStr += "AlgQuotient requires Graph Adapter";
94  throw std::runtime_error(errStr);
95  }
96 
97  AlgQuotient(const RCP<const Environment> &env__,
98  const RCP<const Comm<int> > &problemComm__,
99  const RCP<const VectorAdapter<user_t> > &adapter__,
100  const modelFlag_t& graphFlags_) :
101  env(env__), problemComm(problemComm__), adapter(adapter__), graphFlags(graphFlags_)
102  {
103  std::string errStr = "cannot build CommGraphModel from VectorAdapter, ";
104  errStr += "AlgQuotient requires Graph Adapter";
105  throw std::runtime_error(errStr);
106  }
107 
108  AlgQuotient(const RCP<const Environment> &env__,
109  const RCP<const Comm<int> > &problemComm__,
110  const RCP<const MatrixAdapter<user_t,userCoord_t> > &adapter__,
111  const modelFlag_t& graphFlags_) :
112  env(env__), problemComm(problemComm__), adapter(adapter__), graphFlags(graphFlags_)
113  {
114  std::string errStr = "cannot build CommGraphModel from MatrixAdapter, ";
115  errStr += "AlgQuotient has not been implemented for Matrix Adapter yet.";
116  throw std::runtime_error(errStr);
117  }
118 
119  AlgQuotient(const RCP<const Environment> &env__,
120  const RCP<const Comm<int> > &problemComm__,
121  const RCP<const MeshAdapter<user_t> > &adapter__,
122  const modelFlag_t& graphFlags_) :
123  env(env__), problemComm(problemComm__), adapter(adapter__), graphFlags(graphFlags_)
124  {
125  std::string errStr = "cannot build CommGraphModel from MeshAdapter, ";
126  errStr += "AlgQuotient has not been implemented for Mesh Adapter yet.";
127  throw std::runtime_error(errStr);
128  }
129 
130  AlgQuotient(const RCP<const Environment> &env__,
131  const RCP<const Comm<int> > &problemComm__,
132  const RCP<const GraphAdapter<user_t,userCoord_t> > &adapter__,
133  const modelFlag_t& graphFlags_) :
134  env(env__), problemComm(problemComm__), adapter(adapter__), graphFlags(graphFlags_)
135  {
136  this->innerAlgorithm =
137  rcp(new AlgParMETIS<Adapter, graphModel_t>(env, problemComm, adapter, graphFlags));
138  }
139 
142  static void getValidParameters(ParameterList & pl)
143  {
144  pl.set("quotient_threshold", 1, "threshold for the number of vertices on the active ranks",
146  }
147 
148  void partition(const RCP<PartitioningSolution<Adapter> > &solution);
149  void migrateBack(const RCP<PartitioningSolution<Adapter> > &solution);
150 
151 private:
152 
153  const RCP<const Environment> env;
154  const RCP<const Comm<int> > problemComm;
155  const RCP<const base_adapter_t> adapter;
156  modelFlag_t graphFlags;
157 
158  RCP<Algorithm<Adapter>> innerAlgorithm; // algorithm to partition the quotient graph
159  RCP<PartitioningSolution<Adapter>> quotientSolution; // the solution stored on the active ranks
160 
161 };
162 
163 
165 template <typename Adapter>
167  const RCP<PartitioningSolution<Adapter> > &solution
168 )
169 {
170  HELLO;
171 
172  // Create a different object for pre-migration solution
173  PartitioningSolution<Adapter> *soln = NULL;
174  try{
175  soln = new PartitioningSolution<Adapter>(env, problemComm, 1);
176  }
178  quotientSolution = rcp(soln);
179 
180  try {
181  this->innerAlgorithm->partition(quotientSolution);
182  }
184 
185  // Migrate the solution
186  migrateBack(solution);
187 
188  env->memory("Zoltan2-Quotient: After creating solution");
189 
190 }
191 
192 // Pre-condition:
193 // The partitioning solution in quotientSolution is only stored on active MPI ranks,
194 // which is a single rank if commGraphModel has less than 'threshold_' vertices.
195 // Post-condition:
196 // The partitioning solution in output parameter 'solution' is distributed to all MPI ranks,
197 // so that each rank gets a partitioning vector with the size of the number of local vertices,
198 // and each entry in a goven rank should have the same part value.
199 template <typename Adapter>
201  const RCP<PartitioningSolution<Adapter> > &solution
202 )
203 {
204  const auto model = rcp(new CommGraphModel<base_adapter_t>(
205  this->adapter, this->env, this->problemComm));
206  int me = problemComm->getRank();
207  int nActiveRanks = model->getNumActiveRanks();
208  int dRank = model->getDestinationRank();
209 
210  // Receive the (single entry) partitioning solution for this MPI rank
211  Teuchos::ArrayRCP<part_t> parts(1);
212  RCP<CommRequest<int>> *requests = new RCP<CommRequest<int>>[1];
213  requests[0] = Teuchos::ireceive<int, part_t>(*problemComm, parts, dRank);
214  if (me < nActiveRanks) {
215 
216  const part_t *qtntSlnView = quotientSolution->getPartListView();
217 
218  int sRank = model->getStartRank();
219  int eRank = model->getEndRank();
220 
221  ArrayView<size_t> vtxdist;
222  model->getVertexDist(vtxdist);
223  for (int i = sRank; i < eRank; i++)
224  Teuchos::send<int, part_t>(*problemComm, 1, &qtntSlnView[i - sRank], i);
225  }
226  Teuchos::waitAll<int>(*problemComm, Teuchos::arrayView(requests, 1));
227 
228  // Extend the single-entry solution for all local vertices
229  size_t numLocalVertices = adapter->getLocalNumIDs();
230  Teuchos::ArrayRCP<part_t> extendedParts(numLocalVertices);
231  for(size_t i = 0; i < numLocalVertices; i++)
232  extendedParts[i] = parts[0];
233 
234  // Set the extended partitioning solution
235  solution->setParts(extendedParts);
236 
237 }
238 
239 
240 } // namespace Zoltan2
241 
243 
244 
245 #endif
246 
#define HELLO
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
IdentifierAdapter defines the interface for identifiers.
CommGraphModel< typename Adapter::base_adapter_t > graphModel_t
void migrateBack(const RCP< PartitioningSolution< Adapter > > &solution)
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
MatrixAdapter defines the adapter interface for matrices.
GraphAdapter defines the interface for graph-based user data.
MeshAdapter defines the interface for mesh input.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
AlgQuotient(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const MatrixAdapter< user_t, userCoord_t > > &adapter__, const modelFlag_t &graphFlags_)
AlgQuotient(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const MeshAdapter< user_t > > &adapter__, const modelFlag_t &graphFlags_)
Defines the PartitioningSolution class.
void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
SparseMatrixAdapter_t::part_t part_t
CommGraphModel defines the interface required for communication graph.
A PartitioningSolution is a solution to a partitioning problem.
VectorAdapter defines the interface for vector input.
Algorithm defines the base class for all algorithms.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
AlgQuotient(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const VectorAdapter< user_t > > &adapter__, const modelFlag_t &graphFlags_)
Adapter::userCoord_t userCoord_t
AlgQuotient(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const IdentifierAdapter< user_t > > &adapter__, const modelFlag_t &graphFlags_)
AlgQuotient(const RCP< const Environment > &env__, const RCP< const Comm< int > > &problemComm__, const RCP< const GraphAdapter< user_t, userCoord_t > > &adapter__, const modelFlag_t &graphFlags_)
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
A gathering of useful namespace methods.
Adapter::base_adapter_t base_adapter_t
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition: Metric.cpp:74