You are viewing a plain text version of this content. The canonical link for it is here.
Posted to discuss-archive@tvm.apache.org by "cchung100m (via GitHub)" <gi...@apache.org> on 2026/06/28 16:01:04 UTC
[PR] [TOPI][CUDA] Fix topk/sort gridDim.y overflow by moving the width-block dim to blockIdx.z [tvm]
cchung100m opened a new pull request, #19900:
URL: https://github.com/apache/tvm/pull/19900
Hi Committers,
This PR addresses issue https://github.com/apache/tvm/issues/19549. Any suggestions would be appreciated if you are available.
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [TOPI][CUDA] Fix topk/sort gridDim overflow by remapping grid axes in sort_ir [tvm]
Posted by "cchung100m (via GitHub)" <gi...@apache.org>.
cchung100m commented on PR #19900:
URL: https://github.com/apache/tvm/pull/19900#issuecomment-5384945553
cc @spectrometerHBH
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [TOPI][CUDA] Fix topk/sort gridDim overflow by remapping grid axes in sort_ir [tvm]
Posted by "cchung100m (via GitHub)" <gi...@apache.org>.
cchung100m commented on PR #19900:
URL: https://github.com/apache/tvm/pull/19900#issuecomment-5511501457
Hi @tlopex
Thanks for catching this. I've now swapped `nthread_by` onto `blockIdx.x` for CUDA at all four sites - a pure relabeling of the te.thread_axis tag with no new index arithmetic - while leaving `nbx`/`nbz` on the bounded axes and the non-CUDA mapping untouched.
Rather than fusing batch and width-block via `indexmod`/`indexdiv` as suggested, a plain swap gives the same safety guarantee without introducing new arithmetic into the mergesort inner kernel; I have added test cases to cover large-batch sort/topk on CUDA going forward.
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [TOPI][CUDA] Fix topk/sort gridDim overflow by remapping grid axes in sort_ir [tvm]
Posted by "tlopex (via GitHub)" <gi...@apache.org>.
tlopex merged PR #19900:
URL: https://github.com/apache/tvm/pull/19900
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [TOPI][CUDA] Fix topk/sort gridDim.y overflow by moving the width-block dim to blockIdx.z [tvm]
Posted by "gemini-code-assist[bot] (via GitHub)" <gi...@apache.org>.
gemini-code-assist[bot] commented on code in PR #19900:
URL: https://github.com/apache/tvm/pull/19900#discussion_r3488150416
##########
python/tvm/topi/gpu/sort.py:
##########
@@ -499,17 +499,17 @@ def dual_mergepath(
nbx = tvm.tirx.generic.cast(ceil_div(width, max_threads * thread_work), "int32")
nbz = tvm.tirx.generic.cast(ceil_div(size, width), "int32")
- tx, bx, by, _, _, _ = _get_threads(ntx, nbx, nthread_by * nbz)
+ tx, bx, by, _, _, _ = _get_threads(ntx, nbx, nthread_by)
+ bz = te.thread_axis("blockIdx.z")
with T.frame_scope(
[
T.attr(tx, "thread_extent", ntx),
T.attr(bx, "thread_extent", nbx),
- T.attr(by, "thread_extent", nthread_by * nbz),
+ T.attr(by, "thread_extent", nthread_by),
+ T.attr(bz, "thread_extent", nbz),
]
Review Comment:

In CUDA, the maximum limit for `blockIdx.y` and `blockIdx.z` is 65,535, while `blockIdx.x` can go up to $2^{31} - 1$ (2,147,483,647).
With the current changes in this PR:
- `bx` (extent `nbx`) is bound to `blockIdx.x`
- `by` (extent `nthread_by`) is bound to `blockIdx.y`
- `bz` (extent `nbz`) is bound to `blockIdx.z`
Since `nbz = ceil_div(size, width)` and `width` starts at `block_size` (128), at the beginning of the merge sort, `nbz` can be up to `ceil_div(size, 128)`. If `size` exceeds `128 * 65,535 = 8,388,480` (approx 8.38 million elements), `nbz` will exceed 65,535, causing a `blockIdx.z` overflow and kernel launch failure.
To support much larger sizes without overflow, we can swap the mapping of `bx` and `bz`:
- Bind `bz` (extent `nbz`) to `blockIdx.x` (limit 2,147,483,647)
- Bind `bx` (extent `nbx`) to `blockIdx.z` (limit 65,535)
Since `nbx = ceil_div(width, max_threads * thread_work) <= ceil_div(size, 4096)`, `nbx` will only exceed 65,535 if `size` exceeds `4096 * 65,535 = 268,435,456` (approx 268 million elements). This simple swap increases the maximum supported sort size by 32x (from 8.38M to 268M elements) without adding any division/modulo overhead!
```suggestion
tx = te.thread_axis("threadIdx.x")
bx = te.thread_axis("blockIdx.z")
by = te.thread_axis("blockIdx.y")
bz = te.thread_axis("blockIdx.x")
with T.frame_scope(
[
T.attr(tx, "thread_extent", ntx),
T.attr(bx, "thread_extent", nbx),
T.attr(by, "thread_extent", nthread_by),
T.attr(bz, "thread_extent", nbz),
]
):
```
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [TOPI][CUDA] Fix topk/sort gridDim overflow by remapping grid axes in sort_ir [tvm]
Posted by "cchung100m (via GitHub)" <gi...@apache.org>.
cchung100m commented on PR #19900:
URL: https://github.com/apache/tvm/pull/19900#issuecomment-5659309675
Thanks to @tlopex
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [TOPI][CUDA] Fix topk/sort gridDim overflow by remapping grid axes in sort_ir [tvm]
Posted by "cchung100m (via GitHub)" <gi...@apache.org>.
cchung100m commented on PR #19900:
URL: https://github.com/apache/tvm/pull/19900#issuecomment-4910479366
cc @mshr-h @tlopex
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [TOPI][CUDA] Fix topk/sort gridDim overflow by remapping grid axes in sort_ir [tvm]
Posted by "tlopex (via GitHub)" <gi...@apache.org>.
tlopex commented on PR #19900:
URL: https://github.com/apache/tvm/pull/19900#issuecomment-5466604686
This still overflows `gridDim.y` whenever `nthread_by > 65535`. For example, sorting the last axis of `(66, 1000, 1000)` produces `nthread_by = 66000`, while the reported `(60, 1000, 1000)` only happens to fit at 60000. Could we fuse the batch/merge dimensions onto `blockIdx.x` for CUDA, preserve a valid mapping for non-CUDA targets, and add a regression test for the grid extents?
--
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: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org