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 [ - + ][ - - ]: 180 : Assert( npoin > 0, "Need at least a single mesh point" );
[ - - ][ - - ]
61 [ - + ][ - - ]: 180 : 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 : 18144 : const auto most = std::max_element( begin(owner[e]), end(owner[e]),
87 : 0 : []( const pr& p1, const pr& p2 )
88 [ + - ]: 18144 : { 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 : 360 : 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 [ + - ][ + + ]: 2592 : if (!nkind.count(p)) { // if PE p has no array elements to create
119 : : // Count up number elements for each PE
120 : 5040 : 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 : 42840 : []( const pr& p1, const pr& p2 )
126 [ + - ]: 45360 : { 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 : 2520 : q = m_pe.size(); // quit (enough to replace one)
133 : : }
134 : : }
135 : :
136 : 180 : nkind.clear();
137 [ + + ][ + - ]: 9252 : for (auto p : m_pe) nkind.insert( p );
138 [ - + ][ - - ]: 180 : 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 [ - + ][ - - ]: 1080 : 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 [ - + ][ - - ]: 1080 : 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 [ - + ][ - - ]: 144 : 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"
|
