Collection of Generic Parallel Functions: Sorting, Partitioning, Searching,... More...
Classes | |
class | Mpi_datatype |
An abstract class used for communicating messages using user-defined datatypes. The user must implement the static member function "value()" that returns the MPI_Datatype corresponding to this user-defined datatype. More... | |
class | Mpi_datatype< bool > |
A template specialization of the abstract class Mpi_datatype. This can be used for communicating messages of type "bool". More... | |
class | Mpi_datatype< IndexHolder< T > > |
class | Mpi_datatype< std::complex< T > > |
class | Mpi_pairtype |
Functions | |
template<typename T > | |
int | Mpi_Isend (T *buf, int count, int dest, int tag, MPI_Comm comm, MPI_Request *request) |
template<typename T > | |
int | Mpi_Issend (T *buf, int count, int dest, int tag, MPI_Comm comm, MPI_Request *request) |
template<typename T > | |
int | Mpi_Recv (T *buf, int count, int source, int tag, MPI_Comm comm, MPI_Status *status) |
template<typename T > | |
int | Mpi_Irecv (T *buf, int count, int source, int tag, MPI_Comm comm, MPI_Request *request) |
template<typename T > | |
int | Mpi_Gather (T *sendBuffer, T *recvBuffer, int count, int root, MPI_Comm comm) |
template<typename T , typename S > | |
int | Mpi_Sendrecv (T *sendBuf, int sendCount, int dest, int sendTag, S *recvBuf, int recvCount, int source, int recvTag, MPI_Comm comm, MPI_Status *status) |
template<typename T > | |
int | Mpi_Bcast (T *buffer, int count, int root, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Scan (T *sendbuf, T *recvbuf, int count, MPI_Op op, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Reduce (T *sendbuf, T *recvbuf, int count, MPI_Op op, int root, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Allreduce (T *sendbuf, T *recvbuf, int count, MPI_Op op, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Alltoall (T *sendbuf, T *recvbuf, int count, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Allgatherv (T *sendbuf, int sendcount, T *recvbuf, int *recvcounts, int *displs, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Allgather (T *sendbuf, T *recvbuf, int count, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Alltoallv_sparse (T *sendbuf, int *sendcnts, int *sdispls, T *recvbuf, int *recvcnts, int *rdispls, MPI_Comm comm) |
template<typename T > | |
int | Mpi_Alltoallv_dense (T *sendbuf, int *sendcnts, int *sdispls, T *recvbuf, int *recvcnts, int *rdispls, MPI_Comm comm) |
template<typename T > | |
unsigned int | defaultWeight (const T *a) |
template<typename T > | |
int | partitionW (std::vector< T > &vec, unsigned int(*getWeight)(const T *), MPI_Comm comm) |
A parallel weighted partitioning function. In our implementation, we do not pose any restriction on the input or the number of processors. This function can be used with an odd number of processors as well. Some processors can pass an empty vector as input. The relative ordering of the elements is preserved. More... | |
template<typename T > | |
void | rankSamples (std::vector< T > &arr, std::vector< T > samples, MPI_Comm comm) |
template<typename T > | |
std::vector< T > | Sorted_Sample_Select (std::vector< T > &arr, unsigned int kway, std::vector< unsigned int > &min_idx, std::vector< unsigned int > &max_idx, std::vector< DendroIntL > &splitter_ranks, MPI_Comm comm) |
template<typename T > | |
std::vector< T > | Sorted_approx_Select (std::vector< T > &arr, unsigned int k, MPI_Comm comm) |
template<typename T > | |
std::vector< std::pair< T, DendroIntL > > | Sorted_approx_Select_skewed (std::vector< T > &arr, unsigned int k, MPI_Comm comm) |
new one to handle skewed distributions ... More... | |
template<typename T > | |
std::vector< T > | GetRangeMean (std::vector< T > &arr, std::vector< unsigned int > range_min, std::vector< unsigned int > range_max, MPI_Comm comm) |
template<typename T > | |
std::vector< T > | GuessRangeMedian (std::vector< T > &arr, std::vector< unsigned int > range_min, std::vector< unsigned int > range_max, MPI_Comm comm) |
template<typename T > | |
std::vector< T > | Sorted_k_Select (std::vector< T > &arr, std::vector< unsigned int > min_idx, std::vector< unsigned int > max_idx, std::vector< DendroIntL > K, std::vector< T > guess, MPI_Comm comm) |
A parallel k-selection algorithms. More... | |
template<typename T > | |
int | HyperQuickSort (std::vector< T > &in, std::vector< T > &out, MPI_Comm comm) |
A parallel hyper quick sort implementation. More... | |
template<typename T > | |
int | HyperQuickSort_kway (std::vector< T > &in, std::vector< T > &out, MPI_Comm comm) |
template<typename T > | |
int | HyperQuickSort_cav (std::vector< T > &in, std::vector< T > &out, MPI_Comm comm) |
template<typename T > | |
int | HyperQuickSort (std::vector< T > &arr, MPI_Comm comm) |
template<typename T > | |
int | HyperQuickSort_kway (std::vector< T > &in, MPI_Comm comm) |
template<typename T > | |
int | HyperQuickSort_cav (std::vector< T > &in, MPI_Comm comm) |
template<typename T > | |
int | sampleSort (std::vector< T > &in, std::vector< T > &out, MPI_Comm comm) |
A parallel sample sort implementation. In our implementation, we do not pose any restriction on the input or the number of processors. This function can be used with an odd number of processors as well. Some processors can pass an empty vector as input. If the total number of elements in the vector (globally) is fewer than 10*p^2, where p is the number of processors, then we will use bitonic sort instead of sample sort to sort the vector. We use a paralle bitonic sort to sort the samples in the sample sort algorithm. Hence, the complexity of the algorithm is O(n/p log n/p) + O(p log p). Here, n is the global length of the vector and p is the number of processors. More... | |
template<typename T > | |
int | sampleSort (std::vector< T > &in, MPI_Comm comm) |
int | splitComm2way (bool iAmEmpty, MPI_Comm *new_comm, MPI_Comm orig_comm) |
Splits a communication group into two, one containing processors that passed a value of 'false' for the parameter 'iAmEmpty' and the another containing processors that passed a value of 'true' for the parameter. Both the groups are sorted in the ascending order of their ranks in the old comm. More... | |
int | splitComm2way (const bool *isEmptyList, MPI_Comm *new_comm, MPI_Comm orig_comm) |
Splits a communication group into two depending on the values in isEmptyList. Both the groups are sorted in the ascending order of their ranks in the old comm. All processors must call this function with the same 'isEmptyList' array. More... | |
int | splitCommUsingSplittingRank (int splittingRank, MPI_Comm *new_comm, MPI_Comm orig_comm) |
unsigned int | splitCommBinary (MPI_Comm orig_comm, MPI_Comm *new_comm) |
Splits a communication group into two, the first having a power of 2 number of processors and the other having the remainder. The first group is sorted in the ascending order of their ranks in the old comm and the second group is sorted in the descending order of their ranks in the old comm. More... | |
unsigned int | splitCommBinaryNoFlip (MPI_Comm orig_comm, MPI_Comm *new_comm) |
Splits a communication group into two, the first having a power of 2 number of processors and the other having the remainder. Both the groups are sorted in the ascending order of their ranks in the old comm. More... | |
template<typename T > | |
void | MergeLists (std::vector< T > &listA, std::vector< T > &listB, int KEEP_WHAT) |
Merges lists A, and B, retaining either the low or the High in list A. More... | |
template<typename T > | |
void | MergeSplit (std::vector< T > &local_list, int which_keys, int partner, MPI_Comm comm) |
The main operation in the parallel bitonic sort algorithm. This implements the compare-split operation. More... | |
template<typename T > | |
void | Par_bitonic_sort_incr (std::vector< T > &local_list, int proc_set_size, MPI_Comm comm) |
template<typename T > | |
void | Par_bitonic_sort_decr (std::vector< T > &local_list, int proc_set_size, MPI_Comm comm) |
template<typename T > | |
void | Par_bitonic_merge_incr (std::vector< T > &local_list, int proc_set_size, MPI_Comm comm) |
template<typename T > | |
void | bitonicSort_binary (std::vector< T > &in, MPI_Comm comm) |
An implementation of parallel bitonic sort that expects the number of processors to be a power of 2. However, unlike most implementations, we do not expect the length of the vector (neither locally nor globally) to be a power of 2 or even. Moreover, each processor can call this with a different number of elements. However, we do expect that 'in' atleast has 1 element on each processor. More... | |
template<typename T > | |
void | bitonicSort (std::vector< T > &in, MPI_Comm comm) |
An implementation of parallel bitonic sort that does not expect the number of processors to be a power of 2. In fact, the number of processors can even be odd. Moreover, we do not even expect the length of the vector (neither locally nor globally) to be a power of 2 or even. Moreover, each processor can call this with a different number of elements. However, we do expect that 'in' atleast has 1 element on each processor. This recursively calls the function bitonicSort_binary, followed by a special parallel merge. More... | |
int | AdjustCommunicationPattern (std::vector< int > &send_sizes, std::vector< int > &send_partners, std::vector< int > &recv_sizes, std::vector< int > &recv_partners, MPI_Comm comm) |
Collection of Generic Parallel Functions: Sorting, Partitioning, Searching,...
int par::AdjustCommunicationPattern | ( | std::vector< int > & | send_sizes, |
std::vector< int > & | send_partners, | ||
std::vector< int > & | recv_sizes, | ||
std::vector< int > & | recv_partners, | ||
MPI_Comm | comm | ||
) |
Definition at line 279 of file parUtils.cpp.
void par::bitonicSort | ( | std::vector< T > & | in, |
MPI_Comm | comm | ||
) |
An implementation of parallel bitonic sort that does not expect the number of processors to be a power of 2. In fact, the number of processors can even be odd. Moreover, we do not even expect the length of the vector (neither locally nor globally) to be a power of 2 or even. Moreover, each processor can call this with a different number of elements. However, we do expect that 'in' atleast has 1 element on each processor. This recursively calls the function bitonicSort_binary, followed by a special parallel merge.
in | the vector to be sorted |
void par::bitonicSort_binary | ( | std::vector< T > & | in, |
MPI_Comm | comm | ||
) |
An implementation of parallel bitonic sort that expects the number of processors to be a power of 2. However, unlike most implementations, we do not expect the length of the vector (neither locally nor globally) to be a power of 2 or even. Moreover, each processor can call this with a different number of elements. However, we do expect that 'in' atleast has 1 element on each processor.
in | the vector to be sorted |
unsigned int par::defaultWeight | ( | const T * | a | ) |
std::vector<T> par::GetRangeMean | ( | std::vector< T > & | arr, |
std::vector< unsigned int > | range_min, | ||
std::vector< unsigned int > | range_max, | ||
MPI_Comm | comm | ||
) |
std::vector<T> par::GuessRangeMedian | ( | std::vector< T > & | arr, |
std::vector< unsigned int > | range_min, | ||
std::vector< unsigned int > | range_max, | ||
MPI_Comm | comm | ||
) |
int par::HyperQuickSort | ( | std::vector< T > & | in, |
std::vector< T > & | out, | ||
MPI_Comm | comm | ||
) |
A parallel hyper quick sort implementation.
in | the input vector |
out | the output vector |
comm | the communicator |
int par::HyperQuickSort | ( | std::vector< T > & | arr, |
MPI_Comm | comm | ||
) |
int par::HyperQuickSort_cav | ( | std::vector< T > & | in, |
std::vector< T > & | out, | ||
MPI_Comm | comm | ||
) |
int par::HyperQuickSort_cav | ( | std::vector< T > & | in, |
MPI_Comm | comm | ||
) |
int par::HyperQuickSort_kway | ( | std::vector< T > & | in, |
std::vector< T > & | out, | ||
MPI_Comm | comm | ||
) |
int par::HyperQuickSort_kway | ( | std::vector< T > & | in, |
MPI_Comm | comm | ||
) |
void par::MergeLists | ( | std::vector< T > & | listA, |
std::vector< T > & | listB, | ||
int | KEEP_WHAT | ||
) |
Merges lists A, and B, retaining either the low or the High in list A.
listA | Input list, and where the output is stored. |
listB | Second input list. |
KEEP_WHAT | determines whether to retain the High or the low values from A and B. One of KEEP_HIGH or KEEP_LOW. |
Merging the two lists when their sizes are not the same is a bit involved. The major condition that needs to be used is that all elements that are less than max(min(A), min(B)) are retained by the KEEP_LOW processor, and similarly all elements that are larger larger than min(max(A), max(B)) are retained by the KEEP_HIGH processor.
The reason for this is that, on the Keep_Low side,
max(min(A), min(B)) > min(A) > max(A-)
and similarly on the Keep_high side,
min(max(A), max(B)) < max(A) < min(A+)
which guarantees that the merged lists remain bitonic.
void par::MergeSplit | ( | std::vector< T > & | local_list, |
int | which_keys, | ||
int | partner, | ||
MPI_Comm | comm | ||
) |
The main operation in the parallel bitonic sort algorithm. This implements the compare-split operation.
which_keys | is one of KEEP_HIGH or KEEP_LOW |
partner | is the processor with which to Merge and Split. |
local_list | the input vector |
comm | the communicator |
int par::Mpi_Allgather | ( | T * | sendbuf, |
T * | recvbuf, | ||
int | count, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Allgatherv | ( | T * | sendbuf, |
int | sendcount, | ||
T * | recvbuf, | ||
int * | recvcounts, | ||
int * | displs, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Allreduce | ( | T * | sendbuf, |
T * | recvbuf, | ||
int | count, | ||
MPI_Op | op, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Alltoall | ( | T * | sendbuf, |
T * | recvbuf, | ||
int | count, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Alltoallv_dense | ( | T * | sendbuf, |
int * | sendcnts, | ||
int * | sdispls, | ||
T * | recvbuf, | ||
int * | recvcnts, | ||
int * | rdispls, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Alltoallv_sparse | ( | T * | sendbuf, |
int * | sendcnts, | ||
int * | sdispls, | ||
T * | recvbuf, | ||
int * | recvcnts, | ||
int * | rdispls, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Bcast | ( | T * | buffer, |
int | count, | ||
int | root, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Gather | ( | T * | sendBuffer, |
T * | recvBuffer, | ||
int | count, | ||
int | root, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Irecv | ( | T * | buf, |
int | count, | ||
int | source, | ||
int | tag, | ||
MPI_Comm | comm, | ||
MPI_Request * | request | ||
) |
int par::Mpi_Isend | ( | T * | buf, |
int | count, | ||
int | dest, | ||
int | tag, | ||
MPI_Comm | comm, | ||
MPI_Request * | request | ||
) |
int par::Mpi_Issend | ( | T * | buf, |
int | count, | ||
int | dest, | ||
int | tag, | ||
MPI_Comm | comm, | ||
MPI_Request * | request | ||
) |
int par::Mpi_Recv | ( | T * | buf, |
int | count, | ||
int | source, | ||
int | tag, | ||
MPI_Comm | comm, | ||
MPI_Status * | status | ||
) |
int par::Mpi_Reduce | ( | T * | sendbuf, |
T * | recvbuf, | ||
int | count, | ||
MPI_Op | op, | ||
int | root, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Scan | ( | T * | sendbuf, |
T * | recvbuf, | ||
int | count, | ||
MPI_Op | op, | ||
MPI_Comm | comm | ||
) |
int par::Mpi_Sendrecv | ( | T * | sendBuf, |
int | sendCount, | ||
int | dest, | ||
int | sendTag, | ||
S * | recvBuf, | ||
int | recvCount, | ||
int | source, | ||
int | recvTag, | ||
MPI_Comm | comm, | ||
MPI_Status * | status | ||
) |
void par::Par_bitonic_merge_incr | ( | std::vector< T > & | local_list, |
int | proc_set_size, | ||
MPI_Comm | comm | ||
) |
void par::Par_bitonic_sort_decr | ( | std::vector< T > & | local_list, |
int | proc_set_size, | ||
MPI_Comm | comm | ||
) |
void par::Par_bitonic_sort_incr | ( | std::vector< T > & | local_list, |
int | proc_set_size, | ||
MPI_Comm | comm | ||
) |
int par::partitionW | ( | std::vector< T > & | vec, |
unsigned int(*)(const T *) | getWeight, | ||
MPI_Comm | comm | ||
) |
A parallel weighted partitioning function. In our implementation, we do not pose any restriction on the input or the number of processors. This function can be used with an odd number of processors as well. Some processors can pass an empty vector as input. The relative ordering of the elements is preserved.
vec | the input vector |
getWeight | function pointer to compute the weight of each element. If you pass NULL, then every element will get a weight equal to 1. |
comm | the communicator |
void par::rankSamples | ( | std::vector< T > & | arr, |
std::vector< T > | samples, | ||
MPI_Comm | comm | ||
) |
int par::sampleSort | ( | std::vector< T > & | in, |
std::vector< T > & | out, | ||
MPI_Comm | comm | ||
) |
A parallel sample sort implementation. In our implementation, we do not pose any restriction on the input or the number of processors. This function can be used with an odd number of processors as well. Some processors can pass an empty vector as input. If the total number of elements in the vector (globally) is fewer than 10*p^2, where p is the number of processors, then we will use bitonic sort instead of sample sort to sort the vector. We use a paralle bitonic sort to sort the samples in the sample sort algorithm. Hence, the complexity of the algorithm is O(n/p log n/p) + O(p log p). Here, n is the global length of the vector and p is the number of processors.
in | the input vector |
out | the output vector |
comm | the communicator |
int par::sampleSort | ( | std::vector< T > & | in, |
MPI_Comm | comm | ||
) |
std::vector<T> par::Sorted_approx_Select | ( | std::vector< T > & | arr, |
unsigned int | k, | ||
MPI_Comm | comm | ||
) |
std::vector<std::pair<T, DendroIntL> > par::Sorted_approx_Select_skewed | ( | std::vector< T > & | arr, |
unsigned int | k, | ||
MPI_Comm | comm | ||
) |
new one to handle skewed distributions ...
std::vector<T> par::Sorted_k_Select | ( | std::vector< T > & | arr, |
std::vector< unsigned int > | min_idx, | ||
std::vector< unsigned int > | max_idx, | ||
std::vector< DendroIntL > | K, | ||
std::vector< T > | guess, | ||
MPI_Comm | comm | ||
) |
A parallel k-selection algorithms.
arr | arr from which samples are to be selected |
k | number of samples |
isSorted | if false, arr is locally sorted first. |
std::vector<T> par::Sorted_Sample_Select | ( | std::vector< T > & | arr, |
unsigned int | kway, | ||
std::vector< unsigned int > & | min_idx, | ||
std::vector< unsigned int > & | max_idx, | ||
std::vector< DendroIntL > & | splitter_ranks, | ||
MPI_Comm | comm | ||
) |
int par::splitComm2way | ( | bool | iAmEmpty, |
MPI_Comm * | new_comm, | ||
MPI_Comm | orig_comm | ||
) |
Splits a communication group into two, one containing processors that passed a value of 'false' for the parameter 'iAmEmpty' and the another containing processors that passed a value of 'true' for the parameter. Both the groups are sorted in the ascending order of their ranks in the old comm.
iAmEmpty | Some flag to determine which group the calling processor will be combined into. |
orig_comm | The comm group that needs to be split. |
new_comm | The new comm group. |
Definition at line 120 of file parUtils.cpp.
int par::splitComm2way | ( | const bool * | isEmptyList, |
MPI_Comm * | new_comm, | ||
MPI_Comm | orig_comm | ||
) |
Splits a communication group into two depending on the values in isEmptyList. Both the groups are sorted in the ascending order of their ranks in the old comm. All processors must call this function with the same 'isEmptyList' array.
isEmptyList | flags (of length equal to the number of processors) to determine whether each processor is active or not. |
orig_comm | The comm group that needs to be split. |
new_comm | The new comm group. |
Definition at line 225 of file parUtils.cpp.
unsigned int par::splitCommBinary | ( | MPI_Comm | orig_comm, |
MPI_Comm * | new_comm | ||
) |
Splits a communication group into two, the first having a power of 2 number of processors and the other having the remainder. The first group is sorted in the ascending order of their ranks in the old comm and the second group is sorted in the descending order of their ranks in the old comm.
orig_comm | The comm group that needs to be split. |
new_comm | The new comm group. |
Definition at line 21 of file parUtils.cpp.
unsigned int par::splitCommBinaryNoFlip | ( | MPI_Comm | orig_comm, |
MPI_Comm * | new_comm | ||
) |
Splits a communication group into two, the first having a power of 2 number of processors and the other having the remainder. Both the groups are sorted in the ascending order of their ranks in the old comm.
orig_comm | The comm group that needs to be split. |
new_comm | The new comm group. |
Definition at line 70 of file parUtils.cpp.
int par::splitCommUsingSplittingRank | ( | int | splittingRank, |
MPI_Comm * | new_comm, | ||
MPI_Comm | orig_comm | ||
) |
Definition at line 180 of file parUtils.cpp.