Debian Codegraph @

src/atlas/parallel/omp/sort.h

raw
1 /*
2 * (C) Copyright 2013 ECMWF.
3 *
4 * This software is licensed under the terms of the Apache Licence Version 2.0
5 * which can be obtained at http://www.apache.org/licenses/LICENSE-2.0.
6 * In applying this licence, ECMWF does not waive the privileges and immunities
7 * granted to it by virtue of its status as an intergovernmental organisation
8 * nor does it submit to any jurisdiction.
9 */
10
11 #pragma once
12
13 #include <algorithm>
14 #include <functional>
15 #include <iterator>
16
17 #include "atlas/library/config.h"
18 #include "atlas/parallel/omp/omp.h"
19
20 #if ATLAS_HAVE_OMP && ATLAS_OMP_TASK_SUPPORTED
21 #include <omp.h>
22 #define ATLAS_HAVE_OMP_SORTING 1
23 #else
24 #define ATLAS_HAVE_OMP_SORTING 0
25 #endif
26
27 // Bug in Cray 8.5 or below results in segmentation fault in atlas_test_omp_sort
28 #if ATLAS_HAVE_OMP_SORTING && defined(_CRAYC)
29 #if _RELEASE <= 8 && _RELEASE_MINOR < 6
30 #undef ATLAS_HAVE_OMP_SORTING
31 #define ATLAS_HAVE_OMP_SORTING 0
32 #endif
33 #endif
34
35 namespace atlas {
36 namespace omp {
37
38 /**
39 * sort
40 * ====
41 *
42 * 1) template <typename RandomAccessIterator>
43 * void sort ( RandomAccessIterator first, RandomAccessIterator last );
44 *
45 * 2) template <typename RandomAccessIterator, typename Compare>
46 * void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
47 *
48 * Sort elements in range
49 * Sorts the elements in the range [first,last) into ascending order.
50 *
51 * The elements are compared using operator< for the first version, and comp for the second.
52 *
53 * Equivalent elements are not guaranteed to keep their original relative order (see stable_sort).
54 *
55 * Parameters
56 * ----------
57 * first, last
58 * Random-access iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last),
59 * which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
60 * RandomAccessIterator shall point to a type for which swap is properly defined and which is both move-constructible and move-assignable.
61 * comp
62 * Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool.
63 * The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
64 * The function shall not modify any of its arguments.
65 * This can either be a function pointer or a function object.
66 *
67 *
68 *
69 * merge_blocks
70 * ============
71 *
72 * 1) template<typename RandomAccessIterator, typename RandomAccessIterator2>
73 * void merge_blocks( RandomAccessIterator first, RandomAccessIterator last,
74 * RandomAccessIterator2 blocks_size_first, RandomAccessIterator2 blocks_size_last );
75 *
76 *
77 * 1) template<typename RandomAccessIterator, typename RandomAccessIterator2, typename Compare >
78 * void merge_blocks( RandomAccessIterator first, RandomAccessIterator last,
79 * RandomAccessIterator2 blocks_size_first, RandomAccessIterator2 blocks_size_last,
80 * Compare compare );
81 *
82 * Sort elements in range [first + *blocks_first, first + *blocks_last) using a merge sort
83 * where each block in range [blocks_first,blocks_last) is already sorted.
84 *
85 * Parameters
86 * ----------
87 * first, last
88 * Random-access iterators for bounding the sequence to be sorted
89 * blocks_begin, blocks_end
90 * Random-access iterators that define offsets from paramter "first" of blocks that are already sorted
91 */
92
93
94 namespace detail {
95
96 #if ATLAS_HAVE_OMP_SORTING
97 template <typename RandomAccessIterator, typename Compare>
98 void merge_sort_recursive(const RandomAccessIterator& iterator, size_t begin, size_t end, Compare compare) {
99 auto size = end - begin;
100 if (size >= 256) {
101 auto mid = begin + size / 2;
102 //#pragma omp taskgroup
103 // --> it would be preferred to use taskgroup and taskyield instead of taskwait,
104 // but this leads to segfaults on Cray (cce/8.5.8)
105 {
106 #if ATLAS_OMP_TASK_UNTIED_SUPPORTED
107 #pragma omp task shared(iterator) untied if (size >= (1 << 15))
108 #else
109 #pragma omp task shared(iterator)
110 #endif
111 merge_sort_recursive(iterator, begin, mid, compare);
112 #if ATLAS_OMP_TASK_UNTIED_SUPPORTED
113 #pragma omp task shared(iterator) untied if (size >= (1 << 15))
114 #else
115 #pragma omp task shared(iterator)
116 #endif
117 merge_sort_recursive(iterator, mid, end, compare);
118 //#pragma omp taskyield
119 #pragma omp taskwait
120 }
121 std::inplace_merge(iterator + begin, iterator + mid, iterator + end, compare);
122 }
123 else {
124 std::sort(iterator + begin, iterator + end, compare);
125 }
126 }
127 #endif
128
129 #if ATLAS_HAVE_OMP_SORTING
130 template <typename RandomAccessIterator, typename Indexable, typename Compare>
131 void merge_blocks_recursive(const RandomAccessIterator& iterator, const Indexable& blocks, size_t blocks_begin,
132 size_t blocks_end, Compare compare) {
133 if (blocks_end <= blocks_begin + 1) {
134 // recursion done, go back out
135 return;
136 }
137 size_t blocks_mid = (blocks_begin + blocks_end) / 2;
138 //#pragma omp taskgroup
139 // --> it would be preferred to use taskgroup and taskyield instead of taskwait,
140 // but this leads to segfaults on Cray (cce/8.5.8)
141 {
142 #pragma omp task shared(iterator, blocks)
143 merge_blocks_recursive(iterator, blocks, blocks_begin, blocks_mid, compare);
144 #pragma omp task shared(iterator, blocks)
145 merge_blocks_recursive(iterator, blocks, blocks_mid, blocks_end, compare);
146 //#pragma omp taskyield
147 #pragma omp taskwait
148 }
149 auto begin = iterator + blocks[blocks_begin];
150 auto mid = iterator + blocks[blocks_mid];
151 auto end = iterator + blocks[blocks_end];
152 std::inplace_merge(begin, mid, end, compare);
153 }
154 #endif
155
156 template <typename RandomAccessIterator, typename Indexable, typename Compare>
157 void merge_blocks_recursive_seq(RandomAccessIterator& iterator, const Indexable& blocks, size_t blocks_begin,
158 size_t blocks_end, Compare compare) {
159 if (blocks_end <= blocks_begin + 1) {
160 // recursion done, go back out
161 return;
162 }
163 size_t blocks_mid = (blocks_begin + blocks_end) / 2;
164 {
165 merge_blocks_recursive_seq(iterator, blocks, blocks_begin, blocks_mid, compare);
166 merge_blocks_recursive_seq(iterator, blocks, blocks_mid, blocks_end, compare);
167 }
168 auto begin = iterator + blocks[blocks_begin];
169 auto mid = iterator + blocks[blocks_mid];
170 auto end = iterator + blocks[blocks_end];
171
172 std::inplace_merge(begin, mid, end, compare);
173 }
174
175 } // namespace detail
176
177 template <typename RandomAccessIterator, typename Compare>
178 void sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare) {
179 #if ATLAS_HAVE_OMP_SORTING
180 if (atlas_omp_get_max_threads() > 1) {
181 #pragma omp parallel
182 #pragma omp single
183 detail::merge_sort_recursive(first, 0, std::distance(first, last), compare);
184 }
185 else {
186 std::sort(first, last, compare);
187 }
188 #else
189 std::sort(first, last, compare);
190 #endif
191 }
192
193 template <typename RandomAccessIterator>
194 void sort(RandomAccessIterator first, RandomAccessIterator last) {
195 using value_type = typename std::iterator_traits<RandomAccessIterator>::value_type;
196 ::atlas::omp::sort(first, last, std::less<value_type>());
197 }
198
199 template <typename RandomAccessIterator, typename RandomAccessIterator2, typename Compare>
200 void merge_blocks(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator2 blocks_size_first,
201 RandomAccessIterator2 blocks_size_last, Compare compare) {
202 using size_type = typename std::iterator_traits<RandomAccessIterator2>::value_type;
203 size_type nb_blocks = std::distance(blocks_size_first, blocks_size_last);
204 std::vector<size_type> blocks_displs(nb_blocks + 1);
205 blocks_displs[0] = 0;
206 for (size_t i = 1; i < blocks_displs.size(); ++i) {
207 blocks_displs[i] = blocks_displs[i - 1] + blocks_size_first[i - 1];
208 }
209 #if ATLAS_HAVE_OMP_SORTING
210 if (atlas_omp_get_max_threads() > 1) {
211 #pragma omp parallel
212 #pragma omp single
213 detail::merge_blocks_recursive(first, blocks_displs, 0, nb_blocks, compare);
214 }
215 else {
216 detail::merge_blocks_recursive_seq(first, blocks_displs, 0, nb_blocks, compare);
217 }
218 #else
219 detail::merge_blocks_recursive_seq(first, blocks_displs, 0, nb_blocks, compare);
220 #endif
221 }
222
223 template <typename RandomAccessIterator, typename RandomAccessIterator2>
224 void merge_blocks(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator2 blocks_size_first,
225 RandomAccessIterator2 blocks_size_last) {
226 using value_type = typename std::iterator_traits<RandomAccessIterator>::value_type;
227 ::atlas::omp::merge_blocks(first, last, blocks_size_first, blocks_size_last, std::less<value_type>());
228 }
229
230 } // namespace omp
231 } // namespace atlas
232
233 #undef ATLAS_OMP_TASK_UNTIED_SUPPORTED
234 #undef ATLAS_HAVE_OMP_SORTING