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/12/12 21:23:20 UTC
[GitHub] [tvm] AndrewZhaoLuo opened a new pull request, #13599: [Contrib] Faster Top-K Impl.
AndrewZhaoLuo opened a new pull request, #13599:
URL: https://github.com/apache/tvm/pull/13599
This is a simple rewrite of hand-coded top-k function used for CPU targets.
The old implementation sorted each axis and then took the biggest k elements.
The new implementation does a single pass of each axis, keeping a min heap to store the top-k elements up to that point.
If n is the size of the array, and we want to find top k, the old implementation has runtime in O(nlogn) with additional memory O(n) to store the sorted array. The new implementation is O(n log k), and in practice is probably amortized to O(n / k * log k) in many scenarios and only requires O(k). Note n >> k.
In practice this new kernel led to a 20x speedup over existing one. On a Xeon Platinum 8370C CPU @ 2.80GHz for input shape [1, 3050] with k = 15, the latency went from 300us --> ~10us. There is probably more room for shaving off a little more time on the scale of a single us's, however I have determined it to not be worth it.
This change however is probably in the range of worth comitting.
TODO:
Wider benchmark suite over many shapes + k + hardware platforms.
--
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 merged pull request #13599: [Contrib][Sort] Faster Top-K Implementation
Posted by GitBox <gi...@apache.org>.
tkonolige merged PR #13599:
URL: https://github.com/apache/tvm/pull/13599
--
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] tvm-bot commented on pull request #13599: [Contrib] Faster Top-K Impl.
Posted by GitBox <gi...@apache.org>.
tvm-bot commented on PR #13599:
URL: https://github.com/apache/tvm/pull/13599#issuecomment-1347349325
<!---bot-comment-->
Thanks for contributing to TVM! Please refer to the contributing guidelines https://tvm.apache.org/docs/contribute/ for useful information and tips. Please request code reviews from [Reviewers](https://github.com/apache/incubator-tvm/blob/master/CONTRIBUTORS.md#reviewers) by @-ing them in a comment.
<sub>Generated by [tvm-bot](https://github.com/apache/tvm/blob/main/ci/README.md#github-actions)</sub>
--
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