11《直接内存映射-解决考试题（2）》计算机组成与体系结构系列课

一、引言

二、考题背景与特点

三、考题内容与分析

（一）问题描述

（二）计算缓存行数与元素存储

（三）代码段 P1 与 P2 的缓存未命中分析

（四）计算 M1 与 M2 的比率

四、总结

一、引言

大家好，欢迎回到我们的技术博客。今天，我们将继续深入探讨直接内存映射问题，通过解答往年的有趣考题，帮助大家更好地理解和掌握这一重要概念。

那么，让我们马上开始学习。

二、考题背景与特点

在本次课程中，我们将讨论一个来自 2006 年计算机科学 GATE 考试的问题。在 GATE 或其他竞争性考试中，计算机组织架构（COA）问题，通常具有以下特点：

有时候，问题篇幅较长，但这其实是一个好消息，因为问题越大，提供的信息就越多。我们只需要对这个主题有清晰的概念。
有时候，不同科目的概念会在一个问题中融合。就像这个问题一样，我们可以清楚地看出计算机组织架构和编程的概念在这里融合了。

解答这类问题，实际上可以帮助我们从更广泛的角度理解计算机科学不同科目之间的相互关联。

三、考题内容与分析

（一）问题描述

现在，让我们来看这个问题。

一个CPU有一个32千字节的直接映射缓存，块大小为128字节。这意味着缓存的大小是32千字节，块或行的大小是128字节。假设A是一个512×512的二维数组，每个元素占用8字节。这显然意味着A是一个有512行512列的二维数组。这里的每个元素将占用8字节。

现在考虑以下两个用C语言编写的代码段，这是P1和P2。

P1和P2分别独立执行，具有相同的初始状态。也就是说，数组A不在缓存中。所以，最初数组A不在缓存中，I、J、X意味着这里的I、J和X都在寄存器中。 P1产生的缓存未命中次数记为M1。所以，当它执行时，我们将其缓存未命中次数称为M1，P2的缓存未命中次数为M2。所以，对于P2，缓存未命中次数将是M2。

现在我们需要找出M1和M2之间的比率。所以，我们先来找出M1。

（二）计算缓存行数与元素存储

缓存大小给定为32千字节，这相当于2的15次方字节，因为32是2的5次方，千字节是2的10次方，结果是2的15次方。现在块大小给定为128字节，这相当于2的7次方，因为128是2的7次方。现在我们可以很容易地计算出缓存中的行数，即2的15次方除以2的7次方，结果是2的8次方，因为15减去7等于8。所以缓存中有256行，从缓存行号0开始，一直到缓存行号255。

现在，我们已经知道我们的二维数组，将有512行和512列，这是数组的概念表示。问题中还提到，每个数组元素的大小是8字节，或2的3次方字节。现在我们来计算每个缓存行可以存储多少个元素，即2的7次方除以2的3次方，因为行大小或块大小是2的7次方，每个元素的大小是2的3次方，结果是2的4次方，即16个元素可以存储在每个行中。

现在我们来计算存储数组的每一行需要多少行，也就是说，如果我们想把这一整行存储在缓存中，我们需要多少行。

现在你可以看到，每一行有512个元素，所以512除以每块或行的元素数，也就是说，每个行可以存储2的4次方，即16个元素，因此512除以2的4次方，结果是2的9次方减去4，因为512是2的9次方，结果是2的5次方，即32。所以在执行过程中，为了存储这一整行，我们需要这些行，从行号0开始，一直到行号31。

（三）代码段 P1 与 P2 的缓存未命中分析

现在来看代码段P1，外层for循环，即带有变量i的for循环，用于按行处理数组元素，而内层for循环，即带有变量j的for循环，用于按列处理数组元素。

当P1执行时，由于i和j的排列，数组元素将按行引用。因此，当第一次引用数组元素[0][0]时，我们知道数组最初不在缓存中，所以它将是一个强制性未命中。然后，由于我们的机制，我们可以在一个缓存行中存储16个元素，所以从数组元素[0][0]开始到[0][15]的整个组将被放置在缓存行号0中。因此，当引用数组元素[0][1]、[0][2]到[0][15]时，它们将是缓存命中。

此后，当引用数组元素[0][16]时，它又将是一个强制性未命中。再次由于类似的机制，从[0][16]开始到[0][31]的数组元素组将被放置在缓存行号1中。

现在我们已经知道，为了存储这一整行，我们需要从0到31，即32个缓存行，在这32个缓存行中，第一个总是强制性未命中。因此，每行的缓存未命中数将是32，整个数组有512行。因此，P1经历的未命中数，即M1，是512乘以32，结果是16384。注意M1的值是16384。

现在我们来看P2。在P2的情况下，i和j的排列被反转了，也就是说，i变成了j，j变成了i。这意味着在P2的执行过程中，数组元素将按列引用。

现在当i为0，j为0时，数组的第一个元素，即[0][0]，将被引用，由于P2的独立执行，缓存将再次为空，它将是一个强制性未命中。但由于我们的机制，从[0][0]到[0][15]的元素组将被放置在缓存行号0中，但这些将没有用处，因为j的值增加，即j++将导致1，下一个引用的数组元素将是[1][0]。由于它不在缓存中，它又将是一个强制性未命中，所以由于我们的机制，数组元素[1][0]将被带入缓存，但与此同时，从[1][1]到[1][15]的整个元素组将再次被放置在同一个缓存行1中。现在整个数组有512列，由于P2中i和j的修改排列，每列的缓存未命中数将是512。