vllm.models.deepseek_v41.nvidia.specialized_decode.ampere.topk
¶
The DeepSeek-V4.1 indexer's decode top-k on SM80, in CuTe DSL.
Each decode step, every indexer layer keeps the k best of a row's
lens[row] FP32 scores (the rest of the row, up to the CUDA-graph-static
width max_model_len, is never read). The candidate source layer also
keeps its row's best key blocks: the top k blocks of group positions,
a block scoring the maximum of its positions and the newest block pinned on
top. DecodeTopK does both, one CTA of 1024 threads per row, so the rows
of a step run side by side and a CTA reads only its row's lens scores.
Selection is an exact radix select on the order-preserving 32-bit key of each score (sign-magnitude FP32 bits made unsigned-comparable):
- three digit passes (11, 11 and 10 bits, high first) histogram, in shared
memory, the keys that match the digits found so far, and pick the digit
holding the
k-th best key; a pass whose digit holds exactly the keys still needed ends the search early; - the found prefix splits the row into keys above it (all taken), keys
matching it (the threshold ties,
needof them taken) and the rest; - each thread owns a contiguous run of the row, counts its taken and tied keys, and two block-wide prefix sums give it the run's output offset and how many of its ties to take: ties go to the lowest positions.
The first digit pass reads the CTA's elements from global memory (for blocks,
the maximum of their group scores) and keeps their keys in shared memory,
where the later passes and the output pass read them: a CTA of the first two
stages selects from at most one chunk of elements (at most 64 KB of keys for
the model's k); the last stage reads the chunks' picks from global. A
decode step's rows are few, so these CTAs run one per row or chunk on a
mostly idle GPU, and each re-read of the row from L2 would cost a whole pass
of latency.
The output is the k chosen positions (or block indices) in ascending
order, -1 padded when the row has at most k elements (then all of
them, 0 .. n - 1). It is the same set as any exact top-k of the row; only
threshold ties are resolved, toward lower positions, where vLLM's shared
top-k kernels take any of them.
A long row would leave one CTA streaming it several times, so logits wider
than one chunk (CHUNK scores, or 4 k blocks if more) select in two
launches: CTA (c, row) keeps the k best of the row's chunk c (their
keys and positions, in ascending order) in a workspace, then one CTA per row
selects the k best of those picks. An element of the row's top k
(ties to the lowest positions) is also among its chunk's top k, and the
picks are in position order, so the result is the same. A row within one
chunk gets its answer from the first launch.
A row of compact candidate scores (mqa_logits.candidate_mqa_logits)
selects the same way and writes each chosen column's key position, read from
the row's candidate blocks. Its columns at or past the row's key length score
-inf, so a row of at most k keys takes them all (0 .. len - 1).
When the blocks are listed in ascending order (the SM80 candidate source),
the positions come out ascending and ties go to the lowest positions: the
same keys the dense, masked row selects. In any other order (vLLM's
candidate selection), the output is the same set up to threshold ties, not
sorted.
Classes:
-
DecodeTopK–Top-
kof each row's firstlens[row]scores, or of its blocks of
Functions:
-
chunk_elements–Elements (scores or blocks) per chunk of a long row.
-
decode_topk–Top
out.shape[1]of each row oflogits(FP32[rows, width], -
workspace_bytes–Bytes per row of the two-launch workspace for logits
widthwide
DecodeTopK
¶
Top-k of each row's first lens[row] scores, or of its blocks of
group scores; see the module docstring. stage 0 selects whole
rows, 1 the chunks of long rows, and 2 among the chunks' picks.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 | |
_block_key(row, block, n, positions)
¶
The key of a block: the best key of its positions below
positions, or PINNED for the newest block (n - 1).
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_keys(row, first, n, positions)
¶
Keys of elements first .. first + 3 (first % 4 == 0 and
first < n); those at or past n are garbage for the caller to
skip. A row's padded width keeps the four-score load in bounds.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_load(row, picked_keys, first, n, positions)
¶
Keys of elements first .. first + 3: the row's, or in the last
stage the chunks' picks.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_position(listed, column)
¶
The key position of a column: itself, or for a compact row the key
of its candidate block (the row's list at listed).
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_read(row, picked_keys, cache, cached_at, first, n, positions, fill)
¶
Keys of elements first .. first + 3 through the CTA's shared
key cache: fill (the first pass) loads them and stores them,
later passes read them back. A thread's i-th element sits at
i * THREADS + tid (cached_at for first), so a warp's
accesses fall in distinct banks. Without a cache (the last stage),
every pass loads them.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_scan(a, b, sums, warp, lane)
¶
Block-wide inclusive prefix sums of two per-thread counts, in thread order, and their totals.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_kernel(device_index, k, group, remap=0, stage=0)
cached
¶
DecodeTopK compiled for a device, k, block size, candidate
block size of compact rows (0: dense rows) and stage.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_order_key(bits)
¶
The unsigned key of FP32 bits that orders like the scores: negative values flipped whole, positive ones with the sign bit set.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
_pointer(dtype, tensor, align)
¶
A CuTe DSL global-memory pointer to tensor's data.
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
chunk_elements(k, group)
¶
decode_topk(logits, lens, out, group=1, candidates=None, candidate_block_size=0, key_lens=None)
¶
Top out.shape[1] of each row of logits (FP32 [rows, width],
rows 16-byte aligned) over its first lens[row] columns, or over its
blocks of group columns, into out (int32, unit column stride) in
ascending order, -1 padded. With candidates (int32
[rows, count]), the rows are compact candidate scores
(mqa_logits.candidate_mqa_logits, lens their compact lengths),
key_lens (int32 [rows]) the rows' key lengths, and out gets
the chosen keys' positions; compact rows are at most one chunk wide
(chunk_elements(k, 1) columns).
Source code in vllm/models/deepseek_v41/nvidia/specialized_decode/ampere/topk.py
workspace_bytes(width, k, group=1)
¶
Bytes per row of the two-launch workspace for logits width wide
(the chunks' picked keys and positions), 0 when a row fits one chunk.