6

给定一个 4 字节的寄存器（或 SIMD 的 16 个字节），必须有一种有效的方法来使用几条指令对寄存器中的字节进行排序。

提前致谢。

4

4 回答 4

7

找到了！它位于 Furtak、Amaral 和 Niewiadomski 的 2007 年论文“使用 SIMD 寄存器和指令在排序算法中启用指令级并行性”。第 4 节。

它使用 4 个 SSE 寄存器，有 12 个步骤，运行在 19 条指令中，包括加载和存储。

同一篇论文在使用 SIMD 动态制作排序网络方面做了一些出色的工作。

于 2009-10-17T01:05:02.320 回答
6

查找N = 您关心的字节数（4 或 16）的有效排序网络。将其转换为一系列比较和交换指令。（不过，对于 N=16，这将不仅仅是“几个”。）

于 2009-10-16T23:05:40.563 回答
4

为了加快字符串的排序，我最终在 SSE2 中对每个双精度数打包 7 个字节并排序（排序）了一个包含 16 个双精度数的数组，使用双音排序来创建两个 8 的运行，并使用二进制合并来合并这两个运行。您可以在此处查看第一部分http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (asm) 和此处http://mischasan。 wordpress.com/2011/09/02/update-on-bitonic-sse2-sort-of-16-doubles/（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 中添加可点击的链接。

于 2013-04-30T17:14:12.947 回答
1

所有排序算法都需要将值从一个地方“交换”到另一个地方。由于您在谈论文字 CPU 寄存器，这意味着任何类型都需要另一个寄存器用作临时位置来保存正在交换的字节。

我从未见过具有内置方法对寄存器中的字节进行排序的芯片。不是说它还没有完成，但我想不出这样的指令有多少用途。

于 2009-10-16T22:17:51.443 回答