Zoltan2
Zoltan2_IdentifierMap.hpp
Go to the documentation of this file.
00001 // @HEADER
00002 //
00003 // ***********************************************************************
00004 //
00005 //   Zoltan2: A package of combinatorial algorithms for scientific computing
00006 //                  Copyright 2012 Sandia Corporation
00007 //
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Karen Devine      (kddevin@sandia.gov)
00039 //                    Erik Boman        (egboman@sandia.gov)
00040 //                    Siva Rajamanickam (srajama@sandia.gov)
00041 //
00042 // ***********************************************************************
00043 //
00044 // @HEADER
00045 
00050 #ifndef _ZOLTAN2_IDENTIFIERMAP_HPP_
00051 #define _ZOLTAN2_IDENTIFIERMAP_HPP_
00052 
00053 #include <Zoltan2_IdentifierTraits.hpp>
00054 #include <Zoltan2_InputTraits.hpp>
00055 #include <Zoltan2_AlltoAll.hpp>
00056 #include <Zoltan2_GidLookupHelper.hpp>
00057 
00058 #include <vector>
00059 #include <algorithm>
00060 #include <map>
00061 #include <iostream>
00062 
00063 #include <Teuchos_as.hpp>
00064 #include <Teuchos_CommHelpers.hpp>
00065 
00066 namespace Zoltan2
00067 {
00071 enum TranslationType {
00072   TRANSLATE_APP_TO_LIB,  
00073   TRANSLATE_LIB_TO_APP   
00074 };
00075 
00101 
00102 // Declarations
00104 
00105 template<typename User>
00106     class IdentifierMap{
00107 
00108 public:
00109 
00121   typedef typename InputTraits<User>::lno_t lno_t;
00122   typedef typename InputTraits<User>::gno_t gno_t;
00123   typedef typename InputTraits<User>::gid_t gid_t;
00124 
00125   explicit IdentifierMap( const RCP<const Environment > &env,
00126                           const RCP<const Comm<int> > &comm,
00127                           const ArrayRCP<const gid_t> &gids,
00128                           bool gidsMustBeConsecutive=false);
00129 
00131   ~IdentifierMap() {};
00132 
00134   IdentifierMap(const IdentifierMap &id);
00135 
00137   IdentifierMap &operator=(const IdentifierMap &id);
00138 
00142   bool gnosAreGids() const;
00143 
00146   gno_t getGlobalNumberOfIds() const { return globalNumberOfIds_;}
00147 
00150   gno_t getLocalNumberOfIds() const { return localNumberOfIds_;}
00151 
00155   void getGnoRange(gno_t &min, gno_t &max) const;
00156 
00159   bool gnosAreConsecutive() const;
00160 
00163   bool consecutiveGnosAreRequired() const;
00164 
00167   gno_t getMinimumGlobalId() const;
00168 
00171   gno_t getMaximumGlobalId() const;
00172 
00191   void gidTranslate(ArrayView<gid_t> gid,
00192                     ArrayView<gno_t> gno,
00193                     TranslationType tt) const;
00194 
00216   void lnoTranslate(ArrayView<lno_t> lno,
00217                     ArrayView<gno_t> gno,
00218                     TranslationType tt) const;
00219 
00239   void gidGlobalTranslate( ArrayView<const gid_t> in_gid,
00240                            ArrayView<gno_t> out_gno,
00241                            ArrayView<int> out_proc) const;
00242 
00261   void gnoGlobalTranslate( ArrayView<const gno_t> in_gno,
00262                            ArrayView<gid_t> out_gid,
00263                            ArrayView<int> out_proc) const;
00264 private:
00265 
00266   // Problem parameters, library configuration.
00267 
00268   const RCP<const Environment> env_;
00269 
00270   // Problem communicator
00271 
00272   const RCP<const Comm<int> > comm_;
00273 
00274   // Application global IDs
00275 
00276   const ArrayRCP<const gid_t> myGids_;
00277 
00278   // Zoltan2 gno_ts will be consecutive if the application gid_ts
00279   // were mapped to gno_ts, or if the application gid_ts happen
00280   // to be consecutive ordinals.  In either case, gnoDist_[p]
00281   // is the first gno_t on process p.  gnoDist_[numProcs_] is the
00282   // global total of gno_ts.
00283 
00284   ArrayRCP<gno_t> gnoDist_;
00285 
00286   // If application gids are not consecutive ordinals, the gidLookup_
00287   // object allows lookup of the location of the gid_t in the myGids_ list.
00288 
00289   RCP<GidLookupHelper<gid_t, lno_t > > gidLookup_;
00290 
00291   global_size_t globalNumberOfIds_;
00292   size_t localNumberOfIds_;
00293   int myRank_;
00294   int numProcs_;
00295 
00296   // By "Consecutive" we mean globally consecutive increasing
00297   // with process rank.
00298 
00299   bool userGidsAreTeuchosOrdinal_;
00300   bool userGidsAreConsecutive_;
00301   bool userGidsAreZoltan2Gnos_;
00302   bool zoltan2GnosAreConsecutive_;
00303 
00304   bool consecutiveGidsAreRequired_;
00305 
00306   gno_t minGlobalGno_;
00307   gno_t maxGlobalGno_;
00308 
00309   void setupMap();
00310 };
00311 
00313 // Definitions
00315 
00316 template<typename User>
00317   IdentifierMap<User>::IdentifierMap( const RCP<const Environment> &env,
00318     const RCP<const Comm<int> > &comm,
00319     const ArrayRCP<const gid_t> &gids, bool idsMustBeConsecutive) :
00320       env_(env), comm_(comm), myGids_(gids), gnoDist_(), gidLookup_(),
00321       globalNumberOfIds_(0), localNumberOfIds_(0),
00322       myRank_(comm_->getRank()), numProcs_(comm_->getSize()),
00323       userGidsAreTeuchosOrdinal_(false), userGidsAreConsecutive_(false),
00324       userGidsAreZoltan2Gnos_(false), zoltan2GnosAreConsecutive_(false),
00325       consecutiveGidsAreRequired_(idsMustBeConsecutive),
00326       minGlobalGno_(0), maxGlobalGno_(0)
00327 {
00328   env_->memory("Initial memory in use");
00329 
00330   setupMap();
00331 
00332   env_->memory("After user IDs mapped");
00333 }
00334 
00335 // TODO many of these should be inline
00336 
00337 template< typename User>
00338   bool IdentifierMap<User>::gnosAreGids() const
00339 {
00340   return userGidsAreZoltan2Gnos_;
00341 }
00342 
00343 template <typename User>
00344   void IdentifierMap<User>::getGnoRange(gno_t &min, gno_t &max) const
00345 {
00346   min = minGlobalGno_;
00347   max = maxGlobalGno_;
00348 }
00349 
00350 template< typename User>
00351   bool IdentifierMap<User>::gnosAreConsecutive() const
00352 {
00353   return zoltan2GnosAreConsecutive_;
00354 }
00355 
00356 template< typename User>
00357   bool IdentifierMap<User>::consecutiveGnosAreRequired() const
00358 {
00359   return consecutiveGidsAreRequired_;
00360 }
00361 
00362 template< typename User>
00363   typename InputTraits<User>::gno_t IdentifierMap<User>::getMinimumGlobalId() const
00364 {
00365   return minGlobalGno_;
00366 }
00367 
00368 template< typename User>
00369   typename InputTraits<User>::gno_t IdentifierMap<User>::getMaximumGlobalId() const
00370 {
00371   return maxGlobalGno_;
00372 }
00373 
00374 template< typename User>
00375   void IdentifierMap<User>::gidTranslate(
00376     ArrayView<gid_t> gid,
00377     ArrayView<gno_t> gno,
00378     TranslationType tt) const
00379 {
00380   typename ArrayView<gid_t>::size_type inLen=gid.size();
00381 
00382   if (inLen == 0){
00383     return;
00384   }
00385 
00386   env_->localInputAssertion(__FILE__, __LINE__, "invalid TranslationType",
00387     (tt==TRANSLATE_APP_TO_LIB) || (tt==TRANSLATE_LIB_TO_APP),
00388     BASIC_ASSERTION);
00389 
00390   env_->localInputAssertion(__FILE__, __LINE__,
00391     "Destination array is too small",
00392     ((tt==TRANSLATE_LIB_TO_APP) && (gid.size() >= gno.size())) ||
00393      ((tt==TRANSLATE_APP_TO_LIB) && (gno.size() >= gid.size())),
00394     BASIC_ASSERTION);
00395 
00396   if (userGidsAreZoltan2Gnos_){   // our gnos are the app gids
00397     if (tt == TRANSLATE_LIB_TO_APP)
00398       for (typename ArrayView<gid_t>::size_type i=0; i < inLen; i++)
00399         gid[i] = static_cast<gid_t>(gno[i]);
00400     else
00401       for (typename ArrayView<gid_t>::size_type i=0; i < inLen; i++)
00402         gno[i] = static_cast<gno_t>(gid[i]);
00403   }
00404   else{              // we mapped gids to consecutive gnos
00405     gno_t firstGno = gnoDist_[myRank_];
00406     gno_t endGno = gnoDist_[myRank_ + 1];
00407 
00408     if (tt == TRANSLATE_LIB_TO_APP){
00409       for (typename ArrayView<gid_t>::size_type i=0; i < inLen; i++){
00410 
00411         env_->localInputAssertion(__FILE__, __LINE__, "invalid global number",
00412         (gno[i] >= firstGno) && (gno[i] < endGno), BASIC_ASSERTION);
00413 
00414         gid[i] = myGids_[gno[i] - firstGno];
00415       }
00416     }
00417     else{
00418       lno_t idx=0;
00419       if (userGidsAreConsecutive_){
00420         for (typename ArrayView<gid_t>::size_type i=0; i < inLen; i++){
00421           gno[i] = firstGno + IdentifierTraits<gid_t>::difference(
00422             myGids_[0], gid[i]);
00423           env_->localInputAssertion(__FILE__, __LINE__, "invalid global id",
00424             (gno[i] >= firstGno) && (gno[i] < endGno), BASIC_ASSERTION);
00425         }
00426       }
00427       else{
00428         for (typename ArrayView<gid_t>::size_type i=0; i < inLen; i++){
00429           try{
00430             idx = gidLookup_->lookup(gid[i]);
00431           }
00432           catch (const std::exception &e) {
00433             env_->localInputAssertion(__FILE__, __LINE__, "invalid global id",
00434               false, BASIC_ASSERTION);
00435           }
00436 
00437           gno[i] = firstGno + idx;
00438         }
00439       }
00440     }
00441   }
00442   return;
00443 }
00444 
00445 template< typename User>
00446   void IdentifierMap<User>::lnoTranslate(
00447     ArrayView<lno_t> lno,
00448     ArrayView<gno_t> gno,
00449     TranslationType tt) const
00450 {
00451   typename ArrayView<lno_t>::size_type inLen=lno.size();
00452 
00453   if (inLen == 0){
00454     return;
00455   }
00456   env_->localInputAssertion(__FILE__, __LINE__, "invalid TranslationType",
00457     (tt==TRANSLATE_LIB_TO_APP) || (tt==TRANSLATE_APP_TO_LIB),
00458     BASIC_ASSERTION);
00459 
00460   env_->localInputAssertion(__FILE__, __LINE__,
00461     "Destination array is too small",
00462     ((tt==TRANSLATE_LIB_TO_APP) && (lno.size() >= gno.size())) ||
00463     ((tt==TRANSLATE_APP_TO_LIB) && (gno.size() >= lno.size())),
00464     BASIC_ASSERTION);
00465 
00466   gno_t firstGno(0), endGno(0);
00467   if (gnoDist_.size() > 0){
00468     firstGno = gnoDist_[myRank_];
00469     endGno = gnoDist_[myRank_+1];
00470   }
00471 
00472   if (tt == TRANSLATE_LIB_TO_APP){
00473     if (gnoDist_.size() > 0) {   // gnos are consecutive
00474       for (typename ArrayView<lno_t>::size_type i=0; i < inLen; i++){
00475         env_->localInputAssertion(__FILE__, __LINE__, "invalid global number",
00476           (gno[i] >= firstGno) && (gno[i] < endGno), BASIC_ASSERTION);
00477         lno[i] = gno[i] - firstGno;
00478       }
00479     }
00480     else {                    // gnos must be the app gids
00481       if (userGidsAreConsecutive_){
00482         for (typename ArrayView<lno_t>::size_type i=0; i < inLen; i++){
00483           gid_t tmp = static_cast<gid_t>(gno[i]);
00484           lno[i] = IdentifierTraits<gid_t>::difference(myGids_[0], tmp);
00485           env_->localInputAssertion(__FILE__, __LINE__, "invalid global number",
00486             (lno[i] >= 0) && (lno[i] < lno_t(localNumberOfIds_)),
00487             BASIC_ASSERTION);
00488         }
00489       }
00490       else{
00491         for (typename ArrayView<lno_t>::size_type i=0; i < inLen; i++){
00492           try{
00493             gid_t keyArg = static_cast<gid_t>(gno[i]);
00494             lno[i] = gidLookup_->lookup(keyArg);
00495           }
00496           catch (const std::exception &e) {
00497             env_->localInputAssertion(__FILE__, __LINE__,
00498               "invalid global number", false, BASIC_ASSERTION);
00499           }
00500         }
00501       }
00502     }
00503   }
00504   else{                           // TRANSLATE_APP_TO_LIB
00505     for (typename ArrayView<lno_t>::size_type i=0; i < inLen; i++){
00506       lno_t idx = lno[i];
00507 
00508       if (gnoDist_.size() > 0)  // gnos are consecutive
00509         gno[i] = firstGno + idx;
00510       else                     // gnos must be the app gids
00511         gno[i] = static_cast<gno_t>(myGids_[idx]);
00512     }
00513   }
00514 }
00515 
00516 template< typename User>
00517   void IdentifierMap<User>::gidGlobalTranslate(
00518     ArrayView<const gid_t> in_gid,
00519     ArrayView<gno_t> out_gno,
00520     ArrayView<int> out_proc) const
00521 {
00522   typename ArrayView<const gid_t>::size_type inLen = in_gid.size();
00523 
00524   // It's faster in loops to user raw pointers.
00525   const gid_t *gids = in_gid.getRawPtr();
00526   gno_t *gnos = out_gno.getRawPtr();
00527   int *pids = out_proc.getRawPtr();
00528 
00529   bool needGnos = false;
00530 
00531   if (out_gno.size() > 0){
00532     env_->localInputAssertion(__FILE__, __LINE__, "array too small",
00533       out_gno.size()>=static_cast<typename ArrayView<gno_t>::size_type>(inLen),
00534       BASIC_ASSERTION);
00535 
00536     if (userGidsAreZoltan2Gnos_){
00537       // Global numbers are the application global IDs
00538       for (typename ArrayView<const gid_t>::size_type i=0; i < inLen; i++)
00539         gnos[i] = static_cast<gno_t>(gids[i]);
00540     }
00541     else
00542       needGnos = true;
00543   }
00544 
00545   bool needProcs = false;
00546 
00547   if (out_proc.size() > 0){
00548     env_->localInputAssertion(__FILE__, __LINE__, "array too small",
00549       out_proc.size()>=static_cast<typename ArrayView<int>::size_type>(inLen),
00550       BASIC_ASSERTION);
00551 
00552     if (userGidsAreZoltan2Gnos_ && (gnoDist_.size() > 0)){
00553 
00554       // The gids are the gnos, which are consecutive
00555       // increasing with rank.
00556 
00557       gno_t *gnoDist = gnoDist_.getRawPtr();
00558       gno_t *gnoEnd = gnoDist + numProcs_ + 1;
00559 
00560       for (typename ArrayView<const gid_t>::size_type i=0; i < inLen; i++){
00561         gno_t gno = static_cast<gno_t>(gids[i]);
00562         // pointer to first entry greater than gno
00563         gno_t *ub = std::upper_bound(gnoDist, gnoEnd, gno);
00564 
00565         if (ub == gnoDist || ub == gnoEnd)
00566           pids[i] = -1;   // globally not one of our gids
00567         else
00568           pids[i] = (ub - gnoDist - 1);
00569       }
00570     }
00571     else
00572       needProcs = true;
00573   }
00574 
00575   int haveWork = ((needProcs || needGnos) ? 1 : 0);
00576   int someHaveWork = 0;
00577 
00578   Teuchos::reduceAll<int, int>(*comm_, Teuchos::REDUCE_MAX, 1,
00579     &haveWork, &someHaveWork);
00580 
00581   if (!someHaveWork)
00582     return;
00583 
00585   // First: Hash each of my local gids to a process that will answer
00586   // for it.  Send my gids (and the Gnos if they are different)
00587   // to their assigned processes.  Build a lookup object for
00588   // the gids that were assigned to me, so I can reply with
00589   // with the process owning them (and their Gnos if they are different).
00591 
00592   Array<gid_t> gidOutBuf;
00593   Array<gno_t> gnoOutBuf;
00594   Array<int> countOutBuf(numProcs_, 0);
00595 
00596   ArrayRCP<gid_t> gidInBuf;
00597   ArrayRCP<gno_t> gnoInBuf;
00598   Array<int> countInBuf(numProcs_, 0);
00599 
00600   Array<gno_t> offsetBuf(numProcs_ + 1, 0);
00601 
00602   if (localNumberOfIds_ > 0){
00603 
00604     try{
00605       gidOutBuf.resize(localNumberOfIds_);
00606     }
00607     catch(...){
00608       env_->localMemoryAssertion(__FILE__, __LINE__, localNumberOfIds_, false);
00609     }
00610 
00611     for (size_t i=0; i < localNumberOfIds_; i++){
00612       int hashProc = IdentifierTraits<gid_t>::hashCode(myGids_[i]) % numProcs_;
00613       countOutBuf[hashProc]++;
00614     }
00615 
00616     for (int p=1; p <= numProcs_; p++){
00617       offsetBuf[p] = offsetBuf[p-1] + countOutBuf[p-1];
00618     }
00619 
00620     if (needGnos){
00621       // The gnos are not the gids, which also implies that
00622       // gnos are consecutive numbers given by gnoDist_.
00623       gnoOutBuf.resize(localNumberOfIds_, 0);
00624     }
00625 
00626     for (size_t i=0; i < localNumberOfIds_; i++){
00627       int hashProc = IdentifierTraits<gid_t>::hashCode(myGids_[i]) % numProcs_;
00628       gno_t offset = offsetBuf[hashProc];
00629       gidOutBuf[offset] = myGids_[i];
00630       if (needGnos)
00631         gnoOutBuf[offset] = gnoDist_[myRank_] + i;
00632       offsetBuf[hashProc] = offset + 1;
00633     }
00634   }
00635 
00636   // Z2::AlltoAllv comment: Buffers are in process rank contiguous order.
00637 
00638   ArrayView<const gid_t> gidView = gidOutBuf();
00639   ArrayView<const int> countView = countOutBuf();
00640   try{
00641     AlltoAllv<gid_t>(*comm_, *env_, gidView, countView, gidInBuf, countInBuf());
00642   }
00643   Z2_FORWARD_EXCEPTIONS;
00644 
00645   gidOutBuf.clear();
00646 
00647   if (needGnos){
00648     ArrayView<const gno_t> gnoView = gnoOutBuf();
00649     try{
00650       AlltoAllv<gno_t>(*comm_, *env_, gnoView, countView, gnoInBuf,
00651                        countInBuf());
00652     }
00653     Z2_FORWARD_EXCEPTIONS;
00654   }
00655 
00656   gnoOutBuf.clear();
00657   countOutBuf.clear();
00658 
00659   // Save the information that was hashed to me so I can do lookups.
00660   // This is a lookup from gid to its position in gidInBuf.
00661   // (The list of gids hashed to me is unique.)
00662 
00663   typedef GidLookupHelper<gid_t, lno_t> lookup_t;
00664 
00665   RCP<lookup_t> lookupMine = rcp(new lookup_t(env_, gidInBuf));
00666 
00667   // Use a vector to find process that sent gid.
00668 
00669   std::vector<gno_t> firstIndex;
00670   std::vector<int> sendProc;
00671   gno_t indexTotal = 0;
00672 
00673   if (needProcs){
00674     for (int p=0; p < numProcs_; p++){
00675       int bufLen = countInBuf[p];
00676       if (bufLen > 0){
00677         firstIndex.push_back(indexTotal);
00678         sendProc.push_back(p);
00679         indexTotal += bufLen;
00680       }
00681     }
00682     firstIndex.push_back(indexTotal);
00683   }
00684 
00686   // Send a request for information to the "answer process" for each
00687   // of the unique gids in in_gid.
00688   //
00689   // We may be called by a model that wants to find out what
00690   // process owns neighbors or columns.  Such a list of gids is
00691   // likely to have many duplicates.
00692   //
00693   // It is possible that some of the gids do not belong to any process.
00694   // (This happens in graph subsetting.)
00696 
00697   ArrayRCP<const gid_t> in_gidArray =
00698     arcp(in_gid.getRawPtr(), 0, inLen, false);
00699   RCP<lookup_t> lookupRequested = rcp(new lookup_t(env_, in_gidArray));
00700 
00701   size_t numberOfUniqueGids = lookupRequested->size();
00702 
00703   std::map<gid_t, lno_t> answerMap;// map from gid to position of answer
00704 
00705   ArrayRCP<lno_t> uniqueIndices;
00706   lookupRequested->getIndices(uniqueIndices);
00707 
00708   countOutBuf.resize(numProcs_, 0);
00709 
00710   if (numberOfUniqueGids > 0){
00711     try{
00712       gidOutBuf.resize(numberOfUniqueGids);
00713     }
00714     catch(...){
00715       env_->localMemoryAssertion(__FILE__, __LINE__, numberOfUniqueGids,
00716         false);
00717     }
00718 
00719     for (size_t i=0; i < numberOfUniqueGids; i++){
00720       gid_t gid = in_gid[uniqueIndices[i]];
00721       int hashProc = IdentifierTraits<gid_t>::hashCode(gid) % numProcs_;
00722       countOutBuf[hashProc]++;
00723     }
00724 
00725     offsetBuf[0] = 0;
00726 
00727     for (int p=0; p < numProcs_; p++){
00728       offsetBuf[p+1] = offsetBuf[p] + countOutBuf[p];
00729     }
00730 
00731     for (size_t i=0; i < numberOfUniqueGids; i++){
00732       gid_t gid = in_gid[uniqueIndices[i]];
00733       int hashProc = IdentifierTraits<gid_t>::hashCode(gid) % numProcs_;
00734       gno_t loc = offsetBuf[hashProc];
00735 
00736       answerMap[gid] = loc;
00737 
00738       gidOutBuf[loc] = gid;
00739       offsetBuf[hashProc] = loc + 1;
00740     }
00741   }
00742 
00743   try{
00744     AlltoAllv<gid_t>(*comm_, *env_, gidOutBuf(), countOutBuf(),
00745                      gidInBuf, countInBuf());
00746   }
00747   Z2_FORWARD_EXCEPTIONS;
00748 
00749   gidOutBuf.clear();
00750 
00752   // Create and send answers to the processes that made requests of me.
00754 
00755   gno_t total = 0;
00756   for (int p=0; p < numProcs_; p++){
00757     countOutBuf[p] = countInBuf[p];
00758     total += countOutBuf[p];
00759   }
00760 
00761   ArrayRCP<int> procOutBuf;
00762   ArrayRCP<int> procInBuf;
00763 
00764   if (needProcs){
00765     int *tmp = new int [total];
00766     env_->localMemoryAssertion(__FILE__, __LINE__, total, tmp);
00767     procOutBuf = arcp(tmp, 0, total, true);
00768 
00769   }
00770 
00771   if (needGnos){
00772     try{
00773       gnoOutBuf.resize(total, 0);
00774     }
00775     catch(...){
00776       env_->localMemoryAssertion(__FILE__, __LINE__, total, false);
00777     }
00778   }
00779 
00780   if (total > 0){
00781 
00782     total=0;
00783     typename std::vector<gno_t>::iterator indexFound;
00784 
00785     for (int p=0; p < numProcs_; p++){
00786       for (int i=0; i < countInBuf[p]; i++, total++){
00787 
00788         lno_t index(0);
00789         bool badGid = false;
00790 
00791         try{
00792           index = lookupMine->lookup(gidInBuf[total]);
00793         }
00794         catch (std::exception &e){
00795           badGid = true;
00796         }
00797 
00798         env_->localBugAssertion(__FILE__, __LINE__, "gidToIndex table",
00799           badGid || ((index >= 0)&&(index<=indexTotal)), BASIC_ASSERTION);
00800 
00801         if (!badGid){
00802 
00803           if (needProcs){
00804             indexFound =
00805               upper_bound(firstIndex.begin(), firstIndex.end(), index);
00806             int sendingProc = indexFound - firstIndex.begin() - 1;
00807             procOutBuf[total] = sendProc[sendingProc];
00808           }
00809 
00810           if (needGnos){
00811             gnoOutBuf[total] = gnoInBuf[index];
00812           }
00813         }
00814         else if (needProcs){
00815           // globally not one of our gids, can happen in subsetting
00816           procOutBuf[total] = -1;
00817         }
00818       }
00819     }
00820   }
00821 
00822   gidInBuf.clear();
00823   gnoInBuf.clear();
00824   lookupMine.~RCP<lookup_t>();
00825 
00826   if (needProcs){
00827     try{
00828       AlltoAllv<int>(*comm_, *env_, procOutBuf.view(0, total), countOutBuf(),
00829                      procInBuf, countInBuf());
00830     }
00831     Z2_FORWARD_EXCEPTIONS;
00832 
00833     procOutBuf.clear();
00834   }
00835 
00836   if (needGnos){
00837     try{
00838       AlltoAllv<gno_t>(*comm_, *env_, gnoOutBuf(), countOutBuf(),
00839                        gnoInBuf, countInBuf());
00840     }
00841     Z2_FORWARD_EXCEPTIONS;
00842 
00843     gnoOutBuf.clear();
00844   }
00845 
00846   countOutBuf.clear();
00847 
00849   // Done.  Process the replies to my queries
00851 
00852   for (typename ArrayView<const gid_t>::size_type i=0; i < inLen; i++){
00853     lno_t loc = answerMap[in_gid[i]];
00854     if (needProcs)
00855       out_proc[i] = procInBuf[loc];
00856     if (needGnos)
00857       out_gno[i] = gnoInBuf[loc];
00858   }
00859 }
00860 
00861 template< typename User>
00862   void IdentifierMap<User>::gnoGlobalTranslate(
00863     ArrayView<const gno_t> in_gno,
00864     ArrayView<gid_t> out_gid,
00865     ArrayView<int> out_proc) const
00866 {
00867   typename ArrayView<const gno_t>::size_type inLen = in_gno.size();
00868 
00869   if (userGidsAreZoltan2Gnos_){
00870 
00871     // Easy case - use gidGlobalTranslate.
00872 
00873     const gno_t *gnos = in_gno.getRawPtr();
00874     ArrayView<const gid_t> gids(static_cast<const gid_t *>(gnos), inLen);
00875     ArrayView<gno_t> noGnos;
00876 
00877     try{
00878       gidGlobalTranslate(gids, noGnos, out_proc);
00879     }
00880     Z2_FORWARD_EXCEPTIONS;
00881 
00882     if (out_gid.size() ==
00883                 static_cast<typename ArrayView<gid_t>::size_type>(inLen))
00884       for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++)
00885         out_gid[i] = gids[i];
00886 
00887     return;
00888   }
00889 
00890   bool needProcs = out_proc.size() > 0;
00891   bool needGids = out_gid.size() > 0;
00892 
00893   int haveWork = ((needProcs || needGids) ? 1 : 0);
00894   int someHaveWork = 0;
00895 
00896   Teuchos::reduceAll<int, int>(*comm_, Teuchos::REDUCE_MAX, 1,
00897     &haveWork, &someHaveWork);
00898 
00899   if (!someHaveWork)
00900     return;
00901 
00902   env_->localInputAssertion(__FILE__, __LINE__, "array too small",
00903     (!needProcs ||
00904       out_proc.size()>=static_cast<typename ArrayView<int>::size_type>(inLen))
00905     &&
00906     (!needGids ||
00907       out_gid.size()>=static_cast<typename ArrayView<gid_t>::size_type>(inLen)),
00908      BASIC_ASSERTION);
00909 
00910   // Get process owning each gno.  We need it to get the gid.
00911 
00912   ArrayRCP<int> procArray;
00913 
00914   if (out_proc.size() == static_cast<typename ArrayView<int>::size_type>(inLen))
00915     procArray = arcp(out_proc.getRawPtr(), 0, inLen, false);
00916   else{
00917     int *tmp = new int [inLen];
00918     env_->localMemoryAssertion(__FILE__, __LINE__, inLen, tmp);
00919     procArray = arcp(tmp, 0, inLen, true);
00920   }
00921 
00922   // The fact that global Ids and global Numbers are different
00923   // means that the user's global Ids were mapped to consecutive increasing
00924   // global numbers, so we know the process owning each global number.
00925 
00926   gno_t *gnos = gnoDist_.getRawPtr();
00927   gno_t *final = gnos + numProcs_ + 1;
00928   bool remoteGno = false;
00929   int *pids = procArray.getRawPtr();  // in loops it's faster to use raw ptr
00930 
00931   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++){
00932 
00933     gno_t *ub = std::upper_bound(gnos, final, in_gno[i]);
00934 
00935     pids[i] = (ub - gnos - 1);
00936 
00937     env_->localInputAssertion(__FILE__, __LINE__, "invalid global number",
00938       (pids[i] >= 0) && (pids[i] < env_->numProcs_), BASIC_ASSERTION);
00939 
00940     if (!remoteGno && (pids[i] != myRank_))
00941       remoteGno = true;
00942   }
00943 
00944   if (!needGids)
00945     return;
00946 
00947   if (!remoteGno){
00948 
00949     // Make a local call to get the gids
00950     try{
00951       gidTranslate(out_gid,
00952              ArrayView<gno_t>(const_cast<gno_t *>(in_gno.getRawPtr()),inLen),
00953              TRANSLATE_LIB_TO_APP);
00954 
00955     }
00956     Z2_FORWARD_EXCEPTIONS;
00957 
00958     return;
00959   }
00960 
00961   // Get the global ID from the owner.
00962   // TODO: In gidGlobalTranslate, we go to much trouble to
00963   //   avoid duplicate requests.  (Because that may be used
00964   //   to identify owners of neighbors, which would likely
00965   //   include many duplicates.)  Any reason to go to this
00966   //   trouble here?  Could the list of gnos have many duplicates?
00967 
00968   ArrayRCP<gno_t> gnoOutBuf;
00969   ArrayRCP<gno_t> offsetBuf;
00970   gno_t *tmpGno = NULL;
00971 
00972   if (inLen){
00973     tmpGno = new gno_t [inLen];
00974     env_->localMemoryAssertion(__FILE__, __LINE__, inLen, tmpGno);
00975     gnoOutBuf = arcp(tmpGno, 0, inLen, true);
00976   }
00977 
00978   int *tmpCount = new int [numProcs_];
00979   env_->localMemoryAssertion(__FILE__, __LINE__, numProcs_, tmpCount);
00980   memset(tmpCount, 0, sizeof(int) * numProcs_);
00981   ArrayRCP<int> countOutBuf(tmpCount, 0, numProcs_, true);
00982 
00983   gno_t *tmpOff = new gno_t [numProcs_+1];
00984   env_->localMemoryAssertion(__FILE__, __LINE__, numProcs_+1, tmpOff);
00985   offsetBuf = arcp(tmpOff, 0, numProcs_+1, true);
00986 
00987   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++)
00988     tmpCount[pids[i]]++;
00989 
00990   offsetBuf[0] = 0;
00991   for (int i=0; i < numProcs_; i++)
00992     tmpOff[i+1] = tmpOff[i] + tmpCount[i];
00993 
00994   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++){
00995     int p = pids[i];
00996     gno_t off = tmpOff[p];
00997     tmpGno[off] = in_gno[i];
00998     tmpOff[p]++;
00999   }
01000 
01001   // Reset offsetBuf so we can find replies later.
01002 
01003   tmpOff[0] = 0;
01004   for (int i=0; i < numProcs_; i++)
01005     tmpOff[i+1] = tmpOff[i] + tmpCount[i];
01006 
01007   ArrayRCP<gno_t> gnoInBuf;
01008   Array<int> countInBuf(numProcs_, 0);
01009 
01010   try{
01011     AlltoAllv<gno_t>(*comm_, *env_,
01012       gnoOutBuf.view(0, inLen), countOutBuf.view(0, numProcs_),
01013       gnoInBuf, countInBuf());
01014   }
01015   Z2_FORWARD_EXCEPTIONS;
01016 
01017   gnoOutBuf.clear();
01018   countOutBuf.clear();
01019 
01020   gno_t numRequests = 0;
01021   for (int i=0; i < numProcs_; i++)
01022     numRequests += countInBuf[i];
01023 
01024   ArrayRCP<gid_t> gidQueryBuf;
01025 
01026   if (numRequests){
01027     gid_t *tmpGid = new gid_t [numRequests];
01028     env_->localMemoryAssertion(__FILE__, __LINE__, numRequests, tmpGid);
01029     gidQueryBuf = arcp(tmpGid, 0, numRequests);
01030   }
01031 
01032   try{
01033     gidTranslate(gidQueryBuf.view(0, numRequests),
01034                  gnoInBuf.view(0, numRequests),
01035                  TRANSLATE_LIB_TO_APP);
01036   }
01037   Z2_FORWARD_EXCEPTIONS;
01038 
01039   ArrayRCP<gid_t> gidInBuf;
01040   Array<lno_t> newCountInBuf(numProcs_, 0);
01041 
01042   try{
01043     AlltoAllv<gid_t>(*comm_, *env_,
01044       gidQueryBuf.view(0, numRequests), countInBuf(),
01045       gidInBuf, newCountInBuf());
01046   }
01047   Z2_FORWARD_EXCEPTIONS;
01048 
01049   gidQueryBuf.clear();
01050 
01051   // copy the replies into the output gid list
01052 
01053   gid_t *gidInfo = gidInBuf.getRawPtr();  // faster in a loop
01054 
01055   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++){
01056     int p = pids[i];
01057     gno_t off = tmpOff[p];
01058     out_gid[i] = gidInfo[off];
01059     tmpOff[p]++;
01060   }
01061 }
01062 
01063 template< typename User>
01064   void IdentifierMap<User>::setupMap(void)
01065 {
01066   env_->globalInputAssertion(__FILE__, __LINE__,
01067        "application global ID type is not supported yet",
01068        IdentifierTraits<gid_t>::is_valid_id_type() == true, BASIC_ASSERTION,
01069        comm_);
01070 
01071   if (IdentifierTraits<gid_t>::isGlobalOrdinal())
01072     userGidsAreTeuchosOrdinal_ = true;
01073 
01074   localNumberOfIds_ = myGids_.size();
01075   const gid_t *gidPtr = myGids_.get();
01076   ArrayRCP<gid_t> tmpDist;
01077   gid_t mingid=0, maxgid=0;
01078 
01079   userGidsAreConsecutive_ = globallyConsecutiveOrdinals<gid_t>(
01080     *comm_, *env_, gidPtr, localNumberOfIds_,      // input
01081     tmpDist, globalNumberOfIds_);                  // output
01082 
01083   bool baseZeroConsecutiveIds = false;
01084 
01085   if (userGidsAreTeuchosOrdinal_){
01086     if (!userGidsAreConsecutive_){
01087       mingid = tmpDist[0];
01088       maxgid = tmpDist[1];
01089     }
01090     else{
01091       // A gno_t is large enough to hold gid_ts, but may be a different type.
01092       if (sizeof(gid_t) == sizeof(gno_t)) {
01093         gnoDist_ = arcp_reinterpret_cast<gno_t>(tmpDist);
01094       }
01095       else{
01096         gnoDist_.resize(numProcs_ + 1);
01097         for (lno_t i=0; i <= numProcs_; i++){
01098           gnoDist_[i] = static_cast<gno_t>(tmpDist[i]);
01099         }
01100       }
01101 
01102       if (gnoDist_[0] == 0)
01103         baseZeroConsecutiveIds = true;
01104     }
01105   }
01106 
01107   // If user global IDs are not consecutive ordinals, create a lookup table
01108   // mapping the global IDs to their location in myGids_.
01109 
01110   typedef GidLookupHelper<gid_t, lno_t> lookup_t;
01111 
01112   if (!userGidsAreConsecutive_){
01113     try{
01114       gidLookup_ = rcp(new lookup_t(env_, myGids_));
01115     }
01116     Z2_FORWARD_EXCEPTIONS;
01117   }
01118 
01119   userGidsAreZoltan2Gnos_ = false;
01120 
01121   if (userGidsAreTeuchosOrdinal_ &&
01122       ((consecutiveGidsAreRequired_ && baseZeroConsecutiveIds) ||
01123       !consecutiveGidsAreRequired_))
01124   {
01125     // We can use the application's global IDs
01126     userGidsAreZoltan2Gnos_ = true;
01127   }
01128 
01129   if (userGidsAreZoltan2Gnos_){
01130 
01131     zoltan2GnosAreConsecutive_ = userGidsAreConsecutive_;
01132 
01133     if (userGidsAreConsecutive_){
01134       minGlobalGno_ = gnoDist_[0];
01135       maxGlobalGno_ = gnoDist_[numProcs_]-1;
01136     }
01137     else{
01138       minGlobalGno_ = static_cast<gno_t>(mingid);
01139       maxGlobalGno_ = static_cast<gno_t>(maxgid);
01140     }
01141   } else{
01142     // We map application gids to consecutive global numbers starting with 0.
01143 
01144     zoltan2GnosAreConsecutive_ = true;
01145 
01146     try{
01147       gnoDist_.resize(numProcs_ + 1, 0);
01148     }
01149     Z2_THROW_OUTSIDE_ERROR(*env_);
01150 
01151     gno_t myNum = static_cast<gno_t>(localNumberOfIds_);
01152 
01153     try{
01154       gno_t *p = gnoDist_.getRawPtr();
01155       Teuchos::gatherAll<int, gno_t>(*comm_, 1, &myNum, numProcs_, p+1);
01156     }
01157     Z2_THROW_OUTSIDE_ERROR(*env_);
01158 
01159     for (int i=2; i <= numProcs_; i++){
01160       gnoDist_[i] += gnoDist_[i-1];
01161     }
01162 
01163     minGlobalGno_ = gnoDist_[0];
01164     maxGlobalGno_ = gnoDist_[numProcs_]-1;
01165   }
01166 }
01167 
01168 }   // end namespace Zoltan2
01169 
01170 #endif /* _ZOLTAN2_IDENTIFIERMAP_HPP_ */