佛山建网站定制费用,深圳建设集团有限公司工资,手机搭建wap,南宁企业做网站如何快速实现cache line eviction 一#xff0c;什么是cache hit、miss、linefill、evict #xff1f;1.1 如果要程序员分别制造出cache hit、miss、linefill、evict这四种场景#xff0c;该怎么做#xff1f; 二#xff0c;实现cache line eviction的方法1.1 直接填充法3… 如何快速实现cache line eviction 一什么是cache hit、miss、linefill、evict 1.1 如果要程序员分别制造出cache hit、miss、linefill、evict这四种场景该怎么做 二实现cache line eviction的方法1.1 直接填充法3.2 针对组相联cache的固定set number 填充法 三使用PMU events验证 cache line eviction四思考全相联和直接映射型cache 如何实现 cache eviction 一什么是cache hit、miss、linefill、evict
cache controler 是一个管理cache 内存的硬件结构实际上它的绝大部分行为对程序来说都是不可见的。它会自动地将代码指令或者数据从主存中搬运到cache中响应CPU读写内存的请求并将它们转化成对cache以及外部内存的操作 cache controler收到CPU对某个地址进行读写的请求时它会先检查这个地址是否存在cache中这个动作称为cache look-up缓存查找。具体的的操作为将该地址的部分bit截取下来与cache 中cache line的tagcache line的tag包含了该cache line的地址信息值进行比较。如果匹配成功也称为cache hit命中说明CPU读写的地址已存在cache中并且这个cache line被标记为 valid有效则CPU的读写操作将会使用cache 里面的内容而不会去主存中读写。 反之如果遍历了整个cache都没有找到能与该地址匹配的tag或者该tag是无效的则缓存未命中cache miss。这个cache miss的结果以及对该地址的读写请求会被传递给下一级内存可能是L2、L3 cache或者主存并且会发生 cache linefill缓存行填充。cache linefill是指将下一级内存中关于该被请求地址的数据拷贝到cache中由于cache 操作的最小单位是cache line所以一次填充一个cache line。在cache linefill的同时被请求的数据也会发送给CPU满足其读写请求。这个cache miss 和linefill的行为对程序员来说是不可见的并且CPU并不用等linefill完成才能使用该数据。假设cache line大小为64 bytes所以一个linefill操作需要将64 bytes数据拷贝到cache当中而CPU的读写请求可能是该cache line中的其中一个word4 bytescache controler会优先访问该特定的 word将该word送到CPU的流水线pipeline中与此同时cache硬件以及外部总线接口会将剩余的60 bytes数据读取并填充到指定cache line中。 cache 始终是有空间限制的如果一直miss一直linefill那么将cache填满了后会发生什么eviction。为了让新的cache line数据填进cache中cache 利用替换策略replacement policy在cache中选中一个cache line并将其驱逐evict出去为新的cache line数据腾出空间。被驱逐的cache line也称为victim而被驱逐的过程也就是写回write back到下一级内存可能是L2、L3 cache或者主存的过程。 问题随之而来
1.1 如果要程序员分别制造出cache hit、miss、linefill、evict这四种场景该怎么做
首先要知道cache miss之后必然会出现cache linefill如果cache 满了cache linefill还会造成cache eviction。所以
cache miss linefill 读写一个之前未曾使用过的地址或者当cache为空的时候进行读写即可造成misslinefill。cache hit 重复读写一个内存地址第一遍读写会misslinefill但是第二遍开始就会一直hit。cache evict前面提到过当cache 满了的时候会将某个cache line驱逐出去给新的cache line腾出空间。所以最简单的办法就是连续读写一段与cache容量大小的内存空间将cache 填满。然后再读写一个新的地址时将会发生eviction。除了这种方法下文还会介绍针对组相联结构的cache快速制造eviction的简单方法。
二实现cache line eviction的方法
1.1 直接填充法
在上文中我们知道要想发生 cache line的eviction最简单粗暴的方式就是将整个cache 填满然后再读写一个新地址的时候cache controler就会用replacement policy替换策略选择其中一个cache line将其驱逐也就是write back到下一级内存中。但是将一个cahce 填满也是非常耗时的我们可以简单计算一下 假设当前cache 的大小为32KB其cache line size为64 bytesLDR/STR指令一次读写32 bit( 4 bytes)的数据。我们知道一次读写miss会填充一个cache line64 bytes即使是每次跨一个cache line大小的空间进行读写实际的读写次数也需要512次如下面代码
addr 0x10000000
for(i0;i512;i)
{val*(addr);addr addr64;
}
val*(addr64);//eviction3.2 针对组相联cache的固定set number 填充法
ARM一般使用组相联结构的cache针对组相联cache不必将整个cache填满才会发生eviction我们可以利用cache的set 和way快速地制造eviction具体的原理如下参考下文。 假设有一个 4 way 256 set的cachecache line大小为64 bytes很容易得出该cache的大小为64 Bytes * 256 * 4 64 KB其结构如下 可以发现传入cache的一个内存地址会被cache 分成三部分TagIndexoffset。这三部分决定了该地址上的数据将会被加载到cache中的哪个cache line。
Tag一个地址的高位bits可以用来当作Tag可以告诉cache该cache line的数据来自主存的哪里。Index: 地址的中间部分可以用来表示 Set的下标也就是set的行号不同way中index相同的cache line的集合称为set。Offsetword index byte index一个cache line有64 bytes而一个地址上的数据可能只有4 bytes我们可以用该offset找到该数据位于cache line的哪个word或者byte。
当CPU 读写一个地址后假设该地址为0xB0001234包含该地址数据的一个cache line大小的数据将会被填充到cache中。 我们先来分析该cache line将会被放在cache 的哪个位置。 0xB0001234会被分成三部分 蓝色部分为Tag信息红色部分为Set的index绿色部分为offset:
Tag 0b1011 0000 0000 0000 00Set index 0b 100100 0x24 36offset: word index 0b 1101 13, byte index 0
解析出了这些信息我们就可以给这个cache line找个家了
位于哪个way由于是4 way组相联的cache所以该cache line可以位于 way0、way1、way2、way3中的任意一个way。位于哪个Setset index为36所以该cache line位于某个way的第36行。位于cache line的第13个word的第 0 byte 需要注意的是该地址不是64 bytes对齐的地址所以加载到cache line的64 bytes数据应该是从 0xB0001200开始到 0xB0001240的 64 bytes数据。
我们虽然不知道该cache line位于哪个way但是way 的个数只有四个如果连续写入四个 set index都为36的cache line那么写入第五个的时候会发生什么eviction。
写入第一个set index为36 的cache linecache line 可以保存在way0way1way2way3任意一个way姑且假设放入way2。写入第二个set index为36 的cache linecache line 可以保存在way0way1way3任意一个way姑且假设放入way3。以此类推当写入第四个set index为36 的cache line后way0way1way2way3都保存了一个set index为36且来自不同地址的cache line。如果再写入第五个set index为36 的cache linecache controler将会根据替换策略在现有的四个set index为36的cache line中选择一个将其驱逐出去为第五个set index为36 的cache line腾出空间也就发生了cache eviction。
所以接下来我们只要找到四个set index为36但是Tag不同的地址即可只要保证地址的[13:6]0b0100 100即可保证其set index为36 比如
0xA00012000xC00012000xD00012000xE0001200 所以CPU只需先读写这四个地址然后再读写0xB0001234的时候将会发生cache eviction总共只需读写五次即可实现。
三使用PMU events验证 cache line eviction
光是这样推测是远远不够的我们可以利用PMUPerformance Monitors Unit的事件监控功能把cache 相关的事件用PMU来监控验证是否真的发生了预期的cache 操作。具体的event 可以是 一个eviciton 操作实际上是将旧的cache line写回到下一级缓存然后把新的cache line 加载进来所以可以利用PMU以下的event来监控
L1D_CACHE_WBL2D_CACHE_REFILLL2D_CACHEL1D_CACHEL1D_CACHE_REFILL
四思考全相联和直接映射型cache 如何实现 cache eviction
