NVIDIA / NVIDIA/cccl

`thrust::reduce` says it doesn't support non-commutative operators but in practice it does

Open
#4,296 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

`thrust::reduce`'s documentation states:

```
Note that reduce also assumes that the binary reduction operator (in this case binary_op) is commutative. If the reduction operator is not commutative then thrust::reduce should not be used. Instead, one could use inclusive_scan (which does not require commutativity) and select the last element of the output array.
```

In practice, for the CUDA backend, `thrust::reduce` will happen to respect non-commutativity operators - e.g. the global order of the reduction will be respected, from left to right. This happens because:

- Within a thread, all items are reduced from left to right
- Within a warp, all aggregates are reduced from left to right (is this true?)
- Within a block, all aggregates are reduced from left to right (is this true?)
- Across the grid, all aggregates are reduced from left to right because blocks are rasterized in linear monotonically increasing order.

I am not sure what is true for the other backends. `std::reduce` does not guarantee non-commutativity and in practice there are implementations that do not respect it (such as libstdc++'s default non-execution-policy overload, I believe).

A reduction that works for non-commutative operators is quite useful. [Conor and I have discussed this on ADSP in detail](https://adspthepodcast.com/2021/05/14/Episode-25.html).

C++ has recently added [`std::ranges::fold*`](https://en.cppreference.com/w/cpp/algorithm/ranges/fold_right), a range-based reduction that specifies the accumulation order but does not prescribe it in a way that forces serial execution like `std::accumulate`. So instead of changing the docs for `thrust::reduce`, we could just add `thrust::fold*` and say those work for non-commutative operators.

At the very least, we should probably not advise people to use `inclusive_scan` as an alternative, as that's pretty heavyweight.

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.