Arcane  v3.16.0.0
Documentation développeur
Chargement...
Recherche...
Aucune correspondance
BitonicSort.h
1// -*- tab-width: 2; indent-tabs-mode: nil; coding: utf-8-with-signature -*-
2//-----------------------------------------------------------------------------
3// Copyright 2000-2024 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-2024 */
9/* */
10/* Algorithme de tri bitonique 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/Limits.h"
19#include "arcane/utils/UniqueArray.h"
20
21#include "arcane/core/IParallelSort.h"
22#include "arcane/core/IParallelMng.h"
23
24/*---------------------------------------------------------------------------*/
25/*---------------------------------------------------------------------------*/
26
27namespace Arcane::Parallel
28{
29
30/*---------------------------------------------------------------------------*/
31/*---------------------------------------------------------------------------*/
36template <typename KeyType>
38{
39 public:
40
41 static bool compareLess(const KeyType& k1, const KeyType& k2)
42 {
43 return k1 < k2;
44 }
45 static Request send(IParallelMng* pm, Int32 rank, ConstArrayView<KeyType> values)
46 {
47 return pm->send(values, rank, false);
48 }
49 static Request recv(IParallelMng* pm, Int32 rank, ArrayView<KeyType> values)
50 {
51 return pm->recv(values, rank, false);
52 }
54 static KeyType maxValue()
55 {
56 //return ARCANE_INTEGER_MAX-1;
57 return std::numeric_limits<KeyType>::max();
58 }
59 // Indique si la clé est valide. Elle doit être invalide si k==maxValue()
60 static bool isValid(const KeyType& k)
61 {
62 return k != maxValue();
63 }
64};
65
66/*---------------------------------------------------------------------------*/
67/*---------------------------------------------------------------------------*/
68
99template <typename KeyType, typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>
100class BitonicSort
101: public TraceAccessor
102, public IParallelSort<KeyType>
103{
104 public:
105
106 explicit BitonicSort(IParallelMng* parallel_mng);
107
108 public:
109
115 void sort(ConstArrayView<KeyType> keys) override;
116
118 ConstArrayView<KeyType> keys() const override { return m_keys; }
119
121 Int32ConstArrayView keyRanks() const override { return m_key_ranks; }
122
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
154
157
160
161 private:
162
163 void _init(ConstArrayView<KeyType> keys);
164};
165
166/*---------------------------------------------------------------------------*/
167/*---------------------------------------------------------------------------*/
168
169} // namespace Arcane::Parallel
170
171/*---------------------------------------------------------------------------*/
172/*---------------------------------------------------------------------------*/
173
174#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:38
static KeyType maxValue()
Valeur max possible pour la clé.
Definition BitonicSort.h:54
Int32ConstArrayView keyIndexes() const override
Après un tri, retourne le tableau des indices dans la liste d'origine des éléments de keys().
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 bitonique.
bool m_want_index_and_rank
Indique si on souhaite les infos sur les rangs et index.
void sort(ConstArrayView< KeyType > keys) override
Trie en parallèle les éléments de keys sur tous les rangs.
Int64 m_size
Nombre d'éléments locaux pour le tri bitonique.
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 bitonique de la variable key.
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.