/
ArborX_DetailsSortUtils.hpp
139 lines (119 loc) · 4.95 KB
/
ArborX_DetailsSortUtils.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/****************************************************************************
* Copyright (c) 2017-2022 by the ArborX authors *
* All rights reserved. *
* *
* This file is part of the ArborX library. ArborX is *
* distributed under a BSD 3-clause license. For the licensing terms see *
* the LICENSE file in the top-level directory. *
* *
* SPDX-License-Identifier: BSD-3-Clause *
****************************************************************************/
#ifndef ARBORX_DETAILS_SORT_UTILS_HPP
#define ARBORX_DETAILS_SORT_UTILS_HPP
#include <ArborX_DetailsKokkosExtSort.hpp>
#include <ArborX_DetailsKokkosExtStdAlgorithms.hpp> // iota
#include <ArborX_DetailsKokkosExtViewHelpers.hpp> // clone
#include <ArborX_Exception.hpp>
#include <Kokkos_Core.hpp>
namespace ArborX::Details
{
// NOTE returns the permutation indices **and** sorts the input view
template <typename ExecutionSpace, typename ViewType,
class SizeType = unsigned int>
auto sortObjects(ExecutionSpace const &space, ViewType &view)
{
Kokkos::Profiling::pushRegion("ArborX::Sorting");
Kokkos::View<SizeType *, typename ViewType::device_type> permute(
Kokkos::view_alloc(space, Kokkos::WithoutInitializing,
"ArborX::Sorting::permute"),
view.extent(0));
KokkosExt::iota(space, permute);
KokkosExt::sortByKey(space, view, permute);
Kokkos::Profiling::popRegion();
return permute;
}
// Helper functions and structs for applyPermutations
namespace PermuteHelper
{
template <class DstViewType, class SrcViewType, int Rank = DstViewType::rank>
struct CopyOp;
template <class DstViewType, class SrcViewType>
struct CopyOp<DstViewType, SrcViewType, 1>
{
KOKKOS_INLINE_FUNCTION
static void copy(DstViewType const &dst, size_t i_dst, SrcViewType const &src,
size_t i_src)
{
dst(i_dst) = src(i_src);
}
};
template <class DstViewType, class SrcViewType>
struct CopyOp<DstViewType, SrcViewType, 2>
{
KOKKOS_INLINE_FUNCTION
static void copy(DstViewType const &dst, size_t i_dst, SrcViewType const &src,
size_t i_src)
{
for (unsigned int j = 0; j < dst.extent(1); j++)
dst(i_dst, j) = src(i_src, j);
}
};
template <class DstViewType, class SrcViewType>
struct CopyOp<DstViewType, SrcViewType, 3>
{
KOKKOS_INLINE_FUNCTION
static void copy(DstViewType const &dst, size_t i_dst, SrcViewType const &src,
size_t i_src)
{
for (unsigned int j = 0; j < dst.extent(1); j++)
for (unsigned int k = 0; k < dst.extent(2); k++)
dst(i_dst, j, k) = src(i_src, j, k);
}
};
} // namespace PermuteHelper
template <typename ExecutionSpace, typename PermutationView, typename InputView,
typename OutputView>
void applyInversePermutation(ExecutionSpace const &space,
PermutationView const &permutation,
InputView const &input_view,
OutputView const &output_view)
{
static_assert(std::is_integral<typename PermutationView::value_type>::value);
ARBORX_ASSERT(permutation.extent(0) == input_view.extent(0));
ARBORX_ASSERT(output_view.extent(0) == input_view.extent(0));
Kokkos::parallel_for(
"ArborX::Sorting::inverse_permute",
Kokkos::RangePolicy<ExecutionSpace>(space, 0, input_view.extent(0)),
KOKKOS_LAMBDA(int i) {
PermuteHelper::CopyOp<OutputView, InputView>::copy(
output_view, permutation(i), input_view, i);
});
}
template <typename ExecutionSpace, typename PermutationView, typename InputView,
typename OutputView>
void applyPermutation(ExecutionSpace const &space,
PermutationView const &permutation,
InputView const &input_view,
OutputView const &output_view)
{
static_assert(std::is_integral<typename PermutationView::value_type>::value);
ARBORX_ASSERT(permutation.extent(0) == input_view.extent(0));
ARBORX_ASSERT(output_view.extent(0) == input_view.extent(0));
Kokkos::parallel_for(
"ArborX::Sorting::permute",
Kokkos::RangePolicy<ExecutionSpace>(space, 0, input_view.extent(0)),
KOKKOS_LAMBDA(int i) {
PermuteHelper::CopyOp<OutputView, InputView>::copy(
output_view, i, input_view, permutation(i));
});
}
template <typename ExecutionSpace, typename PermutationView, typename View>
void applyPermutation(ExecutionSpace const &space,
PermutationView const &permutation, View &view)
{
static_assert(std::is_integral<typename PermutationView::value_type>::value);
auto scratch_view = KokkosExt::clone(space, view);
applyPermutation(space, permutation, scratch_view, view);
}
} // namespace ArborX::Details
#endif