fig. 2.2.4 · the query pipeline: a tile that will not fit splits before its first output.⛶ ONE QUERY, TILE BY TILE · QUERY WORKSPACE BOUND 512 MiB BY DEFAULT BOXES ARE STEPS, DIAMONDS ARE CHECKS AGAINST THE BOUND; A TILE THAT FAILS ONE TAKES THE COLOURED LOOP ONCE, AT PREPARE NORMALIZE AND OWN THE INPUT SNAPSHOT CHOOSE DENSE OR A PROJECTION RANK NEXT TILE TAKE A DISJOINT PAIR TILE SCORE AND COUNT BUFFERS FIT? SCREENING DENSE PROJECTED GEMM, OUTWARD BOUND AND COUNT FULL FP32 GEMM AND COUNT TOO MANY CANDIDATES? YES: ≥1% OF THE TILE'S PAIRS REMAINING BUFFERS FIT? SCATTER CANDIDATES AND COMPUTE NEEDED SCORES FUSED ACCEPTANCE CLASSIFICATION FP64 AND EXACT INTEGER REFINEMENT FOR UNCERTAIN PAIRS YIELD INDEPENDENT HOST BATCHES FIRST OUTPUT NO NO SPLIT BEFORE EMITTING OUTPUT BISECT THE LONGER SIDE; BOTH HALVES GO BACK ON THE PENDING STACK THE SAME SPLIT CATCHES A DEVICE OUT-OF-MEMORY NOTHING EMITTED YET: A SPLIT CANNOT REPEAT A DELIVERED PAIR source: gpu-threshold-join docs/ARCHITECTURE.md:9-29, :38-40 · _workspace.py:9-10, :62-77 · _screen_gpu.py:330-376 · cudaPipeline.data.ts
View in context: Knuth's Root of All Evil Has a Break-Even Point → · All figures
Andrew Fribush , software and computer engineer in Austin. I build consequential systems where software meets institutions: finance, healthcare, commerce, government data, and the mechanisms that govern AI agents. Taking new engagements: hello@andrewfribush.com .