MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
BitonicSorter.hpp
Go to the documentation of this file.
1#pragma once
2
3#include "StandardSorter.hpp"
4
7
8/**
9 * @file BitonicSorter.hpp
10 * @brief Exact GPU sorting of numeric channels by a bitonic network over order keys.
11 */
12
13namespace MayaFlux::Yantra {
14
15/**
16 * @class BitonicSorter
17 * @brief Sorts each numeric channel on the GPU, exactly, without fp64.
18 *
19 * The GPU candidate for the settings StandardSorter takes. Values are ordered
20 * through their order keys, so every double sorts exactly and the result
21 * matches a stable CPU sort: equal values keep their input order, -0.0 equals
22 * +0.0 and NaN sorts last, or first when descending. Every SortingAlgorithm is
23 * satisfied by the full sort, as are the in place, partial, parallel and index
24 * strategies, and the result is a sorted copy. The bidirectional order is the
25 * ascending sort laid out by Kinesis mountain_positions, and chunked sorting
26 * sorts each chunk on its own and concatenates them, as the CPU sorter does.
27 * order() gives the permutation of one channel.
28 *
29 * A custom comparator is host code and cannot run in a shader, so
30 * validate_input declines it and another candidate takes the call. fitness
31 * grows with the channel length and is zero while no device is up.
32 */
33template <ComputeData OutputType = std::vector<Kakshya::DataVariant>>
34class BitonicSorter : public Sorter<std::vector<Kakshya::DataVariant>, OutputType> {
35public:
40
41 static constexpr Target target = targets::vulkan;
42
43 /**
44 * @brief Channel length at which this candidate scores the same as a CPU sorter.
45 */
46 static constexpr size_t fitness_scale = 4096;
47
49 {
50 this->set_config(std::move(config));
51 }
52
53 [[nodiscard]] ConfigRefs configs() const override
54 {
55 return this->stored_configs(supports {});
56 }
57
58 [[nodiscard]] SortingType get_sorting_type() const override
59 {
61 }
62
63 /**
64 * @brief Longest channel over fitness_scale, or zero while no device is up.
65 */
66 static float fitness(const input_type& input)
67 {
69 return 0.0F;
70 }
71 size_t longest = 0;
72 for (const auto& channel : input.data) {
73 longest = std::max(longest, std::visit([](const auto& values) { return values.size(); }, channel));
74 }
75 return static_cast<float>(longest) / static_cast<float>(fitness_scale);
76 }
77
78 /**
79 * @brief False for a custom comparator, which cannot run on the device, and for chunked sorting with no chunk size.
80 */
81 bool validate_input(const input_type& /*input*/) const override
82 {
83 const auto& config = this->template config<StandardSorterConfig>();
84 const bool chunk_ok = config.strategy != SortingStrategy::CHUNKED_SORT || config.chunk_size > 0;
85 return config.direction != SortingDirection::CUSTOM && chunk_ok;
86 }
87
88 /**
89 * @brief The indices that order one channel, computed on the GPU in the configured direction.
90 * @return result[i] is the index in values of the i-th value in order. For the
91 * bidirectional order, result[i] is the value placed at position i.
92 */
93 [[nodiscard]] std::vector<size_t> order(std::span<const double> values)
94 {
95 const auto direction = this->template config<StandardSorterConfig>().direction;
96 const bool descending = direction == SortingDirection::DESCENDING;
97 const size_t count = values.size();
98 std::vector<size_t> result(count);
99 std::iota(result.begin(), result.end(), size_t { 0 });
100 if (count < 2) {
101 return result;
102 }
103
104 auto& executor = this->context();
105 const size_t padded = std::bit_ceil(count);
106 executor.stage_words(k_keys_binding, values, padded, descending);
107
108 std::vector<uint32_t> indices(padded);
109 std::iota(indices.begin(), indices.end(), uint32_t { 0 });
110 executor.set_binding_data(k_indices_binding, indices);
111
112 const auto stages = static_cast<uint32_t>(std::countr_zero(padded));
113 executor.set_multipass(stages * (stages + 1U) / 2U,
114 [padded](uint32_t pass_index, void* push) {
115 uint32_t level = 0;
116 uint32_t remaining = pass_index;
117 while (remaining > level) {
118 remaining -= level + 1U;
119 ++level;
120 }
121 const SortPush pc {
122 .stage = level + 1U,
123 .pass = level - remaining,
124 .count = static_cast<uint32_t>(padded),
125 .descending = 0U,
126 };
127 std::memcpy(push, &pc, sizeof(SortPush));
128 });
129
130 executor.execute(Datum<std::vector<Kakshya::DataVariant>> {}, ExecutionContext {});
131
132 const auto sorted = executor.primary_words();
133 if (sorted.size() < count) {
135 std::source_location::current(), "BitonicSorter: the sort returned {} of {} indices",
136 sorted.size(), count);
137 }
138 std::copy_n(sorted.begin(), count, result.begin());
139
140 if (direction == SortingDirection::BIDIRECTIONAL) {
141 const auto positions = Kinesis::Discrete::mountain_positions(count);
142 std::vector<size_t> placed(count);
143 for (size_t rank = 0; rank < count; ++rank) {
144 placed[positions[rank]] = result[rank];
145 }
146 return placed;
147 }
148 return result;
149 }
150
151protected:
153 {
154 std::vector<std::vector<double>> working;
155 auto [channels, structure_info] = OperationHelper::setup_operation_buffer(
156 const_cast<input_type&>(input), working);
157
158 const auto& config = this->template config<StandardSorterConfig>();
159 const bool chunked = config.strategy == SortingStrategy::CHUNKED_SORT;
160 for (auto& channel : channels) {
161 const size_t segment = std::max<size_t>(chunked ? config.chunk_size : channel.size(), 1);
162 for (size_t start = 0; start < channel.size(); start += segment) {
163 arrange(channel.subspan(start, std::min(segment, channel.size() - start)));
164 }
165 }
166
167 output_type result = this->convert_result(working, structure_info);
168 result.metadata = input.metadata;
169 result.facets = input.facets;
171 return result;
172 }
173
174private:
175 struct SortPush {
176 uint32_t stage;
177 uint32_t pass;
178 uint32_t count;
179 uint32_t descending;
180 };
181
182 static constexpr uint32_t k_keys_binding = 0;
183 static constexpr uint32_t k_indices_binding = 1;
184
185 /**
186 * @brief Reorders a segment in place by its GPU permutation.
187 */
188 void arrange(std::span<double> segment)
189 {
190 const auto permutation = order(segment);
191 const std::vector<double> original(segment.begin(), segment.end());
192 for (size_t i = 0; i < permutation.size(); ++i) {
193 segment[i] = original[permutation[i]];
194 }
195 }
196
197 void record_sort(output_type& out, SortPath path) const
198 {
200 record.config = this->template config<StandardSorterConfig>();
201 record.path = path;
202 out.facets.set(record);
203 }
204
205 /**
206 * @brief The context, built on first use so a sorter can be created before any device.
207 */
209 {
210 if (!m_context) {
211 const auto spec = sort_spec();
212 auto bindings = bindings_from_spec(spec);
213 std::ranges::rotate(bindings, bindings.begin() + 1);
214 m_context = std::make_shared<WordPairExecutionContext>(
215 config_from_spec(spec), std::move(bindings), true, "BitonicSorter");
216 }
217 return *m_context;
218 }
219
221 {
225 .tmpl(KernelTemplate::BitonicSort)
226 .ssbo("keys", BindingDirection::InOut, Kakshya::GpuDataFormat::VEC2_U32)
227 .ssbo("indices", BindingDirection::InOut, Kakshya::GpuDataFormat::UINT32)
231 .pc("descending", Kakshya::GpuDataFormat::UINT32)
232 .build();
233 }
234
235 std::shared_ptr<WordPairExecutionContext> m_context;
236};
237
238} // namespace MayaFlux::Yantra
Example concrete implementation of Sorter.
Runs a shader on doubles carried as two 32-bit words, with no fp64 on the device.
ShaderSpec build()
Finalise and return the ShaderSpec.
Assemble & pc(std::string name, Kakshya::GpuDataFormat format)
Declare a push constant field with explicit format.
Assemble & ssbo(std::string name, BindingDirection direction, Kakshya::GpuDataFormat format, Kakshya::DataModality modality=Kakshya::DataModality::SCALAR_F32)
Declare an SSBO binding.
Assemble & tmpl(KernelTemplate t)
Set the kernel template.
Fluent assembler producing a ShaderSpec.
WordPairExecutionContext & context()
The context, built on first use so a sorter can be created before any device.
ConfigRefs configs() const override
The base view of the config structs this operation holds.
static constexpr uint32_t k_indices_binding
static constexpr uint32_t k_keys_binding
void record_sort(output_type &out, SortPath path) const
static float fitness(const input_type &input)
Longest channel over fitness_scale, or zero while no device is up.
std::vector< size_t > order(std::span< const double > values)
The indices that order one channel, computed on the GPU in the configured direction.
Sorter< std::vector< Kakshya::DataVariant >, OutputType > base_type
Supports< StandardSorterConfig > supports
output_type sort_implementation(const input_type &input) override
Pure virtual sorting implementation - derived classes implement this.
typename base_type::output_type output_type
SortingType get_sorting_type() const override
Gets the sorting type category for this sorter.
bool validate_input(const input_type &) const override
False for a custom comparator, which cannot run on the device, and for chunked sorting with no chunk ...
std::shared_ptr< WordPairExecutionContext > m_context
BitonicSorter(StandardSorterConfig config={})
static constexpr size_t fitness_scale
Channel length at which this candidate scores the same as a CPU sorter.
void arrange(std::span< double > segment)
Reorders a segment in place by its GPU permutation.
typename base_type::input_type input_type
static Portal::Graphics::ShaderSpec sort_spec()
static constexpr Target target
const Config & config() const
The stored config struct of type Config, or its defaults when none was set.
void set_config(Config config)
Stores a config struct, whole, under its own type.
ConfigRefs stored_configs(Supports< Configs... >) const
The stored configs among those listed, in listed order.
output_type convert_result(std::vector< std::vector< double > > &result_data, DataStructureInfo &metadata)
Convert processed double data back to OutputType using metadata and optional callback.
static auto setup_operation_buffer(T &input, std::vector< std::vector< double > > &working_buffer)
Setup operation buffer from Datum or ComputeData type.
Template-flexible sorter base with instance-defined I/O types.
Definition Sorter.hpp:106
Shader context whose numeric input is staged as a uvec2 per double.
@ BufferProcessing
Buffer processing (Buffers::BufferManager, processing chains).
@ Yantra
DSP algorithms, computational units, matrix operations, Grammar.
@ VEC2_U32
glm::uvec2: a 64-bit value as low word (x) and high word (y), not a sampled image format
std::vector< size_t > mountain_positions(size_t count)
Target position of each rank in a mountain arrangement of count values.
Definition Sort.cpp:22
KernelTemplate
Structural shape of the generated compute kernel.
MAYAFLUX_API ShaderFoundry & get_shader_foundry()
Get the global shader compiler instance.
BindingDirection
Data flow direction for a shader binding slot.
bool is_initialized()
Check if Portal::Graphics is initialized.
Definition Graphics.cpp:109
@ CHUNKED_SORT
Sort in chunks for large datasets.
Definition Sorter.hpp:77
SortingType
Categories of sorting operations for discovery and organization.
Definition Sorter.hpp:55
@ ALGORITHMIC
Mathematical/computational sorting algorithms.
Definition Sorter.hpp:57
GpuComputeConfig config_from_spec(const Portal::Graphics::ShaderSpec &spec)
Derive a GpuComputeConfig from a ShaderSpec.
std::vector< std::reference_wrapper< const OperationConfig > > ConfigRefs
Borrowed views of the configs an operation holds.
std::vector< GpuBufferBinding > bindings_from_spec(const Portal::Graphics::ShaderSpec &spec)
Derive a GpuBufferBinding list from a ShaderSpec.
SortPath
Which sorting path produced a result.
@ CHUNKED_MERGED
Sorted per chunk, then merged.
@ COPY
Sorted copy of the input.
std::pair< std::shared_ptr< Kriya::BufferPipeline >, std::shared_ptr< Buffers::AudioBuffer > > record(const std::shared_ptr< Kakshya::DynamicSoundStream > &stream, uint32_t input_channel, double seconds, std::optional< uint32_t > monitor, uint32_t channel)
Record a live input channel into a stream for a number of seconds.
Definition Rigs.cpp:262
Complete declarative description of a generated compute shader.
Input/Output container for computation pipeline data flow with structure preservation.
Definition DataIO.hpp:63
Context information controlling how a compute operation executes.
Reflect::EnumByte< SortPath > path
The sorting path that produced the result.
Record of one StandardSorter run, stored on the output's facets.
Settings for standard sorting.
The config structs an operation class accepts, declared as using supports.
A set of (device, runtime) pairs.