Zoltan2
Zoltan2_AlgBlockMapping.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_ALGBLOCKMAPPING_HPP_
46 #define _ZOLTAN2_ALGBLOCKMAPPING_HPP_
47 
48 #include <Zoltan2_Standards.hpp>
49 #include <Zoltan2_Algorithm.hpp>
51 #include <Zoltan2_Util.hpp>
52 #include <Tpetra_Map.hpp>
53 #include <set>
54 
55 
59 // are contiguously numbered from 0 to nParts-1
60 // This use case is common; because it requires no explicit storage
61 // of the parts to ranks,
62 // we separate it from methods that do need extra storage.
64 
65 namespace Zoltan2 {
66 
67 template <typename Adapter, typename MachineRep>
68 class AlgBlockMapping : public Algorithm<Adapter>
69 {
70 
71 private:
72 
73  typedef typename Adapter::lno_t lno_t;
74  typedef typename Adapter::gno_t gno_t;
75  typedef typename Adapter::scalar_t scalar_t;
76  typedef typename Adapter::part_t part_t;
77  typedef typename Adapter::user_t user_t;
78  typedef typename Adapter::userCoord_t userCoord_t;
79 
80 public:
81 
88  const Teuchos::RCP <const Teuchos::Comm<int> > &comm_,
89  const Teuchos::RCP <const MachineRep> &machine_,
90  const Teuchos::RCP <const Adapter> &adapter_,
91  const Teuchos::RCP <const Zoltan2::PartitioningSolution<Adapter> > &psoln_,
92  const Teuchos::RCP <const Environment> &envConst):
93  nRanks(comm_->getSize()), myRank(comm_->getRank()),
94  nMyParts(0), myParts(Teuchos::null)
95  {
96  // Get set of parts from partitioning solution or adapter, if provided
97  // Otherwise, we'll assume set of parts == set of ranks
98  const part_t *partList;
99  if (psoln_ != Teuchos::null) {
100  partList = psoln_->getPartListView();
101  }
102  else {
103  adapter_->getPartsView(partList);
104  }
105 
106  // Compute maxPart, nParts
107 
108  part_t minPart, maxPart;
109 
110  if (partList == NULL) {
111  // Parts for IDs are the same as ranks
112  nParts = nRanks;
113  maxPart = nRanks-1;
114  minPart = 0;
115  }
116  else {
117  // Parts were provided by partitioning solution or input adapter
118 
119  // Find unique parts on this rank,
120  // as Tpetra::Map does not like duplicate GIDs within a rank
121 
122  size_t nLocal = adapter_->getLocalNumIDs();
123 
124  std::set<part_t> unique;
125  for (size_t i = 0; i < nLocal; i++)
126  unique.insert(partList[i]);
127 
128  size_t nUnique = unique.size();
129  Array<part_t> uniquePartList(nUnique);
130  size_t k = 0;
131  for (typename std::set<part_t>::iterator it = unique.begin();
132  it != unique.end(); it++)
133  uniquePartList[k++] = *it;
134 
135  // Use Tpetra::Map to find the max, min, total part.
136 
137  // KDDKDD TODO: As is, building a map with GO=part_t will break
138  // KDDKDD TODO: ETI builds without GO=int.
139  // KDDKDD TODO: Maybe part_t needs to be Tpetra::Map<>::gno_t?
140 
141  global_size_t nGlobalElts =
142  Teuchos::OrdinalTraits<Tpetra::global_size_t>::invalid();
143  Tpetra::Map<lno_t, part_t> tmap(nGlobalElts, uniquePartList(), 0, comm_);
144 
145  nParts = Teuchos::as<part_t>(tmap.getGlobalNumElements());
146  minPart = tmap.getMinAllGlobalIndex();
147  maxPart = tmap.getMaxAllGlobalIndex();
148  }
149 
150  // Determine number of unique parts, as well as min and max part
151  // Can probably use a Tpetra Map.
152 
153  if ((minPart != 0) || (maxPart != nParts-1)) {
154  // Cannot use this mapping method
155  throw std::runtime_error("Cannot use mapping_algorithm = contiguous "
156  "unless parts are numbered from 0 to nParts-1");
157  }
158 
160  }
161 
163  // submethod of the default
164  // Assume that calling method has already confirmed assumptions
165  // about part numbering.
167  const Teuchos::RCP <const Teuchos::Comm<int> > comm_,
168  const part_t nparts) :
169  nRanks(comm_->getSize()),
170  nParts(nparts),
171  myRank(comm_->getRank()),
172  nMyParts(0),
173  myParts(Teuchos::null)
174  {
176  }
177 
179  {
180  nParts_Div_nRanks = nParts / nRanks;
181  nParts_Mod_nRanks = nParts % nRanks;
182  nMyParts = nParts_Div_nRanks + (myRank < nParts_Mod_nRanks);
183  }
184 
185  void map(const Teuchos::RCP<MappingSolution<Adapter> > &msoln) {
186  // Mapping is computed implicitly;
187  // nothing to do here since we implement
188  // getRankForPart and getMyPartsView.
189  }
190 
191  int getRankForPart(part_t p) {
192  if (p < 0 || p >= nParts)
193  throw std::runtime_error("Invalid part in getRankForPart");
194 
195  int tmp = p / nParts_Div_nRanks;
196  while (firstPart(tmp) > p) tmp--;
197  while (firstPart(tmp+1) < p) tmp++;
198  return tmp;
199  }
200 
201  void getMyPartsView(part_t &numParts, part_t *&parts)
202  {
203  // Will need to construct the arrays if this function is called.
204  // Will not work if this is a const method.
205  numParts = nMyParts;
206  if (nMyParts) {
207  if (myParts == Teuchos::null) {
208  myParts = arcp(new part_t[nMyParts], 0, nMyParts, true);
209  for (part_t i = 0; i < nMyParts; i++)
210  myParts[i] = firstPart(myRank) + i;
211  }
212  parts = myParts.getRawPtr();
213  }
214  else
215  parts = NULL;
216  }
217 
218 private:
219 
220  inline part_t firstPart(int rank) {
221  // For contiguous part assignments, the first part assigned to rank
222  return (rank * nParts_Div_nRanks + min(rank, nParts_Mod_nRanks));
223  }
224 
225  const int nRanks; // Global number of ranks
226  part_t nParts; // Global number of parts
227  part_t nParts_Div_nRanks; // (nParts/nRanks) precomputed for frequent use
228  part_t nParts_Mod_nRanks; // (nParts%nRanks) precomputed for frequent use
229 
230  const int myRank; // Local rank
231  part_t nMyParts; // Local number of parts
232  ArrayRCP<part_t> myParts; // Array of my parts; created only if
233  // getMyPartsView is called.
234 };
235 
236 
237 } // namespace Zoltan2
238 
239 #endif
PartitionMapping maps a solution or an input distribution to ranks.
size_t global_size_t
void getMyPartsView(part_t &numParts, part_t *&parts)
In mapping, returns a view of parts assigned to the current rank.
Defines the PartitioningSolution class.
void map(const Teuchos::RCP< MappingSolution< Adapter > > &msoln)
AlgBlockMapping(const Teuchos::RCP< const Teuchos::Comm< int > > &comm_, const Teuchos::RCP< const MachineRep > &machine_, const Teuchos::RCP< const Adapter > &adapter_, const Teuchos::RCP< const Zoltan2::PartitioningSolution< Adapter > > &psoln_, const Teuchos::RCP< const Environment > &envConst)
AlgBlockMapping(const Teuchos::RCP< const Teuchos::Comm< int > > comm_, const part_t nparts)
Constructor that allows this mapping method to be used as a.
A PartitioningSolution is a solution to a partitioning problem.
int getRankForPart(part_t p)
In mapping, returns the rank to which a part is assigned.
Algorithm defines the base class for all algorithms.
Gathering definitions used in software development.
A gathering of useful namespace methods.