我对 SIMD 很好奇，想知道它是否可以处理这个用例。
假设我有一个包含 2048 个整数的数组，例如 [0x018A、0x004B、0x01C0、0x0234、0x0098、0x0343、0x0222、0x0301、0x0398、0x0087、0x0167、0x0389、0x03F2、0x0034、0x0345、...]
注意它们都是如何以 0x00、0x01、0x02 或 0x03 开头的。我想将它们分成 4 个数组:
- 一个代表所有以 0x00 开头的整数
- 1 代表所有以 0x01 开头的整数
- 1 代表所有以 0x02 开头的整数
- 一个代表所有以 0x03 开头的整数
我想我会有这样的代码:
int main() {
uint16_t in[2048] = ...;
// 4 arrays, one for each category
uint16_t out[4][2048];
// Pointers to the next available slot in each of the arrays
uint16_t *nextOut[4] = { out[0], out[1], out[2], out[3] };
for (uint16_t *nextIn = in; nextIn < 2048; nextIn += 4) {
(*** magic simd instructions here ***)
// Equivalent non-simd code:
uint16_t categories[4];
for (int i = 0; i < 4; i++) {
categories[i] = nextIn[i] & 0xFF00;
}
for (int i = 0; i < 4; i++) {
uint16_t category = categories[i];
*nextOut[category] = nextIn[i];
nextOut[category]++;
}
}
// Now I have my categoried arrays!
}
我想我的第一个内部循环不需要SIMD，它可以只是一个(x & 0xFF00FF00FF00FF00)指令，但我想知道我们是否可以将第二个内部循环变成SIMD指令.
是否有任何类型的 SIMD 指令可用于我正在执行的此“分类”操作？
“插入”指令看起来有点有希望，但我有点太新手，无法理解 https://software.intel.com/en-us/node/695331 中的描述。 .
如果不是，有什么接近的吗？
谢谢!
最佳答案
您可以使用 SIMD 来完成此操作，但它的速度具体取决于您可用的指令集以及您在实现过程中的聪明程度。
一种方法是获取数组并“筛选”它以分离出属于不同存储桶的元素。例如，从数组中获取 32 个字节，其中包含 16 个 16 位元素。使用一些 cmpgt 指令获取掩码，该掩码确定每个元素是属于 00 + 01 存储桶还是 02 + 03 存储桶。然后使用某种“压缩”或“过滤”操作将所有屏蔽元素连续移动到寄存器的一端，然后对未屏蔽元素进行同样的操作。
然后再重复一次，从 01 中筛选出 00，从 03 中筛选出 02。
使用 AVX2，您可以从 this question 开始获取“压缩”操作的灵感。使用 AVX512，您可以使用 vcompress 指令来帮助解决:它完全执行此操作，但仅以 32 位或 64 位粒度进行，因此您至少需要为每个 vector 执行几次操作。
您还可以尝试垂直方法，加载 N 个 vector ，然后在它们之间交换，以便第 0 个 vector 具有最小元素等。此时，您可以在压缩阶段使用更优化的算法(例如,.如果您垂直排序足够多的 vector ，则末尾的 vector 可能完全以 0x00 开头，等等)。
最后，您还可以考虑以不同的方式组织数据，无论是在源还是作为预处理步骤:从有效负载字节中分离出始终为 0-3 的“类别”字节。许多处理步骤只需要在其中一个或另一个上发生，因此您可以通过以这种方式拆分它们来潜在地提高效率。例如，您可以对所有类别的 32 个字节进行比较操作，然后对 32 个有效负载字节进行压缩操作(至少在每个类别都是唯一的最后一步中)。
这将导致字节元素数组，而不是 16 位元素，其中“类别”字节是隐式的。您已将数据大小减少了一半，这可能会加快您将来想要对数据执行的所有其他操作。
如果您无法以这种格式生成源数据，则可以在将有效负载放入正确的存储桶时使用存储桶作为删除标签字节的机会，因此输出为uint8_t out[4 ][2048]；。如果您按照评论中的讨论使用 pshufb 字节洗牌进行 SIMD left-pack，则可以选择仅将有效负载字节打包到下半部分的洗牌控制 vector 。
(在 AVX512BW 之前，x86 SIMD 没有任何可变控制字混洗，只有字节或双字，因此您已经需要一个字节混洗，它可以在将有效负载字节打包到底部。)
关于我可以使用 SIMD 进行存储桶排序/分类吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52389997/