Blender V5.3
parallel_prefix_sum.h
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2021-2022 Blender Foundation
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#pragma once
6
8
9/* Parallel prefix sum. */
10
11#include "util/atomic.h"
12
13__device__ void gpu_parallel_prefix_sum(const int global_id,
14 ccl_global int *ccl_restrict counter,
15 ccl_global int *ccl_restrict prefix_sum,
16 const int num_values)
17{
18 int partition_start = 0;
19 int partition_end = num_values;
20 int offset = 0;
21
22#ifndef __KERNEL_METAL__
23 const ushort local_id = ccl_gpu_thread_idx_x;
24 const ushort local_size = ccl_gpu_block_dim_x;
25
26 if (num_values >= local_size) {
27 const int partition_size = divide_up(num_values, local_size);
28 partition_start = partition_size * local_id;
29 partition_end = min(num_values, partition_start + partition_size);
30
31 int total = 0;
32 for (int i = partition_start; i < partition_end; i++) {
33 total += counter[i];
34 }
35 prefix_sum[local_id] = total;
36
38
39 if (local_id == 0) {
40 for (int i = 0; i < local_size; i++) {
41 const int new_offset = offset + prefix_sum[i];
42 prefix_sum[i] = offset;
43 offset = new_offset;
44 }
45 }
46
48 offset = prefix_sum[local_id];
50 }
51 else
52#endif
53 if (global_id != 0)
54 {
55 return;
56 }
57
58 for (int i = partition_start; i < partition_end; i++) {
59 const int new_offset = offset + counter[i];
60 prefix_sum[i] = offset;
61 counter[i] = 0;
62 offset = new_offset;
63 }
64}
65
#define ccl_restrict
#define ccl_global
#define ccl_gpu_block_dim_x
#define ccl_gpu_thread_idx_x
#define ccl_gpu_syncthreads()
#define CCL_NAMESPACE_END
#define __device__
#define local_size(...)
CCL_NAMESPACE_BEGIN __device__ void gpu_parallel_prefix_sum(const int global_id, ccl_global int *ccl_restrict counter, ccl_global int *ccl_restrict prefix_sum, const int num_values)
#define min(a, b)
Definition sort.cc:38
ccl_device_inline size_t divide_up(const size_t x, const size_t y)
Definition types_base.h:54