多项式求和的算法比较.ppt

多项式求和的算法比较,组员：朱振强、杨浩蓝、龙景强、程帆瑾、刘树培,首先我们来看一下代码： 问题一：对于次数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(i0) goto endloop; result *= x； result += ai goto loop; endloop:,再来看下这个循环的汇编代码： mulsd %xmm0,%xmm1 # result *= x addsd 0xb2f60a0(%rdi,%rax,1),%xmm1 # result += ai】 sub $0x8,%rax # i-, for 8-byte pointer cmp $0xfffffffff4d09f58,%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 $0x8,%rax # i+, for 8-byte pointer cmp $0xb2f60a8,%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，