第 6 章家庭作业：6.31～6.37

家庭作业 6.31（★★）假设程序使用作业 6.30 中的高速缓存，引用位于地址 0x071A 处的 1 字节字。用十六进制表示出它所访问的高速缓存条目，以及返回的高速缓存字节值。指明是否发生了高速缓存不命中。如果有高速缓存不命中，对于“返回的高速缓存字节”输入“—”。提示：注意那些有效位！

A. 地址格式（每个小框表示一位）：

12	11	10	9	8	7	6	5	4	3	2	1	0

B. 内存引用：

参数	值
高速缓存块偏移（CO）	`0x______`
高速缓存组索引（CI）	`0x______`
高速缓存标记（CT）	`0x______`
高速缓存命中？（是/否）
返回的高速缓存字节	`0x______`

家庭作业 6.32（★★）对于内存地址 0x16E8 重复作业 6.31。

A. 地址格式（每个小框表示一位）：

12	11	10	9	8	7	6	5	4	3	2	1	0

B. 内存引用：

参数	值
高速缓存块偏移（CO）	`0x______`
高速缓存组索引（CI）	`0x______`
高速缓存标记（CT）	`0x______`
高速缓存命中？（是/否）
返回的高速缓存字节	`0x______`

家庭作业 6.33（★★）对于作业 6.30 中的高速缓存，列出会在组 2 中命中的 8 个内存地址（以十六进制表示）。

家庭作业 6.34（★★）考虑下面的矩阵转置函数：

typedef int array[4][4];

void transpose2(array dst, array src)
{
    int i, j;

    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            dst[j][i] = src[i][j];
        }
    }
}

假设这段代码运行在一台具有如下属性的机器上：

sizeof(int)==4。
数组 src 从地址 0 开始，而数组 dst 从地址 64 开始（十进制）。
只有一个 L1 数据高速缓存，它是直接映射、直写、写分配的，块大小为 16 字节。
这个高速缓存总共有 32 个数据字节，初始为空。
对 src 和 dst 数组的访问分别是读和写不命中的唯一来源。

对于每个 row 和 col，指明对 src[row][col] 和 dst[row][col] 的访问是命中（h）还是不命中（m）。例如，读 src[0][0] 会不命中，而写 dst[0][0] 也会不命中。

dst 数组

	列 0	列 1	列 2	列 3
行 0	m
行 1
行 2
行 3

src 数组

	列 0	列 1	列 2	列 3
行 0	m
行 1
行 2
行 3

家庭作业 6.35（★★）对于一个总大小为 128 数据字节的高速缓存，重复练习题 6.34。

dst 数组

	列 0	列 1	列 2	列 3
行 0	m
行 1
行 2
行 3

src 数组

	列 0	列 1	列 2	列 3
行 0	m
行 1
行 2
行 3

家庭作业 6.36（★★）这道题测试你预测 C 语言代码的高速缓存行为的能力。对下面这段代码进行分析：

int x[2][128];
int i;
int sum = 0;

for (i = 0; i < 128; i++) {
    sum += x[0][i] * x[1][i];
}

假设我们在下列条件下执行这段代码：

sizeof(int)==4。
数组 x 从内存地址 0x0 开始，按照行优先顺序存储。
在下面每种情况中，高速缓存最开始时都是空的。
唯一的内存访问是对数组 x 的条目进行访问。其他所有的变量都存储在寄存器中。

给定这些假设，估计下列情况中的不命中率：

A. 情况 1：假设高速缓存是 512 字节，直接映射，高速缓存块大小为 16 字节。不命中率是多少？

B. 情况 2：如果我们把高速缓存的大小翻倍到 1024 字节，不命中率是多少？

C. 情况 3：现在假设高速缓存是 512 字节，两路组相联，使用 LRU 替换策略，高速缓存块大小为 16 字节。不命中率是多少？

D. 对于情况 3，更大的高速缓存大小会帮助降低不命中率吗？为什么能或者为什么不能？

E. 对于情况 3，更大的块大小会帮助降低不命中率吗？为什么能或者为什么不能？

家庭作业 6.37（★★）这道题也是测试你分析 C 语言代码的高速缓存行为的能力。假设我们在下列条件下执行图 6-47 中的 3 个求和函数：

sizeof(int)==4。
机器有 4KB 直接映射的高速缓存，块大小为 16 字节。
在两个循环中，代码只对数组数据进行内存访问。循环索引和值 sum 都存放在寄存器中。
数组 a 从内存地址 0x08000000 处开始存储。

对于 N=64 和 N=60 两种情况，在表中填写它们大概的高速缓存不命中率。

函数	N=64	N=60
`sumA`
`sumB`
`sumC`

typedef int array_t[N][N];

int sumA(array_t a)
{
    int i, j;
    int sum = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) {
            sum += a[i][j];
        }
    return sum;
}

int sumB(array_t a)
{
    int i, j;
    int sum = 0;
    for (j = 0; j < N; j++)
        for (i = 0; i < N; i++) {
            sum += a[i][j];
        }
    return sum;
}

int sumC(array_t a)
{
    int i, j;
    int sum = 0;
    for (j = 0; j < N; j+=2)
        for (i = 0; i < N; i+=2) {
            sum += (a[i][j] + a[i+1][j]
                    + a[i][j+1] + a[i+1][j+1]);
        }
    return sum;
}

图 6-47　作业 6.37 中引用的函数