Branch data     Line data    Source code

       1                 :            : // *****************************************************************************
       2                 :            : /*!
       3                 :            :   \file      src/LoadBalance/UnsMeshMap.cpp
       4                 :            :   \copyright 2012-2015 J. Bakosi,
       5                 :            :              2016-2018 Los Alamos National Security, LLC.,
       6                 :            :              2019-2021 Triad National Security, LLC.
       7                 :            :              All rights reserved. See the LICENSE file for details.
       8                 :            :   \brief     Advanced Charm++ array creation with a map using an unstructured
       9                 :            :              grid
      10                 :            :   \details   Advanced Charm++ array creation refers to various ways arrays can
      11                 :            :      be created with the Charm++ runtime system. See
      12                 :            :      http://charm.cs.illinois.edu/manuals/html/charm++/manual.html, Sec.
      13                 :            :      Advanced Array Creation. This class does a distribution that is based on
      14                 :            :      which portion of a distributed sparse matrix resulting from discretization
      15                 :            :      on an unstructured grid residing on a PE should hold a given chare array
      16                 :            :      element. (The one that owns most on-PE rows to minimize off-PE
      17                 :            :      communication.)
      18                 :            : 
      19                 :            :      Note that to help with performance, it is not advised to do heavy
      20                 :            :      computations in the overridden member functions, procNum() and
      21                 :            :      populateInitial(), since they can be potentially called many times. See
      22                 :            :      also this note on the inner workings of the Charm++ runtime system
      23                 :            :      regarding map objects and array element creation from long-time Charm++
      24                 :            :      developer, Eric Bohm, also at:
      25                 :            :      http://lists.cs.uiuc.edu/pipermail/charm/2015-May/002047.html
      26                 :            : 
      27                 :            :      _Procnum will be called to construct your chare, the first time a message
      28                 :            :      is sent to it from a node, and each time subsequent sends do not find a
      29                 :            :      precached location record for it. The latter event can occur when many
      30                 :            :      sends have pushed it out of cache, or after migration._
      31                 :            : 
      32                 :            :      _The potential global memory footprint of location management caching is
      33                 :            :      proportional to the total number of objects multiplied by the number of
      34                 :            :      nodes. Therefore, the runtime system keeps a finite number on each node.
      35                 :            :      At the limit, procnum could be called for nearly every message send,
      36                 :            :      therefore procnum should be designed to be inexpensive._
      37                 :            : 
      38                 :            :      The heavy portion of array element placement should therefore be done in
      39                 :            :      the constructor.
      40                 :            : */
      41                 :            : // *****************************************************************************
      42                 :            : 
      43                 :            : #include <algorithm>
      44                 :            : 
      45                 :            : #include "NoWarning/charm.hpp"
      46                 :            : #include "Exception.hpp"
      47                 :            : #include "UnsMeshMap.hpp"
      48                 :            : 
      49                 :            : using tk::UnsMeshMap;
      50                 :            : 
      51                 :        180 : UnsMeshMap::UnsMeshMap( std::size_t npoin,
      52                 :        180 :                         const std::vector< std::vector< std::size_t > >& point )
      53         [ +  - ]:        180 :  : m_pe()
      54                 :            : // *****************************************************************************
      55                 :            : // Constructor
      56                 :            : //! \param[in] npoin Total number of points in mesh
      57                 :            : //! \param[in] point Global mesh point ids owned by each array element
      58                 :            : // *****************************************************************************
      59                 :            : {
      60                 :            :   Assert( npoin > 0, "Need at least a single mesh point" );
      61                 :            :   Assert( point.size() >= static_cast< std::size_t >( CkNumPes() ),
      62                 :            :           "UnsMeshMap only works with nchare >= numPEs" );
      63                 :            : 
      64                 :            :   // Vector of maps to associate the number of mesh points an array element
      65                 :            :   // contributes to a pe to the array element
      66 [ +  - ][ +  - ]:        360 :   std::vector< std::map< std::size_t, std::size_t > > owner( point.size() );
                 [ -  - ]
      67                 :            : 
      68                 :            :   // Compute number of mesh points per PE (chunksize)
      69                 :        180 :   const auto numpes = static_cast< std::size_t >( CkNumPes() );
      70         [ +  - ]:        180 :   const auto chunksize = npoin>numpes ? npoin/numpes : 1;
      71                 :            : 
      72                 :            :   // Count up number of mesh points contributing to a PE for each array element
      73         [ +  + ]:       9252 :   for (std::size_t e=0; e<point.size(); ++e)    // for all array elements
      74         [ +  + ]:     522288 :     for (auto p : point[e]) {           // for all points array element e owns
      75         [ -  + ]:     513216 :       auto pe = p / chunksize;          // PE array element e contributes to
      76         [ -  + ]:     513216 :       if (pe == static_cast<std::size_t>(CkNumPes())) --pe;
      77         [ +  - ]:     513216 :       ++owner[e][pe];  // count up number of points element e contributing to pe
      78                 :            :     }
      79                 :            : 
      80                 :            :   // Find and store the PE with the largest number of points owned by an array
      81                 :            :   // element. This is the key (PE) of the largest mapped_type of the element's
      82                 :            :   // map, owner[e].
      83                 :            :   using pr = decltype(owner)::value_type::value_type;
      84         [ +  - ]:        180 :   m_pe.resize( owner.size() );
      85         [ +  + ]:       9252 :   for (std::size_t e=0; e<owner.size(); ++e) {
      86                 :            :     const auto most = std::max_element( begin(owner[e]), end(owner[e]),
      87                 :            :                                         []( const pr& p1, const pr& p2 )
      88                 :       9072 :                                           { return p1.second < p2.second; } );
      89                 :       9072 :     m_pe[e] = most->first;
      90                 :            :   }
      91                 :            : 
      92                 :            :   // Check if all PEs have at least one array element to create, fix if not
      93         [ +  - ]:        180 :   fixPEs();
      94                 :        180 : }
      95                 :            : 
      96                 :            : void
      97                 :        180 : UnsMeshMap::fixPEs()
      98                 :            : // *****************************************************************************
      99                 :            : //  Check that all PEs create at least a single array element, fix if not
     100                 :            : //! \details This is required because if the array elements, placed using this
     101                 :            : //!   map object, send messages to some Charm++ chare group branches and the
     102                 :            : //!   group happens to use Charm++'s structured dagger, such as Solver,
     103                 :            : //!   memory problems will occur.
     104                 :            : // *****************************************************************************
     105                 :            : {
     106                 :            :   // Build unique set of PEs the array elements are assigned to
     107                 :            :   std::set< std::size_t > nkind;
     108 [ +  + ][ +  - ]:       9252 :   for (auto p : m_pe) nkind.insert( p );
     109                 :            : 
     110                 :            :   // If not all PEs have at least one array element to create, go through all
     111                 :            :   // PEs that have no array elements assigned, and construct a map that
     112                 :            :   // associates the number of PEs to array elements. Then as a replacement PE,
     113                 :            :   // pick the PE that has the most array elements assigned. Then assign the
     114                 :            :   // first of the elements assigned to the PE with the most work to the
     115                 :            :   // replacement PE.
     116         [ +  + ]:        180 :   if (nkind.size() != static_cast<std::size_t>(CkNumPes()))
     117         [ +  + ]:       2664 :     for (std::size_t p=0; p<static_cast<std::size_t>(CkNumPes()); ++p)
     118                 :            :       if (!nkind.count(p)) {    // if PE p has no array elements to create
     119                 :            :         // Count up number elements for each PE
     120                 :            :         std::map< std::size_t, std::size_t > npe;
     121                 :            :         using pr = decltype(npe)::value_type;
     122 [ +  + ][ +  - ]:     138600 :         for (auto q : m_pe) ++npe[q];
     123                 :            :         // Find the PE with the most array elements assigned
     124                 :            :         const auto most = std::max_element( begin(npe), end(npe),
     125                 :            :                                             []( const pr& p1, const pr& p2 )
     126                 :       2520 :                                             { return p1.second < p2.second; } );
     127         [ +  + ]:      47880 :         for (std::size_t q=0; q<m_pe.size(); ++q)
     128         [ +  + ]:      45360 :           if (m_pe[q] == most->first) { // first element of the most loaded PE
     129                 :            :             //std::cout << CkMyPe() << ": replace " << m_pe[q] << " by " << p
     130                 :            :             //          << " for e " << q << std::endl;
     131                 :       2520 :             m_pe[q] = p;        // replace PE of m_pe[q] of element q by p
     132                 :            :             q = m_pe.size();    // quit (enough to replace one)
     133                 :            :           }
     134                 :            :       }
     135                 :            : 
     136                 :            :   nkind.clear();
     137 [ +  + ][ +  - ]:       9252 :   for (auto p : m_pe) nkind.insert( p );
     138                 :            :   Assert( nkind.size() == static_cast<std::size_t>(CkNumPes()),
     139                 :            :           "There are still PE(s) with no array elements assigned" );
     140                 :        180 : }
     141                 :            : 
     142                 :            : int
     143                 :       1080 : UnsMeshMap::procNum( int, const CkArrayIndex& idx )
     144                 :            : // *****************************************************************************
     145                 :            : //  Return the home processor number for the array element based on
     146                 :            : //  unstructured-mesh-aware distribution computed in the constructor
     147                 :            : //! \param[in] idx Charm++ array index object containing the array element index
     148                 :            : //!   to assign a PE to
     149                 :            : //! \return PE assigned
     150                 :            : // *****************************************************************************
     151                 :            : {
     152                 :            :   // array element we assign PE for
     153                 :       1080 :   auto elem = static_cast<std::size_t>(*idx.data());
     154                 :            : 
     155                 :            :   Assert( elem < m_pe.size(),
     156                 :            :           "Array index larger than the number of chares for which the "
     157                 :            :           "UnsMeshMap object holds indices for" );
     158                 :            : 
     159                 :       1080 :   auto pe = static_cast< int >( m_pe[ elem ] );
     160                 :            : 
     161                 :            :   Assert( pe < CkNumPes(), "Assigned PE (" + std::to_string(pe) +
     162                 :            :           ") larger than NumPEs (" + std::to_string(CkNumPes()) + ")" );
     163                 :            : 
     164                 :       1080 :   return pe;
     165                 :            : }
     166                 :            : 
     167                 :            : void
     168                 :        144 : UnsMeshMap::populateInitial( int, CkArrayOptions& opt,
     169                 :            :                              void *msg,
     170                 :            :                              CkArrMgr *mgr )
     171                 :            : // *****************************************************************************
     172                 :            : //  Create initial set of array elements based on the unstructured-mesh-aware
     173                 :            : //  distribution computed in the constructor
     174                 :            : //! \param[in] opt Charm++ array options object containing the number of initial
     175                 :            : //!   array elements to be created
     176                 :            : //! \param[in] msg Charm++ messsage to use for array element creation
     177                 :            : //! \param[in] mgr Array manager to use
     178                 :            : // *****************************************************************************
     179                 :            : {
     180                 :        144 :   int nelem = *opt.getNumInitial().data(); // number of array elements requested
     181         [ +  - ]:        144 :   if (nelem == 0) return;                  // no initial elements requested
     182                 :            : 
     183                 :            :   Assert( static_cast<std::size_t>(nelem) <= m_pe.size(),
     184                 :            :           "Number of initial array elements larger than "
     185                 :            :           "the UnsMeshMap object holds PEs for" );
     186                 :            : 
     187         [ +  + ]:       7920 :   for (int e=0; e<nelem; ++e)
     188         [ +  + ]:       7776 :     if (m_pe[ static_cast<std::size_t>(e) ] ==
     189         [ +  + ]:       7776 :         static_cast<std::size_t>(CkMyPe()))
     190                 :        216 :       mgr->insertInitial( CkArrayIndex(e), CkCopyMsg(&msg) );
     191                 :            : 
     192                 :        144 :   mgr->doneInserting();
     193                 :        144 :   CkFreeMsg( msg );
     194                 :            : }
     195                 :            : 
     196                 :            : #include "NoWarning/unsmeshmap.def.h"