改进的超越函数分段线性逼近方法

《改进的超越函数分段线性逼近方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、改进的超越函数分段线性逼近方法针对超越函数计算机X络中所采用的分段线性逼近算法存在的无法提前确定精度及部分区间资源浪费的问题，提出一种改进的分段线性逼近超越函数算法。该算法由预定义的逼近区间端点计算出用于逼近的线性函数，根据被逼近函数的凹凸性对所计算线性函数进行调整，在此基础上计算出预定义逼近区间内调整后函数与被逼近函数之间的最大误差;按照所需精度的要求，自动调整逼近区间，通过该过程的迭代，获得了较少分段次数。算法结果在Matlab上进行仿真，仿真结果表明，所提算法的分段数相比等分法减少了60%。所提算法在保证精度的前提下，降低了查找表(

2、LUT)的资源消耗。0引言图形处理器(GraphicsProcessingUnit，GPU)是各种嵌入式系统、个人机(Personalputer，PC)、工作站和游戏机等不可缺少的重要部件。浮点超越函数单元是GPU数据通路中的重要部件，其性能直接影响图形渲染效果[1-2]。目前在现场可编程门阵列(FieldProgrammableGateArray，FPGA)中计算超越函数常用的方法有级数近似法、查表法(LookUpTable，LUT)、坐标旋转数字计算(CoordinateRotationDigitalputer，CORDIC)算法和分

3、段线性逼近法等。其中，级数近似法展开式较为复杂，硬件实现复杂，资源消耗较大。查表法虽然计算简单、易于实现，但是所需存储单元随着计算精度的提高呈指数形式增加，资源消耗大[3]。CORDIC算法[4]作为一种便于FPGA实现的超越函数计算方法得到了广泛关注，但其收敛速度与数据的表示精度成反比，当精度要求较高时，算法的迭代次数较多，计算延迟会增大。与之相比，分段线性逼近法[5-6]将低阶多项式与较小的查找表相结合，资源消耗少，速度较快，被广泛应用于传感X络中的数据压缩[7]、非线性模型到线性模型的转换[8]以及图形图像处理[9]等领域，已成为在

4、计算资源有限条件下超越函数计算的一种较为理想的选择。为了提高函数的计算速度，在硬件设计中一般利用查找表实现分段线性逼近算法[6]，段数越多，查找表越大，误差则越小，因此，分段线性逼近算法需要在查找表、精度和分段数目之间寻求一个合理的平衡。其中有均方误差法[10]、区间2k等分法[11]、面积法[12]等多种分段算法，但这些算法都是在计算完成后才可以知道分段精度，难以在精度已知的条件下完成分段数的计算。文献[6]中提出了一种超越函数计算的最佳等距分段线性逼近(OptimalEquiDistantPieceation，OED_Pax=f(x)

5、-y1(x)，对dmax求导数，令导数等于零，将得到x的值，代入dmax计算出最大误差。在本文的改进型分段线性逼近算法中，所有数据采用双精度类型，在每个分段区间上，判断被逼近函数的凹凸性以及该函数在区间内是否存在拐点，求取逼近直线以及被逼近函数之间的最大误差，然后与给定误差进行比较：若小于给定误差，则停止该段的继续细分;若大于给定误差，则对该段逼近区间继续细分。若删除，可从此处删除伪代码。下面是改进型的分段线性逼近算法的C语言伪代码。图3的表述，与此处的“c语言伪代码”?是否有重复表达现象，是否可以删除某一种表述方式?请明确。回复：其中分

6、段区间没有问题，还有就是那个关于伪代码和流程图重复问题，我和我们老师商量了，可以删除也可以不删除，如果要删除，就把伪代码部分删除。(附件是删除伪代码的稿件)：程序前voidsubsection(doublex0，doublex1){doubley0=x0坐标处要逼近的函数值f(x0);doubley1=x1坐标处要逼近的函数值f(x1);y′=f″(x)=sign/对逼近函数求导判断凹凸性，sign=1表示凸函数，sign=0表示凹函数/令f′(c)=0求出c值，c则为函数逼近区间内的拐点;if(y′=0)/函数有拐点/{重新划分逼近区间

7、为[x0，c]及[c，x1]，确保每段新的逼近区间都是单调的;}else;mid=(x0+x1)/2.0;a=(y1-y0)/(x1-x0);b=y1-a(x1);max=d=f(mid)-(amid+b);/mid坐标处的逼近误差/if(sign==1)b1=b+d/2.0;elseb1=b-d/2.0;y1(x)=ax+b1;//得到新的逼近直线y1d=f(x)-y//被逼近函数与逼近函数的差值d′=f′(x)-y′//对函数d求导数d′=f(m)-y1′(m)=0//求函数的极值点mmax=f(m)-y1(m);//逼近区间内的最大

8、误差if(max指定误差){打印x0，x1坐标，并打印逼近直线参数m及n到指定文档;}else{subsection(x0，mid);subsection(mid，x1);}}//说明：x0与