Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2026 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3 :
4 : // This library is free software; you can redistribute it and/or
5 : // modify it under the terms of the GNU Lesser General Public
6 : // License as published by the Free Software Foundation; either
7 : // version 2.1 of the License, or (at your option) any later version.
8 :
9 : // This library is distributed in the hope that it will be useful,
10 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 : // Lesser General Public License for more details.
13 :
14 : // You should have received a copy of the GNU Lesser General Public
15 : // License along with this library; if not, write to the Free Software
16 : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 :
18 :
19 : // Local includes
20 : #include "libmesh/parallel_sort.h"
21 :
22 : // libMesh includes
23 : #include "libmesh/libmesh_common.h"
24 : #include "libmesh/parallel_bin_sorter.h"
25 : #include "libmesh/parallel_hilbert.h"
26 :
27 : // TIMPI includes
28 : #include "timpi/parallel_implementation.h"
29 : #include "timpi/parallel_sync.h"
30 :
31 : // C++ includes
32 : #include <algorithm>
33 : #include <iostream>
34 :
35 :
36 : namespace libMesh
37 : {
38 :
39 :
40 : namespace Parallel {
41 :
42 : // The Constructor sorts the local data using
43 : // std::sort(). Therefore, the construction of
44 : // a Parallel::Sort object takes O(n log n) time,
45 : // where n is the length of _data.
46 : template <typename KeyType, typename IdxType>
47 38626 : Sort<KeyType,IdxType>::Sort(const Parallel::Communicator & comm_in,
48 : std::vector<KeyType> & d) :
49 : ParallelObject(comm_in),
50 38626 : _n_procs(cast_int<processor_id_type>(comm_in.size())),
51 38626 : _proc_id(cast_int<processor_id_type>(comm_in.rank())),
52 12768 : _bin_is_sorted(false),
53 64484 : _data(d)
54 : {
55 38626 : std::sort(_data.begin(), _data.end());
56 :
57 : // Allocate storage
58 38626 : _local_bin_sizes.resize(_n_procs);
59 38626 : }
60 :
61 :
62 :
63 : template <typename KeyType, typename IdxType>
64 38626 : void Sort<KeyType,IdxType>::sort()
65 : {
66 : // Find the global data size. The sorting
67 : // algorithms assume they have a range to
68 : // work with, so catch the degenerate cases here
69 38626 : IdxType global_data_size = cast_int<IdxType>(_data.size());
70 :
71 38626 : this->comm().sum (global_data_size);
72 :
73 38626 : if (global_data_size < 2)
74 : {
75 : // the entire global range is either empty
76 : // or contains only one element
77 1 : _my_bin = _data;
78 :
79 1 : this->comm().allgather (static_cast<IdxType>(_my_bin.size()),
80 1 : _local_bin_sizes);
81 : }
82 : else
83 : {
84 51554 : if (this->n_processors() > 1)
85 : {
86 38580 : this->binsort();
87 38580 : this->communicate_bins();
88 : }
89 : else
90 45 : _my_bin = _data;
91 :
92 38625 : this->sort_local_bin();
93 : }
94 :
95 : // Set sorted flag to true
96 38626 : _bin_is_sorted = true;
97 38626 : }
98 :
99 :
100 :
101 : template <typename KeyType, typename IdxType>
102 6 : void Sort<KeyType,IdxType>::binsort()
103 : {
104 : // Find the global min and max from all the
105 : // processors.
106 8 : std::vector<KeyType> global_min_max(2);
107 :
108 : // Insert the local min and max for this processor
109 8 : global_min_max[0] = -_data.front();
110 6 : global_min_max[1] = _data.back();
111 :
112 : // Communicate to determine the global
113 : // min and max for all processors.
114 6 : this->comm().max(global_min_max);
115 :
116 : // Multiply the min by -1 to obtain the true min
117 6 : global_min_max[0] *= -1;
118 :
119 : // Bin-Sort based on the global min and max
120 8 : Parallel::BinSorter<KeyType> bs(this->comm(), _data);
121 6 : bs.binsort(_n_procs, global_min_max[1], global_min_max[0]);
122 :
123 : // Now save the local bin sizes in a vector so
124 : // we don't have to keep around the BinSorter.
125 18 : for (processor_id_type i=0; i<_n_procs; ++i)
126 16 : _local_bin_sizes[i] = bs.sizeof_bin(i);
127 6 : }
128 :
129 :
130 :
131 : #if defined(LIBMESH_HAVE_LIBHILBERT) && defined(LIBMESH_HAVE_MPI)
132 : // Full specialization for HilbertIndices, there is a fair amount of
133 : // code duplication here that could potentially be consolidated with the
134 : // above method
135 : template <>
136 38574 : void Sort<Parallel::DofObjectKey,unsigned int>::binsort()
137 : {
138 : // Find the global min and max from all the
139 : // processors. Do this using MPI_Allreduce.
140 : Parallel::DofObjectKey
141 12926 : local_min, local_max,
142 12926 : global_min, global_max;
143 :
144 51500 : if (_data.empty())
145 : {
146 982 : local_min.first.rack0 = local_min.first.rack1 = local_min.first.rack2 = static_cast<Hilbert::inttype>(-1);
147 982 : local_min.second = std::numeric_limits<unique_id_type>::max();
148 649 : local_max.first.rack0 = local_max.first.rack1 = local_max.first.rack2 = 0;
149 333 : local_max.second = 0;
150 : }
151 : else
152 : {
153 12593 : local_min = _data.front();
154 12593 : local_max = _data.back();
155 : }
156 :
157 : MPI_Op hilbert_max, hilbert_min;
158 :
159 38574 : MPI_Op_create ((MPI_User_function*)dofobjectkey_max_op, true, &hilbert_max);
160 38574 : MPI_Op_create ((MPI_User_function*)dofobjectkey_min_op, true, &hilbert_min);
161 :
162 : // Communicate to determine the global
163 : // min and max for all processors.
164 38574 : MPI_Allreduce(&local_min,
165 : &global_min,
166 : 1,
167 77148 : Parallel::StandardType<Parallel::DofObjectKey>(&local_min),
168 : hilbert_min,
169 38778 : this->comm().get());
170 :
171 38574 : MPI_Allreduce(&local_max,
172 : &global_max,
173 : 1,
174 64426 : Parallel::StandardType<Parallel::DofObjectKey>(&local_max),
175 : hilbert_max,
176 38778 : this->comm().get());
177 :
178 38574 : MPI_Op_free (&hilbert_max);
179 38574 : MPI_Op_free (&hilbert_min);
180 :
181 : // Bin-Sort based on the global min and max
182 51500 : Parallel::BinSorter<Parallel::DofObjectKey> bs(this->comm(),_data);
183 38574 : bs.binsort(_n_procs, global_max, global_min);
184 :
185 : // Now save the local bin sizes in a vector so
186 : // we don't have to keep around the BinSorter.
187 115722 : for (processor_id_type i=0; i<_n_procs; ++i)
188 103000 : _local_bin_sizes[i] = bs.sizeof_bin(i);
189 38574 : }
190 :
191 : #endif // #ifdef LIBMESH_HAVE_LIBHILBERT
192 :
193 :
194 : template <typename KeyType, typename IdxType>
195 38580 : void Sort<KeyType,IdxType>::communicate_bins()
196 : {
197 : #ifdef LIBMESH_HAVE_MPI
198 : // Find each section of our data to send
199 12928 : IdxType local_offset = 0;
200 25856 : std::map<processor_id_type, std::vector<KeyType> > pushed_keys, received_keys;
201 :
202 115740 : for (processor_id_type i=0; i != _n_procs; ++i)
203 : {
204 77160 : IdxType next_offset = local_offset + _local_bin_sizes[i];
205 77160 : if (_local_bin_sizes[i])
206 : {
207 60816 : auto begin = _data.begin() + local_offset;
208 20388 : auto end = _data.begin() + next_offset;
209 60816 : pushed_keys[i].assign(begin, end);
210 : }
211 :
212 25856 : local_offset = next_offset;
213 : }
214 :
215 79356 : auto keys_action_functor =
216 40080 : [& received_keys]
217 : (processor_id_type pid,
218 20388 : const std::vector<KeyType> & keys)
219 : {
220 60816 : received_keys[pid] = keys;
221 : };
222 :
223 : Parallel::push_parallel_vector_data
224 38580 : (this->comm(), pushed_keys, keys_action_functor);
225 :
226 12928 : std::size_t my_bin_size = 0;
227 99396 : for (auto & p : received_keys)
228 81204 : my_bin_size += p.second.size();
229 :
230 38580 : _my_bin.clear();
231 38580 : _my_bin.reserve(my_bin_size);
232 :
233 99396 : for (auto & p : received_keys)
234 60816 : _my_bin.insert(_my_bin.end(), p.second.begin(), p.second.end());
235 :
236 : #ifdef DEBUG
237 25856 : std::vector<IdxType> global_bin_sizes = _local_bin_sizes;
238 :
239 12928 : this->comm().sum(global_bin_sizes);
240 :
241 12928 : libmesh_assert_equal_to
242 : (global_bin_sizes[this->processor_id()], _my_bin.size());
243 : #endif
244 :
245 : #endif // LIBMESH_HAVE_MPI
246 38580 : }
247 :
248 :
249 :
250 : template <typename KeyType, typename IdxType>
251 38625 : void Sort<KeyType,IdxType>::sort_local_bin()
252 : {
253 38625 : std::sort(_my_bin.begin(), _my_bin.end());
254 38625 : }
255 :
256 :
257 :
258 : template <typename KeyType, typename IdxType>
259 38626 : const std::vector<KeyType> & Sort<KeyType,IdxType>::bin()
260 : {
261 38626 : if (!_bin_is_sorted)
262 : {
263 0 : libMesh::out << "Warning! Bin is not yet sorted!" << std::endl;
264 : }
265 :
266 38626 : return _my_bin;
267 : }
268 :
269 : }
270 :
271 :
272 :
273 : // Explicitly instantiate for int, double
274 : template class LIBMESH_EXPORT Parallel::Sort<int, unsigned int>;
275 : template class LIBMESH_EXPORT Parallel::Sort<double, unsigned int>;
276 : #if defined(LIBMESH_HAVE_LIBHILBERT) && defined(LIBMESH_HAVE_MPI)
277 : template class LIBMESH_EXPORT Parallel::Sort<Parallel::DofObjectKey, unsigned int>;
278 : #endif
279 :
280 : } // namespace libMesh
|
