4 ms·
I was stumped as to how this was possible, until I saw that it relied on memory access relative to a computed offset, for which as far as I know there are no SI
by 0xfaded 9y ago
I was stumped as to how this was possible, until I saw that it relied on memory access relative to a computed offset, for which as far as I know there are no SIMD instructions. I guess it could be argued that a texture in a shader would provide similar functionality.
Also of interest are sorting networks https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network which can be used to perform branchless sort on parallel hardware.
- Tuna-Fish 9y ago> memory access relative to a computed offset, for which as far as I know there are no SIMD instructions. Sure there are? VGATHERDPD and friends. They have been there for a couple of generations, but are only now getting fast.
- nhaehnle 9y agoSince the title mentioned GPU-friendliness: GPUs are built all around scatter/gather memory accesses. The actual performance of memory accesses of course still depends on locality. The first load in a parallel binary search will be fast, since all threads will load the same element, later loads can get progressively worse. That said, the code in the article doesn't actually improve anything specifically for GPUs, because standard binary searches are already "branchless" for practical purposes. Really, the only difference between the article and a standard binary search is that the code in the article has manually unrolled the search loop. That, plus some (not all) binary search implementations can do an early-out if the comparison happens to hit equality. None of these changes make a SIMD- or GPU-specific difference, because loop unrolling doesn't make a difference in terms of control-flow divergence.