受this recent question on SO and the answers given的启发,这让我感到非常无知,我决定花一些时间来了解有关 CPU缓存的更多信息,并编写了一个小程序来验证我是否对这件事做得正确(很可能不是,我是害怕)。我将首先写下构成我期望的假设,因此,如果这些假设是错误的,您可以在这里阻止我。根据我所阅读的内容,通常:
n
方式的关联高速缓存分为s
集,每组包含n
行,每行具有固定大小的L
; A
都可以映射到一组集合的任何n
高速缓存行中; A
映射到的集合:将地址空间划分为每个高速缓存行大小的插槽,然后计算A
的插槽的索引(I = A / L
),最后执行模运算以映射索引到目标集T
(T = I % s
); 我的第一个问题是:这些假设正确吗?
假设它们是,我尝试使用这些概念,以便实际上可以看到它们对程序有具体影响。我编写了一个简单的测试,分配了
B
字节的内存缓冲区,并从缓冲区的开头开始以给定步骤的固定增量重复访问该缓冲区的位置(这意味着如果B
为14且该步骤为3,我只重复访问0、3、6、9和12位置-如果B
是13、14或15,情况也是如此:int index = 0;
for (int i = 0; i < REPS; i++)
{
index += STEP;
if (index >= B) { index = 0; }
buffer[index] = ...; // Do something here!
}
基于以上假设,我的期望是:
STEP
设置为等于临界跨步(即,缓存行的大小乘以缓存中的集合数或L * s
),则性能应为,比明显差,例如,将STEP
设置为( L * s) + 1
,因为我们将仅访问映射到同一集合中的内存位置,从而迫使从该集合更频繁地逐出缓存行,并导致更高的缓存未命中率; STEP
等于临界跨度时,缓冲区的B
大小不会影响的性能,只要它不是太小即可(否则访问的位置太少,并且高速缓存未命中的情况会更少);否则,会影响的性能,因为缓冲区越大,我们越有可能访问映射到不同集合的位置(尤其是B
不是2的倍数时); STEP
)应该具有较小的影响。 因此,我使用RightMark Memory Analyzer来查找L1 CPU数据高速缓存的参数,调整程序中的大小,然后进行尝试。这是我编写主循环的方式(
STEP
是可以从命令行设置的标志): ...
for (int i = 0; i < REPS; i++)
{
...
if (onlyWriteToCache)
{
buffer[index] = (char)(index % 255);
}
else
{
buffer[index] = (char)(buffer[index] % 255);
}
}
简短的结果:
这个事实让我印象深刻,使我觉得有些事情我做得不太对。当
onlyWriteToCache
为256 MB并且B
等于关键跨度时,测试(在GCC 4.7.1上与-O3编译)显示:所以我的第二个问题是:为什么会有这种差异? 我希望读写时的性能损失会比只写时更高。
为了完整起见,下面是我为进行测试而编写的程序,其中的常数反射(reflect)了我的计算机的硬件参数:L1 8路关联数据缓存的大小为32 KB,每一个的大小
STEP
高速缓存行是64个字节,总共有64个字节(CPU具有大小相同且行大小相同的单独的L1 8路指令高速缓存)。#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
// Auxiliary functions
constexpr int pow(int base, int exp)
{
return ((exp == 0) ? 1 : base * pow(base, exp - 1));
}
int main(int argc, char* argv[])
{
//======================================================================
// Define behavior from command-line arguments
//======================================================================
bool useCriticalStep = false;
bool onlyWriteToCache = true;
size_t BUFFER_SIZE = pow(2, 28);
size_t REPS = pow(2, 27);
if (argc > 0)
{
for (int i = 1; i < argc; i++)
{
string option = argv[i];
if (option == "-c")
{
useCriticalStep = true;
}
else if (option == "-r")
{
onlyWriteToCache = false;
}
else if (option[1] == 's')
{
string encodedSizeInMB = option.substr(2);
size_t sizeInMB = atoi(encodedSizeInMB.c_str());
BUFFER_SIZE = sizeInMB * pow(2, 20);
}
else if (option[1] == 'f')
{
string encodedNumOfReps = option.substr(2);
size_t millionsOfReps = atoi(encodedNumOfReps.c_str());
REPS = millionsOfReps * pow(10, 6);
}
}
}
//======================================================================
// Machine parameters
//======================================================================
constexpr int CACHE_SIZE = pow(2, 15);
constexpr int CACHE_LINE_SIZE = 64;
constexpr int CACHE_LINES_PER_SET = 8;
constexpr int SET_SIZE = CACHE_LINE_SIZE * CACHE_LINES_PER_SET;
constexpr int NUM_OF_SETS = CACHE_SIZE / SET_SIZE;
//======================================================================
// Print out the machine parameters
//======================================================================
cout << "CACHE SIZE: " << CACHE_SIZE / 1024 << " KB" << endl;
cout << "CACHE LINE SIZE: " << CACHE_LINE_SIZE << " bytes" << endl;
cout << "CACHE LINES PER SET: " << CACHE_LINES_PER_SET << endl;
cout << "SET SIZE: " << SET_SIZE << " bytes" << endl;
cout << "NUMBER OF SETS: " << NUM_OF_SETS << endl;
fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;
//======================================================================
// Test parameters
//======================================================================
const int STEP = NUM_OF_SETS * CACHE_LINE_SIZE + (useCriticalStep ? 0 : 1);
//======================================================================
// Print out the machine parameters
//======================================================================
cout << "BUFFER SIZE: " << BUFFER_SIZE / pow(2, 20) << " MB" << endl;
cout << "STEP SIZE: " << STEP << " bytes" << endl;
cout << "NUMBER OF REPS: " << REPS << endl;
fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;
//======================================================================
// Start the test
//======================================================================
char* buffer = new char[BUFFER_SIZE];
clock_t t1 = clock();
int index = 0;
for (size_t i = 0; i < REPS; i++)
{
index += STEP;
if (index >= BUFFER_SIZE)
{
index = 0;
}
if (onlyWriteToCache)
{
buffer[index] = (char)(index % 255);
}
else
{
buffer[index] = (char)(buffer[index] % 255);
}
}
clock_t t2 = clock();
//======================================================================
// Print the execution time (in clock ticks) and cleanup resources
//======================================================================
float executionTime = (float)(t2 - t1) / CLOCKS_PER_SEC;
cout << "EXECUTION TIME: " << executionTime << "s" << endl;
delete[] buffer;
}
如果您能仔细阅读这个冗长的问题,请先谢谢您。
最佳答案
关于您的期望值3,您是正确的。如您所料。请检查"What every Programmer should know about memory"了解更多详细信息。这是解释存储器层次结构的一系列优秀文章。
那么为什么很难确认数字3:有两个主要原因。一种是内存分配,另一种是虚拟物理地址转换。
内存分配
不能严格保证分配的内存区域的实际物理地址是多少。当您要测试CPU缓存时,我总是建议使用posix_memalign
强制将分配分配到特定边界。否则,您可能会看到一些奇怪的行为。
地址翻译
我提到的文章很好地解释了地址转换的工作方式。为了验证您的假设,您必须尝试查明预期的行为。最简单的方法如下:
实验
以k
数组的形式分配一组int
大内存区域(大约512MB),并将它们全部对齐到4096b的页面边界。现在,遍历内存区域中的所有元素,并向您的实验中逐渐增加k
的更多区域。测量时间并通过读取的元素数量进行归一化。
代码如下所示:
#define N 10000000
for(size_t i=0; i < k; ++i) {
size_t sum=0;
clock_t t1= clock();
for(size_t j=0; j < N; ++j) {
for(size_t u=0; u<i; ++u) {
sum += data[u][j];
}
}
clock_t t2= clock();
}
那么会发生什么。所有大内存区域都对齐到4k,并且基于先前的假设,同一行的所有元素都将映射到同一缓存集。当循环中计划的内存区域数大于缓存的关联性时,所有访问将导致缓存未命中,并且每个元素的平均处理时间将增加。
更新
如何处理写操作取决于缓存行的使用方式和CPU。现代CPU使用MESI协议(protocol)来处理对高速缓存行的写入,以确保各方在内存上具有相同的 View (高速缓存一致性)。通常,在可以写入缓存行之前,必须先读取然后再写回缓存行。是否识别回写取决于访问数据的方式。如果您再次重新读取缓存行,您可能不会注意到差异。
但是,尽管程序员通常对如何将数据存储在CPU高速缓存中没有影响,但与写入相比有细微的差别。可以执行所谓的流式写入,它不会污染缓存,而是直接写入内存。这些写入也称为non-temporal写入。
关于c++ - CPU缓存关键跨度测试,根据访问类型给出意外结果,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14543965/