sleeepyjack opened a new pull request, #15:
URL: https://github.com/apache/datasketches-cuda/pull/15
## Summary
Draft alternative to #12 and #14.
This replaces the Theta screen/chunk/sort update path with a persistent grid
that
keeps an exact open-addressing set in shared memory. Each resident block
owns one
input partition, while its 32 warps process independent subranges. Accepted
hashes
remain local to the SM until the table reaches its configured load limit.
When a table needs reduction, the block finds the exact rank-k boundary with
eight
8-bit histogram passes, compacts the hashes below that boundary, clears the
table,
and rebuilds it with the retained bottom-k. The new theta is published with a
device-scoped atomic min so other blocks can reject more input without a
global
rendezvous.
After all blocks finish, each emits at most `k + 1` values. A single
device-wide
CUB radix sort and unique pass combines those candidates with the sketch's
previous
retained hashes.
This implementation does not directly depend on cuCollections. HLL still
uses the
cuco components shipped through CCCL.
## Block-local algorithm
- 1024 threads per block, one target block per SM.
- Shared-memory capacity is derived from
`cudaDevAttrMaxSharedMemoryPerBlockOptin` and
`cudaDevAttrMaxSharedMemoryPerMultiprocessor`; it is not hardcoded.
- 32 independent warp workers use `elect.sync` for leader work and warp
ballots to
aggregate successful insertions.
- The set stores already-hashed 64-bit values with linear probing and exact
duplicate detection.
- The empty sentinel, zero hash, and values outside theta are rejected before
insertion.
- The occupancy limit is 80%. Capacity reserves enough space for one
worst-case
in-flight round from all 1024 threads.
- Workers periodically read the device-wide theta, but otherwise communicate
only
through block-scoped counters.
- CTA phase decisions use `__syncthreads_or`, avoiding a race where one warp
could
enter rebuild while another was still reading the previous decision.
- Scoped compiler atomics are used for set loads/CAS and device theta
publication;
CUDA-C block atomics are retained for shared counters because they lower
directly
to shared-memory `ATOMS` instructions.
## Comparison with the existing PRs
### #12: fused screen plus best-effort duplicate cache
#12 hashes and screens into an input-sized global output buffer. It uses
`__match_any_sync` and a small direct-mapped shared cache to remove
inexpensive
duplicates before sorting. Correctness does not depend on the cache because
remaining duplicates are removed globally.
This PR instead keeps an exact set and performs repeated rank-k reduction
entirely
inside each resident block. Global memory receives only `O(blocks * k)`
candidates.
### #14: cuco exact set inside the screen kernel
#14 replaces #12's direct-mapped cache with a 2048-slot exact cuco set and
bulk
retrieval, but retains the same input-sized screen output and global sort
pipeline.
It also depends on private cuco open-addressing internals to obtain an 8-byte
key-only slot.
This PR uses a small purpose-built set with no direct cuco dependency and
uses the
set as the block's persistent retained state, rather than only as a duplicate
filter for an `O(N)` output.
## 16 GiB comparison
RTX PRO 6000 Blackwell Max-Q, CUDA 13.3, SM120, U64 unique input,
`2,147,483,648` keys, `lg_k=12`, 50 isolated samples:
| Approach | Cold update | Warm update |
|---|---:|---:|
| #12 direct-mapped screen | 12.790 ms | **11.762 ms** |
| #14 cuco exact-set screen | 13.372 ms | 12.163 ms |
| This PR, persistent exact set | **12.685 ms** | 12.049 ms |
The differences around one to four percent have similar run-to-run noise. The
persistent path is approximately 0.8% faster cold and 2.4% slower warm than
#12,
and 5.1% faster cold and 0.9% faster warm than #14.
Nsight Compute speed-of-light measurements for the primary scanning kernel:
| Approach | Cold DRAM | Cold kernel | Warm DRAM | Warm kernel |
|---|---:|---:|---:|---:|
| #12 screen kernel | **90.58%** | **11.14 ms** | **91.54%** | **10.98 ms** |
| This PR persistent kernel | 85.53% | 11.80 ms | 90.63% | 11.16 ms |
The persistent design is near the same steady-state bandwidth limit, while
its
cold path spends more time performing local exact reductions.
## Memory footprint
The input allocation itself is excluded below.
| Approach | Additional global memory for a 16 GiB update | Shared memory |
|---|---:|---:|
| #12 | At least one input-sized screen buffer: about 16 GiB, plus survivor
sort/merge temporaries | 8 KiB direct-mapped cache per block |
| #14 | At least one input-sized screen buffer: about 16 GiB, plus survivor
sort/merge temporaries | 16 KiB cuco set per block |
| This PR | About 17.8 MiB of persistent candidate/alternate/unique storage
on this 188-SM GPU, plus small CUB temporary storage | 101.4 KiB per resident
block |
This removes the `O(N)` DRAM scratch allocation, which is the primary
motivation
for the design. The current fixed scratch allocation is still a known
problem for
the future many-sketch use case: every sketch reserves capacity for a full
188-block grid even when an update would use one block. A follow-up should
right-size or pool this scratch before thousands of sketches are expected to
coexist.
## Known draft limitations
- Only `lg_k=12` is currently supported. The existing benchmark definitions
still
contain larger `LgK` values and must be overridden to 12.
- The kernel requires SM90+ and the current CUDA compiler atomic builtins.
This is
not yet enforced by CMake, and the repository-level CUDA 12.0 compatibility
statement has not been revised.
- The remaining performance gap to #12's standalone screen kernel is
primarily in
the cold local-reduction path.
## Validation
- Fresh CUDA 13.3 / SM120 build after merging current `upstream/main`
- SM90 compile succeeds
- All 16 test executables pass
- Persistent-update boundary tests cover empty input, 1, 31/32/33,
1023/1024/1025, `k-1/k/k+1`, load-limit boundaries, shuffled odd-sized
input,
duplicates, zero, theta boundary, and the empty sentinel
- Compute Sanitizer memcheck: zero errors
- Compute Sanitizer racecheck: zero hazards
- Compute Sanitizer synccheck: zero errors
- clang-format hook passes
Related: #12, #14
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
