Commit adf554d23 for llama.cpp
commit adf554d2392ab490a0552abbbbe88a1d317c1a2e
Author: Pascal <admin@serveurperso.com>
Date: Mon Nov 16 11:41:44 2026 +0100
vulkan: make the radix top-k tie selection deterministic (#31931)
* vulkan: make the radix top-k tie selection deterministic
The radix select gathers the elements above the threshold and the ties
with an atomic counter, so with more ties than remaining slots the kept
columns depend on the thread scheduling.
Each subgroup now owns a contiguous chunk of the row with the same
column mapping in every pass, counts its kept elements, and writes them
at ranks from a scan of the subgroup totals; overflowing ties are ranked
in column order with a ballot, so the lowest tied columns win, as on
CUDA and Metal. The radix pipelines require subgroup arithmetic, ballot
and full subgroups. Enable the deterministic top-k check on Vulkan.
* optimize shader for AMD, Intel and Nvidia
---------
Co-authored-by: Ruben Ortlam <rortlam@redhat.com>
diff --git a/ggml/src/ggml-vulkan/ggml-vulkan.cpp b/ggml/src/ggml-vulkan/ggml-vulkan.cpp
index 1af36cdca..f03aa3e44 100644
--- a/ggml/src/ggml-vulkan/ggml-vulkan.cpp
+++ b/ggml/src/ggml-vulkan/ggml-vulkan.cpp
@@ -3886,8 +3886,16 @@ void ggml_vk_load_shaders(vk_device& device, vk_pipeline requested) {
// variant (spec constant 1) additionally gathers the qwen4 indexer input on the fly.
{
const uint32_t BLOCK_SIZE = 1u << std::min(10u, device->max_workgroup_size_log2);
- ggml_vk_create_pipeline2(device, device->pipeline_topk_radix_f32, "topk_radix_f32", topk_radix_select_f32_len, topk_radix_select_f32_data, "main", 5, sizeof(vk_op_topk_radix_push_constants), {BLOCK_SIZE, 1, 1}, {BLOCK_SIZE, 0}, 1, true);
- ggml_vk_create_pipeline2(device, device->pipeline_topk_radix_qsa, "topk_radix_qsa", topk_radix_select_f32_len, topk_radix_select_f32_data, "main", 5, sizeof(vk_op_topk_radix_push_constants), {BLOCK_SIZE, 1, 1}, {BLOCK_SIZE, 1}, 1, true);
+ // the bucket scan needs one invocation per radix bucket
+ if (BLOCK_SIZE >= 256) {
+ if (device->subgroup_arithmetic && device->subgroup_require_full_support) {
+ ggml_vk_create_pipeline2(device, device->pipeline_topk_radix_f32, "topk_radix_f32", topk_radix_select_f32_subgroup_len, topk_radix_select_f32_subgroup_data, "main", 5, sizeof(vk_op_topk_radix_push_constants), {BLOCK_SIZE, 1, 1}, {BLOCK_SIZE, 0, device->subgroup_size}, 1, true, true, device->subgroup_size);
+ ggml_vk_create_pipeline2(device, device->pipeline_topk_radix_qsa, "topk_radix_qsa", topk_radix_select_f32_subgroup_len, topk_radix_select_f32_subgroup_data, "main", 5, sizeof(vk_op_topk_radix_push_constants), {BLOCK_SIZE, 1, 1}, {BLOCK_SIZE, 1, device->subgroup_size}, 1, true, true, device->subgroup_size);
+ } else {
+ ggml_vk_create_pipeline2(device, device->pipeline_topk_radix_f32, "topk_radix_f32", topk_radix_select_f32_len, topk_radix_select_f32_data, "main", 5, sizeof(vk_op_topk_radix_push_constants), {BLOCK_SIZE, 1, 1}, {BLOCK_SIZE, 0}, 1, true);
+ ggml_vk_create_pipeline2(device, device->pipeline_topk_radix_qsa, "topk_radix_qsa", topk_radix_select_f32_len, topk_radix_select_f32_data, "main", 5, sizeof(vk_op_topk_radix_push_constants), {BLOCK_SIZE, 1, 1}, {BLOCK_SIZE, 1}, 1, true);
+ }
+ }
}
ggml_vk_create_pipeline(device, device->pipeline_argmax_f32, "argmax_f32", argmax_f32_len, argmax_f32_data, "main", 2, sizeof(vk_op_push_constants), {1, 1, 1}, { device->subgroup_size }, 1);
diff --git a/ggml/src/ggml-vulkan/vulkan-shaders/topk_radix_select.comp b/ggml/src/ggml-vulkan/vulkan-shaders/topk_radix_select.comp
index 8e14b2e99..4ba656ec9 100644
--- a/ggml/src/ggml-vulkan/vulkan-shaders/topk_radix_select.comp
+++ b/ggml/src/ggml-vulkan/vulkan-shaders/topk_radix_select.comp
@@ -2,11 +2,20 @@
#extension GL_EXT_control_flow_attributes : enable
#extension GL_EXT_shader_16bit_storage : require
+#if USE_SUBGROUPS
+#extension GL_KHR_shader_subgroup_basic : enable
+#extension GL_KHR_shader_subgroup_arithmetic : enable
+#endif
#include "types.glsl"
layout(constant_id = 0) const int BLOCK_SIZE = 1024;
layout(constant_id = 1) const int QSA = 0; // 1: fuse the qwen4 QSA indexer gather + f16 mask
+#if USE_SUBGROUPS
+layout(constant_id = 2) const int SUBGROUP_SIZE = 32;
+
+const uint NUM_SUBGROUPS = BLOCK_SIZE / SUBGROUP_SIZE;
+#endif
layout(local_size_x_id = 0, local_size_y = 1, local_size_z = 1) in;
@@ -26,12 +35,19 @@ layout (push_constant) uniform parameter {
} p;
#define RADIX_BITS 8
+#define UNROLL 4
#define RADIX_SIZE (1 << RADIX_BITS)
shared uint histo[RADIX_SIZE];
shared uint sh_bucket;
shared uint sh_above;
+shared uint sh_tied;
shared uint out_count;
+#if USE_SUBGROUPS
+shared uint sg_tied[NUM_SUBGROUPS];
+#else
+shared uint tie_scan[2 * BLOCK_SIZE];
+#endif
// order-preserving float -> uint mapping
uint f2ui(float x) {
@@ -87,52 +103,155 @@ void topk(const uint row) {
const bool first = (shift == 32 - RADIX_BITS);
const uint hi_mask = (shift + RADIX_BITS >= 32) ? 0u : (0xFFFFFFFFu << uint(shift + RADIX_BITS));
const uint prefix_hi = prefix & hi_mask;
- for (uint i = tid; i < ncols; i += BLOCK_SIZE) {
- const uint key = f2ui(load(row, i, first));
- if ((key & hi_mask) == prefix_hi) {
- atomicAdd(histo[(key >> uint(shift)) & (RADIX_SIZE - 1)], 1u);
+ uint run_b = RADIX_SIZE;
+ uint run_n = 0;
+ for (uint i0 = tid; i0 < ncols; i0 += UNROLL * BLOCK_SIZE) {
+ uint keys[UNROLL];
+ [[unroll]] for (uint u = 0; u < UNROLL; ++u) {
+ const uint i = i0 + u * BLOCK_SIZE;
+ keys[u] = f2ui(load(row, min(i, ncols - 1), first));
+ }
+ [[unroll]] for (uint u = 0; u < UNROLL; ++u) {
+ const uint key = keys[u];
+ if (i0 + u * BLOCK_SIZE < ncols && (key & hi_mask) == prefix_hi) {
+ const uint b = (key >> uint(shift)) & (RADIX_SIZE - 1);
+ if (b != run_b) {
+ if (run_n != 0) {
+ atomicAdd(histo[run_b], run_n);
+ }
+ run_b = b;
+ run_n = 0;
+ }
+ run_n++;
+ }
}
}
+ if (run_n != 0) {
+ atomicAdd(histo[run_b], run_n);
+ }
barrier();
// top-down scan for the bucket holding the K-th value
- if (tid == 0) {
- uint acc = 0;
- uint b = 0;
- for (int bb = RADIX_SIZE - 1; bb >= 0; --bb) {
- const uint c = histo[bb];
- if (acc + c >= desired) { b = uint(bb); break; }
- acc += c;
+#if USE_SUBGROUPS
+ uint c = 0, incl = 0;
+ if (tid < RADIX_SIZE) {
+ c = histo[RADIX_SIZE - 1 - tid];
+ incl = subgroupInclusiveAdd(c);
+ if (gl_SubgroupInvocationID == gl_SubgroupSize - 1) {
+ sg_tied[gl_SubgroupID] = incl;
+ }
+ }
+ barrier();
+ if (tid < RADIX_SIZE) {
+ for (uint s = 0; s < gl_SubgroupID; ++s) {
+ incl += sg_tied[s];
+ }
+ if (incl - c < desired && incl >= desired) {
+ sh_bucket = RADIX_SIZE - 1 - tid;
+ sh_above = incl - c;
+ sh_tied = c;
+ }
+ }
+ barrier();
+#else
+ uint c = 0;
+ if (tid < RADIX_SIZE) {
+ c = histo[RADIX_SIZE - 1 - tid];
+ tie_scan[tid] = c;
+ }
+ barrier();
+ uint src = 0;
+ [[unroll]] for (uint off = 1; off < RADIX_SIZE; off <<= 1) {
+ if (tid < RADIX_SIZE) {
+ const uint v = tie_scan[src + tid];
+ tie_scan[(RADIX_SIZE - src) + tid] = tid >= off ? v + tie_scan[src + tid - off] : v;
+ }
+ src = RADIX_SIZE - src;
+ barrier();
+ }
+ if (tid < RADIX_SIZE) {
+ const uint incl = tie_scan[src + tid];
+ if (incl - c < desired && incl >= desired) {
+ sh_bucket = RADIX_SIZE - 1 - tid;
+ sh_above = incl - c;
+ sh_tied = c;
}
- sh_bucket = b;
- sh_above = acc;
}
barrier();
+#endif
prefix |= sh_bucket << uint(shift);
desired -= sh_above;
barrier();
}
+ const uint threshold = prefix;
+ const bool all_ties = sh_tied == desired;
+
if (tid == 0) {
out_count = 0;
}
barrier();
- // emit everything above the threshold, then fill the rest from ties
- const uint threshold = prefix;
+ if (all_ties) {
+ for (uint i = tid; i < ncols; i += BLOCK_SIZE) {
+ if (f2ui(load(row, i, false)) >= threshold) {
+ data_d[row_out + atomicAdd(out_count, 1u)] = int(i);
+ }
+ }
+ return;
+ }
+
+ // more ties than slots: rank them in invocation order, which does not depend on the scheduling
+ uint ct = 0;
for (uint i = tid; i < ncols; i += BLOCK_SIZE) {
- if (f2ui(load(row, i, false)) > threshold) {
+ const uint key = f2ui(load(row, i, false));
+ if (key > threshold) {
data_d[row_out + atomicAdd(out_count, 1u)] = int(i);
}
+ ct += key == threshold ? 1u : 0u;
+ }
+#if USE_SUBGROUPS
+ const uint sg = gl_SubgroupID;
+ const uint st = subgroupAdd(ct);
+ if (subgroupElect()) {
+ sg_tied[sg] = st;
}
barrier();
- for (uint i = tid; i < ncols; i += BLOCK_SIZE) {
- if (f2ui(load(row, i, false)) == threshold) {
- const uint pos = atomicAdd(out_count, 1u);
- if (pos < p.k) {
- data_d[row_out + pos] = int(i);
+
+ if (sg == 0) {
+ const uint lane = gl_SubgroupInvocationID;
+ uint acc = 0;
+ for (uint c0 = 0; c0 < NUM_SUBGROUPS; c0 += SUBGROUP_SIZE) {
+ const uint c = c0 + lane;
+ const uint t = c < NUM_SUBGROUPS ? sg_tied[c] : 0u;
+ const uint e = subgroupExclusiveAdd(t);
+ if (c < NUM_SUBGROUPS) {
+ sg_tied[c] = acc + e;
}
+ acc += subgroupAdd(t);
+ }
+ }
+ barrier();
+
+ uint pos = p.k - desired + sg_tied[sg] + subgroupExclusiveAdd(ct);
+#else
+ // inclusive Hillis-Steele scan, ping-ponging between the two halves
+ uint src = 0;
+ tie_scan[tid] = ct;
+ barrier();
+ for (uint off = 1; off < BLOCK_SIZE; off <<= 1) {
+ const uint v = tie_scan[src + tid];
+ tie_scan[(BLOCK_SIZE - src) + tid] = tid >= off ? v + tie_scan[src + tid - off] : v;
+ src = BLOCK_SIZE - src;
+ barrier();
+ }
+ uint pos = p.k - desired + tie_scan[src + tid] - ct;
+#endif
+ const uint pos_end = min(p.k, pos + ct);
+ for (uint i = tid; i < ncols && pos < pos_end; i += BLOCK_SIZE) {
+ if (f2ui(load(row, i, false)) == threshold) {
+ data_d[row_out + pos++] = int(i);
}
}
}
diff --git a/ggml/src/ggml-vulkan/vulkan-shaders/vulkan-shaders-gen.cpp b/ggml/src/ggml-vulkan/vulkan-shaders/vulkan-shaders-gen.cpp
index 52e5f0440..3952030fb 100644
--- a/ggml/src/ggml-vulkan/vulkan-shaders/vulkan-shaders-gen.cpp
+++ b/ggml/src/ggml-vulkan/vulkan-shaders/vulkan-shaders-gen.cpp
@@ -1115,6 +1115,7 @@ void process_shaders() {
string_to_spv("topk_argsort_f32", "topk_argsort.comp", {{"A_TYPE", "float"}});
string_to_spv("topk_nary_search_f32", "topk_nary_search.comp", {{"A_TYPE", "float"}});
string_to_spv("topk_radix_select_f32", "topk_radix_select.comp", {{"A_TYPE", "float"}});
+ string_to_spv("topk_radix_select_f32_subgroup", "topk_radix_select.comp", {{"A_TYPE", "float"}, {"USE_SUBGROUPS", "1"}});
string_to_spv("argmax_f32", "argmax.comp", merge_maps(base_dict, {{"A_TYPE", "float"}, {"D_TYPE", "int"}}));
string_to_spv("sum_rows_f32", "sum_rows.comp", merge_maps(base_dict, {{"A_TYPE", "float"}, {"D_TYPE", "float"}}));
diff --git a/tests/test-backend-ops.cpp b/tests/test-backend-ops.cpp
index 4db0d6843..0a1b592d5 100644
--- a/tests/test-backend-ops.cpp
+++ b/tests/test-backend-ops.cpp
@@ -7496,10 +7496,10 @@ struct test_top_k : public test_case {
// the backends may break ties in different ways, but each backend must break them in the same way in each run
bool deterministic(ggml_backend_t backend) override {
- // TODO: Vulkan is not deterministic yet, SYCL gathers the ties with an atomic counter as well
+ // TODO: SYCL is not deterministic yet, it gathers the ties with an atomic counter
const char * name = ggml_backend_reg_name(ggml_backend_dev_backend_reg(ggml_backend_get_device(backend)));
- // ROCm has no cub::DeviceTopK, every row goes through the radix or bitonic path
- if (strcmp(name, "ROCm") == 0) {
+ // ROCm and Vulkan have no cub::DeviceTopK, every row goes through their own deterministic paths
+ if (strcmp(name, "ROCm") == 0 || strcmp(name, "Vulkan") == 0) {
return ties;
}
if (strcmp(name, "CUDA") != 0 && strcmp(name, "MTL") != 0) {
@@ -7673,11 +7673,12 @@ struct test_topk_qsa : public test_case {
}
std::string vars() override {
- return VARS_TO_STR5(n_blocks, n_kv, n_tps, n_stream, width);
+ return VARS_TO_STR6(n_blocks, n_kv, n_tps, n_stream, width, tied);
}
- test_topk_qsa(int64_t n_blocks = 512, int64_t n_kv = 2048, int64_t n_tps = 2, int64_t n_stream = 1, int width = 1500)
- : n_blocks(n_blocks), n_kv(n_kv), n_tps(n_tps), n_stream(n_stream), width(width) {}
+ const bool tied;
+ test_topk_qsa(int64_t n_blocks = 512, int64_t n_kv = 2048, int64_t n_tps = 2, int64_t n_stream = 1, int width = 1500, bool tied = false)
+ : n_blocks(n_blocks), n_kv(n_kv), n_tps(n_tps), n_stream(n_stream), width(width), tied(tied) {}
double max_err() override { return 0.0; }
bool run_whole_graph() override { return true; }
@@ -7710,13 +7711,13 @@ struct test_topk_qsa : public test_case {
}
if (t->type == GGML_TYPE_I32) {
std::vector<int32_t> data(ggml_nelements(t));
- for (auto & v : data) { v = rand() % n_blocks; }
+ for (size_t i = 0; i < data.size(); i++) { data[i] = tied ? (int32_t) ((i % n_kv) * n_blocks / n_kv) : rand() % n_blocks; }
ggml_backend_tensor_set(t, data.data(), 0, data.size() * sizeof(int32_t));
} else if (t->type == GGML_TYPE_F16) {
std::vector<ggml_fp16_t> data(ggml_nelements(t));
for (int64_t r = 0; r < ggml_nrows(t); r++) {
for (int64_t i = 0; i < n_kv; i++) {
- data[r * n_kv + i] = ggml_fp32_to_fp16((float) i);
+ data[r * n_kv + i] = ggml_fp32_to_fp16(tied ? 0.0f : (float) i);
}
}
ggml_backend_tensor_set(t, data.data(), 0, data.size() * sizeof(ggml_fp16_t));
@@ -14032,8 +14033,13 @@ static std::vector<std::unique_ptr<test_case>> make_test_cases_perf() {
for (auto cols : {8192, 32768, 131072}) {
for (auto nrows : {1, 2, 4, 8, 16, 32}) {
test_cases.emplace_back(new test_top_k(GGML_TYPE_F32, {cols, nrows, 1, 1}, 2048));
+ test_cases.emplace_back(new test_top_k(GGML_TYPE_F32, {cols, nrows, 1, 1}, 2048, true));
}
}
+ for (int n_tps : {1, 16, 64}) {
+ test_cases.emplace_back(new test_topk_qsa(516, 33024, n_tps, 1, 2051, true));
+ test_cases.emplace_back(new test_topk_qsa(2064, 132096, n_tps, 1, 2051, true));
+ }
// bitonic vs radix crossover
for (auto cols : {520, 1000, 2048, 3000, 4096}) {
for (auto nrows : {2, 16, 32, 48, 64, 128, 256, 512}) {