多项式求和的算法比较(精品)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,多项式求和的算法比较,组员：朱振强、杨浩蓝、龙景强、程帆瑾、刘树培,首先我们来看一下代码：,问题一：对于次数n,这段代码执行了多少次加法和乘法运算？,乘法：N 加法：N,问题二：该运算的cep为何为8？,图5-12,双精度浮点数乘法:延迟 5 发射时间 1,双精度浮点数加法:延迟 3 发射时间 1,单精度浮点数乘法:延迟 4 发射时间 1,单精度浮点数加法:延迟 3 发射时间 1,整数乘法：延迟 3 发射时间 1,整数加法：延迟 1 发射时间 0.33,for,（,i=,degree,-1;i=0;i-),result=result*x+ai;,return result;,在第一次讨论课的时候我们知道了所有的for循环在汇编时都会变为if语句，让我们来看一下这个for循环变为if语句是什么样的。,i=degree-1,loop:,if(i,0),goto endloop;,result*=x,；,result+=ai,goto loop;,endloop:,再来看下这个循环的汇编代码：,mulsd%xmm0,%xmm1#result*=x,addsd 0 xb2f60a0(%rdi,%rax,1),%xmm1#result+=ai】,sub$0 x8,%rax#i-,for 8-byte pointer,cmp$0 xfffffffff4d09f58,%rax#compare 0:i,jne 400690#if!=,goto loop,注：i in%rax,a in%rdi,x in%xmm0,result in%xmm1,从来自上一次迭代的 result 的值开始，我们必须先把它乘以 x(需要 5 个时钟周期)，然后把它加上 ai(需要 3 个时钟周期)，然后得到本次迭代的值。因此，完成一次循环迭代需要 8 个时钟周期,。由于后一个表达式 result+=ai 的计算需要前一个表达式 result*=x 的值，所以这两个表达式的计算不能在流水线上同时进行。,问题三：,5.5的for循环:,for(i=,1,;i degree,),goto endloop;,z,*=xpwr；,xpwr*=x,result+=,z,goto loop;,endloop:,它的汇编代码如下：,400650,movsd (%rdi,%rax,1),%xmm3,#z=ai,add$0 x8,%rax,#i+,for 8-byte pointer,cmp$0 xb2f60a8,%rax,#compare N:i,mulsd%xmm1,%xmm3#z*=p,mulsd%xmm0,%xmm1#p*=x,addsd%xmm3,%xmm2#result+=z,jne 400650,#if!=,goto loop,注：i in%rax,a in%rdi,x in%xmm0,p in%xmm1,result in%xmm2,z in%xmm3,我们可以看到，这里限制性能的计算是反复地计算表达式 p*=x。这需要一个双精度浮点数乘法(5个时钟周期)，并且直到前一次迭代完成，下一次迭代的计算才能开始。两次连续的迭代之间，还要计算表达式 z*=p，这需要一个双精度浮点乘法(5个时钟周期)，以及计算表达式 result+=z，这需要一个双精度浮点加法(3个时钟周期)。这三个涉及浮点数运算的表达式的计算都可以在流水线上同时地进行。最终，完成一次循环迭代需要5个时钟周期。,谢谢！,