给定一个4字节的寄存器（或16个字节的SIMD寄存器），必须有一种有效的方法使用少量指令在寄存器中对字节进行排序。
提前感谢。
4个回答
7
找到了！它在2007年的论文《使用SIMD寄存器和指令在排序算法中实现指令级并行性》（Furtak，Amaral和Niewiadomski）第4节中。
它使用4个SSE寄存器，有12个步骤，并且包括加载和存储在内的指令共计19条。
同一篇论文还介绍了使用SIMD动态生成排序网络的优秀工作。
- alecco
6
查找一个高效的排序网络，使其适用于您关心的字节数（4或16）。将其转换为比较和交换指令序列。（对于 N=16，这将是不少于“几个”的。）
- Darius Bacon
5
谢谢。我正在寻找一种高效的汇编解决方案。哦，请注意我说的是“几条指令”，而不是“几个周期”;) - alecco
啊，我看到你链接的论文采用了这种方法，使用SSE2指令。很棒。 - Darius Bacon
是的，我不想太啰嗦，因为我希望能用汇编语言实现一些位操作的魔法。事实上，我正在阅读《多核SIMD CPU架构上排序的高效实现》（Chhugani，.. 2008），但是对于算法的说明感到沮丧：
1）a）执行寄存器排序以获得长度为K的排序序列。我猜对于英特尔的研究人员来说，这是一个“显而易见”的过程，但对于我来说并非如此！（我仍然不确定他们是否要执行整个17-19条指令的过程来对寄存器进行排序。）[注：抱歉，由于缺乏声望，我没有给你点赞] - alecco
1我从阅读2007年的论文中学到了一些东西——这已经足够奖励了。 :-) - Darius Bacon
顺便提一下，在原始（2008年）论文中有一个非常高效的同时4个寄存器排序。我自己没看到，我的错。 - alecco
4
为了加快字符串排序，我最终采用每个双精度浮点数7字节的打包方式，并使用比特逆序排序(bitonic sort)对16个双精度浮点数组进行排序(排名)，并使用二进制合并(binary merge)来合并这两个运行(run)。您可以在此处查看第一部分http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/(asm)和这里(C)，以及比特逆序合并步骤(如果您希望全部使用SSE)：http://mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/。我用这种排序方法替换了qsort底部的插入排序，并且其速度比直接使用qsort快约5倍。希望这对您有所帮助。
我没有看到UofA的论文；比特逆序逻辑来自老学派(CTM) GPGPU编程。
对于链接字符串的嵌入式抱歉；我不知道如何在stackoverflow评论中添加可点击的链接。
我没有看到UofA的论文；比特逆序逻辑来自老学派(CTM) GPGPU编程。
对于链接字符串的嵌入式抱歉；我不知道如何在stackoverflow评论中添加可点击的链接。
- Mischa
1
所有的排序算法都需要将值从一个位置交换到另一个位置。由于你谈论的是字面上的CPU寄存器，这意味着任何排序都需要另一个寄存器作为临时存储被交换的字节的地方。
我从未见过内置有在寄存器内部对字节进行排序的芯片。并不是说没有这样做过，但我想不出有多少用途可以使用这样的指令。
我从未见过内置有在寄存器内部对字节进行排序的芯片。并不是说没有这样做过，但我想不出有多少用途可以使用这样的指令。
- richardtallent
3
我的意思是对寄存器中的字节进行排序，当然必须至少使用另一个寄存器。对于造成的误解，我很抱歉。 - alecco
实际上，使用CMPXCHG和旋转eax寄存器，可以进行寄存器内排序的方法，我的一位在x86方面非常有知识的朋友向我展示了这种方法。虽然收益很小，但是确实可行。此外，CMPXCHG速度相当慢。 - alecco
1我使用过的所有SIMD架构都有这样的指令。 - alex strange
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接