注册 登录
开源计算机图形学社区(Open Source Computer Graphics Community) |OpenGPU Forum (2007-2013)| OpenGPU Project 返回首页

titer1的个人空间 http://www.opengpu.org/?43133 [收藏] [复制] [分享] [RSS]

日志

老牛的图形学积累 除法的优化

热度 12已有 2982 次阅读2015-1-29 21:52

<<代码优化-之-优化除法>>

 转自作者 HouSisong@GMail.com

tag:代码优化,除法,牛顿迭代,减法代替除法,除法优化

说明:文章中的很多数据可能在不同的CPU或不同的系统环境下有不同的结果,数据仅供参考


 x86系列的CPU对于位运算、加、减等基本指令都能在1CPU周期内完成(现在的CPU还能乱序执行,从而使指令的平均CPU周期更小);现在的CPU,做乘法也是很快的(需要几个CPU周期,每个周期可能启动一个新的乘指令(x87)),但作为基本指令的除法却超出很多人的预料,它是一条很慢的操作,整数和浮点的除法都慢;我测试的英特尔P5赛扬CPU浮点数的除法差不多是37CPU周期,整数的除法是80CPU周期,AMD2200+浮点数的除法差不多是21CPU周期,整数的除法是40CPU周期。(改变FPU运算精度对于除法无效) (SSE指令集的低路单精度数除法指令DIVPS 18CPU周期,四路单精度数除法指令DIVSS 36CPU周期) (x86求余运算和除法运算是用同一条CPU指令实现的; 据说,很多CPU的整数除法都是用数学协处理器的浮点除法器完成的;有一个推论就是,浮点除法和整数除法不能并行执行. (ps:intelp4 imul指令可能有14周期(15-18)的延迟才能得到结果)

本文将给出一些除法的优化方法或替代算法 (警告:某些替代算法并不能保证完全等价!)

1.尽量少用除法
 比如: if (x/y>z) ...
 改成: if ( ((y>0)&&(x>y*z))||((y<0)&&(x<y*z)) ) ...

(少用求余)
 比如: ++index; if (index>=count) index=index % count; //assert(index<count*2);
 改成: ++index; if (index>=count) index=index - count;

2.用减法代替除法
 如果知道被除数是除数的很小的倍数,那么可以用减法来代替除法
 比如: 

uint32 x=200;
 uint32 y=70;
 uint32 z=x/y;
 改成: uint z=0;
 while (x>=y)
 {
 x-=y; ++z;
 }

一个用减法和移位完成的除法 (如果你没有除法指令可用:)
 uint32 div(uint64 u,uint32 z) //return u/z
 {
 uint32 x=(uint32)(u>>32);
 uint32 y=(uint32)u;
 //y保存商 x保存余数

for (int i=0;i<32;++i)
 {
 uint32 t=((int32)x) >> 31;
 x=(x<<1)|(y>>31);
 y=y<<1;
 if ((x|t)>=z)
 {
 x-=z;
 ++y;
 }
 }
 return y;
 }
 (该函数经过了测试;z==0需要自己处理;对于有符号除法,可以用取绝对值的方法(当然也不是轻松就能
写出完全等价的有符号除法的:) 如果不需s64bit长度,仅需要32bit,那么可以化简这个函数,但改进不多)
 
 3.用移位代替除法 (很多编译器能自动做好这个优化)
 要求除数是2的次方的常量; (同理:对于某些应用,可以优先选取这样的数来做除数)
 比如: uint32 x=213432575;
  uint32 y=x/8;
 改成: y=x>>3;

对于有符号的整数;
 比如: 

int32 x=213432575;
 int32 y=x/8;
 改成: if (x>=0) y=x>>3;
 else y=(x+(1<<3-1))>>3;

4.合并除法 (替代方法不等价,很多编译器都不会帮你做这种优化)
 适用于不能用其它方法避免除法的时候;
 比如: double x=a/b/c;
 改成: double x=a/(b*c);

比如: double x=a/b+c/b;
 改成: double x=(a+c)/b;

比如: double x=a/b;
 double y=c/d;
 double z=e/f;
 改成: double tmp=1.0/(b*d*f);
 double x=a*tmp*d*f;
 double y=c*tmp*b*f;
 double z=e*tmp*b*d;
 
 5.把除法占用的时间充分利用起来
 CPU在做除法的时候,可以不用等待该结果(也就是后面插入的指令不使用该除法结果),而插入多条简单整数
指令(不包含整数除法,而且结果不能是一个全局或外部变量等),把除法占用的时间节约出来;
 (当除法不可避免的时候,这个方法很有用)

6.用查表的方法代替除法
 (适用于除数和被除数的可能的取值范围较小的情况,否则空间消耗太大)
 比如 uint8 x; uint8 y;
 uint8 z=x/y;
 改成 uint8 z=table[x][y]; //其中table是预先计算好的表,table[i][j]=i/j;
 //对于除零的情况需要根据你的应用来处理
 或者:uint8 z=table[x<<8+y]; //其中table[i]=(i>>8)/(i&(1<<8-1));

比如 uint8 x;
 uint8 z=x/17;
 改成 uint8 z=table[x]; //其中table[i]=i/17; 

未完待续


路过

鸡蛋
11

鲜花

握手

雷人

刚表态过的朋友 (11 人)

发表评论 评论 (1 个评论)

回复 noncode 2016-3-1 20:29

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册

‹‹
我的工具栏

关于我们|手机版|Archiver|开源计算机图形学社区(Open Source Computer Graphics Community) | OpenGPU Project | OpenGPU Forum (2007-2013)

GMT+8, 2017-12-15 04:41 , Processed in 0.035258 second(s), 16 queries .

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部