libMesh
Public Member Functions | Protected Attributes | Private Member Functions | Private Attributes | List of all members
libMesh::Parallel::Sort< KeyType, IdxType > Class Template Reference

The parallel sorting method is templated on the type of data which is to be sorted. More...

#include <parallel_sort.h>

Inheritance diagram for libMesh::Parallel::Sort< KeyType, IdxType >:
[legend]

Public Member Functions

 Sort (const Parallel::Communicator &comm, std::vector< KeyType > &d)
 Constructor takes the number of processors, the processor id, and a reference to a vector of data to be sorted. More...
 
void sort ()
 This is the only method which needs to be called by the user. More...
 
const std::vector< KeyType > & bin ()
 Return a constant reference to _my_bin. More...
 
const Parallel::Communicatorcomm () const
 
processor_id_type n_processors () const
 
processor_id_type processor_id () const
 

Protected Attributes

const Parallel::Communicator_communicator
 

Private Member Functions

void binsort ()
 Sorts the local data into bins across all processors. More...
 
void communicate_bins ()
 Communicates the bins from each processor to the appropriate processor. More...
 
void sort_local_bin ()
 After all the bins have been communicated, we can sort our local bin. More...
 

Private Attributes

const processor_id_type _n_procs
 The number of processors to work with. More...
 
const processor_id_type _proc_id
 The identity of this processor. More...
 
bool _bin_is_sorted
 Flag which lets you know if sorting is complete. More...
 
std::vector< KeyType > & _data
 The raw, unsorted data which will need to be sorted (in parallel) across all processors. More...
 
std::vector< IdxType > _local_bin_sizes
 Vector which holds the size of each bin on this processor. More...
 
std::vector< KeyType > _my_bin
 The bin which will eventually be held by this processor. More...
 

Detailed Description

template<typename KeyType, typename IdxType = unsigned int>
class libMesh::Parallel::Sort< KeyType, IdxType >

The parallel sorting method is templated on the type of data which is to be sorted.

It may later be templated on other things if we are ambitious. This class knows about MPI, and knows how many processors there are. It is responsible for transmitting data between the processors and ensuring that the data is properly sorted between all the processors. We assume that a Sort is instantiated on all processors.

Author
Benjamin S. Kirk
John W. Peterson
Date
2007 Object for performing parallel sorts using MPI.

Definition at line 53 of file parallel_sort.h.

Constructor & Destructor Documentation

◆ Sort()

template<typename KeyType , typename IdxType = unsigned int>
libMesh::Parallel::Sort< KeyType, IdxType >::Sort ( const Parallel::Communicator comm,
std::vector< KeyType > &  d 
)

Constructor takes the number of processors, the processor id, and a reference to a vector of data to be sorted.

This vector is sorted by the constructor, therefore, construction of a Sort object takes O(n log n) time, where n is the length of the vector.

Member Function Documentation

◆ bin()

template<typename KeyType , typename IdxType = unsigned int>
const std::vector<KeyType>& libMesh::Parallel::Sort< KeyType, IdxType >::bin ( )

Return a constant reference to _my_bin.

This allows us to do things like check if sorting was successful by printing _my_bin.

◆ binsort()

template<typename KeyType , typename IdxType = unsigned int>
void libMesh::Parallel::Sort< KeyType, IdxType >::binsort ( )
private

Sorts the local data into bins across all processors.

Right now it constructs a BenSorter<KeyType> object. In the future this could be a template parameter.

◆ comm()

const Parallel::Communicator& libMesh::ParallelObject::comm ( ) const
inherited

◆ communicate_bins()

template<typename KeyType , typename IdxType = unsigned int>
void libMesh::Parallel::Sort< KeyType, IdxType >::communicate_bins ( )
private

Communicates the bins from each processor to the appropriate processor.

By the time this function is finished, each processor will hold only its own bin(s).

◆ n_processors()

processor_id_type libMesh::ParallelObject::n_processors ( ) const
inherited
Returns
The number of processors in the group.

Definition at line 93 of file parallel_object.h.

References libMesh::ParallelObject::_communicator, and libMesh::Parallel::Communicator::size().

Referenced by libMesh::MeshBase::partition().

94  { return cast_int<processor_id_type>(_communicator.size()); }
processor_id_type size() const
Definition: communicator.h:175
const Parallel::Communicator & _communicator

◆ processor_id()

processor_id_type libMesh::ParallelObject::processor_id ( ) const
inherited

◆ sort()

template<typename KeyType , typename IdxType = unsigned int>
void libMesh::Parallel::Sort< KeyType, IdxType >::sort ( )

This is the only method which needs to be called by the user.

Its only responsibility is to call three private methods in the correct order.

◆ sort_local_bin()

template<typename KeyType , typename IdxType = unsigned int>
void libMesh::Parallel::Sort< KeyType, IdxType >::sort_local_bin ( )
private

After all the bins have been communicated, we can sort our local bin.

This is nothing more than a call to std::sort

Member Data Documentation

◆ _bin_is_sorted

template<typename KeyType , typename IdxType = unsigned int>
bool libMesh::Parallel::Sort< KeyType, IdxType >::_bin_is_sorted
private

Flag which lets you know if sorting is complete.

Definition at line 98 of file parallel_sort.h.

◆ _communicator

const Parallel::Communicator& libMesh::ParallelObject::_communicator
protectedinherited

◆ _data

template<typename KeyType , typename IdxType = unsigned int>
std::vector<KeyType>& libMesh::Parallel::Sort< KeyType, IdxType >::_data
private

The raw, unsorted data which will need to be sorted (in parallel) across all processors.

Definition at line 105 of file parallel_sort.h.

◆ _local_bin_sizes

template<typename KeyType , typename IdxType = unsigned int>
std::vector<IdxType> libMesh::Parallel::Sort< KeyType, IdxType >::_local_bin_sizes
private

Vector which holds the size of each bin on this processor.

It has size equal to _n_procs.

Definition at line 112 of file parallel_sort.h.

◆ _my_bin

template<typename KeyType , typename IdxType = unsigned int>
std::vector<KeyType> libMesh::Parallel::Sort< KeyType, IdxType >::_my_bin
private

The bin which will eventually be held by this processor.

It may be shorter or longer than _data. It will be dynamically resized when it is needed.

Definition at line 120 of file parallel_sort.h.

◆ _n_procs

template<typename KeyType , typename IdxType = unsigned int>
const processor_id_type libMesh::Parallel::Sort< KeyType, IdxType >::_n_procs
private

The number of processors to work with.

Definition at line 88 of file parallel_sort.h.

◆ _proc_id

template<typename KeyType , typename IdxType = unsigned int>
const processor_id_type libMesh::Parallel::Sort< KeyType, IdxType >::_proc_id
private

The identity of this processor.

Definition at line 93 of file parallel_sort.h.


The documentation for this class was generated from the following file: