Teuchos - Trilinos Tools Package  Version of the Day
Teuchos_PerformanceMonitorBase.cpp
1 // @HEADER
2 // ***********************************************************************
3 //
4 // Teuchos: Common Tools Package
5 // Copyright (2004) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38 //
39 // ***********************************************************************
40 // @HEADER
41 
43 #include "Teuchos_CommHelpers.hpp"
44 #include "Teuchos_DefaultComm.hpp"
45 #include <iterator> // std::back_inserter
46 
47 namespace Teuchos {
48 
49  namespace {
50 
51  // Pack the given array of strings into a single string with an
52  // offsets array. This is a helper routine of \c sendStrings().
53  // For strings[k], offsets[k] gives its start position in
54  // packedString, and offsets[k+1]-ofsets[k] gives its length.
55  // Thus, packedString.substr (offsets[k], offsets[k+1]-offsets[k])
56  // == strings[k].
57  //
58  // \param packedString [out] The packed string. It will be
59  // resized on output as necessary.
60  //
61  // \param offsets [out] Array of offsets, of length one more than
62  // the number of strings in the \c strings array. Thus, the
63  // offsets array always has positive length.
64  //
65  // \param strings [in] The array of strings to pack. It may have
66  // zero length. In that case, on output, the offsets array will
67  // have length one, offsets[0] = 0, and packedString will have
68  // length zero.
69  //
70  // Although std::string could be considered an array, it does not
71  // have a size_type typedef. Instead, it uses size_t for that
72  // purpose.
73  void
74  packStringsForSend (std::string& packedString,
75  Array<size_t>& offsets,
76  const Array<std::string>& strings)
77  {
78  using std::cerr;
79  using std::endl;
80  using std::string;
81 
82  const bool debug = false;
83 
84  // Compute index offsets in the packed string.
85  offsets.resize (strings.size() + 1);
86  size_t totalLength = 0;
87  Array<size_t>::size_type offsetsIndex = 0;
88  for (Array<string>::const_iterator it = strings.begin();
89  it != strings.end(); ++it, ++offsetsIndex)
90  {
91  offsets[offsetsIndex] = totalLength;
92  totalLength += it->size();
93  }
94  offsets[offsetsIndex] = totalLength;
95 
96  // Pack the array of strings into the packed string.
97  packedString.resize (totalLength);
98  string::iterator packedStringIter = packedString.begin();
99  for (Array<string>::const_iterator it = strings.begin();
100  it != strings.end(); ++it)
101  packedStringIter = std::copy (it->begin(), it->end(), packedStringIter);
102 
103  if (debug)
104  {
105  std::ostringstream out;
106  RCP<const Comm<int> > pComm = DefaultComm<int>::getComm ();
107  out << "Proc " << pComm->getRank() << ": in pack: offsets = [";
108  for (Array<size_t>::const_iterator it = offsets.begin();
109  it != offsets.end(); ++it)
110  {
111  out << *it;
112  if (it + 1 != offsets.end())
113  out << ", ";
114  }
115  out << "], packedString = " << packedString << endl;
116  cerr << out.str();
117  }
118  }
119 
120  // \brief Send an array of strings.
121  //
122  // Teuchos::send() (or rather, Teuchos::SerializationTraits)
123  // doesn't know how to send an array of strings. This function
124  // packs an array of strings into a single string with an offsets
125  // array, and sends the offsets array (and the packed string, if
126  // it is not empty).
127  void
128  sendStrings (const Comm<int>& comm, // in
129  const Array<std::string>& strings, // in
130  const int destRank) // in
131  {
132  // Pack the string array into the packed string, and compute
133  // offsets.
134  std::string packedString;
135  Array<size_t> offsets;
136  packStringsForSend (packedString, offsets, strings);
137  TEUCHOS_TEST_FOR_EXCEPTION(offsets.size() == 0, std::logic_error,
138  "packStringsForSend() returned a zero-length offsets "
139  "array on MPI Proc " << comm.getRank() << ", to be "
140  "sent to Proc " << destRank << ". The offsets array "
141  "should always have positive length. Please report "
142  "this bug to the Teuchos developers.");
143 
144  // Send the count of offsets.
145  send (comm, offsets.size(), destRank);
146 
147  // Send the array of offsets. There is always at least one
148  // element in the offsets array, so we can always take the
149  // address of the first element.
150  const int offsetsSendCount = static_cast<int> (offsets.size());
151  send (comm, offsetsSendCount, &offsets[0], destRank);
152 
153  // Now send the packed string. It may be empty if the strings
154  // array has zero elements or if all the strings in the array
155  // are empty. If the packed string is empty, we don't send
156  // anything, since the receiving process already knows (from the
157  // offsets array) not to expect anything.
158  const int stringSendCount = static_cast<int> (packedString.size());
159  if (stringSendCount > 0)
160  send (comm, stringSendCount, &packedString[0], destRank);
161  }
162 
163  void
164  unpackStringsAfterReceive (Array<std::string>& strings,
165  const std::string& packedString,
166  const Array<size_t> offsets)
167  {
168  const bool debug = false;
169  if (debug)
170  {
171  using std::cerr;
172  using std::endl;
173 
174  std::ostringstream out;
175  RCP<const Comm<int> > pComm = DefaultComm<int>::getComm ();
176  out << "Proc " << pComm->getRank() << ": in unpack: offsets = [";
177  for (Array<size_t>::const_iterator it = offsets.begin();
178  it != offsets.end(); ++it)
179  {
180  out << *it;
181  if (it + 1 != offsets.end())
182  out << ", ";
183  }
184  out << "], packedString = " << packedString << endl;
185  cerr << out.str();
186  }
187  TEUCHOS_TEST_FOR_EXCEPTION(offsets.size() == 0, std::logic_error,
188  "The offsets array has length zero, which does not "
189  "make sense. Even when sending / receiving zero "
190  "strings, the offsets array should have one entry "
191  "(namely, zero).");
192  const Array<size_t>::size_type numStrings = offsets.size() - 1;
193  strings.resize (numStrings);
194  for (Array<size_t>::size_type k = 0; k < numStrings; ++k)
195  { // Exclusive index range in the packed string in which to
196  // find the current string.
197  const size_t start = offsets[k];
198  const size_t end = offsets[k+1];
199  strings[k] = packedString.substr (start, end - start);
200  }
201  }
202 
203  // Function corresponding to \c sendStrings() that receives an
204  // array of strings (Array<std::string>) in packed form.
205  void
206  receiveStrings (const Comm<int>& comm,
207  const int sourceRank,
208  Array<std::string>& strings)
209  {
210  // Receive the number of offsets. There should always be at
211  // least 1 offset.
212  Array<size_t>::size_type numOffsets = 0;
213  receive (comm, sourceRank, &numOffsets);
214  TEUCHOS_TEST_FOR_EXCEPTION(numOffsets == 0, std::logic_error,
215  "Invalid number of offsets numOffsets=" << numOffsets
216  << " received on MPI Rank " << comm.getRank()
217  << " from Rank " << sourceRank << ". Please report "
218  "this bug to the Teuchos developers.");
219 
220  // Receive the array of offsets.
221  Array<size_t> offsets (numOffsets);
222  const int offsetsRecvCount = static_cast<int> (numOffsets);
223  receive (comm, sourceRank, offsetsRecvCount, &offsets[0]);
224 
225  // If the packed string is nonempty, receive the packed string,
226  // and unpack it. The last entry of offsets is the length of
227  // the packed string.
228  std::string packedString (offsets.back(), ' ');
229  const int stringRecvCount = static_cast<int> (offsets.back());
230  if (stringRecvCount > 0)
231  {
232  receive (comm, sourceRank, stringRecvCount, &packedString[0]);
233  unpackStringsAfterReceive (strings, packedString, offsets);
234  }
235  }
236 
237 
238  void
239  broadcastStringsHelper (const Comm<int>& comm,
240  const int myRank,
241  const int left,
242  const int right,
243  Array<std::string>& globalNames)
244  {
245  // If left >= right, there is only one process, so we don't need
246  // to do anything.
247  //
248  // If left < right, then split the inclusive interval [left,
249  // right] into [left, mid-1] and [mid, right]. Send from left
250  // to mid, and recurse on the two subintervals.
251  if (left >= right)
252  return;
253  else
254  {
255  const int mid = left + (right - left + 1) / 2;
256 
257  // This could be optimized further on the sending rank, by
258  // prepacking the strings so that they don't have to be
259  // packed more than once.
260  if (myRank == left)
261  sendStrings (comm, globalNames, mid);
262  else if (myRank == mid)
263  receiveStrings (comm, left, globalNames);
264 
265  // Recurse on [left, mid-1] or [mid, right], depending on myRank.
266  if (myRank >= left && myRank <= mid-1)
267  broadcastStringsHelper (comm, myRank, left, mid-1, globalNames);
268  else if (myRank >= mid && myRank <= right)
269  broadcastStringsHelper (comm, myRank, mid, right, globalNames);
270  else
271  return; // Don't recurse if not participating.
272  }
273  }
274 
275 
276  void
277  broadcastStrings (const Comm<int>& comm,
278  Array<std::string>& globalNames)
279  {
280  const int myRank = comm.getRank();
281  const int left = 0;
282  const int right = comm.getSize() - 1;
283 
284  broadcastStringsHelper (comm, myRank, left, right, globalNames);
285  }
286 
287  // \brief Helper function for \c mergeCounterNamesHelper().
288  //
289  // The \c mergeCounterNamesHelper() function implements (using a
290  // parallel reduction) the set union resp. intersection (depending
291  // on the \c setOp argument) of the MPI process' sets of counter
292  // names. This function implements the binary associative
293  // operator which computes the set union resp. intersection of two
294  // sets: the "left" process' intermediate reduction result (global
295  // counter names), and the "mid" process' local counter names.
296  //
297  // \param comm [in] Communicator for which \c
298  // mergeCounterNamesHelper() was called.
299  //
300  // \param myRank [in] Rank of the calling MPI process; must be
301  // either == left or == mid.
302  //
303  // \param left [in] The "left" input argument of
304  // \c mergeCounterNamesHelper().
305  //
306  // \param mid [in] The value of "mid" in the implementation of \c
307  // mergeCounterNamesHelper().
308  //
309  // \param localNames [in] List of counter names belonging to the
310  // calling MPI process.
311  //
312  // \param globalNames [in/out] Only accessed if myRank == left.
313  // If so, on input: the intermediate reduction result of the
314  // union resp. intersection (depending on \c setOp). On output:
315  // the union resp. intersection of the input value of the "left"
316  // MPI process' globalNames with the "mid" MPI process'
317  // localNames.
318  //
319  // \param setOp [in] If Intersection, compute the set intersection
320  // of counter names, else if Union, compute the set union of
321  // counter names.
322  void
323  mergeCounterNamesPair (const Comm<int>& comm,
324  const int myRank,
325  const int left,
326  const int mid,
327  const Array<std::string>& localNames,
328  Array<std::string>& globalNames,
329  const ECounterSetOp setOp)
330  {
331  using std::cerr;
332  using std::endl;
333  using std::string;
334 
335  const bool debug = false;
336 
337  if (myRank == left)
338  { // Receive names from the other process, and merge its names
339  // with the names on this process.
340  Array<string> otherNames;
341  receiveStrings (comm, mid, otherNames);
342 
343  if (debug)
344  {
345  // Buffering locally in an ostringstream before writing to
346  // the shared stderr sometimes helps avoid interleaved
347  // debugging output.
348  std::ostringstream out;
349  out << "Proc " << myRank << ": in mergePair: otherNames = [";
350  for (Array<std::string>::const_iterator it = otherNames.begin();
351  it != otherNames.end(); ++it)
352  {
353  out << "\"" << *it << "\"";
354  if (it + 1 != otherNames.end())
355  out << ", ";
356  }
357  out << "]" << endl;
358  cerr << out.str();
359  }
360 
361  // Assume that both globalNames and otherNames are sorted.
362  // Compute the set intersection / union as specified by the
363  // enum.
364  Array<string> newNames;
365  if (setOp == Intersection)
366  std::set_intersection (globalNames.begin(), globalNames.end(),
367  otherNames.begin(), otherNames.end(),
368  std::back_inserter (newNames));
369  else if (setOp == Union)
370  std::set_union (globalNames.begin(), globalNames.end(),
371  otherNames.begin(), otherNames.end(),
372  std::back_inserter (newNames));
373  else
374  TEUCHOS_TEST_FOR_EXCEPTION(setOp != Intersection && setOp != Union,
375  std::logic_error,
376  "Invalid set operation enum value. Please "
377  "report this bug to the Teuchos developers.");
378  globalNames.swap (newNames);
379  }
380  else if (myRank == mid)
381  sendStrings (comm, localNames, left);
382  else
383  TEUCHOS_TEST_FOR_EXCEPTION(myRank != left && myRank != mid,
384  std::logic_error,
385  "myRank=" << myRank << " is neither left=" << left
386  << " nor mid=" << mid << ". Please report this "
387  "bug to the Teuchos developers.");
388  }
389 
390  // Recursive helper function for \c mergeCounterNames().
391  //
392  // This function implements the set union resp. intersection
393  // (depending on the \c setOp argument) of the MPI process' sets
394  // of counter names, using a parallel reduction. (Since the
395  // Teuchos comm wrappers as of 11 July 2011 lack a wrapper for
396  // MPI_Reduce(), we hand-roll the reduction using a binary tree
397  // via recursion. We don't need an all-reduce in this case.)
398  void
399  mergeCounterNamesHelper (const Comm<int>& comm,
400  const int myRank,
401  const int left,
402  const int right, // inclusive range [left, right]
403  const Array<std::string>& localNames,
404  Array<std::string>& globalNames,
405  const ECounterSetOp setOp)
406  {
407  // Correctness proof:
408  //
409  // 1. Both set intersection and set union are associative (and
410  // indeed even commutative) operations.
411  // 2. mergeCounterNamesHelper() is just a reduction by binary tree.
412  // 3. Reductions may use any tree shape as long as the binary
413  // operation is associative.
414  //
415  // Recursive "reduction" algorithm:
416  //
417  // Let mid be the midpoint of the inclusive interval [left,
418  // right]. If the (intersection, union) of [left, mid-1] and
419  // the (intersection, union) of [mid, right] are both computed
420  // correctly, then the (intersection, union) of these two sets
421  // is the (intersection, union) of [left, right].
422  //
423  // The base case is left == right: the (intersection, union) of
424  // one set is simply that set, so copy localNames into
425  // globalNames.
426  //
427  // We include another base case for safety: left > right,
428  // meaning that the set of processes is empty, so we do nothing
429  // (the (intersection, union) of an empty set of sets is the
430  // empty set).
431  if (left > right)
432  return;
433  else if (left == right)
434  {
435  Array<string> newNames;
436  newNames.reserve (localNames.size());
437  std::copy (localNames.begin(), localNames.end(),
438  std::back_inserter (newNames));
439  globalNames.swap (newNames);
440  }
441  else
442  { // You're sending messages across the network, so don't
443  // bother to optimize away a few branches here.
444  //
445  // Recurse on [left, mid-1] or [mid, right], depending on myRank.
446  const int mid = left + (right - left + 1) / 2;
447  if (myRank >= left && myRank <= mid-1)
448  mergeCounterNamesHelper (comm, myRank, left, mid-1,
449  localNames, globalNames, setOp);
450  else if (myRank >= mid && myRank <= right)
451  mergeCounterNamesHelper (comm, myRank, mid, right,
452  localNames, globalNames, setOp);
453  else
454  return; // Don't call mergeCounterNamesPair() if not participating.
455 
456  // Combine the results of the recursive step.
457  if (myRank == left || myRank == mid)
458  mergeCounterNamesPair (comm, myRank, left, mid,
459  localNames, globalNames, setOp);
460  }
461  }
462 
463  } // namespace (anonymous)
464 
465  void
467  const Array<std::string>& localNames,
468  Array<std::string>& globalNames,
469  const ECounterSetOp setOp)
470  {
471  const int myRank = comm.getRank();
472  const int left = 0;
473  const int right = comm.getSize() - 1;
474  Array<std::string> theGlobalNames;
475  mergeCounterNamesHelper (comm, myRank, left, right,
476  localNames, theGlobalNames, setOp);
477 
478  // Proc 0 has the list of counter names. Now broadcast it back to
479  // all the procs.
480  broadcastStrings (comm, theGlobalNames);
481 
482  // "Transactional" semantics ensure strong exception safety for
483  // output.
484  globalNames.swap (theGlobalNames);
485  }
486 
487 } // namespace Teuchos
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
static Teuchos::RCP< const Comm< OrdinalType > > getComm()
Return the default global communicator.
Ordinal size_type
The type of Array sizes and capacities.
virtual int getRank() const =0
Returns the rank of this process.
void send(const Packet sendBuffer[], const Ordinal count, const int destRank, const int tag, const Comm< Ordinal > &comm)
Variant of send() that takes a tag (and restores the correct order of arguments). ...
void mergeCounterNames(const Comm< int > &comm, const Array< std::string > &localNames, Array< std::string > &globalNames, const ECounterSetOp setOp)
Merge counter names over all processors.
friend void swap(Array< T2 > &a1, Array< T2 > &a2)
std::vector< T >::const_iterator const_iterator
The type of a const forward iterator.
Abstract interface for distributed-memory communication.
The Teuchos namespace contains all of the classes, structs and enums used by Teuchos, as well as a number of utility routines.
Provides common capabilities for collecting and reporting performance data across processors...
ECounterSetOp
Set operation type for mergeCounterNames() to perform.
virtual int getSize() const =0
Returns the number of processes that make up this communicator.