Algorithme de tri bitonique parallèle. Plus de détails...

#include <arcane/core/parallel/BitonicSort.h>

Graphe d'héritage de Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >:

Graphe de collaboration de Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >:

Fonctions membres publiques
	BitonicSort (IParallelMng *parallel_mng)

void	sort (ConstArrayView< KeyType > keys) override
	Trie en parallèle les éléments de keys sur tous les rangs.

ConstArrayView< KeyType >	keys () const override
	Après un tri, retourne la liste des éléments de ce rang.

Int32ConstArrayView	keyRanks () const override
	Après un tri, retourne le tableau des rangs d'origine des éléments de keys().

Int32ConstArrayView	keyIndexes () const override
	Après un tri, retourne le tableau des indices dans la liste d'origine des éléments de keys().

void	setNeedIndexAndRank (bool want_index_and_rank)

Fonctions membres publiques hérités de Arccore::TraceAccessor
	TraceAccessor (ITraceMng *m)
	Construit un accesseur via le gestionnaire de trace m.

	TraceAccessor (const TraceAccessor &rhs)
	Constructeur par recopie.

TraceAccessor &	operator= (const TraceAccessor &rhs)
	Opérateur de recopie.

virtual	~TraceAccessor ()
	Libère les ressources.

ITraceMng *	traceMng () const
	Gestionnaire de trace.

TraceMessage	info () const
	Flot pour un message d'information.

TraceMessage	pinfo () const
	Flot pour un message d'information en parallèle.

TraceMessage	info (char category) const
	Flot pour un message d'information d'une catégorie donnée.

TraceMessage	pinfo (char category) const
	Flot pour un message d'information parallèle d'une catégorie donnée.

TraceMessage	info (bool v) const
	Flot pour un message d'information.

TraceMessage	warning () const
	Flot pour un message d'avertissement.

TraceMessage	pwarning () const

TraceMessage	error () const
	Flot pour un message d'erreur.

TraceMessage	perror () const

TraceMessage	log () const
	Flot pour un message de log.

TraceMessage	plog () const
	Flot pour un message de log.

TraceMessage	logdate () const
	Flot pour un message de log précédé de la date.

TraceMessage	fatal () const
	Flot pour un message d'erreur fatale.

TraceMessage	pfatal () const
	Flot pour un message d'erreur fatale en parallèle.

TraceMessageDbg	debug (Trace::eDebugLevel=Trace::Medium) const
	Flot pour un message de debug.

Trace::eDebugLevel	configDbgLevel () const
	Niveau debug du fichier de configuration.

TraceMessage	info (Int32 verbose_level) const
	Flot pour un message d'information d'un niveau donné

TraceMessage	linfo () const
	Flot pour un message d'information avec le niveau d'information local à cette instance.

TraceMessage	linfo (Int32 relative_level) const
	Flot pour un message d'information avec le niveau d'information local à cette instance.

void	fatalMessage (const StandaloneTraceMessage &o) const

Fonctions membres privées
void	_mergeLevels (Int32 begin, Int32 size)
	Tri bitonique de la variable key.

void	_mergeProcessors (Int32 proc1, Int32 proc2)
	Fusion des listes de deux processeurs .

void	_separator (Int32 begin, Int32 size)
	Etage séparateur de l'algorithme de tri bitonique.

void	_localHeapSort ()
	Tri par tas en local de la variable m_key.

void	_init (ConstArrayView< KeyType > keys)

Attributs privés
UniqueArray< KeyType >	m_keys
	Variable contenant la cle du tri.

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.

IParallelMng *	m_parallel_mng = nullptr
	Gestionnaire du parallèlisme.

Int64	m_init_size = 0
	Nombre d'éléments locaux.

Int64	m_size = 0
	Nombre d'éléments locaux pour le tri bitonique.

bool	m_want_index_and_rank = true
	Indique si on souhaite les infos sur les rangs et index.

Integer	m_nb_merge = 0
	Statistiques sur le nombre de niveaux de messages.

Membres hérités additionnels
Fonctions membres protégées hérités de Arccore::TraceAccessor
void	_setLocalVerboseLevel (Int32 v)

Int32	_localVerboseLevel () const

Description détaillée

template<typename KeyType, typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>
class Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >

Algorithme de tri bitonique parallèle.

