Arcane  v3.16.9.0
Documentation utilisateur
Chargement...
Recherche...
Aucune correspondance
BitonicSort.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/* BitonicSort.h (C) 2000-2025 */
9/* */
10/* Algorithme de tri bi-tonique parallèle. */
11/*---------------------------------------------------------------------------*/
12#ifndef ARCANE_CORE_PARALLEL_BITONICSORT_H
13#define ARCANE_CORE_PARALLEL_BITONICSORT_H
14/*---------------------------------------------------------------------------*/
15/*---------------------------------------------------------------------------*/
16
17#include "arcane/utils/TraceAccessor.h"
18#include "arcane/utils/UniqueArray.h"
19
20#include "arcane/core/IParallelSort.h"
21#include "arcane/core/IParallelMng.h"
22
23/*---------------------------------------------------------------------------*/
24/*---------------------------------------------------------------------------*/
25
26namespace Arcane::Parallel
27{
28
29/*---------------------------------------------------------------------------*/
30/*---------------------------------------------------------------------------*/
31/*!
32 * \brief Fournit les opérations nécessaires pour le tri via la
33 * classe \a BitonicSort.
34 */
35template <typename KeyType>
37{
38 public:
39
40 static bool compareLess(const KeyType& k1, const KeyType& k2)
41 {
42 return k1 < k2;
43 }
44 static Request send(IParallelMng* pm, Int32 rank, ConstArrayView<KeyType> values)
45 {
46 return pm->send(values, rank, false);
47 }
48 static Request recv(IParallelMng* pm, Int32 rank, ArrayView<KeyType> values)
49 {
50 return pm->recv(values, rank, false);
51 }
52 //! Valeur max possible pour la clé.
53 static KeyType maxValue()
54 {
55 //return ARCANE_INTEGER_MAX-1;
56 return std::numeric_limits<KeyType>::max();
57 }
58 // Indique si la clé est valide. Elle doit être invalide si k==maxValue()
59 static bool isValid(const KeyType& k)
60 {
61 return k != maxValue();
62 }
63};
64
65/*---------------------------------------------------------------------------*/
66/*---------------------------------------------------------------------------*/
67
68/*!
69 * \brief Algorithme de tri bi-tonique parallèle.
70 *
71 * Le type de la clé peut être quelconque, mais il doit posséder un opérateur
72 * de comparaison. Les caractéristiques nécessaires sont données par la
73 * classe KeyTypeTraits. L'implémentation fournit les
74 * opérations pour les types Int32, Int64 et Real via la classe
75 * \a BitonicSortDefaultTraits. Pour les autres types, il est nécessaire de
76 * spécialiser cette classe.
77 *
78 * La méthode sort() procède au tri. Après appel à cette méthode, il est
79 * possible de récupérer la liste des clés via \a keys() et les rangs
80 * et indices dans la liste d'origine de chaque élément de la clé via
81 * les méthodes keyRangs() et keyIndexes(). Si ces informations ne sont
82 * pas utiles, il est possible d'appeler setNeedIndexAndRank() pour
83 * les désactiver ce qui permet d'accélérer quelque peu le tri.
84 *
85 * Le tri se fait de telle sorte que les éléments sont triés dans l'ordre croissant
86 * en commençant par le processeur de rang 0, puis de rang 1 et ainsi de
87 * suite jusqu'à la fin. Par exemple, pour une liste de 5000 éléments répartis
88 * sur 4 rangs, le processeur de rang 0 possédera à la fin du tri les 1250 éléments
89 * les plus petits, le processeur de rang 1 les 1250 éléments suivants et ainsi
90 * de suite.
91 *
92 * Pour accélérer l'algorithme, il est préférable que tous les processeurs
93 * aient environ le même nombre d'éléments dans leur liste au départ. A la fin
94 * du tri, il est possible que tous les processeurs n'aient pas le même nombre
95 * d'éléments dans la liste et notamment les processeurs de rang les plus élevés
96 * peuvent ne pas avoir d'éléments.
97 */
98template <typename KeyType, typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>
99class BitonicSort
100: public TraceAccessor
101, public IParallelSort<KeyType>
102{
103 public:
104
105 explicit BitonicSort(IParallelMng* parallel_mng);
106 explicit BitonicSort(IParallelMng* parallel_mng, const KeyTypeTraits& traits);
107
108 public:
109
110 /*!
111 * \brief Trie en parallèle les éléments de \a keys sur tous les rangs.
112 *
113 * Cette opération est collective.
114 */
115 inline void sort(ConstArrayView<KeyType> keys) override;
116
117 //! Après un tri, retourne la liste des éléments de ce rang.
118 ConstArrayView<KeyType> keys() const override { return m_keys; }
119
120 //! Après un tri, retourne le tableau des rangs d'origine des éléments de keys().
121 Int32ConstArrayView keyRanks() const override { return m_key_ranks; }
122
123 //! Après un tri, retourne le tableau des indices dans la liste d'origine des éléments de keys().
124 Int32ConstArrayView keyIndexes() const override { return m_key_indexes; }
125
126 public:
127
128 void setNeedIndexAndRank(bool want_index_and_rank)
129 {
130 m_want_index_and_rank = want_index_and_rank;
131 }
132
133 private:
134
135 void _mergeLevels(Int32 begin, Int32 size);
136 void _mergeProcessors(Int32 proc1, Int32 proc2);
137 void _separator(Int32 begin, Int32 size);
138 void _localHeapSort();
139
140 private:
141
142 //! Variable contenant la cle du tri
144 //! Tableau contenant le rang du processeur où se trouve la clé
145 UniqueArray<Int32> m_key_ranks;
146 //! Tableau contenant l'indice de la clé dans le processeur
147 UniqueArray<Int32> m_key_indexes;
148 //! Gestionnaire du parallèlisme
149 IParallelMng* m_parallel_mng = nullptr;
150 //! Nombre d'éléments locaux
151 Int64 m_init_size = 0;
152 //! Nombre d'éléments locaux pour le tri bi-tonique
153 Int64 m_size = 0;
154
155 //! Indique si on souhaite les infos sur les rangs et index
156 bool m_want_index_and_rank = true;
157
158 //! Statistiques sur le nombre de niveaux de messages
159 Integer m_nb_merge = 0;
160
161 KeyTypeTraits m_traits;
162
163 private:
164
165 void _init(ConstArrayView<KeyType> keys);
166};
167
168/*---------------------------------------------------------------------------*/
169/*---------------------------------------------------------------------------*/
170
171} // namespace Arcane::Parallel
172
173/*---------------------------------------------------------------------------*/
174/*---------------------------------------------------------------------------*/
175
176#endif
Vue modifiable d'un tableau d'un type T.
Vue constante d'un tableau de type T.
Interface du gestionnaire de parallélisme pour un sous-domaine.
virtual void recv(ArrayView< char > values, Int32 rank)=0
Requête d'un message.
Definition Request.h:77
Fournit les opérations nécessaires pour le tri via la classe BitonicSort.
Definition BitonicSort.h:37
static KeyType maxValue()
Valeur max possible pour la clé.
Definition BitonicSort.h:53
Int32ConstArrayView keyIndexes() const override
Après un tri, retourne le tableau des indices dans la liste d'origine des éléments de keys().
ConstArrayView< KeyType > keys() const override
Après un tri, retourne la liste des éléments de ce rang.
void sort(ConstArrayView< KeyType > keys) override
Trie en parallèle les éléments de keys sur tous les rangs.
Int32ConstArrayView keyRanks() const override
Après un tri, retourne le tableau des rangs d'origine des éléments de keys().
Interface d'un algorithme de tri parallèle.
TraceAccessor(ITraceMng *m)
Construit un accesseur via le gestionnaire de trace m.
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.
ConstArrayView< Int32 > Int32ConstArrayView
Equivalent C d'un tableau à une dimension d'entiers 32 bits.
Definition UtilsTypes.h:569
std::int32_t Int32
Type entier signé sur 32 bits.