Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 
12 namespace 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,
54  tgtGblColInds, origNumTgtEnt, tgtIsUnique,
55  srcGblColInds, origNumSrcEnt, srcIsUnique);
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,
70  tgtGblColInds, origNumTgtEnt, tgtIsUnique,
71  srcGblColInds, origNumSrcEnt, srcIsUnique);
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,
86  tgtGblColInds, origNumTgtEnt, tgtIsUnique,
87  srcGblColInds, origNumSrcEnt, srcIsUnique);
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 << ", ";
102  Details::verbosePrintArray(out, keyval.second,
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
126  get_result(const LO targetLocalIndex) const
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.
164  size_t newNumTgtEnt = origNumTgtEnt;
165  auto tgtEnd = tgtGblColInds + origNumTgtEnt;
166  std::sort(tgtGblColInds, tgtEnd);
167  if (! tgtIsUnique) {
168  tgtEnd = std::unique(tgtGblColInds, tgtEnd);
169  newNumTgtEnt = size_t(tgtEnd - tgtGblColInds);
170  TEUCHOS_ASSERT( newNumTgtEnt <= origNumTgtEnt );
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
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...
void verbosePrintArray(std::ostream &out, const ArrayType &x, const char name[], const size_t maxNumToPrint)
Print min(x.size(), maxNumToPrint) entries of x.
Keep track of how much more space a CrsGraph or CrsMatrix needs, when the graph or matrix is the targ...
static bool verbose()
Whether Tpetra is in verbose mode.
Stand-alone utility functions and macros.
static size_t verbosePrintCountThreshold()
Number of entries below which arrays, lists, etc. will be printed in debug mode.
Declaration of Tpetra::Details::Behavior, a class that describes Tpetra&#39;s behavior.