Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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 #include <cmath>
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  // Ideally, we'd use part_t as global ID in the map, but that won't
125  // work if Tpetra is compiled without global ID = int.
126  // typedef part_t use_this_gno_t;
127  // We'll use Tpetra's default instead
128  typedef Tpetra::Map<>::global_ordinal_type use_this_gno_t;
129 
130  std::set<use_this_gno_t> unique;
131  for (size_t i = 0; i < nLocal; i++)
132  unique.insert(partList[i]);
133 
134  size_t nUnique = unique.size();
135  Array<use_this_gno_t> uniquePartList(nUnique);
136  size_t k = 0;
137  for (typename std::set<use_this_gno_t>::iterator it = unique.begin();
138  it != unique.end(); it++)
139  uniquePartList[k++] = *it;
140 
141  // Use Tpetra::Map to find the max, min, total part.
142 
143  global_size_t nGlobalElts =
144  Teuchos::OrdinalTraits<Tpetra::global_size_t>::invalid();
145  Tpetra::Map<lno_t, use_this_gno_t> tmap(nGlobalElts, uniquePartList(),
146  0, comm_);
147 
148  nParts = Teuchos::as<part_t>(tmap.getGlobalNumElements());
149  minPart = tmap.getMinAllGlobalIndex();
150  maxPart = tmap.getMaxAllGlobalIndex();
151  }
152 
153  // Determine number of unique parts, as well as min and max part
154  // Can probably use a Tpetra Map.
155 
156  if ((minPart != 0) || (maxPart != nParts-1)) {
157  // Cannot use this mapping method
158  throw std::runtime_error("Cannot use mapping_algorithm = contiguous "
159  "unless parts are numbered from 0 to nParts-1");
160  }
161 
163  }
164 
166  // submethod of the default
167  // Assume that calling method has already confirmed assumptions
168  // about part numbering.
170  const Teuchos::RCP <const Teuchos::Comm<int> > comm_,
171  const part_t nparts) :
172  nRanks(comm_->getSize()),
173  nParts(nparts),
174  myRank(comm_->getRank()),
175  nMyParts(0),
176  myParts(Teuchos::null)
177  {
179  }
180 
182  {
183  nParts_Div_nRanks = nParts / nRanks;
184  nParts_Mod_nRanks = nParts % nRanks;
185  nMyParts = nParts_Div_nRanks + (myRank < nParts_Mod_nRanks);
186  }
187 
188  void map(const Teuchos::RCP<MappingSolution<Adapter> > &msoln) {
189  // Mapping is computed implicitly;
190  // nothing to do here since we implement
191  // getRankForPart and getMyPartsView.
192  }
193 
194  int getRankForPart(part_t p) {
195  if (p < 0 || p >= nParts)
196  throw std::runtime_error("Invalid part in getRankForPart");
197 
198  int tmp = p / nParts_Div_nRanks;
199  while (firstPart(tmp) > p) tmp--;
200  while (firstPart(tmp+1) < p) tmp++;
201  return tmp;
202  }
203 
204  void getMyPartsView(part_t &numParts, part_t *&parts)
205  {
206  // Will need to construct the arrays if this function is called.
207  // Will not work if this is a const method.
208  numParts = nMyParts;
209  if (nMyParts) {
210  if (myParts == Teuchos::null) {
211  myParts = arcp(new part_t[nMyParts], 0, nMyParts, true);
212  for (part_t i = 0; i < nMyParts; i++)
213  myParts[i] = firstPart(myRank) + i;
214  }
215  parts = myParts.getRawPtr();
216  }
217  else
218  parts = NULL;
219  }
220 
221 private:
222 
223  inline part_t firstPart(int rank) {
224  // For contiguous part assignments, the first part assigned to rank
225  return (rank * nParts_Div_nRanks + std::min(rank, nParts_Mod_nRanks));
226  }
227 
228  const int nRanks; // Global number of ranks
229  part_t nParts; // Global number of parts
230  part_t nParts_Div_nRanks; // (nParts/nRanks) precomputed for frequent use
231  part_t nParts_Mod_nRanks; // (nParts%nRanks) precomputed for frequent use
232 
233  const int myRank; // Local rank
234  part_t nMyParts; // Local number of parts
235  ArrayRCP<part_t> myParts; // Array of my parts; created only if
236  // getMyPartsView is called.
237 };
238 
239 
240 } // namespace Zoltan2
241 
242 #endif
PartitionMapping maps a solution or an input distribution to ranks.
void getMyPartsView(part_t &numParts, part_t *&parts)
In mapping, returns a view of parts assigned to the current rank.
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:18
Defines the PartitioningSolution class.
void map(const Teuchos::RCP< MappingSolution< Adapter > > &msoln)
SparseMatrixAdapter_t::part_t part_t
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.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17
Gathering definitions used in software development.
Tpetra::global_size_t global_size_t
A gathering of useful namespace methods.
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition: Metric.cpp:74