algorithm - 位旋转帮助 : Expanding bits to follow a given bitmask

Question

我对一种“扩展位”的快速方法很感兴趣，它可以定义如下:

1. 设 B 是一个有 n 位的二进制数，即 B\in {0,1}^n
2. 设P为B中所有1/true位的位置，即1 << p[i] & B == 1 , 和 |P|=k
3. 对于另一个给定的数，A\in {0,1}^k，令Ap 为 Ap 的位扩展形式em>A 给定 B，使得 Ap[j] == A[j] << p[j] .
4. “位展开”的结果是Ap。

几个例子:

• 给定B:0010 1110，A:0110，然后Ap 应该是 0000 1100
• 给定 B:1001 1001，A:1101，那么Ap应该是1001 0001

以下是一个简单的算法，但我不禁觉得有一种更快/更简单的方法可以做到这一点。

unsigned int expand_bits(unsigned int A, unsigned int B, int n) {
  int k = popcount(B); // cuda function, but there are good methods for this
  unsigned int Ap = 0;
  int j = k-1;
  // Starting at the most significant bit,
  for (int i = n - 1; i >= 0; --i) {
    Ap <<= 1;
    // if B is 1, add the value at A[j] to Ap, decrement j. 
    if (B & (1 << i)) {
      Ap += (A >> j--) & 1;
    }
  }
  return Ap;
}

Answer 1

问题似乎是要求对 BMI2 指令进行 CUDA 仿真 PDEP ，它采用源操作数 a , 并根据掩码的 1 位的位置存放它的位 b .在当前出货的 GPU 上，没有硬件支持相同或类似的操作；也就是说，直到并包括 Maxwell 架构。

根据给出的两个示例，我假设掩码 b通常是稀疏的，我们可以通过仅迭代 b 的 1 位来最小化工作量.这可能会导致 GPU 上的不同分支，但在不了解特定用例的情况下，性能的确切权衡是未知的。现在，我假设在掩码中利用稀疏性 b与背离的负面影响相比，对性能的正面影响更强。

在下面的仿真代码中，我减少了可能“昂贵”的移位操作的使用，而是主要依赖简单的 ALU 指令。在各种 GPU 上，移位指令的执行吞吐量低于简单的整数运算。我在代码中保留了一个单一的转变，离开关键路径，以避免执行受到算术单元的限制。如果需要，表达式 1U << i可以用加法代替:引入一个变量m初始化为 1在循环之前，每次循环都加倍。

基本思想是隔离掩码的每个 1 位 b依次(从最低有效端开始)，并将其与 a 的第 i 位的值进行运算，并将结果合并到扩展目标中。在来自 b 的 1 位之后已经使用过，我们将其从掩码中移除，并迭代直到掩码变为零。

为了避免移动 a 的第 i 位到位，我们简单地隔离它，然后通过简单的否定将它的值复制到所有更重要的位，利用整数的二进制补码表示。

/* Emulate PDEP: deposit the bits of 'a' (starting with the least significant 
   bit) at the positions indicated by the set bits of the mask stored in 'b'.
*/
__device__ unsigned int my_pdep (unsigned int a, unsigned int b)
{
    unsigned int l, s, r = 0;
    int i;
    for (i = 0; b; i++) { // iterate over 1-bits in mask, until mask becomes 0
        l = b & (0 - b); // extract mask's least significant 1-bit
        b = b ^ l; // clear mask's least significant 1-bit
        s = 0 - (a & (1U << i)); // spread i-th bit of 'a' to more signif. bits
        r = r | (l & s); // deposit i-th bit of 'a' at position of mask's 1-bit
    }
    return r;
}

上面提到的没有任何移位操作的变体如下所示:

/* Emulate PDEP: deposit the bits of 'a' (starting with the least significant 
   bit) at the positions indicated by the set bits of the mask stored in 'b'.
*/
__device__ unsigned int my_pdep (unsigned int a, unsigned int b)
{
    unsigned int l, s, r = 0, m = 1;
    while (b) { // iterate over 1-bits in mask, until mask becomes 0
        l = b & (0 - b); // extract mask's least significant 1-bit
        b = b ^ l; // clear mask's least significant 1-bit
        s = 0 - (a & m); // spread i-th bit of 'a' to more significant bits
        r = r | (l & s); // deposit i-th bit of 'a' at position of mask's 1-bit
        m = m + m; // mask for next bit of 'a'
    }
    return r;
}

在下面的评论中，@Evgeny Kluev 指出了一个免类次 PDEP在 chessprogramming 处进行仿真看起来可能比我上面的两个实现中的任何一个更快的网站；看来值得一试。