d-SEAMS
Install
Output
Methods
Docs
Engine & CLI
Python
Rust
Julia
R
Lua / Fennel
Fortran
PLUMED
linkcell
Wiki
Cite
GitHub
seams-core
v2.14.0
libyodaLib, the C++ engine of d-SEAMS
Toggle main menu visibility
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
13
namespace
seams
{
14
15
inline
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.
28
template
<
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.
89
template
<
class
T,
class
Less>
90
void
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
seams
Definition
cpu_features.hpp:30
seams::teamThreads
int teamThreads()
Definition
par_team.hpp:15
seams::exclusiveScan
void exclusiveScan(std::vector< T > &values)
Definition
par_team.hpp:28
seams::parallelStableSort
void parallelStableSort(std::vector< T > &values, Less less)
Definition
par_team.hpp:90
src
include
internal
par_team.hpp