**5.13**
A.
B. 由浮点数加法的延迟，CPE的下界应该是3。
C. 由整数加法的延迟，CPE的下界应该是1.
D. 由A中的数据流图，虽然浮点数乘法需要5个周期，但是它没有“数据依赖”，也就是说，每次循环时的乘法不需要依赖上一次乘法的结果，可以各自独立进行。但是加法是依赖于上一次的结果的（sum = sum + 乘法结果），所以该循环的“关键路径”是加法这条链。而浮点数加法的延迟为3个周期，所以CPE为3.00。
5.14
A. 由5.13中分析的，关键路径是一个加法，而整数加法的延迟为1个周期，所以CPE的下界为1。
更新：题意弄错，不是只分析6*1整数运算，跳跳熊12138指出，已更正。
下面是跳跳熊12138给的答案：
B. “6 * 1 loop unrolling”只减少了循环的次数（所以整数的CPE下降了，书上把这个称为“overhead”），并没有减少内存读写的次数和流水线的发生，所以浮点数运算还是不能突破“关键路径”的CPE下界。
5.15
/* 6 * 6 loop unrolling */
/*省略*/
data_t sum1 = (data_t) 0;
data_t sum2 = (data_t) 0;
data_t sum3 = (data_t) 0;
data_t sum4 = (data_t) 0;
data_t sum5 = (data_t) 0;
for(i = 0; i < length; i += 6)
{
sum1 = sum1 + udata[i] * vdata[i]; /* 相互独立，可以流水线 */
sum2 = sum2 + udata[i+1] * vdata[i+1];
sum3 = sum3 + udata[i+2] * vdata[i+2];
sum4 = sum4 + udata[i+3] * vdata[i+3];
sum5 = sum5 + udata[i+4] * vdata[i+4];
sum6 = sum6 + udata[i+5] * vdata[i+5];
}
for(; i < length; ++i)
{
sum1 = sum1 + udata[i] * vdata[i];
}
*dest = sum1 + sum2 + sum3 + sum4 + sum5 + sum6;
虽然此时可以流水线，但是浮点数加法的单元的Issue time为1个周期，而Capacity也为1，所以最多每个时钟周期完成I/C = 1个加法操作，即此时CPE的下界为1。
5.16
/* 6 * 1a loop unrolling */
/*省略*/
data_t sum1 = (data_t) 0;
data_t sum2 = (data_t) 0;
data_t sum3 = (data_t) 0;
data_t sum4 = (data_t) 0;
data_t sum5 = (data_t) 0;
for(i = 0; i < length; i += 6)
{
sum = sum + (udata[i] * vdata[i] + udata[i+1] * vdata[i+1] + udata[i+2] * vdata[i+2] + udata[i+3] * vdata[i+3] + udata[i+4] * vdata[i+4] + udata[i+5] * vdata[i+5]);
}
for(; i < length; ++i)
{
sum = sum + udata[i] * vdata[i];
}
*dest = sum;
5.17
#include <limits.h>
#define K sizeof(unsigned long)
void *word_memset(void *s, int c, size_t n)
{
if (n < K)
{
size_t cnt = 0;
unsigned char *schar = s;
while (cnt < n)
{
*schar++ = (unsigned char)c;
cnt++;
}
}
else
{
unsigned long word = 0;
for (int i = 0; i < K; ++i)
{
word <<= K*CHAR_BIT;
word += (unsigned char)c;
}
size_t cnt = 0;
unsigned long *slong = s;
while (cnt < n)
{
*slong++ = word;
cnt += K;
}
unsigned char *schar = slong;
while (cnt < n)
{
*schar++ = (unsigned char)c;
cnt++;
}
}
return s;
}
5.18
答案不唯一，我这里是利用10 × 10的loop unrolling改“direct evaluation”的版本。
原函数的瓶颈在于xpwr = xpwr * x这一句，乘法数据依赖，由书上给出的K >= L*C （第540面），其中L是latency，C是capacity，由于浮点数乘法分别对应5和2，所以这里的K选择为10。
另外，K大的时候很可能会碰到寄存器不够的情况，不得不使用栈来保存局部变量（运行的时候会加载到高速缓存），会有一些性能上的牺牲。
double faster_poly(double a[], double x, long degree)
{
long i;
double result1 = a[0];
double result2 = 0;
double result3 = 0;
double result4 = 0;
double result5 = 0;
double result6 = 0;
double result7 = 0;
double result8 = 0;
double result9 = 0;
double result10 = 0;
double xpwr1 = x;
double xpwr2 = xpwr1 * x;
double xpwr3 = xpwr2 * x;
double xpwr4 = xpwr3 * x;
double xpwr5 = xpwr4 * x;
double xpwr6 = xpwr5 * x;
double xpwr7 = xpwr6 * x;
double xpwr8 = xpwr7 * x;
double xpwr9 = xpwr8 * x;
double xpwr10 = xpwr9 * x;
double x10 = xpwr10;
for (i = 1; (i+9) <= degree; i += 10)
{
result1 += a[i] * xpwr1;
result2 += a[i+1] * xpwr2;
result3 += a[i+2] * xpwr3;
result4 += a[i+3] * xpwr4;
result5 += a[i+4] * xpwr5;
result6 += a[i+5] * xpwr6;
result7 += a[i+6] * xpwr7;
result8 += a[i+7] * xpwr8;
result9 += a[i+8] * xpwr9;
result10 += a[i+9] * xpwr10;
xpwr1 *= x10;
xpwr2 *= x10;
xpwr3 *= x10;
xpwr4 *= x10;
xpwr5 *= x10;
xpwr6 *= x10;
xpwr7 *= x10;
xpwr8 *= x10;
xpwr9 *= x10;
xpwr10 *= x10;
}
for (; i <= degree; ++i)
{
result1 += a[i] * xpwr1;
xpwr1 *= x;
}
result1 += result2;
result1 += result3;
result1 += result4;
result1 += result5;
result1 += result6;
result1 += result7;
result1 += result8;
result1 += result9;
result1 += result10;
return result1;
}
5.19
瓶颈在于val=val+a[i] （书上还加了last_val ，一个意思）这一句，加法数据依赖，由书上给出的K >= L*C （第540面），其中L是latency，C是capacity，由于浮点数加法分别对应3和1，所以这里选择3*1a。
void faster_psum1a(float a[], float p[], long n)
{
long i;
float val = 0;
for (i = 0; (i+2) < n; i += 3)
{
float tmp1 = a[i];
float tmp2 = tmp1 + a[i+1];
float tmp3 = tmp2 + a[i+2];
p[i] = var + tmp1;
p[i+1] = var + tmp2;
p[i+2] = var = var + tmp3;
}
for (; i < n; ++i)
{
var += a[i];
p[i] = var;
}
}