Blender V5.3
parallel_sorted_index.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/* Given an array of states, build an array of indices for which the states
10 * are active and sorted by a given key. The prefix sum of the number of active
11 * states per key must have already been computed.
12 *
13 * TODO: there may be ways to optimize this to avoid this many atomic ops? */
14
16#include "util/atomic.h"
17
19 const uint partition_size,
20 const uint max_shaders,
21 const uint queued_kernel,
22#if defined(__KERNEL_METAL__) || defined(__KERNEL_ONEAPI__)
23 ccl_gpu_shared int *buckets,
24#endif
26 const ushort local_id,
27 const ushort local_size,
28 const uint grid_id,
29#endif
30 ccl_global ushort *d_queued_kernel,
31 ccl_global uint *d_shader_sort_key,
32 ccl_global int *partition_key_offsets)
33{
34#ifndef __KERNEL_METAL__
35# ifndef __KERNEL_ONEAPI__
36 extern ccl_gpu_shared int buckets[];
37# endif
38
39 const ushort local_id = ccl_gpu_thread_idx_x;
40 const ushort local_size = ccl_gpu_block_dim_x;
41 const uint grid_id = ccl_gpu_block_idx_x;
42#endif
43
44 /* Zero the bucket sizes. */
45 for (uint i = local_id; i < max_shaders; i += local_size) {
46 atomic_store_local(&buckets[i], 0);
47 }
48
49#ifdef __KERNEL_ONEAPI__
50 /* NOTE(@nsirgien): For us here only local memory writing (buckets) is important,
51 * so faster local barriers can be used. */
53#else
55#endif
56
57 /* Determine bucket sizes within the partitions. */
58
59 const uint partition_start = partition_size * uint(grid_id);
60 const uint partition_end = min(num_states, partition_start + partition_size);
61
62 for (int state_index = partition_start + uint(local_id); state_index < partition_end;
63 state_index += uint(local_size))
64 {
65 ushort kernel_index = d_queued_kernel[state_index];
66 if (kernel_index == queued_kernel) {
67 uint key = d_shader_sort_key[state_index] % max_shaders;
68 atomic_fetch_and_add_uint32_shared(&buckets[key], 1);
69 }
70 }
71
72#ifdef __KERNEL_ONEAPI__
73 /* NOTE(@nsirgien): For us here only local memory writing (buckets) is important,
74 * so faster local barriers can be used. */
76#else
78#endif
79
80 /* Calculate the partition's local offsets from the prefix sum of bucket sizes. */
81
82 if (local_id == 0) {
83 int offset = 0;
84 for (int i = 0; i < max_shaders; i++) {
85 partition_key_offsets[i + uint(grid_id) * (max_shaders + 1)] = offset;
86 offset = offset + atomic_load_local(&buckets[i]);
87 }
88
89 /* Store the number of active states in this partition. */
90 partition_key_offsets[max_shaders + uint(grid_id) * (max_shaders + 1)] = offset;
91 }
92}
93
94#ifdef __KERNEL_METAL__
95
96# define gpu_parallel_sort_bucket_pass(num_states, \
97 partition_size, \
98 max_shaders, \
99 queued_kernel, \
100 d_queued_kernel, \
101 d_shader_sort_key, \
102 partition_key_offsets) \
103 gpu_parallel_sort_bucket_pass_impl(num_states, \
104 partition_size, \
105 max_shaders, \
106 queued_kernel, \
107 (ccl_gpu_shared int *)threadgroup_array, \
108 metal_local_id, \
109 metal_local_size, \
110 metal_grid_id, \
111 d_queued_kernel, \
112 d_shader_sort_key, \
113 partition_key_offsets)
114
115#elif defined(__KERNEL_ONEAPI__)
116
117# define gpu_parallel_sort_bucket_pass(num_states, \
118 partition_size, \
119 max_shaders, \
120 queued_kernel, \
121 d_queued_kernel, \
122 d_shader_sort_key, \
123 partition_key_offsets) \
124 gpu_parallel_sort_bucket_pass_impl(num_states, \
125 partition_size, \
126 max_shaders, \
127 queued_kernel, \
128 (ccl_gpu_shared int *)threadgroup_array, \
129 d_queued_kernel, \
130 d_shader_sort_key, \
131 partition_key_offsets)
132
133#else
134
135# define gpu_parallel_sort_bucket_pass gpu_parallel_sort_bucket_pass_impl
136
137#endif
138
140 const uint partition_size,
141 const int num_states_limit,
142 ccl_global int *indices,
143 const uint max_shaders,
144 const uint queued_kernel,
145#if defined(__KERNEL_METAL__) || defined(__KERNEL_ONEAPI__)
146 ccl_gpu_shared int *local_offset,
147#endif
148#ifdef __KERNEL_METAL__
149 const ushort local_id,
150 const ushort local_size,
151 const uint grid_id,
152#endif
153 ccl_global ushort *d_queued_kernel,
154 ccl_global uint *d_shader_sort_key,
155 ccl_global int *partition_key_offsets)
156{
157#ifndef __KERNEL_METAL__
158# ifndef __KERNEL_ONEAPI__
159 extern ccl_gpu_shared int local_offset[];
160# endif
161
162 const ushort local_id = ccl_gpu_thread_idx_x;
163 const ushort local_size = ccl_gpu_block_dim_x;
164 const uint grid_id = ccl_gpu_block_idx_x;
165#endif
166
167 /* Calculate each partition's global offset from the prefix sum of the active state counts per
168 * partition. */
169
170 int partition_offset = 0;
171 for (uint i = 0; i < grid_id; i++) {
172 partition_offset += partition_key_offsets[max_shaders + i * (max_shaders + 1)];
173 }
174
175 ccl_global int *key_offsets = partition_key_offsets + grid_id * (max_shaders + 1);
176 for (uint i = local_id; i < max_shaders; i += local_size) {
177 atomic_store_local(&local_offset[i], key_offsets[i] + partition_offset);
178 }
179
180#ifdef __KERNEL_ONEAPI__
181 /* NOTE(@nsirgien): For us here only local memory writing (local_offset) is important,
182 * so faster local barriers can be used. */
184#else
186#endif
187
188 /* Write the sorted active indices. */
189
190 const uint partition_start = partition_size * uint(grid_id);
191 const uint partition_end = min(num_states, partition_start + partition_size);
192
193 for (int state_index = partition_start + uint(local_id); state_index < partition_end;
194 state_index += uint(local_size))
195 {
196 ushort kernel_index = d_queued_kernel[state_index];
197 if (kernel_index == queued_kernel) {
198 uint key = d_shader_sort_key[state_index] % max_shaders;
199 int index = atomic_fetch_and_add_uint32_shared(&local_offset[key], 1);
200 if (index < num_states_limit) {
201 indices[index] = state_index;
202 }
203 }
204 }
205}
206
207#ifdef __KERNEL_METAL__
208
209# define gpu_parallel_sort_write_pass(num_states, \
210 partition_size, \
211 num_states_limit, \
212 indices, \
213 max_shaders, \
214 queued_kernel, \
215 d_queued_kernel, \
216 d_shader_sort_key, \
217 partition_key_offsets) \
218 gpu_parallel_sort_write_pass_impl(num_states, \
219 partition_size, \
220 num_states_limit, \
221 indices, \
222 max_shaders, \
223 queued_kernel, \
224 (ccl_gpu_shared int *)threadgroup_array, \
225 metal_local_id, \
226 metal_local_size, \
227 metal_grid_id, \
228 d_queued_kernel, \
229 d_shader_sort_key, \
230 partition_key_offsets)
231
232#elif defined(__KERNEL_ONEAPI__)
233
234# define gpu_parallel_sort_write_pass(num_states, \
235 partition_size, \
236 num_states_limit, \
237 indices, \
238 max_shaders, \
239 queued_kernel, \
240 d_queued_kernel, \
241 d_shader_sort_key, \
242 partition_key_offsets) \
243 gpu_parallel_sort_write_pass_impl(num_states, \
244 partition_size, \
245 num_states_limit, \
246 indices, \
247 max_shaders, \
248 queued_kernel, \
249 (ccl_gpu_shared int *)threadgroup_array, \
250 d_queued_kernel, \
251 d_shader_sort_key, \
252 partition_key_offsets)
253
254#else
255
256# define gpu_parallel_sort_write_pass gpu_parallel_sort_write_pass_impl
257
258#endif
259
260template<typename GetKeyOp>
261__device__ void gpu_parallel_sorted_index_array(const uint state_index,
262 const uint num_states,
263 const int num_states_limit,
264 ccl_global int *indices,
265 ccl_global int *num_indices,
266 ccl_global int *key_counter,
267 ccl_global int *key_prefix_sum,
268 GetKeyOp get_key_op)
269{
270 const int key = (state_index < num_states) ? get_key_op(state_index) :
272
274 const uint index = atomic_fetch_and_add_uint32(&key_prefix_sum[key], 1);
275 if (index < num_states_limit) {
276 /* Assign state index. */
277 indices[index] = state_index;
278 }
279 else {
280 /* Can't process this state now, increase the counter again
281 * so that it will be handled in another iteration. */
282 atomic_fetch_and_add_uint32(&key_counter[key], 1);
283 }
284 }
285}
286
ATOMIC_INLINE uint32_t atomic_fetch_and_add_uint32(uint32_t *p, uint32_t x)
#define GPU_PARALLEL_SORTED_INDEX_INACTIVE_KEY
Definition block_sizes.h:17
#define ccl_device_inline
#define ccl_global
#define ccl_gpu_block_dim_x
#define ccl_gpu_thread_idx_x
#define ccl_gpu_syncthreads()
#define ccl_gpu_shared
#define ccl_gpu_block_idx_x
#define CCL_NAMESPACE_END
#define __KERNEL_METAL__
#define __device__
#define ccl_gpu_local_syncthreads()
#define __KERNEL_ONEAPI__
#define index(i)
#define local_size(...)
const int num_states
CCL_NAMESPACE_BEGIN ccl_device_inline void gpu_parallel_sort_bucket_pass_impl(const uint num_states, const uint partition_size, const uint max_shaders, const uint queued_kernel, ccl_global ushort *d_queued_kernel, ccl_global uint *d_shader_sort_key, ccl_global int *partition_key_offsets)
__device__ void gpu_parallel_sorted_index_array(const uint state_index, const uint num_states, const int num_states_limit, ccl_global int *indices, ccl_global int *num_indices, ccl_global int *key_counter, ccl_global int *key_prefix_sum, GetKeyOp get_key_op)
ccl_device_inline void gpu_parallel_sort_write_pass_impl(const uint num_states, const uint partition_size, const int num_states_limit, ccl_global int *indices, const uint max_shaders, const uint queued_kernel, ccl_global ushort *d_queued_kernel, ccl_global uint *d_shader_sort_key, ccl_global int *partition_key_offsets)
#define min(a, b)
Definition sort.cc:38