You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2022/03/10 10:39:39 UTC
[GitHub] [tvm] yzh119 opened a new pull request #10562: [bulitin] Add search sorted builtin
yzh119 opened a new pull request #10562:
URL: https://github.com/apache/tvm/pull/10562
The search sorted function was used in the sparse-tir project to perform binary search on indices array. I need to rebase the sparse-tir repo to relax project so I need to push some changes upstream. This PR adds the search sorted function to TIR built-ins. The semantic of `searchsorted` is the same as numpy's (https://numpy.org/doc/stable/reference/generated/numpy.searchsorted.html), we add two arguments `offset_l` and `offset_r` to indicate the interval bound.
@masahi suggests using IRBuilder to define the fine-grained description of binary search. However, at current stage I don't want to decompose the binary search to more fine-grained instructions (this would make the intermediate IR too redundant, and not convenient for scheduling).
I leave the codegen on LLVM a future work.
@MasterJH5574 @junrushao1994
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] yzh119 commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
yzh119 commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064422414
Yes I'm trying to figure out a way to reuse your op defined in `topi`/`relay`.
How about I trigger a `call_extern` like this:
https://github.com/apache/tvm/blob/174d09ee2cef1ea2caab4c84e0bd58d90c09178f/tests/python/contrib/test_ethosu/test_replace_conv2d.py#L347-L350
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] masahi edited a comment on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
masahi edited a comment on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064391425
hmm, can TensorIR `Block` be used to "hide" those implementation details while still allowing TIR-native implementation of binary search ops? If not and if we have to resort to backend-specific hard-coding like this, this sounds like a major step backward to me.
Note that it is not just CUDA and LLVM, there is also opencl, metal, spirv...
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] yzh119 edited a comment on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
yzh119 edited a comment on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064422414
Yes I'm trying to figure out a way to reuse your op defined in `topi`/`relay`.
How about I apply a `call_extern` like this:
https://github.com/apache/tvm/blob/174d09ee2cef1ea2caab4c84e0bd58d90c09178f/tests/python/contrib/test_ethosu/test_replace_conv2d.py#L347-L350
where `ethosu_conv2d` is a relay function.
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] masahi commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
masahi commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064391425
hmm, can TensorIR `Block` be used to "hide" those implementation details while still allowing TIR-native implementation of binary search ops? If not and if we have to resort to backend-specific hard-coding like this, this sounds like a major step backward to me.
Note that it is not just CUDA and LLVM, there is opencl, metal, spirv...
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] masahi edited a comment on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
masahi edited a comment on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064411599
Note that we even have relay / topi `searchsorted` op that does exactly the same lower / upper bound search. So adding a new intrinsic doesn't feel right to me.
> block is not designed to do that
I remember hearing that, one of the reasons `Block` was created was to abstract the details of tensorized instructions so that the rest of code don't need to care about it. Sounds like exactly the situation you are in. Here we are not talking about tensorized instruction but I don't really see a big difference.
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] yzh119 edited a comment on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
yzh119 edited a comment on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064422414
Yes I'm trying to figure out a way to reuse your op defined in `topi`/`relay`.
How about I apply a `call_extern` like this:
https://github.com/apache/tvm/blob/174d09ee2cef1ea2caab4c84e0bd58d90c09178f/tests/python/contrib/test_ethosu/test_replace_conv2d.py#L347-L350
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] yzh119 commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
yzh119 commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064396384
@masahi yes I understand, I also view it as a backstep. `block` is not designed to do that.
Another feasible solution is to lower the intrinsic in a pass, where we replace the intrinsic with fine-grained instructions like what you did in the IRBuilder, WDYT?
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] yzh119 commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
yzh119 commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064417835
@masahi Then difference here is whether we perform statement replacement or expression replacement.
What `tensorize` replace are statements rather than expressions.
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] tkonolige commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
tkonolige commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064496488
I'd prefer for this not to be a builtin. Builtins are for low-level operations like arithmetic. Like Masa, I'd prefer if we use the TIR definition so that we can use this operation on all platforms. It also avoids adding another piece of codegen for new backends/BYOC. Ideally we'd have some sort of metaprogramming/function call ability in TIR that you could use here. But right now, I think `call_extern` is the best bet.
If we do decide to add searchsorted as a builtin, I think it is a big enough change that it should go through the RFC process.
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] yzh119 commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
yzh119 commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1074698522
Hi @tkonolige @masahi , I decide to emit a `search` block and lower it to statements composed of `WhileNode` in sparse-tir fork. This PR is deprecated, thanks for your suggestions!
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] masahi commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
masahi commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064411599
Note that we even have relay / topi `searchsorted` op that does exactly the same lower / upper bound search. So adding a new intrinsic doesn't feel right to me.
> block is not designed to do that
I remember hearing that, one of the reasons `Block` was created was to abstract the details of tensorized instructions so that the rest of code don't need to care about it. Here we are not talking about tensorized instruction but I don't really see a big difference.
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] masahi commented on pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
masahi commented on pull request #10562:
URL: https://github.com/apache/tvm/pull/10562#issuecomment-1064424079
> Another feasible solution is to lower the intrinsic in a pass, where we replace the intrinsic with fine-grained instructions like what you did in the IRBuilder
Ok, as long as we don't duplicate or backend-specific hard-code, I don't have complaint. Yes, we probably need an extern / packed func call.
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] yzh119 closed pull request #10562: [bulitin] Add search sorted builtin
Posted by GitBox <gi...@apache.org>.
yzh119 closed pull request #10562:
URL: https://github.com/apache/tvm/pull/10562
--
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: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org