Teuchos Package Browser (Single Doxygen Collection) Version of the Day
Teuchos_PerformanceMonitorBase.cpp
Go to the documentation of this file.
00001 // @HEADER
00002 // ***********************************************************************
00003 //
00004 //                    Teuchos: Common Tools Package
00005 //                 Copyright (2004) Sandia Corporation
00006 //
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 //
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
00038 //
00039 // ***********************************************************************
00040 // @HEADER
00041 
00042 #include "Teuchos_PerformanceMonitorBase.hpp"
00043 #include "Teuchos_CommHelpers.hpp"
00044 #include "Teuchos_DefaultComm.hpp"
00045 #include <iterator> // std::back_inserter
00046 
00047 namespace Teuchos {
00048 
00049   namespace {
00050 
00051     // Pack the given array of strings into a single string with an
00052     // offsets array.  This is a helper routine of \c sendStrings().
00053     // For strings[k], offsets[k] gives its start position in
00054     // packedString, and offsets[k+1]-ofsets[k] gives its length.
00055     // Thus, packedString.substr (offsets[k], offsets[k+1]-offsets[k])
00056     // == strings[k].
00057     //
00058     // \param packedString [out] The packed string.  It will be
00059     //   resized on output as necessary.
00060     //
00061     // \param offsets [out] Array of offsets, of length one more than
00062     //   the number of strings in the \c strings array.  Thus, the
00063     //   offsets array always has positive length.  
00064     //
00065     // \param strings [in] The array of strings to pack.  It may have
00066     //   zero length.  In that case, on output, the offsets array will
00067     //   have length one, offsets[0] = 0, and packedString will have
00068     //   length zero.
00069     //
00070     // Although std::string could be considered an array, it does not
00071     // have a size_type typedef.  Instead, it uses size_t for that
00072     // purpose.
00073     void
00074     packStringsForSend (std::string& packedString, 
00075       Array<size_t>& offsets,
00076       const Array<std::string>& strings)
00077     {
00078       using std::cerr;
00079       using std::endl;
00080       using std::string;
00081 
00082       const bool debug = false;
00083 
00084       // Compute index offsets in the packed string.
00085       offsets.resize (strings.size() + 1);
00086       size_t totalLength = 0;
00087       Array<size_t>::size_type offsetsIndex = 0;
00088       for (Array<string>::const_iterator it = strings.begin();
00089      it != strings.end(); ++it, ++offsetsIndex)
00090   {
00091     offsets[offsetsIndex] = totalLength;
00092     totalLength += it->size();
00093   }
00094       offsets[offsetsIndex] = totalLength;
00095 
00096       // Pack the array of strings into the packed string.
00097       packedString.resize (totalLength);
00098       string::iterator packedStringIter = packedString.begin();
00099       for (Array<string>::const_iterator it = strings.begin(); 
00100      it != strings.end(); ++it)
00101   packedStringIter = std::copy (it->begin(), it->end(), packedStringIter);
00102 
00103       if (debug)
00104   {
00105     std::ostringstream out;
00106     RCP<const Comm<int> > pComm = DefaultComm<int>::getComm ();
00107     out << "Proc " << pComm->getRank() << ": in pack: offsets = [";
00108     for (Array<size_t>::const_iterator it = offsets.begin(); 
00109          it != offsets.end(); ++it)
00110       {
00111         out << *it;
00112         if (it + 1 != offsets.end())
00113     out << ", ";
00114       }
00115     out << "], packedString = " << packedString << endl;
00116     cerr << out.str();
00117   }
00118     }
00119 
00120     // \brief Send an array of strings.
00121     //
00122     // Teuchos::send() (or rather, Teuchos::SerializationTraits)
00123     // doesn't know how to send an array of strings.  This function
00124     // packs an array of strings into a single string with an offsets
00125     // array, and sends the offsets array (and the packed string, if
00126     // it is not empty).
00127     void
00128     sendStrings (const Comm<int>& comm, // in
00129      const Array<std::string>& strings, // in
00130      const int destRank) // in
00131     {
00132       // Pack the string array into the packed string, and compute
00133       // offsets.
00134       std::string packedString;
00135       Array<size_t> offsets;
00136       packStringsForSend (packedString, offsets, strings);
00137       TEUCHOS_TEST_FOR_EXCEPTION(offsets.size() == 0, std::logic_error, 
00138        "packStringsForSend() returned a zero-length offsets "
00139        "array on MPI Proc " << comm.getRank() << ", to be "
00140        "sent to Proc " << destRank << ".  The offsets array "
00141        "should always have positive length.  Please report "
00142        "this bug to the Teuchos developers.");
00143 
00144       // Send the count of offsets.
00145       send (comm, offsets.size(), destRank);
00146 
00147       // Send the array of offsets.  There is always at least one
00148       // element in the offsets array, so we can always take the
00149       // address of the first element.
00150       const int offsetsSendCount = static_cast<int> (offsets.size());
00151       send (comm, offsetsSendCount, &offsets[0], destRank);
00152 
00153       // Now send the packed string.  It may be empty if the strings
00154       // array has zero elements or if all the strings in the array
00155       // are empty.  If the packed string is empty, we don't send
00156       // anything, since the receiving process already knows (from the
00157       // offsets array) not to expect anything.
00158       const int stringSendCount = static_cast<int> (packedString.size());
00159       if (stringSendCount > 0)
00160   send (comm, stringSendCount, &packedString[0], destRank);
00161     }
00162 
00163     void
00164     unpackStringsAfterReceive (Array<std::string>& strings,
00165              const std::string& packedString,
00166              const Array<size_t> offsets)
00167     {
00168       const bool debug = false;
00169       if (debug)
00170   {
00171     using std::cerr;
00172     using std::endl;
00173 
00174     std::ostringstream out;
00175     RCP<const Comm<int> > pComm = DefaultComm<int>::getComm ();
00176     out << "Proc " << pComm->getRank() << ": in unpack: offsets = [";
00177     for (Array<size_t>::const_iterator it = offsets.begin(); 
00178          it != offsets.end(); ++it)
00179       {
00180         out << *it;
00181         if (it + 1 != offsets.end())
00182     out << ", ";
00183       }
00184     out << "], packedString = " << packedString << endl;
00185     cerr << out.str();
00186   }
00187       TEUCHOS_TEST_FOR_EXCEPTION(offsets.size() == 0, std::logic_error, 
00188        "The offsets array has length zero, which does not "
00189        "make sense.  Even when sending / receiving zero "
00190        "strings, the offsets array should have one entry "
00191        "(namely, zero).");
00192       const Array<size_t>::size_type numStrings = offsets.size() - 1;
00193       strings.resize (numStrings);
00194       for (Array<size_t>::size_type k = 0; k < numStrings; ++k)
00195   { // Exclusive index range in the packed string in which to
00196     // find the current string.
00197     const size_t start = offsets[k];
00198     const size_t end = offsets[k+1];
00199     strings[k] = packedString.substr (start, end - start);
00200   }
00201     }
00202 
00203     // Function corresponding to \c sendStrings() that receives an
00204     // array of strings (Array<std::string>) in packed form.
00205     void
00206     receiveStrings (const Comm<int>& comm,
00207         const int sourceRank,
00208         Array<std::string>& strings)
00209     {
00210       // Receive the number of offsets.  There should always be at
00211       // least 1 offset.
00212       Array<size_t>::size_type numOffsets = 0;
00213       receive (comm, sourceRank, &numOffsets);
00214       TEUCHOS_TEST_FOR_EXCEPTION(numOffsets == 0, std::logic_error, 
00215        "Invalid number of offsets numOffsets=" << numOffsets 
00216        << " received on MPI Rank " << comm.getRank() 
00217        << " from Rank " << sourceRank << ".  Please report "
00218        "this bug to the Teuchos developers.");
00219 
00220       // Receive the array of offsets.
00221       Array<size_t> offsets (numOffsets);
00222       const int offsetsRecvCount = static_cast<int> (numOffsets);
00223       receive (comm, sourceRank, offsetsRecvCount, &offsets[0]);
00224 
00225       // If the packed string is nonempty, receive the packed string,
00226       // and unpack it.  The last entry of offsets is the length of
00227       // the packed string.
00228       std::string packedString (offsets.back(), ' ');
00229       const int stringRecvCount = static_cast<int> (offsets.back());
00230       if (stringRecvCount > 0)
00231   {
00232     receive (comm, sourceRank, stringRecvCount, &packedString[0]);
00233     unpackStringsAfterReceive (strings, packedString, offsets);
00234   }
00235     }
00236 
00237 
00238     void
00239     broadcastStringsHelper (const Comm<int>& comm,
00240           const int myRank,
00241           const int left,
00242           const int right,
00243           Array<std::string>& globalNames)
00244     {
00245       // If left >= right, there is only one process, so we don't need
00246       // to do anything.
00247       //
00248       // If left < right, then split the inclusive interval [left,
00249       // right] into [left, mid-1] and [mid, right].  Send from left
00250       // to mid, and recurse on the two subintervals.
00251       if (left >= right)
00252   return;
00253       else
00254   {
00255     const int mid = left + (right - left + 1) / 2;
00256 
00257     // This could be optimized further on the sending rank, by
00258     // prepacking the strings so that they don't have to be
00259     // packed more than once.
00260     if (myRank == left)
00261       sendStrings (comm, globalNames, mid);
00262     else if (myRank == mid)
00263       receiveStrings (comm, left, globalNames);
00264 
00265     // Recurse on [left, mid-1] or [mid, right], depending on myRank.
00266     if (myRank >= left && myRank <= mid-1)
00267       broadcastStringsHelper (comm, myRank, left, mid-1, globalNames);
00268     else if (myRank >= mid && myRank <= right)
00269       broadcastStringsHelper (comm, myRank, mid, right, globalNames);
00270     else
00271       return; // Don't recurse if not participating.
00272   }
00273     }
00274 
00275 
00276     void
00277     broadcastStrings (const Comm<int>& comm,
00278           Array<std::string>& globalNames)
00279     {
00280       const int myRank = comm.getRank();
00281       const int left = 0;
00282       const int right = comm.getSize() - 1;
00283 
00284       broadcastStringsHelper (comm, myRank, left, right, globalNames);
00285     }
00286 
00287     // \brief Helper function for \c mergeCounterNamesHelper().
00288     //
00289     // The \c mergeCounterNamesHelper() function implements (using a
00290     // parallel reduction) the set union resp. intersection (depending
00291     // on the \c setOp argument) of the MPI process' sets of counter
00292     // names.  This function implements the binary associative
00293     // operator which computes the set union resp. intersection of two
00294     // sets: the "left" process' intermediate reduction result (global
00295     // counter names), and the "mid" process' local counter names.
00296     // 
00297     // \param comm [in] Communicator for which \c
00298     //   mergeCounterNamesHelper() was called.
00299     //
00300     // \param myRank [in] Rank of the calling MPI process; must be
00301     //   either == left or == mid.
00302     //
00303     // \param left [in] The "left" input argument of
00304     //   \c mergeCounterNamesHelper().
00305     //
00306     // \param mid [in] The value of "mid" in the implementation of \c
00307     //   mergeCounterNamesHelper().
00308     //
00309     // \param localNames [in] List of counter names belonging to the
00310     //   calling MPI process.
00311     //
00312     // \param globalNames [in/out] Only accessed if myRank == left.
00313     //   If so, on input: the intermediate reduction result of the
00314     //   union resp. intersection (depending on \c setOp).  On output:
00315     //   the union resp. intersection of the input value of the "left"
00316     //   MPI process' globalNames with the "mid" MPI process'
00317     //   localNames.
00318     //
00319     // \param setOp [in] If Intersection, compute the set intersection
00320     //   of counter names, else if Union, compute the set union of
00321     //   counter names.
00322     void
00323     mergeCounterNamesPair (const Comm<int>& comm, 
00324          const int myRank,
00325          const int left,
00326          const int mid,
00327          const Array<std::string>& localNames,
00328          Array<std::string>& globalNames,
00329          const ECounterSetOp setOp)
00330     {
00331       using std::cerr;
00332       using std::endl;
00333       using std::string;
00334 
00335       const bool debug = false;
00336 
00337       if (myRank == left)
00338   { // Receive names from the other process, and merge its names
00339     // with the names on this process.
00340     Array<string> otherNames;
00341     receiveStrings (comm, mid, otherNames);
00342 
00343     if (debug)
00344       {
00345         // Buffering locally in an ostringstream before writing to
00346         // the shared stderr sometimes helps avoid interleaved
00347         // debugging output.
00348         std::ostringstream out;
00349         out << "Proc " << myRank << ": in mergePair: otherNames = [";
00350         for (Array<std::string>::const_iterator it = otherNames.begin(); 
00351        it != otherNames.end(); ++it)
00352     {
00353       out << "\"" << *it << "\"";
00354       if (it + 1 != otherNames.end())
00355         out << ", ";
00356     }
00357         out << "]" << endl;
00358         cerr << out.str();
00359       }
00360 
00361     // Assume that both globalNames and otherNames are sorted.
00362     // Compute the set intersection / union as specified by the
00363     // enum.
00364     Array<string> newNames;
00365     if (setOp == Intersection)
00366       std::set_intersection (globalNames.begin(), globalNames.end(),
00367            otherNames.begin(), otherNames.end(),
00368            std::back_inserter (newNames));
00369     else if (setOp == Union)
00370       std::set_union (globalNames.begin(), globalNames.end(),
00371           otherNames.begin(), otherNames.end(),
00372           std::back_inserter (newNames));
00373     else
00374       TEUCHOS_TEST_FOR_EXCEPTION(setOp != Intersection && setOp != Union,
00375              std::logic_error,
00376              "Invalid set operation enum value.  Please "
00377              "report this bug to the Teuchos developers.");
00378     globalNames.swap (newNames);
00379   }
00380       else if (myRank == mid)
00381   sendStrings (comm, localNames, left);
00382       else
00383   TEUCHOS_TEST_FOR_EXCEPTION(myRank != left && myRank != mid, 
00384          std::logic_error,
00385          "myRank=" << myRank << " is neither left=" << left
00386          << " nor mid=" << mid << ".  Please report this "
00387          "bug to the Teuchos developers.");
00388     }
00389 
00390     // Recursive helper function for \c mergeCounterNames().
00391     //
00392     // This function implements the set union resp. intersection
00393     // (depending on the \c setOp argument) of the MPI process' sets
00394     // of counter names, using a parallel reduction. (Since the
00395     // Teuchos comm wrappers as of 11 July 2011 lack a wrapper for
00396     // MPI_Reduce(), we hand-roll the reduction using a binary tree
00397     // via recursion.  We don't need an all-reduce in this case.)
00398     void
00399     mergeCounterNamesHelper (const Comm<int>& comm, 
00400            const int myRank,
00401            const int left,
00402            const int right, // inclusive range [left, right]
00403            const Array<std::string>& localNames,
00404            Array<std::string>& globalNames,
00405            const ECounterSetOp setOp)
00406     {
00407       // Correctness proof:
00408       //
00409       // 1. Both set intersection and set union are associative (and
00410       //    indeed even commutative) operations.
00411       // 2. mergeCounterNamesHelper() is just a reduction by binary tree.
00412       // 3. Reductions may use any tree shape as long as the binary
00413       //    operation is associative.
00414       //
00415       // Recursive "reduction" algorithm:
00416       //
00417       // Let mid be the midpoint of the inclusive interval [left,
00418       // right].  If the (intersection, union) of [left, mid-1] and
00419       // the (intersection, union) of [mid, right] are both computed
00420       // correctly, then the (intersection, union) of these two sets
00421       // is the (intersection, union) of [left, right].
00422       //
00423       // The base case is left == right: the (intersection, union) of
00424       // one set is simply that set, so copy localNames into
00425       // globalNames.
00426       //
00427       // We include another base case for safety: left > right,
00428       // meaning that the set of processes is empty, so we do nothing
00429       // (the (intersection, union) of an empty set of sets is the
00430       // empty set).
00431       if (left > right)
00432   return;
00433       else if (left == right)
00434   {
00435     Array<string> newNames;
00436     newNames.reserve (localNames.size());
00437     std::copy (localNames.begin(), localNames.end(), 
00438          std::back_inserter (newNames));
00439     globalNames.swap (newNames);
00440   }
00441       else
00442   { // You're sending messages across the network, so don't
00443     // bother to optimize away a few branches here.
00444     //
00445     // Recurse on [left, mid-1] or [mid, right], depending on myRank.
00446     const int mid = left + (right - left + 1) / 2;
00447     if (myRank >= left && myRank <= mid-1)
00448       mergeCounterNamesHelper (comm, myRank, left, mid-1, 
00449              localNames, globalNames, setOp);
00450     else if (myRank >= mid && myRank <= right)
00451       mergeCounterNamesHelper (comm, myRank, mid, right,
00452              localNames, globalNames, setOp);
00453     else
00454       return; // Don't call mergeCounterNamesPair() if not participating.
00455 
00456     // Combine the results of the recursive step.
00457     if (myRank == left || myRank == mid)
00458       mergeCounterNamesPair (comm, myRank, left, mid, 
00459            localNames, globalNames, setOp);
00460   }
00461     }
00462 
00463   } // namespace (anonymous)
00464 
00465   void
00466   mergeCounterNames (const Comm<int>& comm, 
00467          const Array<std::string>& localNames,
00468          Array<std::string>& globalNames,
00469          const ECounterSetOp setOp)
00470   {
00471     const int myRank = comm.getRank();
00472     const int left = 0;
00473     const int right = comm.getSize() - 1;
00474     Array<std::string> theGlobalNames;
00475     mergeCounterNamesHelper (comm, myRank, left, right, 
00476            localNames, theGlobalNames, setOp);
00477 
00478     // Proc 0 has the list of counter names.  Now broadcast it back to
00479     // all the procs.
00480     broadcastStrings (comm, theGlobalNames);
00481 
00482     // "Transactional" semantics ensure strong exception safety for
00483     // output.
00484     globalNames.swap (theGlobalNames);
00485   }
00486 
00487 } // namespace Teuchos
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines