c - x86-64 整数向量化优化

Question

我正在尝试将逻辑验证问题矢量化以在 Intel 64 上运行。

我首先尝试描述问题:

我有一个 70 位整数(大约 400,000 个)的静态数组 v[]，这些整数在编译时都是已知的。

生产者创建 70 位整数 a，数量很多，速度非常快。

对于每个a，我需要找出v中是否存在一个元素，其中v[i] & a == 0 .

到目前为止，我在 C 中的实现是这样的(简化的):

for (; *v; v++) {
    if (!(a & *v))
        return FOUND;
}

// a had no matching element in v
return NOT_FOUND;

我正在考虑使用 SSE/AVX 对此进行优化，以加快流程并并行执行更多测试。我将 a 和 *v 分别加载到 XMM 寄存器中，并调用 PTEST 指令来执行操作验证。

我想知道是否有办法扩展它以使用新 YMM 寄存器的所有 256 位？也许将 3x70 位打包到一个寄存器中？我不太清楚如何有效地打包/解包它们，以证明每个测试不仅仅使用一个寄存器。

关于输入性质我们了解的一些事情:

• v[] 中的所有元素都设置了很少的位
• 不可能以任何方式排列/压缩 v[] 以使其使用少于 70 位
• 平均检查 v[] 上的 appx 20% 后，预计会满足 FOUND 条件。
• 在批量检查之前可以缓冲多个a。
• 我不一定需要知道 v[] 的哪个元素匹配，只需知道匹配或不匹配即可。
• 生成 a 需要很少的内存，因此上一次调用中留在 L1 中的任何内容可能仍然存在。

生成的代码旨在在支持 SSE4.2、AVX 指令的最新一代 Intel Xeon 处理器上运行。我很乐意接受使用 Intel C 编译器或至少 GCC 编译的汇编语言或 C 语言。

Answer 1

这听起来像您真正需要的是一个更好的数据结构来存储 v[]，以便搜索花费的时间少于线性时间。

考虑一下，如果 (v[0] & v[1]) & a 不为零，则 (v[0] & a) 和 都不是零>(v[1] & a) 可以为零。这意味着可以创建一个树结构，其中 v[] 是叶子，父节点是其子节点的 AND 组合。然后，如果 parentNode & a 为您提供非零值，您可以跳过查看子节点。

但是，这不一定有帮助 - 父节点最终只会测试子节点之间的公共(public)位，因此如果只有其中几个，您最终仍然会测试大量离开节点。但是，如果您可以在数据集中找到聚类，并将许多相似的 v[] 分组到一个共同的父级下，这可能会大大减少您必须执行的比较次数。

另一方面，这样的树搜索涉及大量条件分支(昂贵)，并且很难向量化。我首先尝试是否可以只使用两个级别:首先在集群父节点中进行矢量化搜索，然后针对每个匹配搜索该集群中的条目。

<小时/>

实际上，这是另一个想法，可以帮助解决 70 位不太适合寄存器的问题:您可以将 v[] 拆分为 64 (=2^6) 个不同的数组。在原始 v[] 的 70 位中，最高 6 位用于确定哪个数组将包含该值，只有剩余的 64 位实际存储在数组中。

通过针对数组索引测试掩码 a，您将知道要搜索 64 个数组中的哪一个(在最坏的情况下，如果 a 没有任何6 个最高位组中的所有位)，并且每个单独的数组搜索仅处理每个元素 64 位(更容易打包)。

事实上，第二种方法也可以推广到树结构中，这会给你某种 trie .