Le type de la clé peut être quelconque, mais il doit posséder un opérateur de comparaison. Les caractéristiques nécessaires sont données par la classe KeyTypeTraints. . L'implémentation fournit les opérations pour les type Int32, Int64 et Real via la classe BitonicSortDefaultTraits. Pour les autres types, il est nécessaire de spécialiser cette classe.

La méthode sort() procède au tri. Après appel à cette méthode, il est possible de récupérer la liste des clés via keys() et les rangs et indices dans la liste d'origine de chaque élément de la clé via les méthodes keyRangs() et keyIndexes(). Si ces informations ne sont pas utiles, il est possible d'appeler setNeedIndexAndRank() pour les désactiver ce qui permet d'accéler quelque peu le tri.

Le tri se fait de telle sorte que les éléments sont triés dans l'ordre croissant en commençant par le processeur de rang 0, puis de rang 1 et ainsi de suite jusqu'à la fin. Par exemple, pour une liste de 5000 éléments répartis sur 4 rangs, le processeur de rang 0 possédera à la fin du tri les 1250 éléments les plus petits, le processeur de rang 1 les 1250 éléments suivantes et ainsi de suite.

Pour accélérer l'algorithme, il est préférable que tous les processeurs aient environ le même nombre d'éléments dans leur liste au départ. A la fin du tri, il est possible que tous les processeurs n'aient pas le même nombre d'éléments dans la liste et notamment les processeurs de rang les plus élevés peuvent ne pas avoir d'éléments.

Définition à la ligne 99 du fichier BitonicSort.h.

Documentation des constructeurs et destructeur

◆ BitonicSort()

template<typename KeyType , typename KeyTypeTraits >

Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::BitonicSort ( IParallelMng * parallel_mng )

explicit

Définition à la ligne 29 du fichier BitonicSortT.H.

Documentation des fonctions membres

◆ _init()

template<typename KeyType , typename KeyTypeTraits >

void Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::_init ( ConstArrayView< KeyType > keys )

private

Définition à la ligne 39 du fichier BitonicSortT.H.

◆ _localHeapSort()

template<typename KeyType , typename KeyTypeTraits >

void Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::_localHeapSort ( )

private

Tri par tas en local de la variable m_key.

En sortie de l'appel, la variable est classée par ordre croissant à l'intérieur de chaque processeur

Définition à la ligne 343 du fichier BitonicSortT.H.

◆ _mergeLevels()

template<typename KeyType , typename KeyTypeTraits >

void Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::_mergeLevels	(	Int32	begin,
		Int32	size
	)

private

Tri bitonique de la variable key.

En sortie de l'appel, la variable key est entièrement classée par ordre croissant : les premiers éléments sont situés par ordre croissant sur le processeur 0, les suivants sur le processeur 1, etc... Le rangement se fait 'en place', de sorte que la taille des tableaux sur les différents processeurs n'est pas modifiée.

Définition à la ligne 152 du fichier BitonicSortT.H.

◆ _mergeProcessors()

template<typename KeyType , typename KeyTypeTraits >

void Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::_mergeProcessors	(	Int32	iproc1,
		Int32	iproc2
	)

private

Fusion des listes de deux processeurs .

Paramètres

iproc1	processeur de plus faible Id dont on fusionne la liste
iproc2	processeur de plus fort Id dont on fusionne la liste

Cette opération est la brique élémentaire de l'algorithme de tri fusion bitonique. En entrée, elle prend les numéros de deux processeurs avec iproc1<iproc2. En sortie, les tableaux m_key de ces deux processeurs sont triés : les plus petits éléments sont triés par ordre croissant sur iproc1, les plus grands éléments sont triés par ordre croissant sur iproc2.

Définition à la ligne 199 du fichier BitonicSortT.H.

Références ARCANE_FATAL.

◆ _separator()

template<typename KeyType , typename KeyTypeTraits >

void Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::_separator	(	Int32	begin,
		Int32	size
	)

private

Etage séparateur de l'algorithme de tri bitonique.

Définition à la ligne 176 du fichier BitonicSortT.H.

◆ keyIndexes()

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

Int32ConstArrayView Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::keyIndexes ( ) const

inlineoverridevirtual

Après un tri, retourne le tableau des indices dans la liste d'origine des éléments de keys().

