Any*_*orn 16 optimization performance integer division
我正在研究GPU设备,它具有非常高的除法整数延迟,数百个周期.我希望优化分歧.
分母中的所有除法都在集合{1,3,6,10}中,但分子是运行时正值,大约为32000或更小.由于内存限制,查找表可能不是一个好的选择.
你能想到其他选择吗？我曾想过计算浮点反转,并使用它们来乘以分子.
谢谢
PS.谢谢你们.位移黑客真的很酷.为了从舍入中恢复,我使用以下C段:
// q = m/n
q += (n*(j +1)-1) < m;
dra*_*ard 10
a/b=a*(1/b)
x=(1<<16)/b
a/b=(a*x)>>16
你能为分母建立一个查找表吗？因为你说15位分子,如果所有的都是无符号32位,你可以使用17作为移位:
a/b=a*((1<<17)/b)>>17
移位越大,舍入误差越小.你可以进行强力检查,看看有多少次,如果有的话,这实际上是错误的.
标准嵌入式系统的目的是将整数除以N转换为定点乘法1/N.
假设16位,0.33333可以表示为21845(十进制).乘以,给出32位整数乘积,并向下移16位.
您几乎肯定会遇到一些舍入(截断)错误.这可能是也可能不是你可以忍受的东西.
可能值得仔细研究你的GPU,看看你是否可以手动编写更快的整数除法程序,利用你对分子限制范围的了解.
亨利·沃伦(Henry Warren)所着的"黑客喜悦"(Hacker's Delight)一书中有一整章专门用于按常数进行整数除法,包括将整数除法转换为乘法/移位/加法运算系列的技术.
此页面计算乘法/移位/添加操作的幻数: