欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CPU Cache一探究竟

程序员文章站 2022-05-26 23:53:39
...

Author????:CofCai

personal page????:https://cxx7ud.coding-pages.com/

CSDN page????:https://blog.csdn.net/weixin_44360592?spm=1011.2124.3001.5113

Email✉️:aaa@qq.com

References

gallery-of-processor-cache-effects

7个示例科普CPU Cache

利用CPU Cache写出高性能代码

LRU Cache的实现

cache示意图

CPU Cache一探究竟

程序局部性原理

程序局部性原理是CPU Cache的理论基础。

时间局部性

时间局部性是指被CPU访问的数据,短期内还要被继续访问,比如循环、递归、方法的反复调用等。

空间局部性

空间局部性是指被CPU访问的数据的相邻数据,CPU短期内还要被继续访问,比如顺序执行的代码、连续创建的两个对象、数组等。

一致性原理

写入策略

直写模式(WriteThrough)

在数据更新时,将数据同时写入内存和Cache,该策略操作简单,但是因为每次都要写入内存,速度较慢。

回写模式(WriteBack)

在数据更新时,只将数据写入到Cache中,只有在数据被替换出Cache时,被修改的数据才会被写入到内存中,该策略因为不需要写入到内存中,所以速度较快。但数据仅写在了Cache中,Cache数据和内存数据不一致,此时如果有其它CPU访问数据,就会读到脏数据,出现bug,所以这里需要用到Cache的一致性协议来保证CPU读到的是最新的数据。

一致性

多个CPU对某块内存同时读写,就会引起冲突的问题,被称为Cache一致性问题。通过MESI协议解决,当一个CPU1修改了Cache中的某字节数据时,那么其它的所有CPU都会收到通知,它们的相应Cache就会被置为无效状态,当其他的CPU需要访问此字节的数据时,发现自己的Cache相关数据已失效,这时CPU1会立刻把数据写到内存中,其它的CPU就会立刻从内存中读取该数据。

MESI是通过四种状态的控制来解决Cache一致性问题的,四种状态分别是:

  • M(Modified,已修改)
  • E(Exclusive,独占)
  • S(Shared,共享)
  • I(Invalidated,已失效)

主存与Cache的映射关系

直接映射

每个主存块只能映射Cache的一个特定块。直接映射是最简单的地址映射方式,它的硬件简单,成本低,地址转换速度快,但是这种方式不太灵活,Cache的存储空间得不到充分利用,每个主存块在Cache中只有一个固定位置可存放,容易产生冲突,使Cache效率下降,因此只适合大容量Cache采用。

例如,如果一个程序需要重复引用主存中第0块与第16块,最好将主存第0块与第16块同时复制到Cache中,但由于它们都只能复制到Cache的第0块中去,即使Cache中别的存储空间空着也不能占用,因此这两个块会不断地交替装入Cache中,导致命中率降低。

全相连映射

主存中任何一块都可以映射到Cache中的任何一块位置上,但设计困难。

组相连映射

组相联映射实际上是直接映射和全相联映射的折中方案,主存和Cache都分组,主存中一个组内的块数与Cache中的分组数相同,组间采用直接映射,组内采用全相联映射。也就是说,将Cache分成u组,每组v块,主存块存放到哪个组是固定的,至于存到该组哪一块则是灵活的。例如,主存分为256组,每组8块,Cache分为8组,每组2块。

Cache的替换策略

LRU(Least Recently Use)策略,即最近最少使用。

代码分析

/**
 * author:		CofCai
 * datatime:	2020-11-10 15:37:50
 * file description:
 *	 该文件用于验证CPU Cache的作用,主要是看到了一篇微信公众号
 *	 的推送,然后读完这篇文章,发现我们的通信软件基础课上讲过类似
 *	 的问题,所以在此记录一下。
 *	 原文文章《利用CPU Cache写出高性能代码》:
 *	 		https://mp.weixin.qq.com/s/_hZtklfMINCqYTlBwmz7pA
 *	 		另附:http://igoro.com/archive/gallery-of-processor-cache-effects/
 *	 一致性原理:cache中和内存中的数据可能不一样(不同步),直写模式和回写模式
 *	 程序局部性原理(cache的理论基础):时间局部性、空间局部性
 *	 通过不停改变矩阵的大小,还能大致得出你电脑的CPU Cache的大小(搞懂矩阵在内存中的分布)。
 */

#include <stdio.h>
#include <time.h>

#define	row 	512
#define col 	512
#define count 	20		//调用traverse_by_row/col函数一次:遍历matrix矩阵count次

int matrix[row][col] = {0};		//测试矩阵

void traverse_by_row();
void traverse_by_col();
double test();				/* 调用traverse_by_row/col函数一次 */

int main(int argc, char const *argv[])
{
	printf("test matrix is %d rows, %d cols!\n", row, col);
	int t, times = 20;
	double res[20] = {0};

	FILE *pFile=fopen("./cache.csv","wt+");
        if(pFile==NULL)
        {
            printf("cache.csv opened failed");
            return -1;
        }

	for (t = 0; t < times; t++)
	{
		res[t] = test();
		fprintf(pFile,"%f,",res[t]);
	}

	printf("test over\n");

	return 0;
}

void traverse_by_row()
{
	int sum_row = 0;
	for (int r = 0; r < row; ++r)
	{
		for (int c = 0; c < col; ++c)
		{
			sum_row += matrix[r][c];
		}
	}
}

void traverse_by_col()
{
	int sum_col = 0;
	for (int c = 0; c < col; ++c)
	{
		for (int r = 0; r < row; ++r)
		{
			sum_col += matrix[r][c];
		}
	}
}

double test()
{
	clock_t start, finish;
	double tot_time1, tot_time2;

	/** 按行遍历,会快一些 */
	start = clock();
	for (int i = 0; i < count; ++i)
	{
		traverse_by_row();
	}
	finish = clock();
	tot_time1 = (double)(finish - start);
	printf("traverse by row %d times, totally spend %.2f\n", count, tot_time1);


	/** 按列遍历,会慢一些 */
	start = clock();
	for (int i = 0; i < count; ++i)
	{
		traverse_by_col();
	}
	finish = clock();
	tot_time2 = (double)(finish - start);
	printf("traverse by col %d times, totally spend %.2f\n", count, tot_time2);

	return (tot_time2 - tot_time1);
}