Zoltan2
Loading...
Searching...
No Matches
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
65namespace Zoltan2 {
66
67template <typename Adapter, typename MachineRep>
68class AlgBlockMapping : public Algorithm<Adapter>
69{
70
71private:
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
80public:
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
221private:
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
Defines the PartitioningSolution class.
Gathering definitions used in software development.
A gathering of useful namespace methods.
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.
void map(const Teuchos::RCP< MappingSolution< Adapter > > &msoln)
void getMyPartsView(part_t &numParts, part_t *&parts)
In mapping, returns a view of parts assigned to the current rank.
int getRankForPart(part_t p)
In mapping, returns the rank to which a part is assigned.
Algorithm defines the base class for all algorithms.
PartitionMapping maps a solution or an input distribution to ranks.
A PartitioningSolution is a solution to a partitioning problem.
Created by mbenlioglu on Aug 31, 2020.
Tpetra::global_size_t global_size_t
SparseMatrixAdapter_t::part_t part_t