33template <ComputeData OutputType = std::vector<Kakshya::DataVariant>>
72 for (
const auto& channel : input.data) {
73 longest = std::max(longest, std::visit([](
const auto& values) {
return values.size(); }, channel));
75 return static_cast<float>(longest) /
static_cast<float>(
fitness_scale);
85 return config.direction != SortingDirection::CUSTOM && chunk_ok;
93 [[nodiscard]] std::vector<size_t>
order(std::span<const double> values)
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 });
104 auto& executor = this->
context();
105 const size_t padded = std::bit_ceil(count);
108 std::vector<uint32_t> indices(padded);
109 std::iota(indices.begin(), indices.end(), uint32_t { 0 });
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) {
116 uint32_t remaining = pass_index;
117 while (remaining > level) {
118 remaining -= level + 1U;
123 .pass = level - remaining,
124 .count =
static_cast<uint32_t
>(padded),
127 std::memcpy(push, &pc,
sizeof(
SortPush));
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);
138 std::copy_n(sorted.begin(), count, result.begin());
140 if (direction == SortingDirection::BIDIRECTIONAL) {
142 std::vector<size_t> placed(count);
143 for (
size_t rank = 0; rank < count; ++rank) {
144 placed[positions[rank]] = result[rank];
154 std::vector<std::vector<double>> working;
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)));
168 result.metadata = input.metadata;
169 result.facets = input.facets;
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]];
213 std::ranges::rotate(bindings, bindings.begin() + 1);
214 m_context = std::make_shared<WordPairExecutionContext>(
225 .
tmpl(KernelTemplate::BitonicSort)
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.
Datum< OutputType > output_type
Datum< InputType > input_type
Template-flexible sorter base with instance-defined I/O types.
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.
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.
@ CHUNKED_SORT
Sort in chunks for large datasets.
SortingType
Categories of sorting operations for discovery and organization.
@ ALGORITHMIC
Mathematical/computational sorting algorithms.
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.
Complete declarative description of a generated compute shader.
Input/Output container for computation pipeline data flow with structure preservation.
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.