| 1 | // SPDX-License-Identifier: Apache-2.0 |
| 2 | // SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | |
| 4 | // Sampled top-k for long FP32 sparse-indexer rows, inspired by DeepSelect: |
| 5 | // https://github.com/deepseek-ai/DeepSelect |
| 6 | // A sample estimates a cutoff, then survivors are compacted in shared memory |
| 7 | // for exact FP32 selection. Too few or too many candidates trigger an exact |
| 8 | // full-row fallback. |
| 9 | |
| 10 | #pragma once |
| 11 | |
| 12 | #include <cub/cub.cuh> |
| 13 | #include <cuda_runtime.h> |
| 14 | #include <cstdint> |
| 15 | |
| 16 | #include "persistent_topk.cuh" |
| 17 | |
| 18 | namespace vllm::sampled_topk { |
| 19 | |
| 20 | constexpr int kThreads = 1024; |
| 21 | // Conservative crossover bounds from the B300 batch/length sweep. |
| 22 | template <int K> |
| 23 | constexpr int kMinSampledLength = K == 512 ? 98304 : 65536; |
| 24 | // Target half the buffer to leave room for sampling error. |
| 25 | constexpr int kSample = 4096; |
| 26 | constexpr int kCapacity = 8192; |
| 27 | |
| 28 | struct Storage { |
| 29 | uint2 candidates[kCapacity]; |
| 30 | int histogram[2048]; |
| 31 | typename cub::BlockScan<int, kThreads>::TempStorage scan; |
| 32 | int count; |
| 33 | int remaining; |
| 34 | int bin; |
| 35 | uint32_t prefix; |
| 36 | }; |
| 37 | |
| 38 | __device__ __forceinline__ uint32_t ordered(float value) { |
| 39 | const uint32_t bits = __float_as_uint(value); |
| 40 | return (bits & 0x80000000u) ? ~bits : (bits | 0x80000000u); |
| 41 | } |
| 42 | |
| 43 | __device__ __forceinline__ uint32_t coarse(uint32_t key) { |
| 44 | const uint32_t bits = (key & 0x80000000u) ? (key ^ 0x80000000u) : ~key; |
| 45 | return topk_histogram_4096::extract_coarse_bin_N<11>(__uint_as_float(bits)); |
| 46 | } |
| 47 | |
| 48 | // Select the bin containing the rank and update the rank within that bin. |
| 49 | template <int Bins> |
| 50 | __device__ void select_bin(Storage& s) { |
| 51 | constexpr int kItems = (Bins + kThreads - 1) / kThreads; |
| 52 | int sums[kItems]; |
| 53 | #pragma unroll |
| 54 | for (int j = 0; j < kItems; ++j) { |
| 55 | const int bin = Bins - 1 - (threadIdx.x * kItems + j); |
| 56 | sums[j] = bin >= 0 ? s.histogram[bin] : 0; |
| 57 | } |
| 58 | cub::BlockScan<int, kThreads>(s.scan).InclusiveSum(sums, sums); |
| 59 | const int remaining = s.remaining; |
| 60 | __syncthreads(); |
| 61 | #pragma unroll |
| 62 | for (int j = 0; j < kItems; ++j) { |
| 63 | const int bin = Bins - 1 - (threadIdx.x * kItems + j); |
| 64 | if (bin >= 0 && sums[j] >= remaining && |
| 65 | sums[j] - s.histogram[bin] < remaining) { |
| 66 | s.bin = bin; |
| 67 | s.remaining = remaining - (sums[j] - s.histogram[bin]); |
| 68 | } |
| 69 | } |
| 70 | __syncthreads(); |
| 71 | } |
| 72 | |
| 73 | // Find a coarse bin, then refine its full FP32 keys one byte at a time. |
| 74 | // Read shared candidates normally, or the full row for exact fallback. |
| 75 | template <bool Buffered> |
| 76 | __device__ uint32_t threshold(Storage& s, const float* row, int count, |
| 77 | int rank) { |
| 78 | const int tid = threadIdx.x; |
| 79 | if (tid == 0) { |
| 80 | s.remaining = rank; |
| 81 | s.prefix = 0; |
| 82 | } |
| 83 | for (int i = tid; i < 2048; i += kThreads) s.histogram[i] = 0; |
| 84 | __syncthreads(); |
| 85 | for (int i = tid; i < count; i += kThreads) { |
| 86 | const uint32_t key = Buffered ? s.candidates[i].y : ordered(row[i]); |
| 87 | atomicAdd(&s.histogram[coarse(key)], 1); |
| 88 | } |
| 89 | __syncthreads(); |
| 90 | select_bin<2048>(s); |
| 91 | const int coarse_bin = s.bin; |
| 92 | uint32_t mask = 0; |
| 93 | for (int shift = 24; shift >= 0; shift -= 8) { |
| 94 | if (tid < 256) s.histogram[tid] = 0; |
| 95 | __syncthreads(); |
| 96 | const uint32_t prefix = s.prefix; |
| 97 | for (int i = tid; i < count; i += kThreads) { |
| 98 | const uint32_t key = Buffered ? s.candidates[i].y : ordered(row[i]); |
| 99 | if (coarse(key) == coarse_bin && (key & mask) == prefix) { |
| 100 | atomicAdd(&s.histogram[(key >> shift) & 255], 1); |
| 101 | } |
| 102 | } |
| 103 | __syncthreads(); |
| 104 | select_bin<256>(s); |
| 105 | if (tid == 0) s.prefix = prefix | (static_cast<uint32_t>(s.bin) << shift); |
| 106 | mask |= 255u << shift; |
| 107 | __syncthreads(); |
| 108 | } |
| 109 | return s.prefix; |
| 110 | } |
| 111 | |
| 112 | __device__ __forceinline__ int reserve(bool hit, int* counter) { |
| 113 | const uint32_t mask = __ballot_sync(0xffffffffu, hit); |
| 114 | if (mask == 0) return 0; |
| 115 | const int lane = threadIdx.x & 31; |
| 116 | int base = 0; |
| 117 | if (lane == 0) base = atomicAdd(counter, __popc(mask)); |
| 118 | base = __shfl_sync(0xffffffffu, base, 0); |
| 119 | return base + __popc(mask & ((1u << lane) - 1)); |
| 120 | } |
| 121 | |
| 122 | template <bool Buffered> |
| 123 | __device__ void emit(Storage& s, const float* row, int32_t* dst, int count, |
| 124 | uint32_t cutoff) { |
| 125 | const int tid = threadIdx.x; |
| 126 | if (tid == 0) s.count = 0; |
| 127 | __syncthreads(); |
| 128 | for (int base = 0; base < count; base += kThreads) { |
| 129 | const int i = base + tid; |
| 130 | const uint2 pair = i < count ? (Buffered ? s.candidates[i] |
| 131 | : make_uint2(i, ordered(row[i]))) |
| 132 | : make_uint2(0, 0); |
| 133 | bool keep = i < count && pair.y > cutoff; |
| 134 | if (i < count && pair.y == cutoff) { |
| 135 | keep = atomicSub(&s.remaining, 1) > 0; |
| 136 | } |
| 137 | const int offset = reserve(keep, &s.count); |
| 138 | if (keep) dst[offset] = pair.x; |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | template <int K> |
| 143 | __global__ void __launch_bounds__(kThreads) |
| 144 | sampled_topk_kernel(const float* __restrict__ input, |
| 145 | const int32_t* __restrict__ lengths, |
| 146 | int32_t* __restrict__ output, int64_t stride, |
| 147 | int max_length) { |
| 148 | extern __shared__ __align__(16) unsigned char smem[]; |
| 149 | auto& s = *reinterpret_cast<Storage*>(smem); |
| 150 | const int tid = threadIdx.x; |
| 151 | const int length = max(0, min(lengths[blockIdx.x], max_length)); |
| 152 | const float* row = input + blockIdx.x * stride; |
| 153 | int32_t* dst = output + blockIdx.x * K; |
| 154 | // Graph allocations can hold rows much shorter than the host length bound. |
| 155 | if (length < kMinSampledLength<K>) { |
| 156 | __shared__ filtered_topk::FilteredTopKStorage<K> fallback_storage; |
| 157 | bool selected; |
| 158 | if ((stride & 3) == 0 && (reinterpret_cast<uintptr_t>(row) & 15) == 0) { |
| 159 | selected = |
| 160 | filtered_topk::filtered_topk_row<float, int32_t, 4, K, false, true>( |
| 161 | row, dst, length, K, fallback_storage); |
| 162 | } else { |
| 163 | selected = |
| 164 | filtered_topk::filtered_topk_row<float, int32_t, 1, K, true, true>( |
| 165 | row, dst, length, K, fallback_storage); |
| 166 | } |
| 167 | if (!selected) { |
| 168 | const uint32_t exact_cutoff = threshold<false>(s, row, length, K); |
| 169 | emit<false>(s, row, dst, length, exact_cutoff); |
| 170 | } |
| 171 | return; |
| 172 | } |
| 173 | if (tid == 0) s.remaining = max(1, (kCapacity / 2) * kSample / length); |
| 174 | for (int i = tid; i < 2048; i += kThreads) s.histogram[i] = 0; |
| 175 | __syncthreads(); |
| 176 | // Sample contiguous warps spread across the row to keep loads coalesced. |
| 177 | for (int i = tid; i < kSample; i += kThreads) { |
| 178 | const int index = (i / 32) * (length / (kSample / 32)) + i % 32; |
| 179 | atomicAdd(&s.histogram[coarse(ordered(row[index]))], 1); |
| 180 | } |
| 181 | __syncthreads(); |
| 182 | select_bin<2048>(s); |
| 183 | const uint16_t half_key = s.bin << 5; |
| 184 | const uint16_t half_bits = |
| 185 | (half_key & 0x8000u) ? (half_key ^ 0x8000u) : ~half_key; |
| 186 | const uint32_t cutoff = ordered(__half2float(__ushort_as_half(half_bits))); |
| 187 | if (tid == 0) s.count = 0; |
| 188 | __syncthreads(); |
| 189 | constexpr int kItems = 16; |
| 190 | // Compact survivors with one reservation per warp per tile. Keep counting |
| 191 | // beyond capacity so overflow triggers fallback instead of using a subset. |
| 192 | for (int base = 0; base < length; base += kItems * kThreads) { |
| 193 | uint32_t keys[kItems]; |
| 194 | uint32_t hit_mask = 0; |
| 195 | if ((reinterpret_cast<uintptr_t>(row) & 15) == 0 && |
| 196 | base + kItems * kThreads <= length) { |
| 197 | #pragma unroll |
| 198 | for (int j = 0; j < kItems / 4; ++j) { |
| 199 | const float4 values = |
| 200 | reinterpret_cast<const float4*>(row + base)[tid + j * kThreads]; |
| 201 | keys[4 * j] = ordered(values.x); |
| 202 | keys[4 * j + 1] = ordered(values.y); |
| 203 | keys[4 * j + 2] = ordered(values.z); |
| 204 | keys[4 * j + 3] = ordered(values.w); |
| 205 | } |
| 206 | } else { |
| 207 | #pragma unroll |
| 208 | for (int j = 0; j < kItems; ++j) { |
| 209 | const int i = base + tid * 4 + (j / 4) * kThreads * 4 + j % 4; |
| 210 | keys[j] = i < length ? ordered(row[i]) : 0; |
| 211 | } |
| 212 | } |
| 213 | #pragma unroll |
| 214 | for (int j = 0; j < kItems; ++j) { |
| 215 | const int i = base + tid * 4 + (j / 4) * kThreads * 4 + j % 4; |
| 216 | if (i < length && keys[j] >= cutoff) hit_mask |= 1u << j; |
| 217 | } |
| 218 | const int lane = tid & 31; |
| 219 | const int hits = __popc(hit_mask); |
| 220 | int inclusive = hits; |
| 221 | #pragma unroll |
| 222 | for (int delta = 1; delta < 32; delta *= 2) { |
| 223 | const int previous = __shfl_up_sync(0xffffffffu, inclusive, delta); |
| 224 | if (lane >= delta) inclusive += previous; |
| 225 | } |
| 226 | const int total = __shfl_sync(0xffffffffu, inclusive, 31); |
| 227 | int warp_base = 0; |
| 228 | if (lane == 31 && total != 0) warp_base = atomicAdd(&s.count, total); |
| 229 | warp_base = __shfl_sync(0xffffffffu, warp_base, 31); |
| 230 | int offset = warp_base + inclusive - hits; |
| 231 | #pragma unroll |
| 232 | for (int j = 0; j < kItems; ++j) { |
| 233 | if (hit_mask & (1u << j)) { |
| 234 | if (offset < kCapacity) { |
| 235 | s.candidates[offset] = make_uint2( |
| 236 | base + tid * 4 + (j / 4) * kThreads * 4 + j % 4, keys[j]); |
| 237 | } |
| 238 | ++offset; |
| 239 | } |
| 240 | } |
| 241 | } |
| 242 | __syncthreads(); |
| 243 | const int count = s.count; |
| 244 | if (count >= K && count <= kCapacity) { |
| 245 | const uint32_t exact_cutoff = threshold<true>(s, row, count, K); |
| 246 | emit<true>(s, row, dst, count, exact_cutoff); |
| 247 | } else { |
| 248 | const uint32_t exact_cutoff = threshold<false>(s, row, length, K); |
| 249 | emit<false>(s, row, dst, length, exact_cutoff); |
| 250 | } |
| 251 | } |
| 252 | |
| 253 | } // namespace vllm::sampled_topk |