2

我正在尝试优化QTC视频编解码器以在 Raspberry Pi 上以良好的性能工作。一个重要的瓶颈是在范围解码器中完成的 32 位整数除法，它占用了 18% 的解码时间。由于该设备的 ARM 处理器显然缺少整数除法指令，我认为可以轻松优化这一点。划分必须准确。

每次调用该特定除法中的被除数和除数都不同，但众所周知，除数总是小于 65536。我考虑过建立一个除数反值的查找表。使用该表，我可以使用乘法而不是除法。查找表的大小为 256 kibibytes。

问题

  1. 执行该优化是个好主意吗？
  2. 有没有更好的方法来摆脱软件部门？
  3. 有没有不同的方法来实现算法，使得没有除法？
  4. 其他想法？
4

2 回答 2

5

人们还可以利用这样一个事实，即 Raspberry Pi 包含一个能够执行双精度 FP 除法的 FP 单元，这比整数除法的软件模拟要快。a = b / c用a = (double)b / (double)c对我有用的替换所有整数除法。

于 2012-08-03T01:08:14.160 回答
2

如果你想使用魔法乘法 + LUT，这里有一些代码。

简单的测试器测试随机除数 i。没有详尽地测试所有我的，但在我运行它的短时间内工作。似乎适用于我测试的 i 的所有 32 位状态的股息 (j=0..2^32-1)。

实际上，您会预先计算 i=2..64k-1 或类似范围的查找表（i=0 不起作用，因为 value/0 未定义，而 i=1 不起作用，因为它的魔法乘数就在外面32 位数字的范围）。然后使用使用 i 作为查找索引的方程来获得魔法乘数“m”。根据需要进行更改，不要讨厌我的风格。:P

#include <stdio.h>

int main() {
  unsigned int i,j,k,m,c;

  // compute j/i,
  // compute k = 2^32/i
  // instead of j/i, use m = ~(j*k)>>32
  srand(time(0));
  for(c=0;c<64;c++) {
    // generate random divisor i's for testing, then fully test every j
    i = rand()&0x7fff;      
    // precompute these and put into a lookup table, index on [i]
    k = (((__int64)1)<<32)/i;  
    for(j=0;j!=-1;j++) {
      // status updater so we know it's working...
      if(!(j&0xfffff)) { printf("%d : %d     \r", i, j); fflush(0); }    
      // multiply instead of divide!
      m = (((__int64)j*k)+k/2)>>32; 
      // rare fixup
      if(j - m*i >= i) m++;                          
      if(m != j/i) {
        // as long as this line doesn't print, we're ok
        printf("wrong : %d %d %d   got: %d  should be: %d\n", 
            i, j, k, m, j/i);    
      }
    }
  }
}
于 2012-08-03T00:32:15.520 回答