performance - 分母已知时更快的整数除法？

Question

我正在研究具有非常高的除法整数延迟、数百个周期的 GPU 设备。我正在寻找优化部门。

在集合 { 1,3,6,10 } 中按分母的所有除法，但分子是运行时正值，大约为 32000 或更少。由于内存限制，查找表可能不是一个好的选择。

你能想到替代方案吗？我曾想过计算浮点逆数，并使用它们来乘分子。

谢谢

PS。谢谢大家。bit shift hack 真的很酷。为了从舍入中恢复，我使用以下 C 段：

// q = m/n
q += (n*(j +1)-1) < m;

Answer 1

a/b=a*(1/b)
x=(1<<16)/b
a/b=(a*x)>>16

你能为分母建立一个查找表吗？既然你说的是 15 位分子，那么如果一切都是无符号的 32 位，你可以使用 17 进行移位：

a/b=a*((1<<17)/b)>>17

偏移越大，舍入误差越小。您可以进行蛮力检查，看看有多少次，如果有的话，这实际上是错误的。

Answer 2

Henry Warren所著的《Hacker's Delight》一书有一整章专门介绍了用常量进行整数除法，包括将整数除法转换为乘法/移位/加法系列操作的技术。

此页面计算乘法/移位/加法操作的幻数：

• http://www.hackersdelight.org/magic.htm

Answer 3

标准的嵌入式系统破解方法是将整数除以 N 转换为定点乘以 1/N。

假设 16 位，0.33333 可以表示为 21845（十进制）。相乘，得到一个 32 位整数乘积，然后向下移动 16 位。

您几乎肯定会遇到一些舍入（截断）错误。这可能是也可能不是你可以忍受的东西。

可能值得仔细研究一下您的 GPU，看看您是否可以利用您对分子受限范围的了解，手动编写一个更快的整数除法例程。