Cache地址映射

原创内容,转载请注明:  [http://www.ssdfans.com]  谢谢!

理解Cache地址映射之前补充一些基础知识,Cache的地址映射和MMU(内存管理单元)和TLB Cache(转译查找缓存)中的映射是有区别的。Cache、TLB Cache、MMU在CPU中结构如图1所示,图1展现的是Cortex A9 Processor内部结构,采用的指令和数据总线分开的哈佛结构。CPU访问内部存储和外部存储,以及各种外设空间在硬件层面上看都是物理地址(硬件总线),然后为了满足多进程脆弱的软件系统提出了虚拟地址,虚拟地址是针对应用程序所提出的概念,MMU负责虚拟地址到物理地址的映射工作,从虚拟地址到物理地址的转换过程可知:页表存储在内存中,使用一级页表进行地址转换时,每次读/写数据需要访问两次内存,第一次访问一级页表获得物理地址,第二次才是真正的读/写数据;使用两级页表时,每次读/写数据需要访问三次内存,访问两次页表(一级页表和二级页表)获得物理地址,第三次才是真正的读/写数据,由于这种机制速率很慢,才提出TLB Cache用于存储近期用到的页表条目(段/大页/小页/极小页描述符。TLB Cache是一个内存管理单元用于改进虚拟地址到物理地址转换速度的高速缓存,位于MMU中,本文章不深入分析MMU和TLB。Cache映射是硬件层面物理块与物理块之间建立的联系。

图 1

Cache的容量一般都很小,即使是最大的三级Cache(L3)也只有20MB~30MB。而当今内存的容量都是以GB作为单位,CPU对存储器的访问,通常是一次读写一个字单元。当CPU访Cache不命中时,需将存储在主存中的字单元连同其后若干个字一同调入Cache中,之所以这样做(write-back策略才会有这种机制),是为了使其后的访存能在Cache中命中。因此,主存和Cache之间一次交换的数据单位应该是一个数据块(以前文章中提到的cache line,一般大小为64 Byte)。数据块的大小是固定的,由若干个字组成,且主存和Cache的数据块大小是相同的。

从Cache-主存模型来看,一方面既要使CPU的访存速度接近于访Cache的速度,另一方面为用户程序提供的运行空间应保持为主存容量大小的存储空间。在采Cache-主存层次的系统中,Cache对用户程序而言是透明的,也就是说,用户程序可以不需要知道Cache的存在。因此,CPU每次访存时,依然和未使用Cache的情况一样,给出的是一个主存地址。但在Cache-主存层次中,CPU首先访问的是Cache,并不是主存。为此,需要一种机制将CPU的访主存地址转换成访Cache地址。而主存地址与Cache地址之间的转换是与主存块与Cache块之间的映射关系紧密联系的。如何把内存中的内容存放到Cache中去,这就需要一个映射算法和一个分块机制。

分块机制就是说,Cache和内存以块为单位进行数据交换,块的大小通常以在内存的一个存储周期中能够访问到的数据长度为限。当今主流块的大小都是64字节,因此一个Cache line就是指 64 个字节大小的数据块。Cache容量模型如图 2所示,图中展现了data cache: 32-KB, 8-way set associative(每个组里有8行),64-byte line size的cache容量模型。

图 2

映射算法是指把内存地址空间映射到Cache地址空间。具体来说,就是把存放在内存中的内容按照某种规则装入到 Cache 中,并建立内存地址与 Cache 地址之间的对应关系。当处理器需要访问这个数据块内容时,则需要把内存地址转换成 Cache 地址,从而在Cache 中找到该数据块,最终返回给处理器。Cache 和内存之间的映射关系可以分为三类:全关联型Cache(full associative cache),直接关联型 Cache(direct mapped cache),组关联型 Cache(N-ways associative cache)。

全相联映射是指主存中任一块都可以映射到Cache中任一块的方式,也就是说,当主存中的一块需调入Cache时,可根据当时Cache的块占用或分配情况,选择一个块给主存块存储,所选的Cache块可以是Cache中的任意一块。例如,设Cache共有m块,主存共有n块,当主存的某一块j需调进Cache中时,它可以存入Cache的块0、块1、…、块i、… 或块m的任意一块上,如图3所示,区别在于cache和主存块的对应关系不一样。

图3

在Cache中,需要建立一个目录表,目录表的每个表项都有三部分组成:内存地址、Cache块号和一个有效位。当处理器需要访问某个内存地址时,首先通过该目录表查询是否该内容缓存在Cache中,具体过程如图4所示。当一个主存块调入Cache中时,会同时在一个存储主存块号和Cache块号映射表的相联存储器中进行登记。CPU访存时,主存的块地址A在Cache的相联存储器目录表中进行查询,如果找到等值的内存块地址,检查有效位是否有效,只有有效的情况下,才能通过Cache块号在Cache中找到缓存的内存,并且加上块内地址 B,找到相应数据,这时则称为Cache命中,处理器拿到数据返回;否则称为不命中,处理器则需要在内存中读取相应的数据。使用全关联型 Cache,块的冲突最小,Cache的利用率也高,但是需要一个访问速度很快的相联存储器。随着Cache容量的增加,其电路设计变得十分复杂,因此只有容量很小的Cache才会设计成全关联型。

图 4

直接关联型Cache是指主存中的一块内存只能映射到Cache的一个特定的块中,Cache的目录表只有两部分组成:区号和有效位。其查找过程如图5所示。首先,内存地址被分成三部分:区号A、块号B和块内地址C,在这里区号A和区号B其实是全关联型中主存地址A。根据区号A在目录表中找到完全相等的区号,并且在有效位有效的情况下,说明该数据在Cache中,然后通过内存地址的块号B获得在Cache中的块地址,加上块内地址C,最终找到数据。如果在目录表中找不到相等的区号,或者有效位无效的情况下,则说明该内容不在Cache中,需要到内存中读取。直接相联映射方式的优点 是比较电路最简单,但缺点是Cache块冲突率较高,从而降低了Cache的利用率。

图 5

以上两种方式各有优缺点,而且非常有趣的是,它