3

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

我将首先尝试描述问题：

我有一个v[]70 位整数的静态数组（其中大约 400,000 个），它们在编译时都是已知的。

生产者创建 70 位整数a，其中很多，非常快。

对于每个a我需要找出是否存在一个元素 from vwhich 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 位
  • 平均检查大约 20% 后，该FOUND条件有望得到满足。v[]
  • a在批量检查它们之前，可以缓冲一个以上。
  • 我不一定需要知道v[]匹配的哪个元素，只需要知道那个匹配或不匹配。
  • 生产a只需要很少的内存，所以之前调用在 L1 中留下的任何东西都可能仍然存在。

生成的代码旨在在支持 SSE4.2、AVX 指令的最新一代英特尔至强处理器上运行。我很乐意接受使用英特尔 C 编译器或至少 GCC 编译的程序集或 C。

4

1 回答 1

3

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

考虑如果(v[0] & v[1]) & a不为零，则既不(v[0] & a)也(v[1] & a)不可能为零。这意味着可以创建一个树结构，其中 v[] 是叶子，父节点是其子节点的 AND 组合。然后，如果parentNode & a给你一个非零值，你可以跳过看孩子。

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

另一方面，这样的树搜索涉及很多条件分支（昂贵），并且很难向量化。如果您可以仅使用两个级别，我将首先尝试：首先在集群父节点之间进行矢量化搜索，然后为每个匹配项搜索该集群中的条目。

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

通过针对数组索引测试掩码a，您将知道要搜索 64 个数组中的哪一个（在最坏的情况下，如果a没有设置任何 6 个最高位，那就是全部），以及每个人数组搜索仅处理每个元素 64 位（更容易打包）。

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

于 2012-10-14T17:40:18.760 回答