seams-core v2.14.0
libyodaLib, the C++ engine of d-SEAMS
Loading...
Searching...
No Matches
par_team.hpp
Go to the documentation of this file.
1#ifndef SEAMS_PAR_TEAM_H_
2#define SEAMS_PAR_TEAM_H_
3
4#include <algorithm>
5#include <iterator>
6#include <utility>
7#include <vector>
8
9#ifdef SEAMS_HAS_OPENMP
10#include <omp.h>
11#endif
12
13namespace seams {
14
15inline int teamThreads() {
16#ifdef SEAMS_HAS_OPENMP
17 if (omp_in_parallel()) {
18 return 1;
19 }
20 const int n = omp_get_max_threads();
21 return n > 0 ? n : 1;
22#else
23 return 1;
24#endif
25}
26
27// In-place exclusive prefix: values[i] becomes the sum of the earlier entries.
28template <class T> void exclusiveScan(std::vector<T> &values) {
29 const int n = static_cast<int>(values.size());
30 const int threads = teamThreads();
31 if (threads <= 1 || n < threads * 2) {
32 T sum = 0;
33 for (int i = 0; i < n; i++) {
34 const T current = values[static_cast<std::size_t>(i)];
35 values[static_cast<std::size_t>(i)] = sum;
36 sum += current;
37 }
38 return;
39 }
40 const int chunk = (n + threads - 1) / threads;
41 std::vector<T> block(static_cast<std::size_t>(threads), 0);
42#ifdef SEAMS_HAS_OPENMP
43#pragma omp parallel
44#endif
45 {
46#ifdef SEAMS_HAS_OPENMP
47 const int tid = omp_get_thread_num();
48#else
49 const int tid = 0;
50#endif
51 const int lo = tid * chunk;
52 const int hi = std::min(n, lo + chunk);
53 T sum = 0;
54 for (int i = lo; i < hi; i++) {
55 sum += values[static_cast<std::size_t>(i)];
56 }
57 if (tid < threads) {
58 block[static_cast<std::size_t>(tid)] = sum;
59 }
60 }
61 T carried = 0;
62 for (int tid = 0; tid < threads; tid++) {
63 const T sum = block[static_cast<std::size_t>(tid)];
64 block[static_cast<std::size_t>(tid)] = carried;
65 carried += sum;
66 }
67#ifdef SEAMS_HAS_OPENMP
68#pragma omp parallel
69#endif
70 {
71#ifdef SEAMS_HAS_OPENMP
72 const int tid = omp_get_thread_num();
73#else
74 const int tid = 0;
75#endif
76 const int lo = tid * chunk;
77 const int hi = std::min(n, lo + chunk);
78 T sum = block[static_cast<std::size_t>(tid)];
79 for (int i = lo; i < hi; i++) {
80 const T current = values[static_cast<std::size_t>(i)];
81 values[static_cast<std::size_t>(i)] = sum;
82 sum += current;
83 }
84 }
85}
86
87// Stable merge sort. Ties keep the earlier element, so the order matches
88// one serial stable sort at every thread count.
89template <class T, class Less>
90void parallelStableSort(std::vector<T> &values, Less less) {
91 const int n = static_cast<int>(values.size());
92 const int threads = teamThreads();
93 if (threads <= 1 || n < threads * 2) {
94 std::stable_sort(values.begin(), values.end(), less);
95 return;
96 }
97 const int chunk = (n + threads - 1) / threads;
98#ifdef SEAMS_HAS_OPENMP
99#pragma omp parallel for schedule(static)
100#endif
101 for (int tid = 0; tid < threads; tid++) {
102 const int lo = tid * chunk;
103 const int hi = std::min(n, lo + chunk);
104 if (hi - lo > 1) {
105 std::stable_sort(values.begin() + lo, values.begin() + hi, less);
106 }
107 }
108 std::vector<T> buffer(values.size());
109 T *src = values.data();
110 T *dst = buffer.data();
111 for (int width = chunk; width < n; width *= 2) {
112#ifdef SEAMS_HAS_OPENMP
113#pragma omp parallel for schedule(static)
114#endif
115 for (int start = 0; start < n; start += width * 2) {
116 const int mid = std::min(n, start + width);
117 const int stop = std::min(n, start + width * 2);
118 int i = start;
119 int j = mid;
120 int k = start;
121 while (i < mid && j < stop) {
122 if (less(src[j], src[i])) {
123 dst[k++] = src[j++];
124 } else {
125 dst[k++] = src[i++];
126 }
127 }
128 while (i < mid) {
129 dst[k++] = src[i++];
130 }
131 while (j < stop) {
132 dst[k++] = src[j++];
133 }
134 }
135 std::swap(src, dst);
136 }
137 if (src != values.data()) {
138 std::copy(src, src + n, values.begin());
139 }
140}
141
142} // namespace seams
143
144#endif
int teamThreads()
Definition par_team.hpp:15
void exclusiveScan(std::vector< T > &values)
Definition par_team.hpp:28
void parallelStableSort(std::vector< T > &values, Less less)
Definition par_team.hpp:90