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