Block-Structured AMR Software Framework
Loading...
Searching...
No Matches
AMReX_DenseBins.H
Go to the documentation of this file.
1#ifndef AMREX_DENSEBINS_H_
2#define AMREX_DENSEBINS_H_
3#include <AMReX_Config.H>
4
5#include <AMReX_Gpu.H>
6#include <AMReX_Scan.H>
7#include <AMReX_IntVect.H>
8#include <AMReX_BLProfiler.H>
9#include <AMReX_BinIterator.H>
10
11namespace amrex
12{
14namespace detail
15{
16#if defined(AMREX_USE_CUDA) || defined(AMREX_USE_HIP)
29 template <typename T>
31 T warpRunAggregatedIncrement (T* counts, T bin, bool active) noexcept
32 {
33 constexpr int warp_size = Gpu::Device::warp_size;
34#if defined(AMREX_USE_HIP)
35 using mask_t = unsigned long long;
36 const int lane = static_cast<int>(__lane_id());
37 const mask_t active_mask = __ballot(active);
38 const T prev_bin = __shfl_up(bin, 1);
39#else
40 using mask_t = unsigned int;
41 constexpr mask_t full_mask = 0xffffffffu;
42 const int lane = static_cast<int>(threadIdx.x) % warp_size;
43 const mask_t active_mask = __ballot_sync(full_mask, active);
44 const T prev_bin = __shfl_up_sync(full_mask, bin, 1);
45#endif
46 const bool prev_active = (lane > 0) && ((active_mask >> (lane-1)) & 1);
47 const bool head = active && (!prev_active || bin != prev_bin);
48#if defined(AMREX_USE_HIP)
49 const mask_t heads = __ballot(head);
50#else
51 const mask_t heads = __ballot_sync(full_mask, head);
52#endif
53 // lanes <= this lane
54 const mask_t lanes_le = (lane == warp_size-1) ? ~mask_t(0)
55 : (mask_t(1) << (lane+1)) - 1;
56
57 // The first lane of this lane's run, and (for heads) the length of the run,
58 // which ends at the next head or inactive lane.
59 int run_start = lane;
60 T base = 0;
61 if (active) {
62 const mask_t heads_le = heads & lanes_le;
63#if defined(AMREX_USE_HIP)
64 run_start = 63 - __clzll(static_cast<long long>(heads_le));
65#else
66 run_start = 31 - __clz(static_cast<int>(heads_le));
67#endif
68 }
69 if (head) {
70 const mask_t ends = (heads | ~active_mask) & ~lanes_le;
71#if defined(AMREX_USE_HIP)
72 const int run_end = (ends != 0) ? __ffsll(static_cast<long long>(ends)) - 1
73 : warp_size;
74#else
75 const int run_end = (ends != 0) ? __ffs(static_cast<int>(ends)) - 1
76 : warp_size;
77#endif
78 base = Gpu::Atomic::Add(&counts[bin], static_cast<T>(run_end - lane));
79 }
80#if defined(AMREX_USE_HIP)
81 base = __shfl(base, run_start);
82#else
83 base = __shfl_sync(full_mask, base, run_start);
84#endif
85 return base + static_cast<T>(lane - run_start);
86 }
87#endif
88}
90
91namespace BinPolicy
92{
93 struct GPUBinPolicy {};
94 struct OpenMPBinPolicy {};
95 struct SerialBinPolicy {};
96
97 static constexpr GPUBinPolicy GPU{};
98 static constexpr OpenMPBinPolicy OpenMP{};
99 static constexpr SerialBinPolicy Serial{};
100
101#ifdef AMREX_USE_GPU
102 static constexpr GPUBinPolicy Default{};
103#else
104 static constexpr OpenMPBinPolicy Default{};
105#endif
106}
107
108template <typename T>
110{
112
113 using const_pointer_type = std::conditional_t<IsParticleTileData<T>(),
114 T,
115 const T*
116 >;
117
119 const Gpu::DeviceVector<index_type>& permutation,
120 const T* items)
121 : m_offsets_ptr(offsets.dataPtr()),
122 m_permutation_ptr(permutation.dataPtr()),
123 m_items(items)
124 {}
125
126 [[nodiscard]] AMREX_GPU_HOST_DEVICE
127 BinIterator<T> getBinIterator(const int bin_number) const noexcept
128 {
130 }
131
135};
136
137
153template <typename T>
155{
156public:
157
160
161 using const_pointer_type = std::conditional_t<IsParticleTileData<T>(),
162 T,
163 const T*
164 >;
165
166 using const_pointer_input_type = std::conditional_t<IsParticleTileData<T>(),
167 const T&,
168 const T*
169 >;
170
171private:
172
173 template <typename F, typename Index>
175 static auto call_f (F const& f, const_pointer_input_type v, Index& index) {
176 if constexpr (IsCallable<F, decltype(v), Index>::value) {
177 return f(v, index);
178 } else {
179 return f(v[index]);
180 }
181 }
182
183public:
184
207 template <typename N, typename F>
208 void build (N nitems, const_pointer_input_type v, const Box& bx, F&& f)
209 {
210 build(BinPolicy::Default, nitems, v, bx, std::forward<F>(f));
211 }
212
234 template <typename N, typename F>
235 void build (N nitems, const_pointer_input_type v, int nbins, F&& f)
236 {
237 build(BinPolicy::Default, nitems, v, nbins, std::forward<F>(f));
238 }
239
262 template <typename N, typename F>
263 void build (BinPolicy::GPUBinPolicy, N nitems, const_pointer_input_type v, const Box& bx, F const& f)
264 {
265 const auto lo = lbound(bx);
266 const auto hi = ubound(bx);
267 build(BinPolicy::GPU, nitems, v, bx.numPts(),
269 {
270 auto iv = call_f(f,t,i);
271 auto iv3 = iv.dim3();
272 int nx = hi.x-lo.x+1;
273 int ny = hi.y-lo.y+1;
274 int nz = hi.z-lo.z+1;
275 index_type uix = amrex::min(nx-1,amrex::max(0,iv3.x));
276 index_type uiy = amrex::min(ny-1,amrex::max(0,iv3.y));
277 index_type uiz = amrex::min(nz-1,amrex::max(0,iv3.z));
278 return (uiz * ny + uiy) * nx + uix;
279 });
280 }
281
303 template <typename N, typename F>
304 void build (BinPolicy::GPUBinPolicy, N nitems, const_pointer_input_type v, int nbins, F const& f)
305 {
306 BL_PROFILE("DenseBins<T>::buildGPU");
307
308 m_items = v;
309
310 m_bins.resize(0);
311 m_bins.resize(nitems);
312 m_perm.resize(0);
313 m_perm.resize(nitems);
314 m_local_offsets.resize(0);
315 m_local_offsets.resize(nitems);
316
317 m_counts.resize(0);
318 m_counts.resize(nbins+1, 0);
319
320 m_offsets.resize(0);
321 m_offsets.resize(nbins+1);
322
323 index_type* pbins = m_bins.dataPtr();
324 index_type* pcount = m_counts.dataPtr();
325 index_type* plocal_offsets = m_local_offsets.dataPtr();
326#if defined(AMREX_USE_CUDA) || defined(AMREX_USE_HIP)
327 // Items are often (partially) sorted by bin, so adjacent threads tend to increment
328 // the same counter. Aggregate those increments within each warp to reduce contention.
329 constexpr int block_size = AMREX_GPU_MAX_THREADS;
330 const auto nblocks = static_cast<int>((Long(nitems) + block_size - 1) / block_size);
331 if (nblocks > 0) {
333 [=] AMREX_GPU_DEVICE () noexcept
334 {
335 const Long li = Long(blockIdx.x) * block_size + threadIdx.x;
336 const bool active = li < Long(nitems);
337 const auto i = static_cast<index_type>(li);
338 index_type bin = 0;
339 if (active) {
340 bin = static_cast<index_type>(call_f(f,v,i));
341 pbins[i] = bin;
342 }
343 index_type off = detail::warpRunAggregatedIncrement(pcount, bin, active);
344 if (active) {
345 plocal_offsets[i] = off;
346 }
347 });
348 }
349#else
350 amrex::ParallelFor(nitems, [=] AMREX_GPU_DEVICE (int i) noexcept
351 {
352 pbins[i] = call_f(f,v,i);
353 index_type off = Gpu::Atomic::Add(&pcount[pbins[i]], index_type{ 1 });
354 plocal_offsets[i] = off;
355 });
356#endif
357
358 Gpu::exclusive_scan(m_counts.begin(), m_counts.end(), m_offsets.begin());
359
360 index_type* pperm = m_perm.dataPtr();
361 index_type* poffsets = m_offsets.dataPtr();
362 amrex::ParallelFor(nitems, [=] AMREX_GPU_DEVICE (int i) noexcept
363 {
364 index_type index = poffsets[pbins[i]] + plocal_offsets[i];
365 pperm[index] = i;
366 });
367
369 }
370
394 template <typename N, typename F>
395 void build (BinPolicy::OpenMPBinPolicy, N nitems, const_pointer_input_type v, const Box& bx, F const& f)
396 {
397 const auto lo = lbound(bx);
398 const auto hi = ubound(bx);
399 build(BinPolicy::OpenMP, nitems, v, bx.numPts(),
400 [=] (const_pointer_type t, index_type i) noexcept
401 {
402 auto iv = call_f(f,t,i);
403 auto iv3 = iv.dim3();
404 int nx = hi.x-lo.x+1;
405 int ny = hi.y-lo.y+1;
406 int nz = hi.z-lo.z+1;
407 index_type uix = amrex::min(nx-1,amrex::max(0,iv3.x));
408 index_type uiy = amrex::min(ny-1,amrex::max(0,iv3.y));
409 index_type uiz = amrex::min(nz-1,amrex::max(0,iv3.z));
410 return (uiz * ny + uiy) * nx + uix;
411 });
412 }
413
436 template <typename N, typename F>
437 void build (BinPolicy::OpenMPBinPolicy, N nitems, const_pointer_input_type v, int nbins, F const& f)
438 {
439 BL_PROFILE("DenseBins<T>::buildOpenMP");
440
441 if (nbins <= 0) { return; }
442
443 m_items = v;
444
445 m_bins.resize(0);
446 m_bins.resize(nitems);
447 m_perm.resize(0);
448 m_perm.resize(nitems);
449
450 int nchunks = OpenMP::get_max_threads();
451 int chunksize = nitems / nchunks;
452 auto* counts = (index_type*)(The_Arena()->alloc(nchunks*nbins*sizeof(index_type)));
453 for (int i = 0; i < nbins*nchunks; ++i) { counts[i] = 0;}
454
455 m_counts.resize(0);
456 m_counts.resize(nbins+1, 0);
457
458 m_offsets.resize(0);
459 m_offsets.resize(nbins+1);
460
461#ifdef AMREX_USE_OMP
462#pragma omp parallel for
463#endif
464 for (int j = 0; j < nchunks; ++j) {
465 int istart = j*chunksize;
466 int istop = (j == nchunks-1) ? nitems : (j+1)*chunksize;
467 for (int i = istart; i < istop; ++i) {
468 m_bins[i] = call_f(f,v,i);
469 ++counts[nbins*j+m_bins[i]];
470 }
471 }
472
473#ifdef AMREX_USE_OMP
474#pragma omp parallel for
475#endif
476 for (int i = 0; i < nbins; ++i) {
477 index_type total = 0;
478 for (int j = 0; j < nchunks; ++j) {
479 auto tmp = counts[nbins*j+i];
480 counts[nbins*j+i] = total;
481 total += tmp;
482 }
483 m_counts[i] = total;
484 }
485
486 // note - this part has to be serial
487 m_offsets[0] = 0;
488 for (int i = 0; i < nbins; ++i) {m_offsets[i+1] = m_offsets[i] + m_counts[i];}
489
490#ifdef AMREX_USE_OMP
491#pragma omp parallel for
492#endif
493 for (int i = 0; i < nbins; ++i) {
494 for (int j = 0; j < nchunks; ++j) {
495 counts[nbins*j+i] += m_offsets[i];
496 }
497 }
498
499#ifdef AMREX_USE_OMP
500#pragma omp parallel for
501#endif
502 for (int j = 0; j < nchunks; ++j) {
503 int istart = j*chunksize;
504 int istop = (j == nchunks-1) ? nitems : (j+1)*chunksize;
505 for (int i = istart; i < istop; ++i) {
506 auto bid = m_bins[i];
507 m_perm[counts[nbins*j+bid]++] = i;
508 }
509 }
510
511 The_Arena()->free(counts);
512 }
513
537 template <typename N, typename F>
538 void build (BinPolicy::SerialBinPolicy, N nitems, const_pointer_input_type v, const Box& bx, F const& f)
539 {
540 const auto lo = lbound(bx);
541 const auto hi = ubound(bx);
542 build(BinPolicy::Serial, nitems, v, bx.numPts(),
543 [=] (const_pointer_type t, index_type i) noexcept
544 {
545 auto iv = call_f(f,t,i);
546 auto iv3 = iv.dim3();
547 int nx = hi.x-lo.x+1;
548 int ny = hi.y-lo.y+1;
549 int nz = hi.z-lo.z+1;
550 index_type uix = amrex::min(nx-1,amrex::max(0,iv3.x));
551 index_type uiy = amrex::min(ny-1,amrex::max(0,iv3.y));
552 index_type uiz = amrex::min(nz-1,amrex::max(0,iv3.z));
553 return (uiz * ny + uiy) * nx + uix;
554 });
555 }
556
579 template <typename N, typename F>
580 void build (BinPolicy::SerialBinPolicy, N nitems, const_pointer_input_type v, int nbins, F const& f)
581 {
582 BL_PROFILE("DenseBins<T>::buildSerial");
583
584 m_items = v;
585
586 m_bins.resize(0);
587 m_bins.resize(nitems);
588 m_perm.resize(0);
589 m_perm.resize(nitems);
590
591 m_counts.resize(0);
592 m_counts.resize(nbins+1, 0);
593
594 m_offsets.resize(0);
595 m_offsets.resize(nbins+1);
596
597 for (N i = 0; i < nitems; ++i) {
598 m_bins[i] = call_f(f,v,i);
599 ++m_counts[m_bins[i]];
600 }
601
602 Gpu::exclusive_scan(m_counts.begin(), m_counts.end(), m_offsets.begin());
603
604 Gpu::copy(Gpu::deviceToDevice, m_offsets.begin(), m_offsets.end(), m_counts.begin());
605
606 for (N i = 0; i < nitems; ++i) {
607 index_type index = m_counts[m_bins[i]]++;
608 m_perm[index] = i;
609 }
610 }
611
613 [[nodiscard]] Long numItems () const noexcept { return m_perm.size(); }
614
616 [[nodiscard]] Long numBins () const noexcept { return m_offsets.size()-1; }
617
619 [[nodiscard]] index_type* permutationPtr () noexcept { return m_perm.dataPtr(); }
620
622 [[nodiscard]] index_type* offsetsPtr () noexcept { return m_offsets.dataPtr(); }
623
625 [[nodiscard]] index_type* binsPtr () noexcept { return m_bins.dataPtr(); }
626
628 [[nodiscard]] const index_type* permutationPtr () const noexcept { return m_perm.dataPtr(); }
629
631 [[nodiscard]] const index_type* offsetsPtr () const noexcept { return m_offsets.dataPtr(); }
632
634 [[nodiscard]] const index_type* binsPtr () const noexcept { return m_bins.dataPtr(); }
635
638 {
639 return DenseBinIteratorFactory<T>(m_offsets, m_perm, m_items);
640 }
641
642private:
643
644 const_pointer_type m_items;
645
648 Gpu::DeviceVector<index_type> m_local_offsets;
651};
652
653}
654
655#endif
#define BL_PROFILE(a)
Definition AMReX_BLProfiler.H:593
#define AMREX_FORCE_INLINE
Definition AMReX_Extension.H:123
#define AMREX_GPU_DEVICE
Definition AMReX_GpuQualifiers.H:18
#define AMREX_GPU_HOST_DEVICE
Definition AMReX_GpuQualifiers.H:20
Convenience header for the core AMReX GPU facilities.
virtual void free(void *pt)=0
Free a previously allocated block pointed to by pt.
__host__ __device__ Long numPts() const noexcept
Return the number of points contained in the BoxND.
Definition AMReX_Box.H:385
A container for storing items in a set of bins.
Definition AMReX_DenseBins.H:155
const index_type * permutationPtr() const noexcept
returns const pointer to the permutation array
Definition AMReX_DenseBins.H:628
DenseBinIteratorFactory< T > getBinIteratorFactory() const noexcept
returns a GPU-capable object that can create iterators over the items in a bin.
Definition AMReX_DenseBins.H:637
const index_type * binsPtr() const noexcept
returns the const pointer to the bins array
Definition AMReX_DenseBins.H:634
index_type * offsetsPtr() noexcept
returns the pointer to the offsets array
Definition AMReX_DenseBins.H:622
index_type * permutationPtr() noexcept
returns the pointer to the permutation array
Definition AMReX_DenseBins.H:619
std::conditional_t< IsParticleTileData< T >(), const T &, const T * > const_pointer_input_type
Definition AMReX_DenseBins.H:166
void build(BinPolicy::OpenMPBinPolicy, N nitems, const_pointer_input_type v, const Box &bx, F const &f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:395
void build(BinPolicy::GPUBinPolicy, N nitems, const_pointer_input_type v, const Box &bx, F const &f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:263
void build(N nitems, const_pointer_input_type v, const Box &bx, F &&f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:208
int index_type
Definition AMReX_DenseBins.H:159
void build(BinPolicy::SerialBinPolicy, N nitems, const_pointer_input_type v, const Box &bx, F const &f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:538
void build(BinPolicy::GPUBinPolicy, N nitems, const_pointer_input_type v, int nbins, F const &f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:304
const index_type * offsetsPtr() const noexcept
returns const pointer to the offsets array
Definition AMReX_DenseBins.H:631
std::conditional_t< IsParticleTileData< T >(), T, const T * > const_pointer_type
Definition AMReX_DenseBins.H:161
void build(BinPolicy::OpenMPBinPolicy, N nitems, const_pointer_input_type v, int nbins, F const &f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:437
void build(N nitems, const_pointer_input_type v, int nbins, F &&f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:235
Long numItems() const noexcept
the number of items in the container
Definition AMReX_DenseBins.H:613
void build(BinPolicy::SerialBinPolicy, N nitems, const_pointer_input_type v, int nbins, F const &f)
Populate the bins with a set of items.
Definition AMReX_DenseBins.H:580
DenseBinIteratorFactory< T > BinIteratorFactory
Definition AMReX_DenseBins.H:158
Long numBins() const noexcept
the number of bins in the container
Definition AMReX_DenseBins.H:616
index_type * binsPtr() noexcept
returns the pointer to the bins array
Definition AMReX_DenseBins.H:625
static void streamSynchronize() noexcept
Definition AMReX_GpuDevice.cpp:992
static constexpr int warp_size
Definition AMReX_GpuDevice.H:239
amrex_long Long
Definition AMReX_INT.H:30
OutIter exclusive_scan(InIter begin, InIter end, OutIter result)
Definition AMReX_Scan.H:1181
__host__ __device__ Dim3 ubound(Array4< T > const &a) noexcept
Return the inclusive upper bounds of an Array4 in Dim3 form.
Definition AMReX_Array4.H:1377
__host__ __device__ Dim3 lbound(Array4< T > const &a) noexcept
Return the inclusive lower bounds of an Array4 in Dim3 form.
Definition AMReX_Array4.H:1363
PODVector< T, ArenaAllocator< T > > DeviceVector
A PODVector that uses the standard memory Arena. Note that the memory might or might not be managed d...
Definition AMReX_GpuContainers.H:24
Arena * The_Arena()
Definition AMReX_Arena.cpp:839
__host__ __device__ constexpr const T & min(const T &a, const T &b) noexcept
Definition AMReX_Algorithm.H:31
__host__ __device__ constexpr const T & max(const T &a, const T &b) noexcept
Definition AMReX_Algorithm.H:54
Definition AMReX_DenseBins.H:92
static constexpr OpenMPBinPolicy OpenMP
Definition AMReX_DenseBins.H:98
static constexpr GPUBinPolicy Default
Definition AMReX_DenseBins.H:102
static constexpr SerialBinPolicy Serial
Definition AMReX_DenseBins.H:99
static constexpr GPUBinPolicy GPU
Definition AMReX_DenseBins.H:97
__host__ __device__ AMREX_FORCE_INLINE T Add(T *sum, T value) noexcept
Definition AMReX_GpuAtomic.H:239
void copy(HostToDevice, InIter begin, InIter end, OutIter result) noexcept
A host-to-device copy routine. Note this is just a wrapper around memcpy, so it assumes contiguous st...
Definition AMReX_GpuContainers.H:128
static constexpr DeviceToDevice deviceToDevice
Definition AMReX_GpuContainers.H:107
gpuStream_t gpuStream() noexcept
Definition AMReX_GpuDevice.H:310
constexpr int get_max_threads()
Definition AMReX_OpenMP.H:36
Definition AMReX_Amr.cpp:50
@ F
Definition AMReX_Order.H:7
void launch(T const &n, L const &f) noexcept
Definition AMReX_GpuLaunchFunctsC.H:122
void ParallelFor(TypeList< CTOs... > ctos, std::array< int, sizeof...(CTOs)> const &runtime_options, T N, F &&f)
Definition AMReX_CTOParallelForImpl.H:202
BoxND< 3 > Box
Box is an alias for amrex::BoxND instantiated with AMREX_SPACEDIM.
Definition AMReX_BaseFwd.H:35
const int[]
Definition AMReX_BLProfiler.cpp:1665
Definition AMReX_BinIterator.H:24
Definition AMReX_DenseBins.H:93
Definition AMReX_DenseBins.H:94
Definition AMReX_DenseBins.H:95
Definition AMReX_DenseBins.H:110
DenseBinIteratorFactory(const Gpu::DeviceVector< index_type > &offsets, const Gpu::DeviceVector< index_type > &permutation, const T *items)
Definition AMReX_DenseBins.H:118
const index_type * m_permutation_ptr
Definition AMReX_DenseBins.H:133
int index_type
Definition AMReX_DenseBins.H:111
__host__ __device__ BinIterator< T > getBinIterator(const int bin_number) const noexcept
Definition AMReX_DenseBins.H:127
const_pointer_type m_items
Definition AMReX_DenseBins.H:134
std::conditional_t< IsParticleTileData< T >(), T, const T * > const_pointer_type
Definition AMReX_DenseBins.H:113
const index_type * m_offsets_ptr
Definition AMReX_DenseBins.H:132
Test if a given type T is callable with arguments of type Args...
Definition AMReX_TypeTraits.H:208