12#ifndef ARCANE_CORE_PARALLEL_BITONICSORT_IMPL_H
13#define ARCANE_CORE_PARALLEL_BITONICSORT_IMPL_H
17#include "arcane/utils/TraceAccessor.h"
18#include "arcane/utils/FatalErrorException.h"
20#include "arcane/core/IParallelMng.h"
21#include "arcane/core/parallel/BitonicSort.h"
35, m_parallel_mng(parallel_mng)
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)
50template <
typename KeyType,
typename KeyTypeTraits>
void BitonicSort<KeyType, KeyTypeTraits>::
51_init(ConstArrayView<KeyType> keys)
53 m_init_size = keys.size();
57 m_size = m_parallel_mng->reduce(Parallel::ReduceMax, m_init_size);
59 m_keys.resize(m_size);
60 m_key_ranks.resize(m_size);
61 m_key_indexes.resize(m_size);
63 Int32 rank = m_parallel_mng->commRank();
67 for (Integer i = 0; i < m_init_size; ++i) {
70 m_key_ranks[i] = rank;
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;
96template <
typename KeyType,
typename KeyTypeTraits>
void
97BitonicSort<KeyType, KeyTypeTraits>::
106 <<
" memsize=" <<
sizeof(KeyType) *
m_size
107 <<
" structsize=" <<
sizeof(KeyType);
116 while (nb_rank > test) {
123 for (
Int32 ilevel = 0; ilevel < nb_level; ++ilevel) {
127 for (
Int32 jproc = 0; jproc < nb_rank; jproc += size) {
137 if (!m_traits.isValid(
m_keys[i])) {
162template <
typename KeyType,
typename KeyTypeTraits>
void
163BitonicSort<KeyType, KeyTypeTraits>::
167 for (
Int32 i = 0; i < size / 2; ++i)
174 Int32 div_size = size;
175 while (div_size > 1) {
177 for (
Int32 iproc = 0; iproc < size; iproc += div_size)
187template <
typename KeyType,
typename KeyTypeTraits>
void BitonicSort<KeyType, KeyTypeTraits>::
190 for (
Int32 i = 0; i < size / 2; ++i)
210template <
typename KeyType,
typename KeyTypeTraits>
void BitonicSort<KeyType, KeyTypeTraits>::
213 if (iproc1 >= iproc2)
214 ARCANE_FATAL(
"Invalid merge iproc1={0} iproc2={1}", iproc1, iproc2);
221 bool is_proc2 = (iproc2 == my_rank);
222 bool is_proc1 = (iproc1 == my_rank);
224 if (!is_proc1 && !is_proc2)
227 info() <<
"SORT iproc1=" << iproc1 <<
" iproc2=" << iproc2;
241 if (is_want_index_rank) {
247 if (is_want_index_rank) {
266 if (is_want_index_rank) {
267 buf2_proc.
resize(buf_size);
268 buf2_local_id.
resize(buf_size);
273 if (is_want_index_rank) {
279 buf2.
add(m_traits.maxValue());
286 if (is_want_index_rank) {
287 buf_proc_merge.
resize(total_size);
288 buf_local_id_merge.
resize(total_size);
292 info() <<
"SIZE=" << buf_size <<
" total=" << total_size <<
" m_size=" <<
m_size
293 <<
" proc2=" << iproc2 <<
" init-size=" <<
m_init_size;
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];
310 buf_merge[i] =
m_keys[cursor1];
311 if (is_want_index_rank) {
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];
330 if (is_want_index_rank) {
336 for (
Integer i = 0; i < buf_size; i++) {
338 if (is_want_index_rank) {
354template <
typename KeyType,
typename KeyTypeTraits>
355void BitonicSort<KeyType, KeyTypeTraits>::
368 Integer tmp_local_id = NULL_ITEM_LOCAL_ID;
369 Integer tmp_proc = A_NULL_RANK;
397 if (j < ir && m_traits.compareLess(
m_keys[j],
m_keys[j + 1]))
399 if (m_traits.compareLess(rra,
m_keys[j])) {
#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.
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.
Classe d'accès aux traces.
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.
std::int32_t Int32
Type entier signé sur 32 bits.