Arcane  v3.16.9.0
Documentation développeur
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/*---------------------------------------------------------------------------*/
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
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/*---------------------------------------------------------------------------*/
162template <typename KeyType, typename KeyTypeTraits> void
163BitonicSort<KeyType, KeyTypeTraits>::
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/*---------------------------------------------------------------------------*/
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/*---------------------------------------------------------------------------*/
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;
233 //traitement du processeur 2
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
255 //traitement du processeur 1
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/*---------------------------------------------------------------------------*/
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];
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];
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.
Vue modifiable d'un tableau d'un type T.
void resize(Int64 s)
Change le nombre d'éléments du tableau à s.
void add(ConstReferenceType val)
Ajoute l'élément val à la fin du tableau.
Vue constante d'un tableau de type T.
Interface du gestionnaire de parallélisme pour un sous-domaine.
Requête d'un message.
Definition Request.h:77
Algorithme de tri bi-tonique parallèle.
void _mergeProcessors(Int32 proc1, Int32 proc2)
Fusion des listes de deux processeurs.
Integer m_nb_merge
Statistiques sur le nombre de niveaux de messages.
ConstArrayView< KeyType > keys() const override
Après un tri, retourne la liste des éléments de ce rang.
void _separator(Int32 begin, Int32 size)
Etage séparateur de l'algorithme de tri bi-tonique.
bool m_want_index_and_rank
Indique si on souhaite les infos sur les rangs et index.
Int64 m_size
Nombre d'éléments locaux pour le tri bi-tonique.
UniqueArray< Int32 > m_key_ranks
Tableau contenant le rang du processeur où se trouve la clé
UniqueArray< Int32 > m_key_indexes
Tableau contenant l'indice de la clé dans le processeur.
Int64 m_init_size
Nombre d'éléments locaux.
UniqueArray< KeyType > m_keys
Variable contenant la cle du tri.
IParallelMng * m_parallel_mng
Gestionnaire du parallèlisme.
void _localHeapSort()
Tri par tas en local de la variable m_key.
void _mergeLevels(Int32 begin, Int32 size)
Tri bi-tonique de la variable key.
TraceMessage info() const
Flot pour un message d'information.
Vecteur 1D de données avec sémantique par valeur (style STL).
Implémentation de la concurrence.
std::int64_t Int64
Type entier signé sur 64 bits.
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.