NVIDIA / NVIDIA/cudf

[FEA] Optimize shared-memory aggregation iteration order for lower cardinality

Open
#17,442 0 comments 1 reaction 0 assignees View on GitHub
feature request libcudf Performance
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

**Is your feature request related to a problem? Please describe.**
The shared-memory aggregations track the cardinality observed by a block. If the cardinality seen by a block exceeds a certain size ([currently 128 unique elements](https://github.com/rapidsai/cudf/blob/f05e89db8f6750232a452d072fa9f9ea988a6b34/cpp/src/groupby/hash/helpers.cuh#L37)) then the block will fall back to using global instead of shared memory for the hashmap. We want to use shared memory instead of global memory any time that we can for performance.

**Describe the solution you'd like**
I proposed to @PointKernel that we might be able to optimize this. Currently we have each block handle data in a strided fashion, but maybe we can keep the cardinality _seen by a block_ at a lower value (e.g. for sorted or semi-sorted data) by having each block take a contiguous chunk of the table rather than doing a grid stride loop over the whole table. That might reduce the fallback to global memory. https://github.com/rapidsai/cudf/blob/5a89d0066b5cfbb38d5a392b425865d66b82a8b6/cpp/src/groupby/hash/compute_mapping_indices.cuh#L131

For an example of data that might benefit, consider:
```
0, 0, 0, ..., 0, 0, 0, 1, 1, 1, ..., 1, 1, 1, 2, 2, 2, ..., 2, 2, 2, 3, 3, 3, ..., 3, 3, 3, [...], N, N, N, ..., N, N, N
```
Using the strided iteration order, every block could see every value from `0` to `N` (assuming that the number of repeats is large and not a particular multiple of the block size). Using the proposed block-contiguous iteration order, we might have block 0 only see elements `0-4`, block 1 see elements `5-9`, and so on. The key observation here is that _the cardinality of a contiguous chunk of a table is likely to be smaller than the cardinality of an equivalent number of rows distributed in block-sized chunks spaced throughout the table_.

We would change the iteration order from
```
for (auto idx = cudf::detail::grid_1d::global_thread_id(); idx - block.thread_rank() < num_input_rows; idx += stride)
```
to something like
```
for (auto idx = block_start; idx - block.thread_rank() < block_end; idx += block_size)
```
where `block_start` and `block_end` represent a contiguous chunk of rows, and each block is assigned `num_input_rows / num_blocks` rows to work with.

Implementing this would require changes in a few places, at least `compute_mapping_indices.cuh` and `compute_shared_memory_aggs.cu`.

**Additional context**
I do not expect any negative performance differences, as the case our current iteration order is optimized for is a very unusual one (low cardinality in block-sized chunks of rows that are separated by the grid size). However, low-cardinality sorted (or nearly-sorted) data should see a boost if it is able to use shared memory groupby where previously only global memory groupby was used.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.