Implémente Arcane::Parallel::IParallelSort< KeyType >.

Définition à la ligne 123 du fichier BitonicSort.h.

Références Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_key_indexes.

◆ keyRanks()

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

Int32ConstArrayView Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::keyRanks ( ) const

inlineoverridevirtual

Après un tri, retourne le tableau des rangs d'origine des éléments de keys().

Implémente Arcane::Parallel::IParallelSort< KeyType >.

Définition à la ligne 120 du fichier BitonicSort.h.

Références Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_key_ranks.

◆ keys()

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

ConstArrayView< KeyType > Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::keys ( ) const

inlineoverridevirtual

Après un tri, retourne la liste des éléments de ce rang.

Implémente Arcane::Parallel::IParallelSort< KeyType >.

Définition à la ligne 117 du fichier BitonicSort.h.

Références Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_keys.

◆ setNeedIndexAndRank()

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

void Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::setNeedIndexAndRank ( bool want_index_and_rank )

inline

Définition à la ligne 127 du fichier BitonicSort.h.

◆ sort()

template<typename KeyType , typename KeyTypeTraits >

void Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::sort ( ConstArrayView< KeyType > keys )

overridevirtual

Trie en parallèle les éléments de keys sur tous les rangs.

Tri bitonique de la variable m_key.

Cette opération est collective.

En sortie de l'appel, la variable key est entièrement classée par ordre croissant : les premiers éléments sont situés par ordre croissant sur le processeur 0, les suivants sur le processeur 1, etc... Le rangement se fait 'en place', de sorte que la taille des tableaux sur les différents processeurs n'est pas modifiée.

Implémente Arcane::Parallel::IParallelSort< KeyType >.

Définition à la ligne 86 du fichier BitonicSortT.H.

Documentation des données membres

◆ m_init_size

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

Int64 Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_init_size = 0

private

Nombre d'éléments locaux.

Définition à la ligne 150 du fichier BitonicSort.h.

◆ m_key_indexes

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

UniqueArray<Int32> Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_key_indexes

private

Tableau contenant l'indice de la clé dans le processeur.

Définition à la ligne 146 du fichier BitonicSort.h.

Référencé par Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::keyIndexes().

◆ m_key_ranks

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

UniqueArray<Int32> Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_key_ranks

private

Tableau contenant le rang du processeur où se trouve la clé

Définition à la ligne 144 du fichier BitonicSort.h.

Référencé par Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::keyRanks().

◆ m_keys

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

UniqueArray<KeyType> Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_keys

private

Variable contenant la cle du tri.

Définition à la ligne 142 du fichier BitonicSort.h.

Référencé par Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::keys().

◆ m_nb_merge

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

Integer Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_nb_merge = 0

private

Statistiques sur le nombre de niveaux de messages.

Définition à la ligne 158 du fichier BitonicSort.h.

◆ m_parallel_mng

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

IParallelMng* Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_parallel_mng = nullptr

private

Gestionnaire du parallèlisme.

Définition à la ligne 148 du fichier BitonicSort.h.

◆ m_size

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

Int64 Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_size = 0

private

Nombre d'éléments locaux pour le tri bitonique.

Définition à la ligne 152 du fichier BitonicSort.h.

◆ m_want_index_and_rank

template<typename KeyType , typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>

bool Arcane::Parallel::BitonicSort< KeyType, KeyTypeTraits >::m_want_index_and_rank = true

private

Indique si on souhaite les infos sur les rangs et index.

Définition à la ligne 155 du fichier BitonicSort.h.

La documentation de cette classe a été générée à partir des fichiers suivants :

Fonctions membres publiques

Fonctions membres privées

Attributs privés

Membres hérités additionnels

Description détaillée

Documentation des constructeurs et destructeur

◆ BitonicSort()

Documentation des fonctions membres

◆ _init()

◆ _localHeapSort()

◆ _mergeLevels()

◆ _mergeProcessors()

◆ _separator()

◆ keyIndexes()

◆ keyRanks()

◆ keys()

◆ setNeedIndexAndRank()

◆ sort()

Documentation des données membres

◆ m_init_size

◆ m_key_indexes

◆ m_key_ranks

◆ m_keys

◆ m_nb_merge

◆ m_parallel_mng

◆ m_size

◆ m_want_index_and_rank