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

多项式求和的算法比较 组员：朱振强、杨浩蓝、龙景强、程帆瑾、刘树培 首先我们来看一下代码： 问题一：对于次数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 + a[i]; return result; 在第一次讨论课的时候我们知道了所有的for循环在汇编时都会变为if语句，让我们来看一下这个for循环变为if语句是什么样的。 i=degree-1 loop: if(i0) {goto endloop; } result *= x； result += a[i] goto loop; endloop: 再来看下这个循环的汇编代码： mulsd %xmm0,%xmm1 # result *= x addsd 0xb2f60a0(%rdi,%rax,1),%xmm1 # result += a[i】 sub $0x8,%rax # i--, for 8-byte pointer cmp $0xfffffffff4d09f58,%rax # compare 0 : i jne 400690 polyh+0x10 # if !=, goto loop 注：i in %rax, a in %rdi, x in %xmm0, result in %xmm1 从来自上一次迭代的 result 的值开始，我们必须先把它乘以 x (需要 5 个时钟周期)，然后把它加上 a[i] (需要 3 个时钟周期)，然后得到本次迭代的值。因此，完成一次循环迭代需要 8 个时钟周期。由于后一个表达式 result += a[i] 的计算需要前一个表达式 result *= x 的值，所以这两个表达式的计算不能在流水线上同时进行。 问题三： 5.5的for循环: for ( i = 1; i =degree; i++,) {result += a[i] * xpwr; xpwr=x*xpwr;} 将其转换为if语句： i=1 loop: if(idegree) {goto endloop; } z *=xpwr； xpwr*=x result += z goto loop; endloop: 它的汇编代码如下： 400650 movsd (%rdi,%rax,1),%xmm3 # z = a[i] 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 poly+0x10 # 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个时钟周期。 * *