Kokkos Core Kernels Package Version of the Day
Loading...
Searching...
No Matches
Kokkos_Bitset.hpp
1//@HEADER
2// ************************************************************************
3//
4// Kokkos v. 4.0
5// Copyright (2022) National Technology & Engineering
6// Solutions of Sandia, LLC (NTESS).
7//
8// Under the terms of Contract DE-NA0003525 with NTESS,
9// the U.S. Government retains certain rights in this software.
10//
11// Part of Kokkos, under the Apache License v2.0 with LLVM Exceptions.
12// See https://kokkos.org/LICENSE for license information.
13// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
14//
15//@HEADER
16
17#ifndef KOKKOS_BITSET_HPP
18#define KOKKOS_BITSET_HPP
19#ifndef KOKKOS_IMPL_PUBLIC_INCLUDE
20#define KOKKOS_IMPL_PUBLIC_INCLUDE
21#define KOKKOS_IMPL_PUBLIC_INCLUDE_NOTDEFINED_BITSET
22#endif
23
24#include <Kokkos_Core.hpp>
25#include <Kokkos_Functional.hpp>
26
27#include <impl/Kokkos_Bitset_impl.hpp>
28
29namespace Kokkos {
30
31template <typename Device = Kokkos::DefaultExecutionSpace>
32class Bitset;
33
34template <typename Device = Kokkos::DefaultExecutionSpace>
35class ConstBitset;
36
37template <typename DstDevice, typename SrcDevice>
38void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice> const& src);
39
40template <typename DstDevice, typename SrcDevice>
41void deep_copy(Bitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src);
42
43template <typename DstDevice, typename SrcDevice>
44void deep_copy(ConstBitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src);
45
47template <typename Device>
48class Bitset {
49 public:
50 using execution_space = typename Device::execution_space;
51 using size_type = unsigned int;
52
53 static constexpr unsigned BIT_SCAN_REVERSE = 1u;
54 static constexpr unsigned MOVE_HINT_BACKWARD = 2u;
55
56 static constexpr unsigned BIT_SCAN_FORWARD_MOVE_HINT_FORWARD = 0u;
57 static constexpr unsigned BIT_SCAN_REVERSE_MOVE_HINT_FORWARD =
58 BIT_SCAN_REVERSE;
59 static constexpr unsigned BIT_SCAN_FORWARD_MOVE_HINT_BACKWARD =
60 MOVE_HINT_BACKWARD;
61 static constexpr unsigned BIT_SCAN_REVERSE_MOVE_HINT_BACKWARD =
62 BIT_SCAN_REVERSE | MOVE_HINT_BACKWARD;
63
64 private:
65 enum : unsigned {
66 block_size = static_cast<unsigned>(sizeof(unsigned) * CHAR_BIT)
67 };
68 enum : unsigned { block_mask = block_size - 1u };
69 enum : unsigned {
70 block_shift = Kokkos::Impl::integral_power_of_two(block_size)
71 };
72
73 public:
76 Bitset(unsigned arg_size = 0u)
77 : m_size(arg_size),
78 m_last_block_mask(0u),
79 m_blocks("Bitset", ((m_size + block_mask) >> block_shift)) {
80 for (int i = 0, end = static_cast<int>(m_size & block_mask); i < end; ++i) {
81 m_last_block_mask |= 1u << i;
82 }
83 }
84
85 KOKKOS_DEFAULTED_FUNCTION
86 Bitset(const Bitset<Device>&) = default;
87
88 KOKKOS_DEFAULTED_FUNCTION
89 Bitset& operator=(const Bitset<Device>&) = default;
90
91 KOKKOS_DEFAULTED_FUNCTION
92 Bitset(Bitset<Device>&&) = default;
93
94 KOKKOS_DEFAULTED_FUNCTION
95 Bitset& operator=(Bitset<Device>&&) = default;
96
97 KOKKOS_DEFAULTED_FUNCTION
98 ~Bitset() = default;
99
102 KOKKOS_FORCEINLINE_FUNCTION
103 unsigned size() const { return m_size; }
104
107 unsigned count() const {
108 Impl::BitsetCount<Bitset<Device> > f(*this);
109 return f.apply();
110 }
111
114 void set() {
115 Kokkos::deep_copy(m_blocks, ~0u);
116
117 if (m_last_block_mask) {
118 // clear the unused bits in the last block
119 Kokkos::Impl::DeepCopy<typename Device::memory_space, Kokkos::HostSpace>(
120 m_blocks.data() + (m_blocks.extent(0) - 1u), &m_last_block_mask,
121 sizeof(unsigned));
122 Kokkos::fence(
123 "Bitset::set: fence after clearing unused bits copying from "
124 "HostSpace");
125 }
126 }
127
130 void reset() { Kokkos::deep_copy(m_blocks, 0u); }
131
134 void clear() { Kokkos::deep_copy(m_blocks, 0u); }
135
138 KOKKOS_FORCEINLINE_FUNCTION
139 bool set(unsigned i) const {
140 if (i < m_size) {
141 unsigned* block_ptr = &m_blocks[i >> block_shift];
142 const unsigned mask = 1u << static_cast<int>(i & block_mask);
143
144 return !(atomic_fetch_or(block_ptr, mask) & mask);
145 }
146 return false;
147 }
148
151 KOKKOS_FORCEINLINE_FUNCTION
152 bool reset(unsigned i) const {
153 if (i < m_size) {
154 unsigned* block_ptr = &m_blocks[i >> block_shift];
155 const unsigned mask = 1u << static_cast<int>(i & block_mask);
156
157 return atomic_fetch_and(block_ptr, ~mask) & mask;
158 }
159 return false;
160 }
161
164 KOKKOS_FORCEINLINE_FUNCTION
165 bool test(unsigned i) const {
166 if (i < m_size) {
167#ifdef KOKKOS_ENABLE_SYCL
168 const unsigned block = Kokkos::atomic_load(&m_blocks[i >> block_shift]);
169#else
170 const unsigned block = volatile_load(&m_blocks[i >> block_shift]);
171#endif
172 const unsigned mask = 1u << static_cast<int>(i & block_mask);
173 return block & mask;
174 }
175 return false;
176 }
177
181 KOKKOS_FORCEINLINE_FUNCTION
182 unsigned max_hint() const { return m_blocks.extent(0); }
183
188 KOKKOS_INLINE_FUNCTION
190 unsigned hint,
191 unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const {
192 const unsigned block_idx =
193 (hint >> block_shift) < m_blocks.extent(0) ? (hint >> block_shift) : 0;
194 const unsigned offset = hint & block_mask;
195#ifdef KOKKOS_ENABLE_SYCL
196 unsigned block = Kokkos::atomic_load(&m_blocks[block_idx]);
197#else
198 unsigned block = volatile_load(&m_blocks[block_idx]);
199#endif
200 block = !m_last_block_mask || (block_idx < (m_blocks.extent(0) - 1))
201 ? block
202 : block & m_last_block_mask;
203
204 return find_any_helper(block_idx, offset, block, scan_direction);
205 }
206
211 KOKKOS_INLINE_FUNCTION
213 unsigned hint,
214 unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const {
215 const unsigned block_idx = hint >> block_shift;
216 const unsigned offset = hint & block_mask;
217#ifdef KOKKOS_ENABLE_SYCL
218 unsigned block = Kokkos::atomic_load(&m_blocks[block_idx]);
219#else
220 unsigned block = volatile_load(&m_blocks[block_idx]);
221#endif
222 block = !m_last_block_mask || (block_idx < (m_blocks.extent(0) - 1))
223 ? ~block
224 : ~block & m_last_block_mask;
225
226 return find_any_helper(block_idx, offset, block, scan_direction);
227 }
228
229 KOKKOS_INLINE_FUNCTION constexpr bool is_allocated() const {
230 return m_blocks.is_allocated();
231 }
232
233 private:
234 KOKKOS_FORCEINLINE_FUNCTION
235 Kokkos::pair<bool, unsigned> find_any_helper(unsigned block_idx,
236 unsigned offset, unsigned block,
237 unsigned scan_direction) const {
238 Kokkos::pair<bool, unsigned> result(block > 0u, 0);
239
240 if (!result.first) {
241 result.second = update_hint(block_idx, offset, scan_direction);
242 } else {
243 result.second =
244 scan_block((block_idx << block_shift), offset, block, scan_direction);
245 }
246 return result;
247 }
248
249 KOKKOS_FORCEINLINE_FUNCTION
250 unsigned scan_block(unsigned block_start, int offset, unsigned block,
251 unsigned scan_direction) const {
252 offset = !(scan_direction & BIT_SCAN_REVERSE)
253 ? offset
254 : (offset + block_mask) & block_mask;
255 block = Impl::rotate_right(block, offset);
256 return (((!(scan_direction & BIT_SCAN_REVERSE)
257 ? Impl::bit_scan_forward(block)
258 : Impl::int_log2(block)) +
259 offset) &
260 block_mask) +
261 block_start;
262 }
263
264 KOKKOS_FORCEINLINE_FUNCTION
265 unsigned update_hint(long long block_idx, unsigned offset,
266 unsigned scan_direction) const {
267 block_idx += scan_direction & MOVE_HINT_BACKWARD ? -1 : 1;
268 block_idx = block_idx >= 0 ? block_idx : m_blocks.extent(0) - 1;
269 block_idx =
270 block_idx < static_cast<long long>(m_blocks.extent(0)) ? block_idx : 0;
271
272 return static_cast<unsigned>(block_idx) * block_size + offset;
273 }
274
275 private:
276 unsigned m_size;
277 unsigned m_last_block_mask;
278 View<unsigned*, Device, MemoryTraits<RandomAccess> > m_blocks;
279
280 private:
281 template <typename DDevice>
282 friend class Bitset;
283
284 template <typename DDevice>
285 friend class ConstBitset;
286
287 template <typename Bitset>
288 friend struct Impl::BitsetCount;
289
290 template <typename DstDevice, typename SrcDevice>
291 friend void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice> const& src);
292
293 template <typename DstDevice, typename SrcDevice>
294 friend void deep_copy(Bitset<DstDevice>& dst,
295 ConstBitset<SrcDevice> const& src);
296};
297
300template <typename Device>
302 public:
303 using execution_space = typename Device::execution_space;
304 using size_type = unsigned int;
305
306 private:
307 enum { block_size = static_cast<unsigned>(sizeof(unsigned) * CHAR_BIT) };
308 enum { block_mask = block_size - 1u };
309 enum { block_shift = Kokkos::Impl::integral_power_of_two(block_size) };
310
311 public:
312 KOKKOS_FUNCTION
313 ConstBitset() : m_size(0) {}
314
315 KOKKOS_FUNCTION
316 ConstBitset(Bitset<Device> const& rhs)
317 : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
318
319 KOKKOS_FUNCTION
321 : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
322
323 KOKKOS_FUNCTION
324 ConstBitset<Device>& operator=(Bitset<Device> const& rhs) {
325 this->m_size = rhs.m_size;
326 this->m_blocks = rhs.m_blocks;
327
328 return *this;
329 }
330
331 KOKKOS_FUNCTION
332 ConstBitset<Device>& operator=(ConstBitset<Device> const& rhs) {
333 this->m_size = rhs.m_size;
334 this->m_blocks = rhs.m_blocks;
335
336 return *this;
337 }
338
339 KOKKOS_FORCEINLINE_FUNCTION
340 unsigned size() const { return m_size; }
341
342 unsigned count() const {
343 Impl::BitsetCount<ConstBitset<Device> > f(*this);
344 return f.apply();
345 }
346
347 KOKKOS_FORCEINLINE_FUNCTION
348 bool test(unsigned i) const {
349 if (i < m_size) {
350 const unsigned block = m_blocks[i >> block_shift];
351 const unsigned mask = 1u << static_cast<int>(i & block_mask);
352 return block & mask;
353 }
354 return false;
355 }
356
357 private:
358 unsigned m_size;
360
361 private:
362 template <typename DDevice>
363 friend class ConstBitset;
364
365 template <typename Bitset>
366 friend struct Impl::BitsetCount;
367
368 template <typename DstDevice, typename SrcDevice>
369 friend void deep_copy(Bitset<DstDevice>& dst,
370 ConstBitset<SrcDevice> const& src);
371
372 template <typename DstDevice, typename SrcDevice>
373 friend void deep_copy(ConstBitset<DstDevice>& dst,
374 ConstBitset<SrcDevice> const& src);
375};
376
377template <typename DstDevice, typename SrcDevice>
378void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice> const& src) {
379 if (dst.size() != src.size()) {
380 Kokkos::Impl::throw_runtime_exception(
381 "Error: Cannot deep_copy bitsets of different sizes!");
382 }
383
384 Kokkos::fence("Bitset::deep_copy: fence before copy operation");
385 Kokkos::Impl::DeepCopy<typename DstDevice::memory_space,
386 typename SrcDevice::memory_space>(
387 dst.m_blocks.data(), src.m_blocks.data(),
388 sizeof(unsigned) * src.m_blocks.extent(0));
389 Kokkos::fence("Bitset::deep_copy: fence after copy operation");
390}
391
392template <typename DstDevice, typename SrcDevice>
393void deep_copy(Bitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src) {
394 if (dst.size() != src.size()) {
395 Kokkos::Impl::throw_runtime_exception(
396 "Error: Cannot deep_copy bitsets of different sizes!");
397 }
398
399 Kokkos::fence("Bitset::deep_copy: fence before copy operation");
400 Kokkos::Impl::DeepCopy<typename DstDevice::memory_space,
401 typename SrcDevice::memory_space>(
402 dst.m_blocks.data(), src.m_blocks.data(),
403 sizeof(unsigned) * src.m_blocks.extent(0));
404 Kokkos::fence("Bitset::deep_copy: fence after copy operation");
405}
406
407template <typename DstDevice, typename SrcDevice>
408void deep_copy(ConstBitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src) {
409 if (dst.size() != src.size()) {
410 Kokkos::Impl::throw_runtime_exception(
411 "Error: Cannot deep_copy bitsets of different sizes!");
412 }
413
414 Kokkos::fence("Bitset::deep_copy: fence before copy operation");
415 Kokkos::Impl::DeepCopy<typename DstDevice::memory_space,
416 typename SrcDevice::memory_space>(
417 dst.m_blocks.data(), src.m_blocks.data(),
418 sizeof(unsigned) * src.m_blocks.extent(0));
419 Kokkos::fence("Bitset::deep_copy: fence after copy operation");
420}
421
422} // namespace Kokkos
423
424#ifdef KOKKOS_IMPL_PUBLIC_INCLUDE_NOTDEFINED_BITSET
425#undef KOKKOS_IMPL_PUBLIC_INCLUDE
426#undef KOKKOS_IMPL_PUBLIC_INCLUDE_NOTDEFINED_BITSET
427#endif
428#endif // KOKKOS_BITSET_HPP
A thread safe view to a bitset.
KOKKOS_FORCEINLINE_FUNCTION bool set(unsigned i) const
KOKKOS_FORCEINLINE_FUNCTION unsigned max_hint() const
KOKKOS_FORCEINLINE_FUNCTION unsigned size() const
KOKKOS_INLINE_FUNCTION Kokkos::pair< bool, unsigned > find_any_unset_near(unsigned hint, unsigned scan_direction=BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const
Bitset(unsigned arg_size=0u)
unsigned count() const
KOKKOS_FORCEINLINE_FUNCTION bool test(unsigned i) const
KOKKOS_FORCEINLINE_FUNCTION bool reset(unsigned i) const
KOKKOS_INLINE_FUNCTION Kokkos::pair< bool, unsigned > find_any_set_near(unsigned hint, unsigned scan_direction=BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const
View to an array of data.
KOKKOS_INLINE_FUNCTION constexpr std::enable_if_t< std::is_integral< iType >::value, size_t > extent(const iType &r) const noexcept
rank() to be implemented
Replacement for std::pair that works on CUDA devices.
Definition: Kokkos_Pair.hpp:43