FLAMES 0.1.0
Matrix-Empowered HLS Library
Loading...
Searching...
No Matches
sort.hpp
Go to the documentation of this file.
1
12#ifndef _FLAMES_SORT_HPP_
13#define _FLAMES_SORT_HPP_
14
15#ifndef _FLAMES_CORE_HPP_
16# include "core.hpp"
17#endif
18
19namespace flames {
20
21template <typename V>
22static void mergeSort(V& vec) {
23 constexpr size_t size = V::size();
24 typename V::value_type temp[size];
25MERGE_SORT_STAGE:
26 for (int width = 1; width < size; width *= 2) {
27 int f1 = 0;
28 int f2 = width;
29 int i2 = width;
30 int i3 = 2 * width;
31 if (i2 >= size) i2 = size;
32 if (i3 >= size) i3 = size;
33 MERGE_ARRAYS:
34 for (int i = 0; i < size; ++i) {
35 FLAMES_PRAGMA(PIPELINE II = 1)
36 typename V::value_type t1 = vec[f1];
37 typename V::value_type t2 = (f2 == i3) ? static_cast<typename V::value_type>(0) : vec[f2];
38 if (f2 == i3 || (f1 < i2 && t1 <= t2)) {
39 temp[i] = t1;
40 ++f1;
41 } else {
42 assert(f2 < i3);
43 temp[i] = t2;
44 ++f2;
45 }
46 if (f1 == i2 && f2 == i3) {
47 f1 = i3;
48 i2 += 2 * width;
49 i3 += 2 * width;
50 if (i2 >= size) i2 = size;
51 if (i3 >= size) i3 = size;
52 f2 = i2;
53 }
54 }
55 MERGE_SORT_COPY:
56 for (int i = 0; i < size; ++i) {
57 FLAMES_PRAGMA(UNROLL factor = FLAMES_MAT_COPY_UNROLL_FACTOR)
58 vec[i] = temp[i];
59 }
60 }
61}
62
63template <typename V1, typename V2>
64static void mergeSort(const V1& in, V2& out) {
65 constexpr size_t size = V1::size();
66 static_assert(size == V2::size(), "Sort in and out vectors/matrices should be of same size.");
67 typename V1::value_type temp[size];
68MERGE_SORT_STAGE:
69 for (int width = 1; width < size; width *= 2) {
70 int f1 = 0;
71 int f2 = width;
72 int i2 = width;
73 int i3 = 2 * width;
74 if (i2 >= size) i2 = size;
75 if (i3 >= size) i3 = size;
76 MERGE_ARRAYS:
77 for (int i = 0; i < size; ++i) {
78 FLAMES_PRAGMA(PIPELINE II = 1)
79 typename V1::value_type t1 = in[f1];
80 // TODO: here minimum is zero
81 typename V1::value_type t2 = (f2 == i3) ? static_cast<typename V1::value_type>(0) : in[f2];
82 if (f2 == i3 || (f1 < i2 && t1 <= t2)) {
83 out[i] = t1;
84 ++f1;
85 } else {
86 assert(f2 < i3);
87 out[i] = t2;
88 ++f2;
89 }
90 if (f1 == i2 && f2 == i3) {
91 f1 = i3;
92 i2 += 2 * width;
93 i3 += 2 * width;
94 if (i2 >= size) i2 = size;
95 if (i3 >= size) i3 = size;
96 f2 = i2;
97 }
98 }
99 }
100}
101
102template <typename V>
103static inline void sort(V& vec) {
104 return mergeSort(vec);
105}
106
107template <typename V1, typename V2>
108static inline void sort(const V1& in, V2& out) {
109 return mergeSort(in, out);
110}
111
112template <typename T, typename I>
113static inline void argmax_4_2(T in1, T in2, T in3, T in4, I i_in1, I i_in2, I i_in3, I i_in4, T& out1, T& out2,
114 I& i_out1, I& i_out2, bool sorted = false) {
115 FLAMES_PRAGMA(INLINE)
116 if (sorted) {
117 assert(in1 >= in2 && in3 >= in4 && "Should be sorted in flames::argmax_4_2 with sorted=true.");
118 if (in1 < in4) { // 3, 4
119 out1 = in3;
120 out2 = in4;
121 i_out1 = i_in3;
122 i_out2 = i_in4;
123 } else if (in3 < in2) { // 1, 2
124 out1 = in1;
125 out2 = in2;
126 i_out1 = i_in1;
127 i_out2 = i_in2;
128 } else if (in1 < in3) { // 3, 1
129 out1 = in3;
130 out2 = in1;
131 i_out1 = i_in3;
132 i_out2 = i_in1;
133 } else { // 1, 3
134 out1 = in1;
135 out2 = in3;
136 i_out1 = i_in1;
137 i_out2 = i_in3;
138 }
139 } else {
140 T _in1, _in2, _in3, _in4;
141 I _i_in1, _i_in2, _i_in3, _i_in4;
142 // pre sort 1 and 2
143 if (in1 > in2) {
144 _in1 = in1;
145 _in2 = in2;
146 _i_in1 = i_in1;
147 _i_in2 = i_in2;
148 } else {
149 _in1 = in2;
150 _in2 = in1;
151 _i_in1 = i_in2;
152 _i_in2 = i_in1;
153 }
154 if (in3 > in4) {
155 _in3 = in3;
156 _in4 = in4;
157 _i_in3 = i_in3;
158 _i_in4 = i_in4;
159 } else {
160 _in3 = in4;
161 _in4 = in3;
162 _i_in3 = i_in4;
163 _i_in4 = i_in3;
164 }
165 // now same as sorted=true
166 if (_in1 < _in4) { // 3, 4
167 out1 = _in3;
168 out2 = _in4;
169 i_out1 = _i_in3;
170 i_out2 = _i_in4;
171 } else if (_in3 < _in2) { // 1, 2
172 out1 = _in1;
173 out2 = _in2;
174 i_out1 = _i_in1;
175 i_out2 = _i_in2;
176 } else if (_in1 < _in3) { // 3, 1
177 out1 = _in3;
178 out2 = _in1;
179 i_out1 = _i_in3;
180 i_out2 = _i_in1;
181 } else { // 1, 3
182 out1 = _in1;
183 out2 = _in3;
184 i_out1 = _i_in1;
185 i_out2 = _i_in3;
186 }
187 }
188}
189
190} // namespace flames
191
192#endif
flames::Mat
Matrix.
Definition core.hpp:575
flames::Mat::size
static constexpr size_t size() noexcept
Get the matrix size of storage.
Definition core.hpp:842
flames::Mat::value_type
T value_type
Definition core.hpp:603
core.hpp
Core Utilities for FLAMES.
FLAMES_PRAGMA
#define FLAMES_PRAGMA(x)
Definition core.hpp:50
FLAMES_MAT_COPY_UNROLL_FACTOR
#define FLAMES_MAT_COPY_UNROLL_FACTOR
Definition core.hpp:85
flames
Namespace for the FLAMES library.
Definition core.hpp:166
flames::mergeSort
static void mergeSort(V &vec)
Definition sort.hpp:22
flames::sort
static void sort(V &vec)
Definition sort.hpp:103
flames::argmax_4_2
static void argmax_4_2(T in1, T in2, T in3, T in4, I i_in1, I i_in2, I i_in3, I i_in4, T &out1, T &out2, I &i_out1, I &i_out2, bool sorted=false)
Definition sort.hpp:113