COMBINATORIAL_BLAS  1.6
parUtils.h
Go to the documentation of this file.
1 
8 #ifndef __PAR_UTILS_H_
9 #define __PAR_UTILS_H_
10 
11 #define KEEP_HIGH 100
12 #define KEEP_LOW 101
13 
14 #ifdef __DEBUG__
15 #ifndef __DEBUG_PAR__
16 #define __DEBUG_PAR__
17 #endif
18 #endif
19 
20 #include "mpi.h"
21 #include <vector>
22 
23 #ifdef __USE_64_BIT_INT__
24 #define DendroIntL long long
25 #define DendroIntLSpecifier %lld
26 #define DendroUIntLSpecifier %llu
27 #else
28 #define DendroIntL int
29 #define DendroIntLSpecifier %d
30 #define DendroUIntLSpecifier %u
31 #endif
32 
38 namespace par {
39 
40  template <typename T>
41  int Mpi_Isend(T* buf, int count, int dest, int tag, MPI_Comm comm, MPI_Request* request);
42 
43  template <typename T>
44  int Mpi_Issend(T* buf, int count, int dest, int tag, MPI_Comm comm, MPI_Request* request);
45 
46  template <typename T>
47  int Mpi_Recv(T* buf, int count, int source, int tag, MPI_Comm comm, MPI_Status* status);
48 
49  template <typename T>
50  int Mpi_Irecv(T* buf, int count, int source, int tag, MPI_Comm comm, MPI_Request* request);
51 
52  template <typename T>
53  int Mpi_Gather( T* sendBuffer, T* recvBuffer, int count, int root, MPI_Comm comm);
54 
55  template <typename T, typename S>
56  int Mpi_Sendrecv( T* sendBuf, int sendCount, int dest, int sendTag,
57  S* recvBuf, int recvCount, int source, int recvTag,
58  MPI_Comm comm, MPI_Status* status);
59 
60  template <typename T>
61  int Mpi_Bcast( T* buffer, int count, int root, MPI_Comm comm);
62 
63  template <typename T>
64  int Mpi_Scan( T* sendbuf, T* recvbuf, int count, MPI_Op op, MPI_Comm comm);
65 
66  template <typename T>
67  int Mpi_Reduce( T* sendbuf, T* recvbuf, int count, MPI_Op op, int root, MPI_Comm comm);
68 
69  template <typename T>
70  int Mpi_Allreduce( T* sendbuf, T* recvbuf, int count, MPI_Op op, MPI_Comm comm);
71 
72  template <typename T>
73  int Mpi_Alltoall(T* sendbuf, T* recvbuf, int count, MPI_Comm comm);
74 
75  template <typename T>
76  int Mpi_Allgatherv(T* sendbuf, int sendcount, T* recvbuf,
77  int* recvcounts, int* displs, MPI_Comm comm);
78 
79  template <typename T>
80  int Mpi_Allgather(T* sendbuf, T* recvbuf, int count, MPI_Comm comm);
81 
82  template <typename T>
83  int Mpi_Alltoallv_sparse(T* sendbuf, int* sendcnts, int* sdispls,
84  T* recvbuf, int* recvcnts, int* rdispls, MPI_Comm comm);
85 
86  template <typename T>
87  int Mpi_Alltoallv_dense(T* sendbuf, int* sendcnts, int* sdispls,
88  T* recvbuf, int* recvcnts, int* rdispls, MPI_Comm comm);
89 
90 
91  template<typename T>
92  unsigned int defaultWeight(const T *a);
93 
105  template<typename T>
106  int partitionW(std::vector<T>& vec,
107  unsigned int (*getWeight)(const T *), MPI_Comm comm);
108 
109 
110  template<typename T>
111  void rankSamples(std::vector<T>& arr, std::vector<T> samples, MPI_Comm comm);
112 
113  template<typename T>
114  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);
115  template<typename T>
116  std::vector<T> Sorted_approx_Select(std::vector<T>& arr, unsigned int k, MPI_Comm comm);
118  template<typename T>
119  std::vector<std::pair<T, DendroIntL> > Sorted_approx_Select_skewed(std::vector<T>& arr, unsigned int k, MPI_Comm comm);
120 
121  template<typename T>
122  std::vector<T> GetRangeMean(std::vector<T>& arr, std::vector<unsigned int> range_min, std::vector<unsigned int> range_max, MPI_Comm comm);
123  template<typename T>
124  std::vector<T> GuessRangeMedian(std::vector<T>& arr, std::vector<unsigned int> range_min, std::vector<unsigned int> range_max, MPI_Comm comm);
125 
135  template<typename T>
136  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);
137 
145  template<typename T>
146  int HyperQuickSort(std::vector<T>& in, std::vector<T> & out, MPI_Comm comm);
147 
148  template<typename T>
149  int HyperQuickSort_kway(std::vector<T>& in, std::vector<T> & out, MPI_Comm comm);
150 
151  template<typename T>
152  int HyperQuickSort_cav(std::vector<T>& in, std::vector<T> & out, MPI_Comm comm);
153 
154  /* mem-efficient version */
155  template<typename T>
156  int HyperQuickSort(std::vector<T>& arr, MPI_Comm comm);
157 
158  template<typename T>
159  int HyperQuickSort_kway(std::vector<T>& in, MPI_Comm comm);
160 
161  template<typename T>
162  int HyperQuickSort_cav(std::vector<T>& in, MPI_Comm comm);
163 
176  template<typename T>
177  int sampleSort(std::vector<T>& in, std::vector<T> & out, MPI_Comm comm);
178 
179  template<typename T>
180  int sampleSort(std::vector<T>& in, MPI_Comm comm);
181 
191  int splitComm2way(bool iAmEmpty, MPI_Comm* new_comm, MPI_Comm orig_comm);
192 
202  int splitComm2way(const bool* isEmptyList, MPI_Comm* new_comm, MPI_Comm orig_comm);
203 
204  /*
205  @author Rahul Sampath
206  @brief Splits a communication group into two, processors with
207  ranks less than splittingRank form one group and the other
208  processors form the second group. Both the groups are sorted in
209  the ascending order of their ranks in the old comm.
210  @param splittingRank The rank used for splitting the communicator
211  @param orig_comm The comm group that needs to be split.
212  @param new_comm The new comm group.
213  */
214  int splitCommUsingSplittingRank(int splittingRank, MPI_Comm* new_comm, MPI_Comm orig_comm);
215 
225  unsigned int splitCommBinary( MPI_Comm orig_comm, MPI_Comm* new_comm);
226 
227 
236  unsigned int splitCommBinaryNoFlip( MPI_Comm orig_comm, MPI_Comm* new_comm);
237 
263  template <typename T>
264  void MergeLists( std::vector<T> &listA, std::vector<T> &listB, int KEEP_WHAT) ;
265 
274  template <typename T>
275  void MergeSplit( std::vector<T> &local_list, int which_keys, int partner, MPI_Comm comm);
276 
280  template <typename T>
281  void Par_bitonic_sort_incr( std::vector<T> &local_list, int proc_set_size, MPI_Comm comm );
282 
286  template <typename T>
287  void Par_bitonic_sort_decr( std::vector<T> &local_list, int proc_set_size, MPI_Comm comm);
288 
292  template <typename T>
293  void Par_bitonic_merge_incr( std::vector<T> &local_list, int proc_set_size, MPI_Comm comm );
294 
304  template <typename T>
305  void bitonicSort_binary(std::vector<T> & in, MPI_Comm comm) ;
306 
319  template <typename T>
320  void bitonicSort(std::vector<T> & in, MPI_Comm comm) ;
321 
322 }//end namespace
323 
324 #include "parUtils.tcc"
325 
326 #endif
327 
int Mpi_Irecv(T *buf, int count, int source, int tag, MPI_Comm comm, MPI_Request *request)
int HyperQuickSort(std::vector< T > &in, std::vector< T > &out, MPI_Comm comm)
A parallel hyper quick sort implementation.
int Mpi_Alltoallv_sparse(T *sendbuf, int *sendcnts, int *sdispls, T *recvbuf, int *recvcnts, int *rdispls, MPI_Comm comm)
int Mpi_Allgatherv(T *sendbuf, int sendcount, T *recvbuf, int *recvcounts, int *displs, MPI_Comm comm)
int Mpi_Reduce(T *sendbuf, T *recvbuf, int count, MPI_Op op, int root, MPI_Comm comm)
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.
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.
void rankSamples(std::vector< T > &arr, std::vector< T > samples, MPI_Comm comm)
void Par_bitonic_merge_incr(std::vector< T > &local_list, int proc_set_size, MPI_Comm comm)
int Mpi_Alltoall(T *sendbuf, T *recvbuf, int count, MPI_Comm comm)
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)
void Par_bitonic_sort_incr(std::vector< T > &local_list, int proc_set_size, MPI_Comm comm)
int Mpi_Bcast(T *buffer, int count, int root, MPI_Comm comm)
int Mpi_Allgather(T *sendbuf, T *recvbuf, int count, MPI_Comm comm)
int Mpi_Issend(T *buf, int count, int dest, int tag, MPI_Comm comm, MPI_Request *request)
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 ...
unsigned int defaultWeight(const T *a)
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 operatio...
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...
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 oth...
Definition: parUtils.cpp:21
std::vector< T > GuessRangeMedian(std::vector< T > &arr, std::vector< unsigned int > range_min, std::vector< unsigned int > range_max, MPI_Comm comm)
int Mpi_Recv(T *buf, int count, int source, int tag, MPI_Comm comm, MPI_Status *status)
int HyperQuickSort_cav(std::vector< T > &in, std::vector< T > &out, MPI_Comm comm)
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 t...
std::vector< T > GetRangeMean(std::vector< T > &arr, std::vector< unsigned int > range_min, std::vector< unsigned int > range_max, MPI_Comm comm)
int Mpi_Allreduce(T *sendbuf, T *recvbuf, int count, MPI_Op op, MPI_Comm comm)
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 powe...
Collection of Generic Parallel Functions: Sorting, Partitioning, Searching,...
Definition: dtypes.h:18
int splitCommUsingSplittingRank(int splittingRank, MPI_Comm *new_comm, MPI_Comm orig_comm)
Definition: parUtils.cpp:180
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)
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 oth...
Definition: parUtils.cpp:70
std::vector< T > Sorted_approx_Select(std::vector< T > &arr, unsigned int k, MPI_Comm comm)
int HyperQuickSort_kway(std::vector< T > &in, std::vector< T > &out, MPI_Comm comm)
int Mpi_Scan(T *sendbuf, T *recvbuf, int count, MPI_Op op, 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 &#39;false&#39; for t...
Definition: parUtils.cpp:120
void Par_bitonic_sort_decr(std::vector< T > &local_list, int proc_set_size, MPI_Comm comm)
int Mpi_Alltoallv_dense(T *sendbuf, int *sendcnts, int *sdispls, T *recvbuf, int *recvcnts, int *rdispls, MPI_Comm comm)
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 i...
int Mpi_Gather(T *sendBuffer, T *recvBuffer, int count, int root, MPI_Comm comm)
int Mpi_Isend(T *buf, int count, int dest, int tag, MPI_Comm comm, MPI_Request *request)