Tpetra parallel linear algebra Version of the Day
Loading...
Searching...
No Matches
Tpetra_Details_CrsPadding.hpp
1#ifndef TPETRA_DETAILS_CRSPADDING_HPP
2#define TPETRA_DETAILS_CRSPADDING_HPP
3
5#include "Tpetra_Util.hpp"
6#include <algorithm>
7#include <iostream>
8#include <memory>
9#include <sstream>
10#include <vector>
11
12namespace Tpetra {
13 namespace Details {
14
18 template<class LocalOrdinal, class GlobalOrdinal>
19 class CrsPadding {
20 private:
21 using LO = LocalOrdinal;
22 using GO = GlobalOrdinal;
23
24 enum class Phase {
25 SAME,
26 PERMUTE,
27 IMPORT
28 };
29
30 public:
31 CrsPadding(const int myRank,
32 const size_t /* numSameIDs */,
33 const size_t /* numPermutes */)
34 : myRank_(myRank)
35 {}
36
37 CrsPadding(const int myRank,
38 const size_t /* numImports */)
39 : myRank_(myRank)
40 {}
41
42 void
43 update_same(
44 const LO targetLocalIndex,
45 GO tgtGblColInds[],
46 const size_t origNumTgtEnt,
47 const bool tgtIsUnique,
48 GO srcGblColInds[],
49 const size_t origNumSrcEnt,
50 const bool srcIsUnique)
51 {
52 const LO whichSame = targetLocalIndex;
53 update_impl(Phase::SAME, whichSame, targetLocalIndex,
56 }
57
58 void
59 update_permute(
60 const LO whichPermute, // index in permuteFrom/To
61 const LO targetLocalIndex,
62 GO tgtGblColInds[],
63 const size_t origNumTgtEnt,
64 const bool tgtIsUnique,
65 GO srcGblColInds[],
66 const size_t origNumSrcEnt,
67 const bool srcIsUnique)
68 {
69 update_impl(Phase::PERMUTE, whichPermute, targetLocalIndex,
72 }
73
74 void
75 update_import(
76 const LO whichImport,
77 const LO targetLocalIndex,
78 GO tgtGblColInds[],
79 const size_t origNumTgtEnt,
80 const bool tgtIsUnique,
81 GO srcGblColInds[],
82 const size_t origNumSrcEnt,
83 const bool srcIsUnique)
84 {
85 update_impl(Phase::IMPORT, whichImport, targetLocalIndex,
88 }
89
90 void print(std::ostream& out) const {
91 const size_t maxNumToPrint =
93 const size_t size = entries_.size();
94 out << "entries: [";
95 size_t k = 0;
96 for (const auto& keyval : entries_) {
97 if (k > maxNumToPrint) {
98 out << "...";
99 break;
100 }
101 out << "(" << keyval.first << ", ";
103 "Global column indices", maxNumToPrint);
104 out << ")";
105 if (k + size_t(1) < size) {
106 out << ", ";
107 }
108 ++k;
109 }
110 out << "]";
111 }
112
113 struct Result {
114 size_t numInSrcNotInTgt;
115 bool found;
116 };
117
125 Result
127 {
128 auto it = entries_.find(targetLocalIndex);
129 if (it == entries_.end()) {
130 return {0, false};
131 }
132 else {
133 return {it->second.size(), true};
134 }
135 }
136
137 private:
138 void
139 update_impl(
140 const Phase phase,
141 const LO whichImport,
142 const LO targetLocalIndex,
143 GO tgtGblColInds[],
144 const size_t origNumTgtEnt,
145 const bool tgtIsUnique,
146 GO srcGblColInds[],
147 const size_t origNumSrcEnt,
148 const bool srcIsUnique)
149 {
150 using std::endl;
151 std::unique_ptr<std::string> prefix;
152 if (verbose_) {
153 prefix = createPrefix("update_impl");
154 std::ostringstream os;
155 os << *prefix << "Start: "
156 << "targetLocalIndex=" << targetLocalIndex
157 << ", origNumTgtEnt=" << origNumTgtEnt
158 << ", origNumSrcEnt=" << origNumSrcEnt << endl;
159 std::cerr << os.str();
160 }
161
162 // FIXME (08 Feb 2020) We only need to sort and unique
163 // tgtGblColInds if we haven't already seen it before.
166 std::sort(tgtGblColInds, tgtEnd);
167 if (! tgtIsUnique) {
168 tgtEnd = std::unique(tgtGblColInds, tgtEnd);
171 }
172
173 if (verbose_) {
174 std::ostringstream os;
175 os << *prefix << "finished src; process tgt" << endl;
176 std::cerr << os.str();
177 }
178
179 size_t newNumSrcEnt = origNumSrcEnt;
180 auto srcEnd = srcGblColInds + origNumSrcEnt;
181 std::sort(srcGblColInds, srcEnd);
182 if (! srcIsUnique) {
183 srcEnd = std::unique(srcGblColInds, srcEnd);
184 newNumSrcEnt = size_t(srcEnd - srcGblColInds);
185 TEUCHOS_ASSERT( newNumSrcEnt <= origNumSrcEnt );
186 }
187
188 merge_with_current_state(phase, whichImport, targetLocalIndex,
189 tgtGblColInds, newNumTgtEnt,
190 srcGblColInds, newNumSrcEnt);
191 if (verbose_) {
192 std::ostringstream os;
193 os << *prefix << "Done" << endl;
194 std::cerr << os.str();
195 }
196 }
197
198 std::vector<GO>&
199 get_difference_col_inds(const Phase /* phase */,
200 const LO /* whichIndex */,
201 const LO tgtLclRowInd)
202 {
203 return entries_[tgtLclRowInd];
204 }
205
206 void
207 merge_with_current_state(
208 const Phase phase,
209 const LO whichIndex,
210 const LO tgtLclRowInd,
211 const GO tgtColInds[], // sorted & merged
212 const size_t numTgtEnt,
213 const GO srcColInds[], // sorted & merged
214 const size_t numSrcEnt)
215 {
216 using std::endl;
217 std::unique_ptr<std::string> prefix;
218 if (verbose_) {
219 prefix = createPrefix("merge_with_current_state");
220 std::ostringstream os;
221 os << *prefix << "Start: "
222 << "tgtLclRowInd=" << tgtLclRowInd
223 << ", numTgtEnt=" << numTgtEnt
224 << ", numSrcEnt=" << numSrcEnt << endl;
225 std::cerr << os.str();
226 }
227 // We only need to accumulate those source indices that are
228 // not already target indices. This is because we always have
229 // the target indices on input to this function, so there's no
230 // need to store them here again. That still could be a lot
231 // to store, but it's better than duplicating target matrix
232 // storage.
233 //
234 // This means that consumers of this data structure need to
235 // treat entries_[tgtLclRowInd].size() as an increment, not as
236 // the required new allocation size itself.
237 //
238 // We store
239 //
240 // difference(union(incoming source indices,
241 // already stored source indices),
242 // target indices)
243
244 auto tgtEnd = tgtColInds + numTgtEnt;
245 auto srcEnd = srcColInds + numSrcEnt;
246
247 // At least one input source index isn't in the target.
248 std::vector<GO>& diffColInds =
249 get_difference_col_inds(phase, whichIndex, tgtLclRowInd);
250 const size_t oldDiffNumEnt = diffColInds.size();
251
252 if (oldDiffNumEnt == 0) {
253 if (verbose_) {
254 std::ostringstream os;
255 os << *prefix << "oldDiffNumEnt=0; call "
256 "set_difference(src,tgt,diff)" << endl;
257 std::cerr << os.str();
258 }
259 diffColInds.resize(numSrcEnt);
260 auto diffEnd = std::set_difference(srcColInds, srcEnd,
261 tgtColInds, tgtEnd,
262 diffColInds.begin());
263 const size_t newLen(diffEnd - diffColInds.begin());
264 TEUCHOS_ASSERT( newLen <= numSrcEnt );
265 diffColInds.resize(newLen);
266 }
267 else {
268 // scratch = union(srcColInds, diffColInds);
269 // diffColInds = difference(scratch, tgtColInds);
270
271 const size_t maxUnionSize = numSrcEnt + oldDiffNumEnt;
272 if (verbose_) {
273 std::ostringstream os;
274 os << *prefix << "oldDiffNumEnt=" << oldDiffNumEnt
275 << ", maxUnionSize=" << maxUnionSize
276 << "; call set_union(src,diff,union)" << endl;
277 std::cerr << os.str();
278 }
279 if (scratchColInds_.size() < maxUnionSize) {
280 scratchColInds_.resize(maxUnionSize);
281 }
282 auto unionBeg = scratchColInds_.begin();
283 auto unionEnd = std::set_union(srcColInds, srcEnd,
284 diffColInds.begin(), diffColInds.end(),
285 unionBeg);
286 const size_t unionSize(unionEnd - unionBeg);
287 TEUCHOS_ASSERT( unionSize <= maxUnionSize );
288
289 if (verbose_) {
290 std::ostringstream os;
291 os << *prefix << "oldDiffNumEnt=" << oldDiffNumEnt
292 << ", unionSize=" << unionSize << "; call "
293 "set_difference(union,tgt,diff)" << endl;
294 std::cerr << os.str();
295 }
296 diffColInds.resize(unionSize);
297 auto diffEnd = std::set_difference(unionBeg, unionEnd,
298 tgtColInds, tgtEnd,
299 diffColInds.begin());
300 const size_t diffLen(diffEnd - diffColInds.begin());
301 TEUCHOS_ASSERT( diffLen <= unionSize );
302 diffColInds.resize(diffLen);
303 }
304
305 if (verbose_) {
306 std::ostringstream os;
307 os << *prefix << "Done" << endl;
308 std::cerr << os.str();
309 }
310 }
311
312 std::unique_ptr<std::string>
313 createPrefix(const char funcName[])
314 {
315 std::ostringstream os;
316 os << "Proc " << myRank_ << ": CrsPadding::" << funcName
317 << ": ";
318 return std::unique_ptr<std::string>(new std::string(os.str()));
319 }
320
321 // imports may overlap with sames and/or permutes, so it makes
322 // sense to store them all in one map.
323 std::map<LO, std::vector<GO> > entries_;
324 std::vector<GO> scratchColInds_;
325 int myRank_ = -1;
326 bool verbose_ = Behavior::verbose("CrsPadding");
327 };
328 } // namespace Details
329} // namespace Tpetra
330
331#endif // TPETRA_DETAILS_CRSPADDING_HPP
Declaration of Tpetra::Details::Behavior, a class that describes Tpetra's behavior.
Stand-alone utility functions and macros.
Struct that holds views of the contents of a CrsMatrix.
static bool verbose()
Whether Tpetra is in verbose mode.
static size_t verbosePrintCountThreshold()
Number of entries below which arrays, lists, etc. will be printed in debug mode.
Keep track of how much more space a CrsGraph or CrsMatrix needs, when the graph or matrix is the targ...
Result get_result(const LO targetLocalIndex) const
For a given target matrix local row index, return the number of unique source column indices to merge...
Implementation details of Tpetra.
void verbosePrintArray(std::ostream &out, const ArrayType &x, const char name[], const size_t maxNumToPrint)
Print min(x.size(), maxNumToPrint) entries of x.
Namespace Tpetra contains the class and methods constituting the Tpetra library.