COMBINATORIAL_BLAS 1.6
 
Loading...
Searching...
No Matches
psort_util.h
Go to the documentation of this file.
1/*
2Copyright (c) 2009, David Cheng, Viral B. Shah.
3
4Permission is hereby granted, free of charge, to any person obtaining a copy
5of this software and associated documentation files (the "Software"), to deal
6in the Software without restriction, including without limitation the rights
7to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8copies of the Software, and to permit persons to whom the Software is
9furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20THE SOFTWARE.
21*/
22
23#ifndef PSORT_UTIL_H
24#define PSORT_UTIL_H
25
26#include <mpi.h>
27#include <cassert>
28#include <stdexcept>
29#include <limits>
30#include <cstdlib>
31#include <iostream>
32#include <iomanip>
33#include <fstream>
34#include <string>
35#include <functional>
36#include <iterator>
37#include <numeric>
38#include <algorithm>
39#include <vector>
40
41#ifdef PSORTDEBUG
42#define PSORT_DEBUG(_a) _a
43#else
44#define PSORT_DEBUG(_a)
45#endif
46
47#include "psort_seqsort.h"
48#include "psort_splitters.h"
49#include "psort_alltoall.h"
50#include "psort_merge.h"
51
52namespace vpsort {
53 using namespace std;
54
55 static double psort_timing[10];
56
57 template <typename _RandomAccessIter, typename _Compare>
58 bool is_sorted (_RandomAccessIter first,
59 _RandomAccessIter last,
60 _Compare comp,
61 MPI_Comm comm) {
62
63 int nproc, rank;
64 MPI_Comm_size (comm, &nproc);
65 MPI_Comm_rank (comm, &rank);
66
67 int not_sorted = 0;
68
69 typedef typename iterator_traits<_RandomAccessIter>::pointer _IterType;
70 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
71
72 for (_IterType iter=first+1; iter<last; ++iter) {
73 if (comp(*(iter), *(iter-1)) == true) {
74 not_sorted = 1;
75 break;
76 }
77 }
78
79 _ValueType *left_boundary = new _ValueType[nproc];
80 _ValueType *right_boundary = new _ValueType[nproc];
81
82 _ValueType left = *first;
83 MPI_Allgather (&left, sizeof (_ValueType), MPI_CHAR,
84 left_boundary, sizeof (_ValueType), MPI_CHAR,
85 comm);
86
87 _ValueType right = *(last-1);
88 MPI_Allgather (&right, sizeof (_ValueType), MPI_CHAR,
89 right_boundary, sizeof (_ValueType), MPI_CHAR,
90 comm);
91
92 for (int i=0; i<nproc-1; ++i) {
93 if (comp(left_boundary[i+1], right_boundary[i]) == true) {
94 not_sorted = 1;
95 break;
96 }
97 }
98
99 delete [] left_boundary;
100 delete [] right_boundary;
101
102 int result[nproc];
103 MPI_Allgather (&not_sorted, 1, MPI_INT,
104 result, 1, MPI_INT, comm);
105
106 int all_result = accumulate (result, result + nproc, 0);
107 if (all_result == 0)
108 return true;
109 else
110 return false;
111
112 }
113
114 template <typename _RandomAccessIter, typename _Compare>
115 bool is_sorted (_RandomAccessIter first,
116 _RandomAccessIter last,
117 MPI_Comm comm) {
118
119 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
120 return is_sorted (first, last, std::less<_ValueType>(), comm);
121 }
122
123
124 static inline void progress (int rank, int step, const char *s, MPI_Comm comm) {
125 MPI_Barrier (comm);
126 psort_timing[step] = MPI_Wtime ();
127 if (rank == 0) {
128 PSORT_DEBUG (cout << step << ". " << s << endl;);
129 }
130 }
131
132
133 template <typename _Distance>
134 void print_perf_data (_Distance *dist, MPI_Comm comm) {
135
136 STLSort stl_sort;
137 MedianSplit median_split;
138 OOPTreeMerge oop_tree_merge;
139
140 print_perf_data (dist, stl_sort, median_split, oop_tree_merge, comm);
141 }
142
143 template <typename _SeqSortType, typename _SplitType, typename _MergeType, typename _Distance>
144 void print_perf_data (_Distance *dist,
145 SeqSort<_SeqSortType> &mysort,
146 Split<_SplitType> &mysplit,
147 Merge<_MergeType> &mymerge,
148 MPI_Comm comm) {
149
150 int rank, nproc;
151 MPI_Comm_size (comm, &nproc);
152 MPI_Comm_rank (comm, &rank);
153
154 /*
155 AL: This is the original code. This is legal in C but not in C++ because
156 C++ string literals are const char* instead of just char*, so this code has constness
157 errors.
158
159 char **stage = new char*[5];
160 stage[1] = mysort.description();
161 stage[2] = mysplit.description();
162 stage[3] = "alltoall";
163 stage[4] = mymerge.description();
164 */
165 const char *stage[5] = {
166 "",
167 mysort.description(),
168 mysplit.description(),
169 "alltoall",
170 mymerge.description()
171 };
172
173 if (rank == 0) cout << endl;
174 double rtime[5];
175 for (int i=1; i<=4; ++i) {
176 double time_i = psort_timing[i] - psort_timing[i-1];
177 if (rank == 0) {
178 cout << i << ". "
179 << setw(30) << left << stage[i]
180 << setw(10) << right << ": "
181 << setprecision(6) << time_i << " sec" << endl;
182 rtime[i] = time_i;
183 }
184 }
185
186 long n_sort = 0L; for (int i=0; i<nproc; ++i) n_sort += dist[i];
187 double total_time = rtime[1] + rtime[2] + rtime[3] + rtime[4];
188 double mkeys_per_sec;
189 double mkeys_per_sec_proc;
190 if (rank == 0) {
191 mkeys_per_sec = ((n_sort * log2(n_sort)) / total_time) / 1e6;
192 mkeys_per_sec_proc = (((n_sort * log2(n_sort)) / total_time) / nproc) / 1e6;
193
194 cout << setprecision(6) << endl;
195 cout << setw(33) << left << "* MKeys/sec"
196 << setw(10) << right << ": " << mkeys_per_sec << endl;
197 cout << setw(33) << left << "* MKeys/sec/proc"
198 << setw(10) << right << ": " << mkeys_per_sec_proc << endl;
199 cout << endl;
200 }
201
202 if (rank == 0) {
203 ofstream results;
204 results.open ("./results", ios::app);
205
206 results << mysort.description() << ", "
207 << mysplit.description() << ", "
208 << mymerge.description() << ", "
209 << nproc << ", "
210 << n_sort << ", "
211 << rtime[1] << ", "
212 << rtime[2] << ", "
213 << rtime[3] << ", "
214 << rtime[4] << ", "
215 << total_time << ", "
216 << mkeys_per_sec << ", "
217 << mkeys_per_sec_proc
218 << endl;
219
220 results.close ();
221 }
222
223 }
224
225
226 template <typename _SeqSortType, typename _Distance>
227 void print_perf_data_samplesort (_Distance *dist,
228 SeqSort<_SeqSortType> &mysort,
229 MPI_Comm comm) {
230
231 int rank, nproc;
232 MPI_Comm_size (comm, &nproc);
233 MPI_Comm_rank (comm, &rank);
234
235 /*
236 AL: This is the original code. This is legal in C but not in C++ because
237 C++ string literals are const char* instead of just char*, so this code has constness
238 errors.
239
240 char **stage = new char*[6];
241 stage[1] = "sample splitters";
242 stage[2] = "partition";
243 stage[3] = "alltoall";
244 stage[4] = mysort.description();
245 stage[5] = "adjust boundaries";
246 */
247 const char* stage[6] = {
248 "",
249 "sample splitters",
250 "partition",
251 "alltoall",
252 mysort.description(),
253 "adjust boundaries"
254 };
255
256 if (rank == 0) cout << endl;
257 double rtime[6];
258 for (int i=1; i<=5; ++i) {
259 double time_i = psort_timing[i] - psort_timing[i-1];
260 if (rank == 0) {
261 cout << i << ". "
262 << setw(30) << left << stage[i]
263 << setw(10) << right << ": "
264 << setprecision(6) << time_i << " sec" << endl;
265 rtime[i] = time_i;
266 }
267 }
268
269 long n_sort = 0L; for (int i=0; i<nproc; ++i) n_sort += dist[i];
270 double total_time = rtime[1] + rtime[2] + rtime[3] + rtime[4];
271 double mkeys_per_sec;
272 double mkeys_per_sec_proc;
273 if (rank == 0) {
274 mkeys_per_sec = ((n_sort * log2(n_sort)) / total_time) / 1e6;
275 mkeys_per_sec_proc = (((n_sort * log2(n_sort)) / total_time) / nproc) / 1e6;
276
277 cout << setprecision(6) << endl;
278 cout << setw(33) << left << "* MKeys/sec"
279 << setw(10) << right << ": " << mkeys_per_sec << endl;
280 cout << setw(33) << left << "* MKeys/sec/proc"
281 << setw(10) << right << ": " << mkeys_per_sec_proc << endl;
282 cout << endl;
283 }
284
285 if (rank == 0) {
286 ofstream results;
287 results.open ("./results", ios::app);
288
289 results << "sample sort" << ", "
290 << mysort.description() << ", "
291 << nproc << ", "
292 << n_sort << ", "
293 << rtime[1] << ", "
294 << rtime[2] << ", "
295 << rtime[3] << ", "
296 << rtime[4] << ", "
297 << rtime[5] << ", "
298 << total_time << ", "
299 << mkeys_per_sec << ", "
300 << mkeys_per_sec_proc
301 << endl;
302
303 results.close ();
304 }
305 }
306
307}
308
309
310#endif /* PSORT_UTIL_H */
rank
int rank
PSORT_DEBUG
#define PSORT_DEBUG(_a)
Definition psort_util.h:44
vpsort
Definition psort.h:28
vpsort::print_perf_data
void print_perf_data(_Distance *dist, MPI_Comm comm)
Definition psort_util.h:134
vpsort::is_sorted
bool is_sorted(_RandomAccessIter first, _RandomAccessIter last, _Compare comp, MPI_Comm comm)
Definition psort_util.h:58
vpsort::print_perf_data_samplesort
void print_perf_data_samplesort(_Distance *dist, SeqSort< _SeqSortType > &mysort, MPI_Comm comm)
Definition psort_util.h:227
psort_alltoall.h
psort_merge.h
psort_seqsort.h
psort_splitters.h