Tpetra_Distributor.hpp

00001 // @HEADER
00002 // ***********************************************************************
00003 // 
00004 //          Tpetra: Templated Linear Algebra Services Package
00005 //                 Copyright (2008) 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 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //  
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //  
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00025 // 
00026 // ***********************************************************************
00027 // @HEADER
00028 
00029 #ifndef TPETRA_DISTRIBUTOR_HPP
00030 #define TPETRA_DISTRIBUTOR_HPP
00031 
00032 #include "Tpetra_Util.hpp"
00033 #include <Teuchos_RCP.hpp>
00034 #include <Teuchos_as.hpp>
00035 #include <Teuchos_TypeNameTraits.hpp>
00036 #include <Teuchos_Describable.hpp>
00037 #include <Teuchos_Comm.hpp>
00038 #include <Teuchos_CommHelpers.hpp>
00039 #include <Teuchos_Array.hpp>
00040 #include <Teuchos_ArrayView.hpp>
00041 #include <Teuchos_ArrayRCP.hpp>
00042 
00043 
00044 // FINISH: some of the get accessors may not be necessary anymore. clean up.
00045 // FINISH: This class may not be const correct. doPosts() et al. perhaps should be const, with affected members made mutable.
00046 
00047 namespace Tpetra {
00048 
00050 
00055   class Distributor : public Teuchos::Describable {
00056   public:
00057 
00059 
00060 
00062     explicit Distributor(const Teuchos::RCP<const Teuchos::Comm<int> > & comm);
00063 
00065     Distributor(const Distributor &distributor);
00066 
00068     ~Distributor();
00069 
00071 
00072 
00074 
00075 
00077 
00094     size_t createFromSends(const Teuchos::ArrayView<const int> &exportNodeIDs);
00095 
00097 
00117     template <class Ordinal>
00118     void createFromRecvs(const Teuchos::ArrayView<const Ordinal> &remoteIDs, 
00119                          const Teuchos::ArrayView<const int> &remoteNodeIDs, 
00120                                Teuchos::ArrayRCP<Ordinal> &exportIDs, 
00121                                Teuchos::ArrayRCP<int> &exportNodeIDs);
00122 
00124 
00126 
00127 
00129     size_t getNumReceives() const;
00130 
00132     size_t getNumSends() const;
00133 
00135 
00136     bool hasSelfMessage() const;
00137 
00139     size_t getMaxSendLength() const;
00140 
00142     size_t getTotalReceiveLength() const;
00143 
00145     Teuchos::ArrayView<const int> getImagesFrom() const;
00146 
00148     Teuchos::ArrayView<const int> getImagesTo() const;
00149 
00151 
00152     Teuchos::ArrayView<const size_t> getLengthsFrom() const;
00153 
00155 
00156     Teuchos::ArrayView<const size_t> getLengthsTo() const;
00157 
00159 
00161 
00162 
00164 
00167     const Teuchos::RCP<Distributor> & getReverse() const;
00168 
00170 
00172 
00173 
00175 
00186     template <class Packet>
00187     void doPostsAndWaits(const Teuchos::ArrayView<const Packet> &exports,
00188                          size_t numPackets,
00189                          const Teuchos::ArrayView<Packet> &imports);
00190 
00192 
00203     template <class Packet>
00204     void doPosts(const Teuchos::ArrayView<const Packet> &exports,
00205                  size_t numPackets,
00206                  const Teuchos::ArrayRCP<Packet> &imports);
00207 
00209     void doWaits();
00210 
00212 
00223     template <class Packet>
00224     void doReversePostsAndWaits(const Teuchos::ArrayView<const Packet> &exports,
00225                                 size_t numPackets,
00226                                 const Teuchos::ArrayView<Packet> &imports);
00227 
00229 
00240     template <class Packet>
00241     void doReversePosts(const Teuchos::ArrayView<const Packet> &exports,
00242                         size_t numPackets,
00243                         const Teuchos::ArrayRCP<Packet> &imports);
00244 
00246     void doReverseWaits();
00247 
00249 
00251 
00252 
00254     std::string description() const;
00255 
00257     void describe(Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const;
00258 
00260 
00261   private:
00262 
00263     // private data members
00264     Teuchos::RCP<const Teuchos::Comm<int> > comm_;
00265 
00266     size_t numExports_;
00267     // selfMessage_ is whether I have a send for myself
00268     bool selfMessage_;
00269     // numSends_ is number of sends to other nodes; is less than or equal to the number of nodes
00270     size_t numSends_;
00271     // imagesTo_, startsTo_ and lengthsTo_ each have size 
00272     //   numSends_ + selfMessage_
00273     Teuchos::Array<int> imagesTo_;
00274     /* Given an export buffer that contains all of the item being sent by this node,
00275        the block of values for node i will start at position startsTo_[i]  */
00276     Teuchos::Array<size_t> startsTo_;
00277     Teuchos::Array<size_t> lengthsTo_;
00278     // maxSendLength_ is the maximum send to another node: 
00279     //   max(lengthsTo_[i]) for i != me
00280     size_t maxSendLength_;
00281     Teuchos::Array<size_t> indicesTo_;
00282     // numReceives_ is the number of receives by me from other procs, not
00283     // counting self receives
00284     size_t numReceives_;
00285     // totalReceiveLength_ is the total number of Packet received, used to 
00286     // allocate the receive buffer
00287     size_t totalReceiveLength_;
00288     // imagesFrom_, startsFrom_ and lengthsFrom_ each have size 
00289     //   numReceives_ + selfMessage_
00290     Teuchos::Array<size_t> lengthsFrom_;
00291     Teuchos::Array<int> imagesFrom_;
00292     Teuchos::Array<size_t> startsFrom_;
00293     Teuchos::Array<size_t> indicesFrom_;
00294 
00295     // requests associated with non-blocking receives
00296     Teuchos::Array<Teuchos::RCP<Teuchos::CommRequest> > requests_;
00297 
00298     mutable Teuchos::RCP<Distributor> reverseDistributor_;
00299 
00300     // compute receive info from sends
00301     void computeReceives();
00302 
00303     // compute send info from receives
00304     template <class Ordinal>
00305     void computeSends(const Teuchos::ArrayView<const Ordinal> &importIDs,
00306                       const Teuchos::ArrayView<const int> &importNodeIDs,
00307                             Teuchos::ArrayRCP<Ordinal> &exportIDs,
00308                             Teuchos::ArrayRCP<int> &exportNodeIDs);
00309 
00310     // create a distributor for the reverse communciation pattern (pretty much
00311     // swap all send and receive info)
00312     void createReverseDistributor() const;
00313 
00314   }; // class Distributor
00315 
00316 
00317   template <class Packet>
00318   void Distributor::doPostsAndWaits(
00319       const Teuchos::ArrayView<const Packet>& exports,
00320       size_t numPackets,
00321       const Teuchos::ArrayView<Packet>& imports) 
00322   {
00323     TEST_FOR_EXCEPTION(requests_.size() != 0, std::runtime_error,
00324         Teuchos::typeName(*this) << "::doPostsAndWaits(): Cannot call with outstanding posts.");
00325     // doPosts takes imports as an ArrayRCP, requiring that the memory location is persisting
00326     // however, it need only persist until doWaits is called, so it is safe for us to 
00327     // use a non-persisting reference in this case
00328     doPosts(exports, numPackets, Teuchos::arcp<Packet>(imports.getRawPtr(),0,imports.size(),false));
00329     doWaits();
00330   }
00331 
00332 
00333   template <class Packet>
00334   void Distributor::doPosts(const Teuchos::ArrayView<const Packet>& exports,
00335                             size_t numPackets,
00336                             const Teuchos::ArrayRCP<Packet>& imports) {
00337     using Teuchos::ArrayRCP;
00338     // start of actual doPosts function
00339     const int myImageID = comm_->getRank();
00340     size_t selfReceiveOffset = 0;
00341 
00342 #ifdef HAVE_TEUCHOS_DEBUG
00343     TEST_FOR_EXCEPTION(Teuchos::as<size_t>(imports.size()) != totalReceiveLength_ * numPackets, std::runtime_error,
00344         Teuchos::typeName(*this) << "::doPosts(): imports must be large enough to store the imported data.");
00345 #endif
00346 
00347     // allocate space in requests
00348     requests_.resize(0);
00349     requests_.reserve(numReceives_);
00350 
00351     // start up the Irecv's
00352     {
00353       size_t curBufferOffset = 0;
00354       for (size_t i = 0; i < numReceives_ + (selfMessage_ ? 1 : 0); ++i) {
00355         if (imagesFrom_[i] != myImageID) { 
00356           // receiving this one from another image
00357           // setup reference into imports of the appropriate size and at the appropriate place
00358           ArrayRCP<Packet> impptr = imports.persistingView(curBufferOffset,lengthsFrom_[i]*numPackets);
00359           requests_.push_back( Teuchos::ireceive<int,Packet>(*comm_,impptr,imagesFrom_[i]) );
00360         }
00361         else {
00362           // receiving this one from myself 
00363           // note that offset
00364           selfReceiveOffset = curBufferOffset;
00365         }
00366         curBufferOffset += lengthsFrom_[i]*numPackets;
00367       }
00368     }
00369 
00370     // wait for everyone else before posting ready-sends below to ensure that 
00371     // all non-blocking receives above have been posted
00372     Teuchos::barrier(*comm_);
00373 
00374     // setup scan through imagesTo_ list starting with higher numbered images
00375     // (should help balance message traffic)
00376     size_t numBlocks = numSends_+ selfMessage_;
00377     size_t imageIndex = 0;
00378     while ((imageIndex < numBlocks) && (imagesTo_[imageIndex] < myImageID)) {
00379       ++imageIndex;
00380     }
00381     if (imageIndex == numBlocks) {
00382       imageIndex = 0;
00383     }
00384 
00385     size_t selfNum = 0;
00386     size_t selfIndex = 0;
00387 
00388     if (indicesTo_.empty()) { // data is already blocked by processor
00389       for (size_t i = 0; i < numBlocks; ++i) {
00390         size_t p = i + imageIndex;
00391         if (p > (numBlocks - 1)) {
00392           p -= numBlocks;
00393         }
00394 
00395         if (imagesTo_[p] != myImageID) {
00396           // sending it to another image
00397           Teuchos::ArrayView<const Packet> tmpSend(&exports[startsTo_[p]*numPackets],lengthsTo_[p]*numPackets);
00398           Teuchos::readySend<int,Packet>(*comm_,tmpSend,imagesTo_[p]);
00399         }
00400         else {
00401           // sending it to ourself
00402           selfNum = p;
00403         }
00404       }
00405 
00406       if (selfMessage_) {
00407         std::copy(exports.begin()+startsTo_[selfNum]*numPackets, exports.begin()+startsTo_[selfNum]*numPackets+lengthsTo_[selfNum]*numPackets, 
00408                   imports.begin()+selfReceiveOffset);
00409       }
00410     }
00411     else { // data is not blocked by image, use send buffer
00412       // allocate sendArray buffer
00413       Teuchos::Array<Packet> sendArray(maxSendLength_*numPackets); 
00414 
00415       for (size_t i = 0; i < numBlocks; ++i) {
00416         size_t p = i + imageIndex;
00417         if (p > (numBlocks - 1)) {
00418           p -= numBlocks;
00419         }
00420 
00421         if (imagesTo_[p] != myImageID) { 
00422           // sending it to another image
00423           typename Teuchos::ArrayView<const Packet>::iterator srcBegin, srcEnd;
00424           size_t sendArrayOffset = 0;
00425           size_t j = startsTo_[p];
00426           for (size_t k = 0; k < lengthsTo_[p]; ++k, ++j) {
00427             srcBegin = exports.begin() + indicesTo_[j]*numPackets;
00428             srcEnd   = srcBegin + numPackets;
00429             std::copy( srcBegin, srcEnd, sendArray.begin()+sendArrayOffset );
00430             sendArrayOffset += numPackets;
00431           }
00432           Teuchos::ArrayView<const Packet> tmpSend = sendArray(0,lengthsTo_[p]*numPackets);
00433           Teuchos::readySend<int,Packet>(*comm_,tmpSend,imagesTo_[p]);
00434         }
00435         else { 
00436           // sending it to myself
00437           selfNum = p;
00438           selfIndex = startsTo_[p];
00439         }
00440       }
00441 
00442       if (selfMessage_) {
00443         for (size_t k = 0; k < lengthsTo_[selfNum]; ++k) {
00444           std::copy( exports.begin()+indicesTo_[selfIndex]*numPackets,
00445                      exports.begin()+indicesTo_[selfIndex]*numPackets + numPackets,
00446                      imports.begin() + selfReceiveOffset );
00447           ++selfIndex;
00448           selfReceiveOffset += numPackets;
00449         }
00450       }
00451     }
00452   }
00453 
00454 
00455   template <class Packet>
00456   void Distributor::doReversePostsAndWaits(
00457       const Teuchos::ArrayView<const Packet>& exports,
00458       size_t numPackets,
00459       const Teuchos::ArrayView<Packet>& imports) 
00460   {
00461     // doPosts takes imports as an ArrayRCP, requiring that the memory location is persisting
00462     // however, it need only persist until doWaits is called, so it is safe for us to 
00463     // use a non-persisting reference in this case
00464     doReversePosts(exports, numPackets, Teuchos::arcp<Packet>(imports.getRawPtr(),0,imports.size(),false));
00465     doReverseWaits();
00466   }
00467 
00468 
00469   template <class Packet>
00470   void Distributor::doReversePosts(
00471       const Teuchos::ArrayView<const Packet>& exports,
00472       size_t numPackets,
00473       const Teuchos::ArrayRCP<Packet>& imports) 
00474   {
00475     TEST_FOR_EXCEPTION(!indicesTo_.empty(),std::runtime_error,
00476         Teuchos::typeName(*this) << "::doReversePosts(): Can only do reverse comm when original data is blocked by image.");
00477     if (reverseDistributor_ == Teuchos::null) {
00478       createReverseDistributor();
00479     }
00480     reverseDistributor_->doPosts(exports,numPackets,imports);
00481   }
00482 
00483 
00484   // note: assumes that size_t >= Ordinal
00486   template <class Ordinal>
00487   void Distributor::computeSends(
00488       const Teuchos::ArrayView<const Ordinal> & importIDs,
00489       const Teuchos::ArrayView<const int> & importNodeIDs,
00490             Teuchos::ArrayRCP<Ordinal>& exportIDs,
00491             Teuchos::ArrayRCP<int>& exportNodeIDs)
00492   {
00493     int myImageID = comm_->getRank();
00494 
00495     size_t numImports = importNodeIDs.size();
00496     Teuchos::Array<size_t> importObjs(2*numImports);
00497     for (size_t i = 0; i < numImports; ++i ) {  
00498       importObjs[2*i]   = Teuchos::as<size_t>(importIDs[i]);
00499       importObjs[2*i+1] = Teuchos::as<size_t>(myImageID);
00500     }
00501 
00502     size_t numExports;
00503     Distributor tempPlan(comm_);
00504     numExports = tempPlan.createFromSends(importNodeIDs);
00505     if (numExports > 0) {
00506       exportIDs = Teuchos::arcp<Ordinal>(numExports);
00507       exportNodeIDs = Teuchos::arcp<int>(numExports);
00508     }
00509 
00510     Teuchos::Array<size_t> exportObjs(tempPlan.getTotalReceiveLength()*2);
00511     tempPlan.doPostsAndWaits<size_t>(importObjs(),2,exportObjs());
00512 
00513     for (size_t i = 0; i < numExports; ++i) {
00514       exportIDs[i]     = Teuchos::as<Ordinal>(exportObjs[2*i]);
00515       exportNodeIDs[i] = exportObjs[2*i+1];
00516     }
00517   }
00518 
00519 
00521   template <class Ordinal>
00522   void Distributor::createFromRecvs(
00523       const Teuchos::ArrayView<const Ordinal> &remoteIDs, 
00524       const Teuchos::ArrayView<const int> &remoteImageIDs, 
00525             Teuchos::ArrayRCP<Ordinal> &exportGIDs, 
00526             Teuchos::ArrayRCP<int> &exportNodeIDs)
00527   {
00528     {
00529       const int myImageID = comm_->getRank();
00530       int err_node = (remoteIDs.size() != remoteImageIDs.size()) ? myImageID : -1;
00531       int gbl_err;
00532       Teuchos::reduceAll(*comm_,Teuchos::REDUCE_MAX,err_node,&gbl_err);
00533       TEST_FOR_EXCEPTION(gbl_err != -1, std::runtime_error,
00534           Teuchos::typeName(*this) 
00535           << "::createFromRecvs(): lists of remote IDs and remote node IDs must have the same size (error on node " 
00536           << gbl_err << ").");
00537     }
00538     computeSends(remoteIDs, remoteImageIDs, exportGIDs, exportNodeIDs);
00539     (void)createFromSends(exportNodeIDs());
00540   }
00541 
00542 } // namespace Tpetra
00543 
00544 #endif // TPETRA_DISTRIBUTOR_HPP

Generated on Wed May 12 21:40:14 2010 for Tpetra Matrix/Vector Services by  doxygen 1.4.7