Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_AlgDefaultMapping.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_ALGDEFAULTMAPPING_HPP_
46 #define _ZOLTAN2_ALGDEFAULTMAPPING_HPP_
47 
48 #include <Zoltan2_Standards.hpp>
49 #include <Zoltan2_Algorithm.hpp>
51 #include <Zoltan2_Util.hpp>
52 
53 
57 //
59 
60 namespace Zoltan2 {
61 
62 template <typename Adapter, typename MachineRep>
63 class AlgDefaultMapping : public Algorithm<Adapter>
64 {
65 
66 private:
67 
68  typedef typename Adapter::lno_t lno_t;
69  typedef typename Adapter::gno_t gno_t;
70  typedef typename Adapter::scalar_t scalar_t;
71  typedef typename Adapter::part_t part_t;
72  typedef typename Adapter::user_t user_t;
73  typedef typename Adapter::userCoord_t userCoord_t;
74 
75  const RCP<const Environment> env;
76  const RCP<const Comm<int> > problemComm;
77  const RCP<const typename Adapter::base_adapter_t> adapter;
78 
79 public:
80 
87  const Teuchos::RCP <const Teuchos::Comm<int> > &comm_,
88  const Teuchos::RCP <const MachineRep> &machine_,
89  const Teuchos::RCP <const Adapter> &adapter_,
90  const Teuchos::RCP <const Zoltan2::PartitioningSolution<Adapter> > &psoln_,
91  const Teuchos::RCP <const Environment> &envConst)
92  : env(envConst), adapter(adapter_),
93  partIsRank(false), haveContiguousParts(false)
94  rankForPart(Teuchos::null)
95  {
96  int nRanks = comm->getSize();
97 
98  // Get set of parts from partitioning solution or adapter, if provided
99  // Otherwise, we'll assume set of parts == set of ranks
100  const *partList;
101  if (psoln_ != Teuchos::null) {
102  partList = psoln_->getPartListView();
103  }
104  else {
105  adapter->getPartsView(partList);
106  }
107 
108  // Compute maxPart, nParts
109  typedef typename Tpetra::Map<lno_t, part_t> tpetraMap_t
110  Teuchos::RCP<tpetraMap_t> tmap;
111 
112  part_t minPart, maxPart;
113 
114  if (partList == NULL) {
115  // Parts for IDs are the same as ranks
116  nParts = nRanks;
117  maxPart = nRanks-1;
118  minPart = 0;
119  }
120  else {
121  // Parts were provided by partitioning solution or input adapter
122 
123  // Find unique parts on this rank,
124  // as Tpetra::Map does not like duplicate GIDs within a rank
125 
126  size_t nLocal = adapter->getLocalNumIDs();
127 
128  std::set<part_t> unique(nLocal);
129  for (size_t i; i < adapter->getLocalNumIDs(); i++)
130  unique.insert(partList[i]);
131 
132  size_t nUnique = unique.size();
133  Array<const part_t> uniquePartList(nUnique);
134  size_t k = 0;
135  for (typename std::set<part_t>::iterator it = set.begin();
136  it != set.end(); it++)
137  uniquePartList[k++] = *it;
138 
139  // Use Tpetra::Map to find the max, min, total part.
140 
141  global_size_t nGlobalElts =
142  Teuchos::OrdinalTraits<Tpetra::global_size_t>::invalid();
143  tmap = rcp(new tpetraMap_t(nGlobalElts, uniquePartList(), 0, comm));
144 
145  nParts = as<part_t>(tmap->getGlobalNumElements());
146  minPart = tmap->getMinAllGlobalIndex();
147  maxPart = tmap->getMaxAllGlobalIndex();
148  }
149 
150  nParts_Div_nRanks = nParts / nRanks;
151  nParts_Mod_nRanks = nParts % nRanks;
152 
153  // Determine number of unique parts, as well as min and max part
154  // Can probably use a Tpetra Map.
155 
156  if (maxPart < nRanks)
157  partIsRank = true; // Most common case
158 
159  if ((minPart == 0) && (maxPart == nParts-1))
160  // Have a contiguous set of parts; can use simplest default mapping
161  haveContiguousParts = true;
162 
163  if (!partIsRank && !haveContiguousParts) {
164  // Use Tpetra createOneToOne to map parts to ranks
165  Teuchos::RCP<tpetraMap_t> oneToOneMap = Tpetra::createOneToOne(tmap);
166 
167  // Each rank needs names of all parts
168  // Should we gather map to one rank, or copy to all?
169  // I don't know how to do it.
170  Teuchos::RCP<tpetraMap_t> gatheredMap = ;
171 
172  Teuchos::ArrayView<const part_t> allParts =
173  gatheredMap->getLocalElementList();
174 
175  // Look up the rank for all parts assigned by oneToOneMap
176  Teuchos::Array<int> allRanks(allParts.size());
177  oneToOneMap->getRemoveIndexList(allParts, allRanks());
178 
179  for (size_t i = 0; i < allPart.size())
180  (*rankForPart)[allParts[i]] = allRanks[i];
181  }
182  }
183 
184  void map(Teuchos::RCP<MappingSolution<Adapter> > msoln) {
185  // Mapping was computed in constructor;
186  // nothing to do here since we implement getRankForPart and
187  // getMyPartsView. (If we didn't we would need to store
188  // the mapping in the soln here.)
189  }
190 
191  int getRankForPart(part_t p) {
192  if (p < 0 || p > maxPart)
193  throw std::runtime_error("Invalid part in getRankForPart");
194 
195  // Most common case: at most one part per rank
196  if (partIsRank)
197  return as<int>(p);
198 
199  // Multiple parts per rank
200  if (haveContiguousParts) {
201  int tmp = p / nParts_Div_nRanks;
202  while (firstContiguousPart(tmp) > p) tmp--;
203  while (firstContiguousPart(tmp+1) < p) tmp++;
204  return tmp;
205  }
206 
207  // None of the simple schemes apply; use the unordered_map.
208  return rankForPart[p];
209  }
210 
211  void getMyPartsView(part_t &numParts, part_t *&parts)
212  {
213  // Will need to construct the arrays if this function is called.
214  // Will not work if this is a const method.
215  partsForRankIdx = rcp(new part_t[nRanks+1]);
216  partsForRank = rcp(new part_t[nParts]);
217 
218  }
219 
220  void map(const RCP<PartitioningSolution<Adapter> > &solution);
221 
222 private:
223 
224  inline part_t firstContiguousPart(int rank) {
225  // For contiguous part assignments, the first part assigned to rank
226  return (rank * nParts_Div_nRanks + min(rank, nParts_Mod_nRanks));
227  }
228  bool partIsRank;
229  bool haveContiguousParts;
230  Teuchos::RCP<rankForPart_t> rankForPart;
231 };
232 
233 
234 } // namespace Zoltan2
235 
236 #endif
#define nParts
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.
void map(Teuchos::RCP< MappingSolution< Adapter > > msoln)
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:18
Defines the PartitioningSolution class.
SparseMatrixAdapter_t::part_t part_t
A PartitioningSolution is a solution to a partitioning problem.
AlgDefaultMapping(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)
Algorithm defines the base class for all algorithms.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17
int getRankForPart(part_t p)
In mapping, returns the rank to which a part is assigned.
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