deepselect-topk-optimizer
Optimize high-throughput TopK selection and DeepSeek Sparse Attention (DSA) workloads using randomized block scans, monotonic threshold filtering, denormal FP32 simulation, and Threadblock Clusters. Do not use for generic sorting or CPU-only arrays.
- License 许可
- MIT
- 最近更新
- 2026-11-15
- Stars
- ★ 0
- Forks
- 0
01 前言 Front Matter
- name
- deepselect-topk-optimizer
- description
- Optimize high-throughput TopK selection and DeepSeek Sparse Attention (DSA) workloads using randomized block scans, monotonic threshold filtering, denormal FP32 simulation, and Threadblock Clusters. Do not use for generic sorting or CPU-only arrays.
02 资源文件 3
- 参考文档CARD.md3.2 KB
- 参考文档config.default.yaml332 B
- 脚本scripts/deepselect_engine.py11.8 KB
03 SKILL.md 正文
DeepSelect TopK Optimizer: High-Performance Kernel Architecture & DSA Routing
deepselect-topk-optimizer provides domain engineering, performance bound estimation, hardware contention mitigation, and kernel dispatch configuration for high-performance TopK selection kernels derived from the DeepSeek Sparse Attention (DSA) architecture.
See CARD.md for the companion summary card, stage progression table, and invariants checklist. Consult config.default.yaml for baseline operational budgets and timeout thresholds.
The 5-Stage TopK Optimization Lifecycle
[1. Workload Characterization & Stride Alignment]
│
▼
[2. Complexity Bound Estimation & Harmonic Calculus]
│
▼
[3. Hardware Contention Mitigation & ALU Planning]
│
▼
[4. Kernel Dispatch & Threadblock Cluster Sizing]
│
▼
[5. Monotonic Simulation & Verification Protocol]
1. Workload Characterization & Stride Alignment
Analyze input tensor dimensions and hardware alignment requirements:
- Lightning Indexer Scenario:
torch.bfloat16, batch size $1 \sim +\infty$, vocab size $1 \sim +\infty$, small topk ($k \le 4096$). Disablesorted_indexunless index ordering is mandatory. Setreturn_value=Falsewhen values are not consumed (~10% throughput boost). - Sampling Scenario:
torch.float32, vocab size around 128k, small topk ($k \le 4096$). - Stride Invariant: Row stride of the input tensor must be aligned to
1024bytes. Output strides must align to32bytes.
2. Complexity Bound Estimation & Harmonic Calculus
Evaluate expected total elements processed across all in-loop TopK calls:
- For input length $N$, block size $B$, and candidate compaction threshold $B_2$, define: $$m = \lceil N / B \rceil, \quad L = k + B + B_2, \quad H_m = \sum_{i=1}^m \frac{1}{i}$$
- The expected total elements $W$ processed by RadixSelectTopK across the entire scan satisfies: $$\mathbb{E}[W] \le \left(1 + \frac{k}{B_2}\right) L H_m = O\left(k \log\frac{N}{k}\right) \quad \text{when } B, B_2 = \Theta(k)$$
- The compute complexity is completely decoupled from $N$ except logarithmically, ensuring uniform high memory bandwidth utilization.
3. Hardware Contention Mitigation & ALU Planning
Bypass CUDA Core instruction contention using low-level bit manipulation and IEEE-754 denormal emulation:
- Single-Pass Bitmask Accumulation: Use PTX instructions (
set.s32.bf16x2,prmt.b32,dp4a.s32.s32) to generate 32-bit boolean masks in registers during count pass. Traverse qualifying elements via hardware__ffs(mask)andmask &= mask - 1u, eliminating redundant memory passes. - Denormal FP32 Simulated Addition: For non-negative integer operands $x, y \le 2^{22}$, integer addition is bitwise identical to floating-point addition on denormal numbers:
__float_as_uint(__uint_as_float(x) + __uint_as_float(y)). DeepSelect uses this to bypass integer ALU contention with bitwise/comparison instructions.
4. Kernel Dispatch & Threadblock Cluster Sizing
Mitigate wave quantization when batch sizes or active SM ratios are low:
- When $\text{batch_size} < \frac{\text{active_SMs}}{2}$, enable Threadblock Clusters (
cluster_size = 16). - Divide each sequence into segments across CTAs in the cluster; each CTA computes local TopK and streams candidates into CTA0 via distributed shared memory (DSMEM).
- For large batch sizes ($\ge \text{active_SMs} \times 2$), dispatch non-cluster variants (
cluster_size = 1) to eliminate inter-CTA synchronization overhead.
5. Monotonic Simulation & Verification Protocol
Verify selection accuracy and benchmark performance against standard baselines:
- Execute python-level simulation of the randomized block scan, monotonic threshold filter, and shared-memory compaction.
- Assert 100% TopK candidate parity with exact ground truth.
- Verify that input row strides and output buffers adhere strictly to 1024-byte and 32-byte alignment invariants.
The Three Foundational Pillars
1. The Decoupled Complexity Bound Pillar
Compaction work must scale as $O(k \log(N/k))$ rather than $O(N \log k)$. By reading global memory strictly once in contiguous blocks and maintaining a monotonic non-decreasing threshold $T$, later blocks rarely pass the filter.
2. Hardware ALU Contention Elimination Pillar
Never allow integer addition to bottleneck comparison-heavy kernels. Utilize denormal FP32 addition for values $\le 2^{22}$ and single-pass PTX bitmasks to maximize SM execution pipe concurrency.
3. Wave-Quantization Cluster Resilience Pillar
Never allow GPU Streaming Multiprocessors to sit idle during tail execution waves. Partition small-batch sequences across Threadblock Clusters to sustain maximum occupancy.
The Visual Brief Pillar
When completing TopK selection benchmark runs or Sparse Attention (DSA) tuning sessions, synthesize throughput comparisons, denormal FP32 boundary test results, and Threadblock Cluster performance matrices into a standalone interactive HTML visual brief written to %TEMP%\deepselect-topk-<timestamp>.html. Render performance curves as inline SVG bar charts with P50/P99 latency annotations.
Mandatory Checkpoint Gates
Before finalizing any TopK kernel implementation or DSA configuration:
- Gate 1 (Correctness): Assert TopK selection results match reference brute-force output on all randomized test vectors (tolerance ≤ 1e-5).
- Gate 2 (Denormal FP32 Guard): Assert zero denormal float inputs reach the hot selection loop (flush-to-zero confirmed).
- Gate 3 (Timeout Bound): Assert no single benchmark run exceeds declared async timeout (≤ 5.0s per vector by default).
Anti-Patterns
- Global Heap Exhaustion — Inserting all elements of an N-element vector into a global priority queue or heap causing O(N log k) branch-divergent memory access.
- Two-Pass Filter Stall — Reading global memory or registers twice for candidate counting and writing, doubling register pressure and stalling pipelines.
- Integer ALU Saturation — Using integer multiply-add instructions when int ALU is saturated, delivering half the throughput of floating-point units.
- Single-CTA Sequence Confinement — Forcing one threadblock to process an entire massive sequence alone while GPU SMs sit idle in the tail wave.
- Unbounded Float Denormal Emulation — Applying denormal FP32 integer addition when operands exceed 2^22, triggering exponent overflow and data corruption.
04 同仓库更多 Skills
ui-behavior-primitive-architect
Architect, audit, and verify zero-dependency headless UI behavior primitives, WebMCP agent bridges, WAI-ARIA/SSR/RTL tri-modal checks, and framework expert routing. Do not use for static CSS theme styling or backend database migrations.
trustgraph-ontology-governor
Govern knowledge graphs, SHACL-AF triple policies, OntologyRAG subclass validation, PROV-O dual named graphs, and Laya entropy decision scoring. Do not use for relational SQL queries or generic web scraping.
shim-harness-governor
Govern universal CLI agent loops, 4-tier tool permissions, ancestor-symlink workspace sandboxes, deterministic-first command routing, collision-safe MCP namespacing, and layered skill loading. Do not use for static UI styling or external SQL analytics.
graphiti-zep-memory-governor
Govern bi-temporal knowledge graphs with Graphiti future-edge clamping, MinHash/LSH entity dedup, RRF/MMR reranking, and Zep typed ontologies. Do not use for static SQL joins or generic web crawling.
agora-mcp-workbench-architect
Architect, audit, and orchestrate Agora Workbench MCP servers, loopback sidecars, unified state graphs, gateway/dispatcher connectors, and policy-enforced data lakes. Do not use for static frontend CSS styling or non-MCP desktop GUI automation.
skill-eval-assurance-runner
Evaluate and assure agent skills using small-N Wilson confidence intervals, unbiased pass^k reliability, deterministic trajectory graders, preflight boundary honesty, and sealed digest verification. Do not use for subjective prose review or unconstrained production deployment.