Zoltan 2 Version 0.5
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   ArrayRCP<int> countInBuf;
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, countInBuf);
00651     }
00652     Z2_FORWARD_EXCEPTIONS;
00653   }
00654 
00655   gnoOutBuf.clear();
00656   countOutBuf.clear();
00657 
00658   // Save the information that was hashed to me so I can do lookups.
00659   // This is a lookup from gid to its position in gidInBuf.
00660   // (The list of gids hashed to me is unique.)
00661 
00662   typedef GidLookupHelper<gid_t, lno_t> lookup_t;
00663 
00664   RCP<lookup_t> lookupMine = rcp(new lookup_t(env_, gidInBuf));
00665 
00666   // Use a vector to find process that sent gid.
00667 
00668   std::vector<gno_t> firstIndex;
00669   std::vector<int> sendProc;
00670   gno_t indexTotal = 0;
00671 
00672   if (needProcs){
00673     for (int p=0; p < numProcs_; p++){
00674       int bufLen = countInBuf[p];
00675       if (bufLen > 0){
00676         firstIndex.push_back(indexTotal);
00677         sendProc.push_back(p);
00678         indexTotal += bufLen;
00679       }
00680     }
00681     firstIndex.push_back(indexTotal);
00682   }
00683 
00685   // Send a request for information to the "answer process" for each
00686   // of the unique gids in in_gid.
00687   //
00688   // We may be called by a model that wants to find out what
00689   // process owns neighbors or columns.  Such a list of gids is
00690   // likely to have many duplicates.
00691   //
00692   // It is possible that some of the gids do not belong to any process.
00693   // (This happens in graph subsetting.)
00695 
00696   ArrayRCP<const gid_t> in_gidArray =
00697     arcp(in_gid.getRawPtr(), 0, inLen, false);
00698   RCP<lookup_t> lookupRequested = rcp(new lookup_t(env_, in_gidArray));
00699 
00700   size_t numberOfUniqueGids = lookupRequested->size();
00701 
00702   std::map<gid_t, lno_t> answerMap;// map from gid to position of answer
00703 
00704   ArrayRCP<lno_t> uniqueIndices;
00705   lookupRequested->getIndices(uniqueIndices);
00706 
00707   countOutBuf.resize(numProcs_, 0);
00708 
00709   if (numberOfUniqueGids > 0){
00710     try{
00711       gidOutBuf.resize(numberOfUniqueGids);
00712     }
00713     catch(...){
00714       env_->localMemoryAssertion(__FILE__, __LINE__, numberOfUniqueGids,
00715         false);
00716     }
00717 
00718     for (size_t i=0; i < numberOfUniqueGids; i++){
00719       gid_t gid = in_gid[uniqueIndices[i]];
00720       int hashProc = IdentifierTraits<gid_t>::hashCode(gid) % numProcs_;
00721       countOutBuf[hashProc]++;
00722     }
00723 
00724     offsetBuf[0] = 0;
00725 
00726     for (int p=0; p < numProcs_; p++){
00727       offsetBuf[p+1] = offsetBuf[p] + countOutBuf[p];
00728     }
00729 
00730     for (size_t i=0; i < numberOfUniqueGids; i++){
00731       gid_t gid = in_gid[uniqueIndices[i]];
00732       int hashProc = IdentifierTraits<gid_t>::hashCode(gid) % numProcs_;
00733       gno_t loc = offsetBuf[hashProc];
00734 
00735       answerMap[gid] = loc;
00736 
00737       gidOutBuf[loc] = gid;
00738       offsetBuf[hashProc] = loc + 1;
00739     }
00740   }
00741 
00742   try{
00743     ArrayView<const gid_t> gidView = gidOutBuf();
00744     ArrayView<const int> countView = countOutBuf();
00745     AlltoAllv<gid_t>(*comm_, *env_, gidView, countView,
00746       gidInBuf, countInBuf);
00747   }
00748   Z2_FORWARD_EXCEPTIONS;
00749 
00750   gidOutBuf.clear();
00751 
00753   // Create and send answers to the processes that made requests of me.
00755 
00756   gno_t total = 0;
00757   for (int p=0; p < numProcs_; p++){
00758     countOutBuf[p] = countInBuf[p];
00759     total += countOutBuf[p];
00760   }
00761 
00762   ArrayRCP<int> procOutBuf;
00763   ArrayRCP<int> procInBuf;
00764 
00765   if (needProcs){
00766     int *tmp = new int [total];
00767     env_->localMemoryAssertion(__FILE__, __LINE__, total, tmp);
00768     procOutBuf = arcp(tmp, 0, total, true);
00769 
00770   }
00771 
00772   if (needGnos){
00773     try{
00774       gnoOutBuf.resize(total, 0);
00775     }
00776     catch(...){
00777       env_->localMemoryAssertion(__FILE__, __LINE__, total, false);
00778     }
00779   }
00780 
00781   if (total > 0){
00782 
00783     total=0;
00784     typename std::vector<gno_t>::iterator indexFound;
00785 
00786     for (int p=0; p < numProcs_; p++){
00787       for (int i=0; i < countInBuf[p]; i++, total++){
00788 
00789         lno_t index(0);
00790         bool badGid = false;
00791 
00792         try{
00793           index = lookupMine->lookup(gidInBuf[total]);
00794         }
00795         catch (std::exception &e){
00796           badGid = true;
00797         }
00798 
00799         env_->localBugAssertion(__FILE__, __LINE__, "gidToIndex table",
00800           badGid || ((index >= 0)&&(index<=indexTotal)), BASIC_ASSERTION);
00801 
00802         if (!badGid){
00803 
00804           if (needProcs){
00805             indexFound =
00806               upper_bound(firstIndex.begin(), firstIndex.end(), index);
00807             int sendingProc = indexFound - firstIndex.begin() - 1;
00808             procOutBuf[total] = sendProc[sendingProc];
00809           }
00810 
00811           if (needGnos){
00812             gnoOutBuf[total] = gnoInBuf[index];
00813           }
00814         }
00815         else if (needProcs){
00816           // globally not one of our gids, can happen in subsetting
00817           procOutBuf[total] = -1;
00818         }
00819       }
00820     }
00821   }
00822 
00823   gidInBuf.clear();
00824   gnoInBuf.clear();
00825   lookupMine.~RCP<lookup_t>();
00826 
00827   if (needProcs){
00828     try{
00829       ArrayView<const int> procView = procOutBuf.view(0, total);
00830       ArrayView<const int> countView = countOutBuf();
00831       AlltoAllv<int>(*comm_, *env_, procView, countView, procInBuf, countInBuf);
00832     }
00833     Z2_FORWARD_EXCEPTIONS;
00834 
00835     procOutBuf.clear();
00836   }
00837 
00838   if (needGnos){
00839     try{
00840       ArrayView<const gno_t> gnoView = gnoOutBuf();
00841       ArrayView<const int> countView = countOutBuf();
00842       AlltoAllv<gno_t>(*comm_, *env_, gnoView, countView, gnoInBuf, countInBuf);
00843     }
00844     Z2_FORWARD_EXCEPTIONS;
00845 
00846     gnoOutBuf.clear();
00847   }
00848 
00849   countOutBuf.clear();
00850 
00852   // Done.  Process the replies to my queries
00854 
00855   for (typename ArrayView<const gid_t>::size_type i=0; i < inLen; i++){
00856     lno_t loc = answerMap[in_gid[i]];
00857     if (needProcs)
00858       out_proc[i] = procInBuf[loc];
00859     if (needGnos)
00860       out_gno[i] = gnoInBuf[loc];
00861   }
00862 }
00863 
00864 template< typename User>
00865   void IdentifierMap<User>::gnoGlobalTranslate(
00866     ArrayView<const gno_t> in_gno,
00867     ArrayView<gid_t> out_gid,
00868     ArrayView<int> out_proc) const
00869 {
00870   typename ArrayView<const gno_t>::size_type inLen = in_gno.size();
00871 
00872   if (userGidsAreZoltan2Gnos_){
00873 
00874     // Easy case - use gidGlobalTranslate.
00875 
00876     const gno_t *gnos = in_gno.getRawPtr();
00877     ArrayView<const gid_t> gids(static_cast<const gid_t *>(gnos), inLen);
00878     ArrayView<gno_t> noGnos;
00879 
00880     try{
00881       gidGlobalTranslate(gids, noGnos, out_proc);
00882     }
00883     Z2_FORWARD_EXCEPTIONS;
00884 
00885     if (out_gid.size() ==
00886                 static_cast<typename ArrayView<gid_t>::size_type>(inLen))
00887       for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++)
00888         out_gid[i] = gids[i];
00889 
00890     return;
00891   }
00892 
00893   bool needProcs = out_proc.size() > 0;
00894   bool needGids = out_gid.size() > 0;
00895 
00896   int haveWork = ((needProcs || needGids) ? 1 : 0);
00897   int someHaveWork = 0;
00898 
00899   Teuchos::reduceAll<int, int>(*comm_, Teuchos::REDUCE_MAX, 1,
00900     &haveWork, &someHaveWork);
00901 
00902   if (!someHaveWork)
00903     return;
00904 
00905   env_->localInputAssertion(__FILE__, __LINE__, "array too small",
00906     (!needProcs ||
00907       out_proc.size()>=static_cast<typename ArrayView<int>::size_type>(inLen))
00908     &&
00909     (!needGids ||
00910       out_gid.size()>=static_cast<typename ArrayView<gid_t>::size_type>(inLen)),
00911      BASIC_ASSERTION);
00912 
00913   // Get process owning each gno.  We need it to get the gid.
00914 
00915   ArrayRCP<int> procArray;
00916 
00917   if (out_proc.size() == static_cast<typename ArrayView<int>::size_type>(inLen))
00918     procArray = arcp(out_proc.getRawPtr(), 0, inLen, false);
00919   else{
00920     int *tmp = new int [inLen];
00921     env_->localMemoryAssertion(__FILE__, __LINE__, inLen, tmp);
00922     procArray = arcp(tmp, 0, inLen, true);
00923   }
00924 
00925   // The fact that global Ids and global Numbers are different
00926   // means that the user's global Ids were mapped to consecutive increasing
00927   // global numbers, so we know the process owning each global number.
00928 
00929   gno_t *gnos = gnoDist_.getRawPtr();
00930   gno_t *final = gnos + numProcs_ + 1;
00931   bool remoteGno = false;
00932   int *pids = procArray.getRawPtr();  // in loops it's faster to use raw ptr
00933 
00934   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++){
00935 
00936     gno_t *ub = std::upper_bound(gnos, final, in_gno[i]);
00937 
00938     pids[i] = (ub - gnos - 1);
00939 
00940     env_->localInputAssertion(__FILE__, __LINE__, "invalid global number",
00941       (pids[i] >= 0) && (pids[i] < env_->numProcs_), BASIC_ASSERTION);
00942 
00943     if (!remoteGno && (pids[i] != myRank_))
00944       remoteGno = true;
00945   }
00946 
00947   if (!needGids)
00948     return;
00949 
00950   if (!remoteGno){
00951 
00952     // Make a local call to get the gids
00953 
00954     const gno_t *gnos = in_gno.getRawPtr();
00955     ArrayView<gno_t> gnoList(const_cast<gno_t *>(gnos), inLen);
00956 
00957     try{
00958       gidTranslate(out_gid, gnoList, TRANSLATE_LIB_TO_APP);
00959     }
00960     Z2_FORWARD_EXCEPTIONS;
00961 
00962     return;
00963   }
00964 
00965   // Get the global ID from the owner.
00966   // TODO: In gidGlobalTranslate, we go to much trouble to
00967   //   avoid duplicate requests.  (Because that may be used
00968   //   to identify owners of neighbors, which would likely
00969   //   include many duplicates.)  Any reason to go to this
00970   //   trouble here?  Could the list of gnos have many duplicates?
00971 
00972   ArrayRCP<gno_t> gnoOutBuf;
00973   ArrayRCP<gno_t> offsetBuf;
00974   gno_t *tmpGno = NULL;
00975 
00976   if (inLen){
00977     tmpGno = new gno_t [inLen];
00978     env_->localMemoryAssertion(__FILE__, __LINE__, inLen, tmpGno);
00979     gnoOutBuf = arcp(tmpGno, 0, inLen, true);
00980   }
00981 
00982   int *tmpCount = new int [numProcs_];
00983   env_->localMemoryAssertion(__FILE__, __LINE__, numProcs_, tmpCount);
00984   memset(tmpCount, 0, sizeof(int) * numProcs_);
00985   ArrayRCP<int> countOutBuf(tmpCount, 0, numProcs_, true);
00986 
00987   gno_t *tmpOff = new gno_t [numProcs_+1];
00988   env_->localMemoryAssertion(__FILE__, __LINE__, numProcs_+1, tmpOff);
00989   offsetBuf = arcp(tmpOff, 0, numProcs_+1, true);
00990 
00991   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++)
00992     tmpCount[pids[i]]++;
00993 
00994   offsetBuf[0] = 0;
00995   for (int i=0; i < numProcs_; i++)
00996     tmpOff[i+1] = tmpOff[i] + tmpCount[i];
00997 
00998   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++){
00999     int p = pids[i];
01000     gno_t off = tmpOff[p];
01001     tmpGno[off] = in_gno[i];
01002     tmpOff[p]++;
01003   }
01004 
01005   // Reset offsetBuf so we can find replies later.
01006 
01007   tmpOff[0] = 0;
01008   for (int i=0; i < numProcs_; i++)
01009     tmpOff[i+1] = tmpOff[i] + tmpCount[i];
01010 
01011   ArrayRCP<gno_t> gnoInBuf;
01012   ArrayRCP<int> countInBuf;
01013 
01014   try{
01015     AlltoAllv<gno_t>(*comm_, *env_,
01016       gnoOutBuf.view(0, inLen), countOutBuf.view(0, numProcs_),
01017       gnoInBuf, countInBuf);
01018   }
01019   Z2_FORWARD_EXCEPTIONS;
01020 
01021   gnoOutBuf.clear();
01022   countOutBuf.clear();
01023 
01024   gno_t numRequests = 0;
01025   for (int i=0; i < numProcs_; i++)
01026     numRequests += countInBuf[i];
01027 
01028   ArrayRCP<gid_t> gidQueryBuf;
01029 
01030   if (numRequests){
01031     gid_t *tmpGid = new gid_t [numRequests];
01032     env_->localMemoryAssertion(__FILE__, __LINE__, numRequests, tmpGid);
01033     gidQueryBuf = arcp(tmpGid, 0, numRequests);
01034   }
01035 
01036   try{
01037     gidTranslate(gidQueryBuf.view(0, numRequests),
01038                  gnoInBuf.view(0, numRequests),
01039                  TRANSLATE_LIB_TO_APP);
01040   }
01041   Z2_FORWARD_EXCEPTIONS;
01042 
01043   ArrayRCP<gid_t> gidInBuf;
01044   ArrayRCP<lno_t> newCountInBuf;
01045 
01046   try{
01047     AlltoAllv<gid_t>(*comm_, *env_,
01048       gidQueryBuf.view(0, numRequests), countInBuf.view(0, numProcs_),
01049       gidInBuf, newCountInBuf);
01050   }
01051   Z2_FORWARD_EXCEPTIONS;
01052 
01053   gidQueryBuf.clear();
01054 
01055   // copy the replies into the output gid list
01056 
01057   gid_t *gidInfo = gidInBuf.getRawPtr();  // faster in a loop
01058 
01059   for (typename ArrayView<const gno_t>::size_type i=0; i < inLen; i++){
01060     int p = pids[i];
01061     gno_t off = tmpOff[p];
01062     out_gid[i] = gidInfo[off];
01063     tmpOff[p]++;
01064   }
01065 }
01066 
01067 template< typename User>
01068   void IdentifierMap<User>::setupMap(void)
01069 {
01070   env_->globalInputAssertion(__FILE__, __LINE__,
01071        "application global ID type is not supported yet",
01072        IdentifierTraits<gid_t>::is_valid_id_type() == true, BASIC_ASSERTION,
01073        comm_);
01074 
01075   if (IdentifierTraits<gid_t>::isGlobalOrdinal())
01076     userGidsAreTeuchosOrdinal_ = true;
01077 
01078   localNumberOfIds_ = myGids_.size();
01079   const gid_t *gidPtr = myGids_.get();
01080   ArrayRCP<gid_t> tmpDist;
01081   gid_t mingid=0, maxgid=0;
01082 
01083   userGidsAreConsecutive_ = globallyConsecutiveOrdinals<gid_t>(
01084     *comm_, *env_, gidPtr, localNumberOfIds_,      // input
01085     tmpDist, globalNumberOfIds_);                  // output
01086 
01087   bool baseZeroConsecutiveIds = false;
01088 
01089   if (userGidsAreTeuchosOrdinal_){
01090     if (!userGidsAreConsecutive_){
01091       mingid = tmpDist[0];
01092       maxgid = tmpDist[1];
01093     }
01094     else{
01095       // A gno_t is large enough to hold gid_ts, but may be a different type.
01096       if (sizeof(gid_t) == sizeof(gno_t)) {
01097         gnoDist_ = arcp_reinterpret_cast<gno_t>(tmpDist);
01098       }
01099       else{
01100         gnoDist_.resize(numProcs_ + 1);
01101         for (lno_t i=0; i <= numProcs_; i++){
01102           gnoDist_[i] = static_cast<gno_t>(tmpDist[i]);
01103         }
01104       }
01105 
01106       if (gnoDist_[0] == 0)
01107         baseZeroConsecutiveIds = true;
01108     }
01109   }
01110 
01111   // If user global IDs are not consecutive ordinals, create a lookup table
01112   // mapping the global IDs to their location in myGids_.
01113 
01114   typedef GidLookupHelper<gid_t, lno_t> lookup_t;
01115 
01116   if (!userGidsAreConsecutive_){
01117     try{
01118       gidLookup_ = rcp(new lookup_t(env_, myGids_));
01119     }
01120     Z2_FORWARD_EXCEPTIONS;
01121   }
01122 
01123   userGidsAreZoltan2Gnos_ = false;
01124 
01125   if (userGidsAreTeuchosOrdinal_ &&
01126       ((consecutiveGidsAreRequired_ && baseZeroConsecutiveIds) ||
01127       !consecutiveGidsAreRequired_))
01128   {
01129     // We can use the application's global IDs
01130     userGidsAreZoltan2Gnos_ = true;
01131   }
01132 
01133   if (userGidsAreZoltan2Gnos_){
01134 
01135     zoltan2GnosAreConsecutive_ = userGidsAreConsecutive_;
01136 
01137     if (userGidsAreConsecutive_){
01138       minGlobalGno_ = gnoDist_[0];
01139       maxGlobalGno_ = gnoDist_[numProcs_]-1;
01140     }
01141     else{
01142       minGlobalGno_ = static_cast<gno_t>(mingid);
01143       maxGlobalGno_ = static_cast<gno_t>(maxgid);
01144     }
01145   } else{
01146     // We map application gids to consecutive global numbers starting with 0.
01147 
01148     zoltan2GnosAreConsecutive_ = true;
01149 
01150     try{
01151       gnoDist_.resize(numProcs_ + 1, 0);
01152     }
01153     Z2_THROW_OUTSIDE_ERROR(*env_);
01154 
01155     gno_t myNum = static_cast<gno_t>(localNumberOfIds_);
01156 
01157     try{
01158       gno_t *p = gnoDist_.getRawPtr();
01159       Teuchos::gatherAll<int, gno_t>(*comm_, 1, &myNum, numProcs_, p+1);
01160     }
01161     Z2_THROW_OUTSIDE_ERROR(*env_);
01162 
01163     for (int i=2; i <= numProcs_; i++){
01164       gnoDist_[i] += gnoDist_[i-1];
01165     }
01166 
01167     minGlobalGno_ = gnoDist_[0];
01168     maxGlobalGno_ = gnoDist_[numProcs_]-1;
01169   }
01170 }
01171 
01172 }   // end namespace Zoltan2
01173 
01174 #endif /* _ZOLTAN2_IDENTIFIERMAP_HPP_ */