Changeset 865

Timestamp:

06/09/16 11:33:08 (9 years ago)

Author:

mhnguyen

Message:

Optimizing codes: Change the way to compute distribution of grid

+) Instead of using DHT on grid, we make use of it only for elements of grid
+) Make change to calculation of server distribution.

Test
+) On Curie
+) Two times faster than the precedent commit.

Location:

XIOS/trunk/src

Files:

• node/grid.cpp (modified) (7 diffs)
• node/grid.hpp (modified) (2 diffs)
• server_distribution_description.cpp (modified) (2 diffs)
• server_distribution_description.hpp (modified) (2 diffs)

XIOS/trunk/src/node/grid.cpp

@@ -32 +32 @@
       , transformations_(0), isTransformed_(false)
       , axisPositionInGrid_(), positionDimensionDistributed_(1), hasDomainAxisBaseRef_(false)
-      , gridSrc_(), hasTransform_(false), order_()
+      , gridSrc_(), hasTransform_(false), order_(), globalIndexOnServer_()
    {
      setVirtualDomainGroup();
@@ -47 +47 @@
       , transformations_(0), isTransformed_(false)
       , axisPositionInGrid_(), positionDimensionDistributed_(1), hasDomainAxisBaseRef_(false)
-      , gridSrc_(), hasTransform_(false), order_()
+      , gridSrc_(), hasTransform_(false), order_(), globalIndexOnServer_()
    {
      setVirtualDomainGroup();
@@ -409 +409 @@
    //---------------------------------------------------------------
 
+   /*!
+     Compute the global index of grid to send to server as well as the connected server of the current client.
+     First of all, from the local data on each element of grid, we can calculate their local index which also allows us to know
+     their global index. We can have a map of global index of grid and local index that each client holds
+     Then, each client holds a piece of information about the distribution of servers, which permits to compute the connected server(s)
+     of the current client.
+   */
    void CGrid::computeIndex(void)
    {
@@ -434 +441 @@
 
      // Compute mapping between client and server
-     size_t globalSizeIndex = 1, indexBegin, indexEnd;
-     int range, clientSize = client->clientSize;
-     for (int i = 0; i < globalDim_.size(); ++i) globalSizeIndex *= globalDim_[i];
-     indexBegin = 0;
-     for (int i = 0; i < clientSize; ++i)
-     {
-       range = globalSizeIndex / clientSize;
-       if (i < (globalSizeIndex%clientSize)) ++range;
-       if (i == client->clientRank) break;
-       indexBegin += range;
-     }
-     indexEnd = indexBegin + range - 1;
-
-     // Then compute distribution on server side
+     std::vector<boost::unordered_map<size_t,std::vector<int> > > indexServerOnElement;
      CServerDistributionDescription serverDistributionDescription(globalDim_, client->serverSize);
-     serverDistributionDescription.computeServerGlobalIndexInRange(std::make_pair<size_t,size_t>(indexBegin, indexEnd), positionDimensionDistributed_);
-
-     // Finally, compute index mapping between client(s) and server(s)
-     clientServerMap_ = new CClientServerMappingDistributed(serverDistributionDescription.getGlobalIndexRange(),
-                                                            client->intraComm,
-                                                            clientDistribution_->isDataDistributed());
-
-     clientServerMap_->computeServerIndexMapping(clientDistribution_->getGlobalIndex());
-     const CClientServerMapping::GlobalIndexMap& globalIndexOnServer = clientServerMap_->getGlobalIndexOnServer();
+     serverDistributionDescription.computeServerGlobalByElement(indexServerOnElement,
+                                                                client->clientRank,
+                                                                client->clientSize,
+                                                                axis_domain_order,
+                                                                positionDimensionDistributed_);
+     computeIndexByElement(indexServerOnElement, globalIndexOnServer_);
 
      const CDistributionClient::GlobalLocalDataMap& globalLocalIndexSendToServer = clientDistribution_->getGlobalLocalDataSendToServer();
      CDistributionClient::GlobalLocalDataMap::const_iterator iteGlobalLocalIndexMap = globalLocalIndexSendToServer.end(), itGlobalLocalIndexMap;
      CClientServerMapping::GlobalIndexMap::const_iterator iteGlobalMap, itbGlobalMap, itGlobalMap;
-     itGlobalMap  = itbGlobalMap = globalIndexOnServer.begin();
-     iteGlobalMap = globalIndexOnServer.end();
+     itGlobalMap  = itbGlobalMap = globalIndexOnServer_.begin();
+     iteGlobalMap = globalIndexOnServer_.end();
 
      for (; itGlobalMap != iteGlobalMap; ++itGlobalMap)
@@ -491 +482 @@
    }
 
+   /*!
+      Compute the global of (client) grid to send to server with the global index of each element of grid
+      Each element of grid has its own global index associated to a groups of server. We only search for the global index of each element whose
+      server is the same, then calculate the global index of grid. This way can reduce so much the time for executing DHT, which only needs to run
+      on each element whose size is much smaller than one of whole grid.
+      \param [in] indexServerOnElement global index of each element and the rank of server associated with these index
+      \param [out] globalIndexOnServer global index of grid and its corresponding rank of server.
+   */
+   void CGrid::computeIndexByElement(const std::vector<boost::unordered_map<size_t,std::vector<int> > >& indexServerOnElement,
+                                     CClientServerMapping::GlobalIndexMap& globalIndexOnServer)
+   {
+     CContext* context = CContext::getCurrent();
+     CContextClient* client = context->client;
+     int serverSize = client->serverSize;
+     std::vector<CDomain*> domList = getDomains();
+     std::vector<CAxis*> axisList = getAxis();
+
+     // Some pre-calculations of global index on each element of current grid.
+     int nbElement = axis_domain_order.numElements();
+     std::vector<CArray<size_t,1> > globalIndexElement(nbElement);
+     int domainIdx = 0, axisIdx = 0;
+     std::vector<size_t> elementNGlobal(nbElement);
+     elementNGlobal[0] = 1;
+     size_t globalSize = 1;
+     for (int idx = 0; idx < nbElement; ++idx)
+     {
+       elementNGlobal[idx] = globalSize;
+       size_t elementSize;
+       size_t elementGlobalSize = 1;
+       if (axis_domain_order(idx))
+       {
+         elementSize = domList[domainIdx]->i_index.numElements();
+         globalIndexElement[idx].resize(elementSize);
+         for (int jdx = 0; jdx < elementSize; ++jdx)
+         {
+           globalIndexElement[idx](jdx) = (domList[domainIdx]->i_index)(jdx) + domList[domainIdx]->ni_glo * (domList[domainIdx]->j_index)(jdx);
+         }
+         elementGlobalSize = domList[domainIdx]->ni_glo.getValue() * domList[domainIdx]->nj_glo.getValue();
+         ++domainIdx;
+       }
+       else
+       {
+         elementSize = axisList[axisIdx]->index.numElements();
+         globalIndexElement[idx].resize(elementSize);
+         for (int jdx = 0; jdx < elementSize; ++jdx)
+         {
+           globalIndexElement[idx](jdx) = (axisList[axisIdx]->index)(jdx);
+         }
+         elementGlobalSize = axisList[axisIdx]->n_glo.getValue();
+         ++axisIdx;
+       }
+       globalSize *= elementGlobalSize;
+     }
+
+     std::vector<std::vector<bool> > elementOnServer(nbElement, std::vector<bool>(serverSize, false));
+     std::vector<boost::unordered_map<int,std::vector<size_t> > > globalElementIndexOnServer(nbElement);
+     for (int idx = 0; idx < nbElement; ++idx)
+     {
+       std::vector<int> nbIndexOnServer(serverSize,0);
+       const boost::unordered_map<size_t,std::vector<int> >& indexServerElement = indexServerOnElement[idx];
+       const CArray<size_t,1>& globalIndexElementOnClient = globalIndexElement[idx];
+       CClientClientDHTInt clientClientDHT(indexServerElement, client->intraComm);
+       clientClientDHT.computeIndexInfoMapping(globalIndexElementOnClient);
+       const CClientClientDHTInt::Index2VectorInfoTypeMap& globalIndexElementOnServerMap = clientClientDHT.getInfoIndexMap();
+       CClientClientDHTInt::Index2VectorInfoTypeMap::const_iterator itb = globalIndexElementOnServerMap.begin(),
+                                                                    ite = globalIndexElementOnServerMap.end(), it;
+       for (it = itb; it != ite; ++it)
+       {
+         const std::vector<int>& tmp = it->second;
+         for (int i = 0; i < tmp.size(); ++i)
+         {
+           ++nbIndexOnServer[tmp[i]];
+         }
+       }
+
+       for (int i = 0; i < serverSize; ++i)
+       {
+         if (0 != nbIndexOnServer[i])
+         {
+           globalElementIndexOnServer[idx][i].resize(nbIndexOnServer[i]);
+           nbIndexOnServer[i] = 0;
+           elementOnServer[idx][i] = true;
+         }
+       }
+
+       for (it = itb; it != ite; ++it)
+       {
+         const std::vector<int>& tmp = it->second;
+         for (int i = 0; i < tmp.size(); ++i)
+         {
+           globalElementIndexOnServer[idx][tmp[i]][nbIndexOnServer[tmp[i]]] = it->first;
+           ++nbIndexOnServer[tmp[i]];
+         }
+       }
+     }
+
+    // Determine server which contain global source index
+    std::vector<bool> intersectedProc(serverSize, true);
+    for (int idx = 0; idx < nbElement; ++idx)
+    {
+      std::transform(elementOnServer[idx].begin(), elementOnServer[idx].end(),
+                     intersectedProc.begin(), intersectedProc.begin(),
+                     std::logical_and<bool>());
+    }
+
+    std::vector<int> srcRank;
+    for (int idx = 0; idx < serverSize; ++idx)
+    {
+      if (intersectedProc[idx]) srcRank.push_back(idx);
+    }
+
+    // Compute the global index of grid from global index of each element.
+    for (int i = 0; i < srcRank.size(); ++i)
+    {
+      size_t ssize = 1;
+      int rankSrc = srcRank[i];
+      std::vector<std::vector<size_t>* > globalIndexOfElementTmp(nbElement);
+      std::vector<size_t> currentIndex(nbElement,0);
+      for (int idx = 0; idx < nbElement; ++idx)
+      {
+        ssize *= (globalElementIndexOnServer[idx][rankSrc]).size();
+        globalIndexOfElementTmp[idx] = &(globalElementIndexOnServer[idx][rankSrc]);
+      }
+      globalIndexOnServer[rankSrc].resize(ssize);
+
+      std::vector<int> idxLoop(nbElement,0);
+      int innnerLoopSize = (globalIndexOfElementTmp[0])->size();
+      size_t idx = 0;
+      while (idx < ssize)
+      {
+        for (int ind = 0; ind < nbElement; ++ind)
+        {
+          if (idxLoop[ind] == (globalIndexOfElementTmp[ind])->size())
+          {
+            idxLoop[ind] = 0;
+            ++idxLoop[ind+1];
+          }
+
+          currentIndex[ind] = (*(globalIndexOfElementTmp[ind]))[idxLoop[ind]];
+        }
+
+        for (int ind = 0; ind < innnerLoopSize; ++ind)
+        {
+          currentIndex[0] = (*globalIndexOfElementTmp[0])[ind];
+          size_t globalSrcIndex = 0;
+          for (int idxElement = 0; idxElement < nbElement; ++idxElement)
+          {
+            globalSrcIndex += currentIndex[idxElement] * elementNGlobal[idxElement];
+          }
+          globalIndexOnServer[rankSrc][idx] = globalSrcIndex;
+          ++idx;
+          ++idxLoop[0];
+        }
+      }
+    }
+   }
    //----------------------------------------------------------------
 
@@ -783 +930 @@
     list<CMessage> listMsg;
     list<CArray<size_t,1> > listOutIndex;
-    const CClientServerMapping::GlobalIndexMap& globalIndexOnServer = clientServerMap_->getGlobalIndexOnServer();
+//    const CClientServerMapping::GlobalIndexMap& globalIndexOnServer = clientServerMap_->getGlobalIndexOnServer();
+//    const CClientServerMapping::GlobalIndexMap& globalIndexOnServer = clientServerMap_->getGlobalIndexOnServer();
     const CDistributionClient::GlobalLocalDataMap& globalLocalIndexSendToServer = clientDistribution_->getGlobalLocalDataSendToServer();
     CDistributionClient::GlobalLocalDataMap::const_iterator itIndex = globalLocalIndexSendToServer.begin(),
@@ -820 +968 @@
     {
       CClientServerMapping::GlobalIndexMap::const_iterator iteGlobalMap, itGlobalMap;
-      itGlobalMap = globalIndexOnServer.begin();
-      iteGlobalMap = globalIndexOnServer.end();
+      itGlobalMap = globalIndexOnServer_.begin();
+      iteGlobalMap = globalIndexOnServer_.end();
 
       std::map<int,std::vector<int> >localIndexTmp;

XIOS/trunk/src/node/grid.hpp

@@ -242 +242 @@
 
         void checkAttributesAfterTransformation();
-
-
         void setTransformationAlgorithms();
-
+        void computeIndexByElement(const std::vector<boost::unordered_map<size_t,std::vector<int> > >& indexServerOnElement,
+                                   CClientServerMapping::GlobalIndexMap& globalIndexOnServer);
 
 
@@ -274 +273 @@
         std::map<CGrid*, std::pair<bool,StdString> > gridSrc_;
         bool hasTransform_;
+        CClientServerMapping::GlobalIndexMap globalIndexOnServer_;
             // List order of axis and domain in a grid, if there is a domain, it will take value 1 (true), axis 0 (false)
         std::vector<bool> order_;

XIOS/trunk/src/server_distribution_description.cpp

@@ -97 +97 @@
   Compute global index assigned to a server with a range.E.g: if a grid has 100 points and
   there are 2 servers, the first one takes index from 0 to 49, the second has index from 50 to 99
-
   \param [in] indexBeginEnd begining and ending index of range
+  \param [in] positionDimensionDistributed dimension of server on which we make the cut.
 */
 void CServerDistributionDescription::computeServerGlobalIndexInRange(const std::pair<size_t, size_t>& indexBeginEnd,
@@ -161 +161 @@
     }
   }
-
+}
+
+/*!
+  Compute the global index of grid elements (domain, axis) and their associated server rank.
+  Each client knows the general distribution of servers and from which they can compute the pieces of information to hold
+  \param [out] indexServerOnElement global index of each element as well as the corresponding server which contains these indices
+  \param [in] clientRank rank of client
+  \param [in] clientSize number of client
+  \param [in] axisDomainOrder the order of element in grid (true for domain, false for axis)
+  \param [in] positionDimensionDistributed dimension of server on which we make the cut.
+*/
+void CServerDistributionDescription::computeServerGlobalByElement(std::vector<boost::unordered_map<size_t,std::vector<int> > >& indexServerOnElement,
+                                                                  int clientRank,
+                                                                  int clientSize,
+                                                                  const CArray<bool,1>& axisDomainOrder,
+                                                                  int positionDimensionDistributed)
+{
+  switch (serverType_) {
+    case BAND_DISTRIBUTION:
+      computeBandDistribution(nServer_, positionDimensionDistributed);
+      break;
+    default:
+      break;
+  }
+
+  int nbElement = axisDomainOrder.numElements();
+  indexServerOnElement.resize(nbElement);
+  int idx = 0;
+  std::vector<int> idxMap(nbElement);
+  for (int i = 0; i < nbElement; ++i)
+  {
+    idxMap[i] = idx;
+    if (true == axisDomainOrder(i)) idx += 2;
+    else ++idx;
+  }
+
+  for (int idxServer = 0; idxServer < nServer_; ++idxServer)
+  {
+    std::vector<int> elementDimension(4);
+    for (int i = 0; i < nbElement; ++i)
+    {
+      int elementSize = 1;
+      if (axisDomainOrder(i))
+      {
+        elementSize *= dimensionSizes_[idxServer][idxMap[i]] * dimensionSizes_[idxServer][idxMap[i]+1];
+        elementDimension[0] = indexBegin_[idxServer][idxMap[i]];
+        elementDimension[1] = indexBegin_[idxServer][idxMap[i]+1];
+        elementDimension[2] = dimensionSizes_[idxServer][idxMap[i]];
+        elementDimension[3] = dimensionSizes_[idxServer][idxMap[i]+1];
+      }
+
+      else
+      {
+        elementSize *= dimensionSizes_[idxServer][idxMap[i]];
+        elementDimension[0] = indexBegin_[idxServer][idxMap[i]];
+        elementDimension[1] = 0;
+        elementDimension[2] = dimensionSizes_[idxServer][idxMap[i]];
+        elementDimension[3] = 1;
+      }
+
+      int rangeBegin, rangeSize;
+      computeRangeProcIndex(clientRank, clientSize, elementSize, rangeBegin, rangeSize);
+
+      size_t globalIndexElement;
+      idx = 0; int idxRange = 0;
+      for (int k = 0; k < elementDimension[3]; ++k)
+        for (int l = 0; l < elementDimension[2]; ++l)
+        {
+          globalIndexElement = (l+elementDimension[0]) + (k+elementDimension[1])*elementDimension[2];
+          if ((rangeBegin <= idx) && (idxRange < rangeSize))
+          {
+            indexServerOnElement[i][globalIndexElement].push_back(idxServer);
+            ++idxRange;
+          }
+          ++idx;
+        }
+    }
+  }
+}
+
+/*!
+  Compute a range of index on server which a client holds
+  For a range of index on a specific server, each client can hold a piece of the index range
+  If the range size is smaller than the number of client, there are some clients holding the same index
+  \param [in] clientRank rank of client
+  \param [in] clientSize number of client
+  \param [in] rangeProcSize index range size
+  \param [out] rangeBegin begin of range index a client holds
+  \param [out] rangeSize size of range index a client holds
+*/
+void CServerDistributionDescription::computeRangeProcIndex(int clientRank,
+                                                           int clientSize,
+                                                           int rangeProcSize,
+                                                           int& rangeBegin,
+                                                           int& rangeSize)
+{
+  if (rangeProcSize < clientSize)
+  {
+    int rangeIndex = 0;
+    for (int idx = 0; idx < clientSize; ++idx)
+    {
+      if (idx == clientRank)
+      {
+        rangeBegin = rangeIndex;
+        rangeSize = 1;
+      }
+      ++rangeIndex;
+      if (rangeIndex == rangeProcSize) rangeIndex = 0;
+    }
+    return;
+  }
+
+  int range, indexBegin = 0;
+  for (int i = 0; i < clientSize; ++i)
+  {
+    range = rangeProcSize / clientSize;
+    if (i < (rangeProcSize%clientSize)) ++range;
+    if (i == clientRank) break;
+    indexBegin += range;
+  }
+  rangeBegin = indexBegin;
+  rangeSize = range;
 }
 

XIOS/trunk/src/server_distribution_description.hpp

@@ -39 +39 @@
     void computeServerDistribution(bool doComputeGlobalIndex = false, int positionDimensionDistributed = 1);
     void computeServerGlobalIndexInRange(const std::pair<size_t, size_t>& indexBeginEnd, int positionDimensionDistributed = 1);
+    void computeServerGlobalByElement(std::vector<boost::unordered_map<size_t,std::vector<int> > >& indexServerOnElement,
+                                      int rank,
+                                      int clientSize,
+                                      const CArray<bool,1>& axisDomainOrder,
+                                      int positionDimensionDistributed = 1);
 
     std::vector<std::vector<int> > getServerIndexBegin() const;
@@ -49 +54 @@
     void computeBandDistribution(int nServer, int positionDimensionDistributed = 1);
     void computePlanDistribution(int nServer);
+    void computeRangeProcIndex(int clientRank,
+                               int clientSize,
+                               int rangeProcSize,
+                               int& rangeBegin,
+                               int& rangeSize);
 
   private: