Arcane  v3.16.9.0
Documentation utilisateur
Chargement...
Recherche...
Aucune correspondance
BitonicSortT.H
1// -*- tab-width: 2; indent-tabs-mode: nil; coding: utf-8-with-signature -*-
2//-----------------------------------------------------------------------------
3// Copyright 2000-2025 CEA (www.cea.fr) IFPEN (www.ifpenergiesnouvelles.com)
4// See the top-level COPYRIGHT file for details.
5// SPDX-License-Identifier: Apache-2.0
6//-----------------------------------------------------------------------------
7/*---------------------------------------------------------------------------*/
8/* BitonicSortT.H (C) 2000-2025 */
9/* */
10/* Algorithme de tri bi-tonique parallèle. */
11/*---------------------------------------------------------------------------*/
12#ifndef ARCANE_CORE_PARALLEL_BITONICSORT_IMPL_H
13#define ARCANE_CORE_PARALLEL_BITONICSORT_IMPL_H
14/*---------------------------------------------------------------------------*/
15/*---------------------------------------------------------------------------*/
16
17#include "arcane/utils/TraceAccessor.h"
18#include "arcane/utils/FatalErrorException.h"
19
20#include "arcane/core/IParallelMng.h"
21#include "arcane/core/parallel/BitonicSort.h"
22
23/*---------------------------------------------------------------------------*/
24/*---------------------------------------------------------------------------*/
25
26namespace Arcane::Parallel
27{
28
29/*---------------------------------------------------------------------------*/
30/*---------------------------------------------------------------------------*/
31
32template <typename KeyType, typename KeyTypeTraits> BitonicSort<KeyType, KeyTypeTraits>::
33BitonicSort(IParallelMng* parallel_mng)
34: TraceAccessor(parallel_mng->traceMng())
35, m_parallel_mng(parallel_mng)
36{
37}
38
39template <typename KeyType, typename KeyTypeTraits> BitonicSort<KeyType, KeyTypeTraits>::
40BitonicSort(IParallelMng* parallel_mng, const KeyTypeTraits& traits)
41: TraceAccessor(parallel_mng->traceMng())
42, m_parallel_mng(parallel_mng)
43, m_traits(traits)
44{
45}
46
47/*---------------------------------------------------------------------------*/
48/*---------------------------------------------------------------------------*/
49
50template <typename KeyType, typename KeyTypeTraits> void BitonicSort<KeyType, KeyTypeTraits>::
51_init(ConstArrayView<KeyType> keys)
52{
53 m_init_size = keys.size();
54
55 // Il est indispensable que tous les rangs aient la même valeur
56 // de m_size
57 m_size = m_parallel_mng->reduce(Parallel::ReduceMax, m_init_size);
58
59 m_keys.resize(m_size);
60 m_key_ranks.resize(m_size);
61 m_key_indexes.resize(m_size);
62
63 Int32 rank = m_parallel_mng->commRank();
64
65 // Les valeurs de la variable aux mailles tab sont stockées
66 // dans le tableau m_key
67 for (Integer i = 0; i < m_init_size; ++i) {
68 m_keys[i] = keys[i];
69 m_key_indexes[i] = i;
70 m_key_ranks[i] = rank;
71 }
72
73 // Remplit la fin du tableau avec des valeurs non significatives
74 // Afin que chaque processeur ait le meme nombre d'elements
75 KeyType max_value = m_traits.maxValue();
76 for (Int64 i = m_init_size; i < m_size; i++) {
77 m_keys[i] = max_value;
78 m_key_indexes[i] = -1;
79 m_key_ranks[i] = rank;
80 }
81}
82
83/*---------------------------------------------------------------------------*/
84/*---------------------------------------------------------------------------*/
85/*!
86 \brief Tri bi-tonique de la variable \a m_key
87
88 En sortie de l'appel, la variable key est entièrement classée
89 par ordre croissant : les premiers éléments sont situés
90 par ordre croissant sur le processeur 0, les suivants sur
91 le processeur 1, etc...
92 Le rangement se fait 'en place', de sorte que la taille
93 des tableaux sur les différents processeurs n'est pas modifiée.
94
95*/
96template <typename KeyType, typename KeyTypeTraits> void
97BitonicSort<KeyType, KeyTypeTraits>::
99{
100 _init(keys);
101
102 m_nb_merge = 0;
103
104 info() << "BITONIC_SORT (64bit) want_rank?=" << m_want_index_and_rank
105 << " size=" << m_size
106 << " memsize=" << sizeof(KeyType) * m_size
107 << " structsize=" << sizeof(KeyType);
108
109 // Appel au tri local des cles
110 _localHeapSort();
111
112 // Définition du nombre de niveaux pour l'algorithme
113 Int32 nb_level = 0;
114 Int32 test = 1;
115 Int32 nb_rank = m_parallel_mng->commSize();
116 while (nb_rank > test) {
117 nb_level++;
118 test *= 2;
119 }
120 Int32 size = 1;
121
122 // Boucle sur les niveaux de profondeurs de l'algorithme
123 for (Int32 ilevel = 0; ilevel < nb_level; ++ilevel) {
124 size *= 2;
125
126 // Boucle sur les groupes de processeurs à traiter
127 for (Int32 jproc = 0; jproc < nb_rank; jproc += size) {
128 _mergeLevels(jproc, size);
129 }
130 }
131
132 // Le nombre d'éléments valides de la liste peut-être inférieur
133 // au nombre d'éléments alloués. Dès qu'une valeur est invalide,
134 // on arrête la liste.
135 // TODO: partir de la fin
136 for (Integer i = 0; i < m_size; ++i) {
137 if (!m_traits.isValid(m_keys[i])) {
138 m_size = i;
139 break;
140 }
141 }
142
143 info() << "END_BITONIC_SORT nb_merge=" << m_nb_merge;
144
145 m_keys.resize(m_size);
146 m_key_ranks.resize(m_size);
147 m_key_indexes.resize(m_size);
148}
149
150/*---------------------------------------------------------------------------*/
151/*---------------------------------------------------------------------------*/
152/*!
153 \brief Tri bi-tonique de la variable \a key.
154
155 En sortie de l'appel, la variable key est entièrement classée
156 par ordre croissant : les premiers éléments sont situés
157 par ordre croissant sur le processeur 0, les suivants sur
158 le processeur 1, etc...
159 Le rangement se fait 'en place', de sorte que la taille
160 des tableaux sur les différents processeurs n'est pas modifiée.
161*/
162template <typename KeyType, typename KeyTypeTraits> void
164_mergeLevels(Int32 begin, Int32 size)
165{
166 //etage separateur
167 for (Int32 i = 0; i < size / 2; ++i)
168 _mergeProcessors(begin + i, begin + size - 1 - i);
169
170 if (size <= 2)
171 return;
172
173 // Application de la trieuse bitonique de niveau n/2
174 Int32 div_size = size;
175 while (div_size > 1) {
176 div_size /= 2;
177 for (Int32 iproc = 0; iproc < size; iproc += div_size)
178 _separator(begin + iproc, div_size);
179 }
180}
181
182/*---------------------------------------------------------------------------*/
183/*---------------------------------------------------------------------------*/
184/*!
185 * \brief Etage séparateur de l'algorithme de tri bi-tonique
186 */
187template <typename KeyType, typename KeyTypeTraits> void BitonicSort<KeyType, KeyTypeTraits>::
188_separator(Int32 begin, Int32 size)
189{
190 for (Int32 i = 0; i < size / 2; ++i)
191 _mergeProcessors(begin + i, begin + i + size / 2);
192}
193
194/*---------------------------------------------------------------------------*/
195/*---------------------------------------------------------------------------*/
196/*!
197 * \brief Fusion des listes de deux processeurs.
198 *
199 \param iproc1 processeur de plus faible Id dont on fusionne la liste
200 \param iproc2 processeur de plus fort Id dont on fusionne la liste
201
202 * Cette opération est la brique élémentaire de
203 * l'algorithme de tri fusion bi-tonique. En entrée, elle
204 * prend les numéros de deux processeurs avec iproc1<iproc2.
205 * En sortie, les tableaux m_key de ces deux processeurs
206 * sont triés : les plus petits éléments sont triés par ordre croissant
207 * sur iproc1, les plus grands éléments sont triés par ordre croissant
208 * sur iproc2.
209 */
210template <typename KeyType, typename KeyTypeTraits> void BitonicSort<KeyType, KeyTypeTraits>::
211_mergeProcessors(Int32 iproc1, Int32 iproc2)
212{
213 if (iproc1 >= iproc2)
214 ARCANE_FATAL("Invalid merge iproc1={0} iproc2={1}", iproc1, iproc2);
215
216 Int32 my_rank = m_parallel_mng->commRank();
217
218 if (iproc2 >= m_parallel_mng->commSize())
219 return;
220
221 bool is_proc2 = (iproc2 == my_rank);
222 bool is_proc1 = (iproc1 == my_rank);
223
224 if (!is_proc1 && !is_proc2)
225 return;
226
227 info() << "SORT iproc1=" << iproc1 << " iproc2=" << iproc2;
228 ++m_nb_merge;
229
230 const Int64 buf_size = m_size;
231 const bool is_want_index_rank = m_want_index_and_rank;
232 ////////////////////////////////////////////
233 //traitement du processeur 2
234 ////////////////////////////////////////////
235
236 if (is_proc2) {
237 //envoi de la liste au proc 1
238 UniqueArray<KeyType> send_keys(m_keys);
239 UniqueArray<Request> requests;
240 requests.add(m_traits.send(m_parallel_mng, iproc1, send_keys));
241 if (is_want_index_rank) {
242 requests.add(m_parallel_mng->send(m_key_indexes, iproc1, false));
243 requests.add(m_parallel_mng->send(m_key_ranks, iproc1, false));
244 }
245 //reception de la fin de la liste fusionnee par le proc1
246 requests.add(m_traits.recv(m_parallel_mng, iproc1, m_keys));
247 if (is_want_index_rank) {
248 requests.add(m_parallel_mng->recv(m_key_indexes, iproc1, false));
249 requests.add(m_parallel_mng->recv(m_key_ranks, iproc1, false));
250 }
251 m_parallel_mng->waitAllRequests(requests);
252 }
253
254 //////////////////////////////////////
255 //traitement du processeur 1
256 //////////////////////////////////////
257 if (is_proc1) {
258 //reception de la liste du proc2
259
260 UniqueArray<KeyType> buf2(buf_size);
261 Int32UniqueArray buf2_proc;
262 Int32UniqueArray buf2_local_id;
263 //on alloue buf2 a la taille+1 afin de placer une sentinelle en
264 //buf2[size]
265 buf2.resize(buf_size);
266 if (is_want_index_rank) {
267 buf2_proc.resize(buf_size);
268 buf2_local_id.resize(buf_size);
269 }
270
271 Request recv_request = m_traits.recv(m_parallel_mng, iproc2, buf2);
272 m_parallel_mng->waitAllRequests(ArrayView<Request>(1, &recv_request));
273 if (is_want_index_rank) {
274 m_parallel_mng->recv(buf2_local_id, iproc2);
275 m_parallel_mng->recv(buf2_proc, iproc2);
276 }
277
278 //à remplacer par le plus grand nombre representable par un Integer
279 buf2.add(m_traits.maxValue());
280
281 // allocation d'un buffer de travail pour la fusion des deux listes
282 Int64 total_size = m_size + buf_size;
283 UniqueArray<KeyType> buf_merge(total_size);
284 UniqueArray<Int32> buf_proc_merge;
285 UniqueArray<Int32> buf_local_id_merge;
286 if (is_want_index_rank) {
287 buf_proc_merge.resize(total_size);
288 buf_local_id_merge.resize(total_size);
289 }
290
291#if 0
292 info() << "SIZE=" << buf_size << " total=" << total_size << " m_size=" << m_size
293 << " proc2=" << iproc2 << " init-size=" << m_init_size;
294#endif
295
296 // Fusion des deux listes en partant du principe que chacune est
297 // déjà triée.
298 Int64 cursor1 = 0;
299 Int64 cursor2 = 0;
300 for (Int64 i = 0; i < total_size; ++i) {
301 if (cursor1 >= m_size || (m_traits.compareLess(buf2[cursor2], m_keys[cursor1]) && cursor2 < buf_size)) {
302 buf_merge[i] = buf2[cursor2];
303 if (is_want_index_rank) {
304 buf_local_id_merge[i] = buf2_local_id[cursor2];
305 buf_proc_merge[i] = buf2_proc[cursor2];
306 }
307 ++cursor2;
308 }
309 else {
310 buf_merge[i] = m_keys[cursor1];
311 if (is_want_index_rank) {
312 buf_local_id_merge[i] = m_key_indexes[cursor1];
313 buf_proc_merge[i] = m_key_ranks[cursor1];
314 }
315 ++cursor1;
316 }
317 }
318 buf2.resize(buf_size);
319
320 // Recopie et envoi de la fin de la liste vers le proc2
321 for (Integer ii = 0; ii < buf_size; ii++) {
322 buf2[ii] = buf_merge[m_size + ii];
323 if (is_want_index_rank) {
324 buf2_local_id[ii] = buf_local_id_merge[m_size + ii];
325 buf2_proc[ii] = buf_proc_merge[m_size + ii];
326 }
327 }
328 Request send_request = m_traits.send(m_parallel_mng, iproc2, buf2);
329 m_parallel_mng->waitAllRequests(ArrayView<Request>(1, &send_request));
330 if (is_want_index_rank) {
331 m_parallel_mng->send(buf2_local_id, iproc2);
332 m_parallel_mng->send(buf2_proc, iproc2);
333 }
334
335 // recopie du debut de la liste dans la variable m_work_unique_id
336 for (Integer i = 0; i < buf_size; i++) {
337 m_keys[i] = buf_merge[i];
338 if (is_want_index_rank) {
339 m_key_indexes[i] = buf_local_id_merge[i];
340 m_key_ranks[i] = buf_proc_merge[i];
341 }
342 }
343 }
344}
345
346/*---------------------------------------------------------------------------*/
347/*---------------------------------------------------------------------------*/
348/*!
349 * \brief Tri par tas en local de la variable \a m_key.
350 *
351 * En sortie de l'appel, la variable est classée
352 * par ordre croissant à l'intérieur de chaque processeur.
353 */
354template <typename KeyType, typename KeyTypeTraits>
355void BitonicSort<KeyType, KeyTypeTraits>::
356_localHeapSort()
357{
358 // Cas particulier d'une liste réduite à zero ou un element
359 if (m_size < 2)
360 return;
361
362 // Suivant du parent du dernier element
363 Int64 l = m_size / 2;
364 Int64 ir = m_size - 1;
365 KeyType rra;
366 Int64 i = 0;
367 Int64 j = 0;
368 Integer tmp_local_id = NULL_ITEM_LOCAL_ID;
369 Integer tmp_proc = A_NULL_RANK;
370
371 for (;;) {
372 if (l > 0) {
373 --l;
374 rra = m_keys[l];
375 tmp_local_id = m_key_indexes[l];
376 tmp_proc = m_key_ranks[l];
377 }
378 else {
379 rra = m_keys[ir];
380 tmp_local_id = m_key_indexes[ir];
381 tmp_proc = m_key_ranks[ir];
382
383 m_keys[ir] = m_keys[0];
384 m_key_indexes[ir] = m_key_indexes[0];
385 m_key_ranks[ir] = m_key_ranks[0];
386
387 if (--ir == 0) {
388 m_keys[0] = rra;
389 m_key_indexes[0] = tmp_local_id;
390 m_key_ranks[0] = tmp_proc;
391 break;
392 }
393 }
394 i = l;
395 j = l + l + 1;
396 while (j <= ir) {
397 if (j < ir && m_traits.compareLess(m_keys[j], m_keys[j + 1]))
398 ++j;
399 if (m_traits.compareLess(rra, m_keys[j])) {
400 m_keys[i] = m_keys[j];
401 m_key_indexes[i] = m_key_indexes[j];
402 m_key_ranks[i] = m_key_ranks[j];
403 i = j;
404 //enfant a gauche
405 j = j * 2 + 1;
406 }
407 else
408 j = ir + 1;
409 }
410 m_keys[i] = rra;
411 m_key_indexes[i] = tmp_local_id;
412 m_key_ranks[i] = tmp_proc;
413 }
414}
415
416/*---------------------------------------------------------------------------*/
417/*---------------------------------------------------------------------------*/
418
419} // namespace Arcane::Parallel
420
421/*---------------------------------------------------------------------------*/
422/*---------------------------------------------------------------------------*/
423
424#endif
#define ARCANE_FATAL(...)
Macro envoyant une exception FatalErrorException.
void resize(Int64 s)
Change le nombre d'éléments du tableau à s.
Vue constante d'un tableau de type T.
Interface du gestionnaire de parallélisme pour un sous-domaine.
Algorithme de tri bi-tonique parallèle.
ConstArrayView< KeyType > keys() const override
Après un tri, retourne la liste des éléments de ce rang.
TraceMessage info() const
Flot pour un message d'information.
Implémentation de la concurrence.
Int32 Integer
Type représentant un entier.
UniqueArray< Int32 > Int32UniqueArray
Tableau dynamique à une dimension d'entiers 32 bits.
Definition UtilsTypes.h:428
std::int32_t Int32
Type entier signé sur 32 bits.