如何用织梦做网站,广州网站设计开发,设计外贸英文网站,贸易公司名称大全简单大气本文节选自书籍《大话处理器#xff1a;处理器基础知识读本》 PDF版本可以访问我的网盘通过网盘分享的文件#xff1a;大话处理器#xff1a;处理器基础知识读本.pdf 提取码: 1234
0 什么是 Cache
随处可见的Cache–技术来源于生活 使用电脑的人对 Cachc 并不会陌生#…本文节选自书籍《大话处理器处理器基础知识读本》 PDF版本可以访问我的网盘通过网盘分享的文件大话处理器处理器基础知识读本.pdf 提取码: 1234
0 什么是 Cache
随处可见的Cache–技术来源于生活 使用电脑的人对 Cachc 并不会陌生只要在 Windows 下搜索“Cache”就会找到一大堆命名包括“Cache”的文件和文件夹系统目录下有浏览器目录下有QQ目录下有PPStream目录下有迅雷看看目录下有…… 维基百科对 Cache的定义是:它是一个部件透明地存储了一些数据当下次需要这些数据时就能更快的访问到。以迅雷看看为例在网络上看完一个节目后节目就存储在本地硬盘上当下次再看这个节目时就真接访问硬盘上缓存的内容而不是从网络上去取,这样获取节目的速度就加快了。“透明”的意思是,用户不需要关心这段数据存在哪。Cache 的思想并不是计算机专有的它来源于生活。我们在大学读书时书都放在宿舍里今天要上《高数》课就把《高数》的课本放进书包明天要上《C语言》就把书包中的《高数》课本取出来把《C语言》课本放进书包这个包就是一个 Cache(缓存)。垃圾篓、旅行包等都可以叫Cache。
1 处理器的 Cache 结构
1.1 Cache 的层次–层次化管理
我们通常会有这样的生活习惯将最常用的东西放在桌上这样可以最方便地拿到将次常用的东西放在抽屉里也能较快地拿到将不常用的东西放在箱子里去箱子里拿东西需要耗一点时间。 这种思想也被用在了Cache中现在的处理器都采用多级的Cache 组织形式来达到性能和功耗的最优。
单核处理器大都采用如下的 Cache 结构: 单核处理器通常包含两级Cache:L1Cache和L2 CacheL表示 Level(级)。在 L1中程序(Program)和数据(Data)使用各自的缓存(LIP和LID)而在L2中程序和数据共用一套缓存。通常 L1空间为几十KL2空间为几百K。 当内核需要访问程序或数据时会先从L1中去取如果L1中没有则L1从L2中将数据导入如果 L2中也没有则L2从内存中将数据导入。 L1 通常和内核同频率以保证速度L2通常会降频使用工作频率比内核低这样能降低功耗。多核处理器大都采用如下的 Cache 结构 在多核处理器中一般每个内核独享自己的L1和L2所有的内核会共用一个大容量的 L3。
1.2 Cache的工作方式——命中与未命中
整个 Cache 空间被分成了N个line每个line(Cache line)通常是32 byte、64 byte等Cache line 是 Cache 和内存交换数据的最小单位每个Cache line 最少会包含如下3部分
block中存储的是内存在Cache中缓存的数据tag中存储的是该Cacheline 对应的内存块的地址。valid 表示该Cache line中的数据是否有效。
下面描述了一个基本的Cache 工作方式假设处理器只有一级Cache当内核访问一个数据时内核首先会在Cache中找一开始自然找不到于是就发生了Cachemiss(未命中)这时内存中的数据被导入到一个Cache line的block中将地址写到相应的 tag 位置处并将valid 标志置1。当下一次内核继续访问这个数据时处理器根据地址在Cache中找到对应的 Cache line发现 valid 标志为1并且tag 标志也匹配就知道找到了数据,直接从 Cache 中取这个数据这个过程叫 Cache hit。
当Cache 命中时内核直接从Cache中取数据时间通常为几个cycle当 Cache 未命中时数据需要从内存中导入时间通常是几十、几百个cycle极大地拖垮了处理器的性能。
1.3 Cache的映射方式–多对一的策略
由于内存的空间要远远大于Cache的空间因此内存中的数据搬到Cache 中时会存在一个多对一的映射。
Full-associative Cache(全关联 Cache) 内存以字节为存储单位不过由于内存和Cache交换数据的最小单位是一个Cacheline因此姑且将内存也看成按照 line的方式存储。 在Full-associativeCache中,内存中的每个1ine能够被映射到Cache中的任意一个Cacheline如下图:
在 32位处理器中地址线为32bit如果每个1ine为64byte(6 bit表示)那么每个Cache line 的tag需要 26bit(32-626)。 全关联 Cache 有个缺点那就是当判断一个数据是不是在 Cache 中时它需要将地址和所有 Cache line 的tag 进行匹配成本太高。在实际的处理器中这种方式很少见。 Direct-mapped Cache(直接映射 Cache) 与Full-associative Cache 不同的是Direct-mapped Cache 将内存按照 Cache 的大小分成了N个Page每个Page 和 Cache 大小相同。Page 中的line0只能映射到 Cache 中的 line0依次类推。 内存的 Cache Page 示例如下 假设Cache有4个Cache line那么 Direct-mapped 的映射方式如下Direct-mapped 映射方式最直接的一个好处是:随便给一个地址通过地址就能知道它位于哪个 Cache line 中这是因为每一个内存地址都只会映射到唯一一个 Cache line 中。为了 Cache line知道自己存储的是哪个地址处的数据,tag需要记录Page的索引。以C64 DSP的L1P Cache 为例地址总线为32bitL1P大小为16Kbyte(14bit 表示 2 的14次方等于 16384 就是16Kyte大小)每个 Cache line32 byte(5bit 表示)于是tag需要18bit(32-14)。 每个 32bit 的地址被分成了3部分:tag用于标识该Cacheline属于哪个Pageline指示该数据应该存储在哪一行Cache中,Ofset表示数据应该存储在Cache line中的哪个位置。下图为C64 DSPL1P Cache中32 bit地址的结构。 使用 Direct-mapped CacheCache 控制器要判断一-个数据是否在 Cache 中时首先根据这个数据的地址提取出TAG(头18bit)和LINE(中间 9bit)根据 LINE 找到对应的Cache line如果 Cache line 中的 tag和 TAG 一致并且 valid 标志为1那么 Cache 就命中反之则未命中。 Set-associative Cache(组关联 Cache) Direct-mapped Cache要比Full-associative Cache 简单也是处理器上比较常用的方式不过 Direct-mapped Cache 在很多情况下会有很大的缺陷。 以下面这段程序为例子
for (i0;i10;i )
{c a[i] b[i];假设 Cachc 只有4个Cache line,数组a存储在内存的line0,数组b存储在内存的 line4则 Cache 访问过程如下 (1)CPU 访问 a[0]Cache miss,数组a从内存中被搬移到Cache line0中。(2)CPU访问 b[0]Cache miss,数组b从内存中被搬移到 Cache line0中。 (3)CPU访问 af1]Cache miss,数组a从内存中被搬移到 Cache line0中。 (4)CPU 访问 b1]Cache miss,数组 b从内存中被搬移到 Cache linc0中。 (5)… 由于a和b都映射到Cache line0每次访问数据都发生Cache miss严重影响效率。 在上面的这个例子中Cache line1、Cache line 2、Cache line3 都浪费了而 Cache line0却冲突严重。其实 Full-associative Cache 可以解决这个问题因为内存中的每个 1ine 都可以映射到任意 Cache line 中从这个角度来看Full-associative Cache 效率最高但是由于查找复杂所以很少使用。而商用的处理器都使用 Set-associative Cache 来解决这个问题。
Set-associative Cache将Cache 分成了多个way(份)如下图所示: Cache way1和 Cache way0是完全相同的结构访问a时,a被 Cache 到 way0 的 line0中访问b时发现way0的line0已经被使用了就将b缓存到way1的 line0中这样就解决了上面的冲突问题。数组a和b的访问只在第一次访问 a[0]和 b[0]时需要从内存导入其他的时候都能直接从 Cache 中取数。
Direct-mapped Cache等同于1-way Set associative Cache。 在相同 Cache 容量下Cache way越多则每个 Cache way 的容量就越少。Cache way的增多会减少 Cache miss但是 Cache way 容量的减小又会增加 Cache miss。Cache way越多Cache 的硬件结构也越复杂功耗也越高。不同的处理器都会根据自己的应用来设定最佳的 Cache way 数目、每个 Cache way 的容量。
在TI的c64 DSP 内核中L1P使用1wayCacheLID使用2way CacheL2 不区分程序和数据使用4wayCache。x86CPU使用更多的Cache way。
置换策略 Cache 的容量毕竟有限Cachc way也有用完的时候当Cache way用完时再来数据就要替换其中的一个了那么替换哪个呢? 常用的替换策略有: (1)随机(Random)随便找个替换。 (2)先进先出(FirstInFirstOutFIFO)最早被使用的那个 way 被替换。(3)最近最少被使用(LeastRecentlyUsed,LRU)替换最近最少被使用的那个 way。在这几种策略中LRU性能最好LRU基于Cache的时间相关性刚刚被访问的数据很有可能继续被访问很久都没有被访问的数据则很可能就不会被访问了。
1.4 Cache的写方式
前面只提到了Cache 的读方式当CPU修改了Cache 中的数据内存中的数据需不需要跟着改变呢? Cache 提供了两种写策略。 Write through(写通) Write through 策略是指每次 CPU修改了Cache 中的内容,Cache 立即更新内存的内容 在上面的这个例子中内核读入了变量x它的值为3不久后内核将x改成5内核修改的是 Cache 中的数据当 Cache 采用 Write through 略时Cache 控制器将x的值更新到内存中。 Write back(写回) Write back 策略是指内核修改 Cache 的内容后Cache 并不会立即更新内存中的内容,而是等到这个Cache line因为某种原因需要从Cache中移除时,Cache才更新内存中的数据例如Cache的1ine0已经存储了内存line0的数据内核想修改地址在内存line0中的变量它实际上修改的是Cache line0中的数据当内核访问内存1ine4时这块数据也需要使用 Cache line0这时 Cache 控制器会先将Cacheline0的内容更新到内存的line 0然后再将 Cache line0作为内存1ine4的缓存。内存1ine0在很长时间内存储的都不是最新的数据不过这并不影响程序的正确性。
在上面的这个例子中内核修改了x但是x并没有被更新到内存中Write through(写通)由于有大量的访问内存的操作效率较低大多数处理器都使用 Write back(写回)策略。 Cache 怎么知道这行的数据有没有被修改呢?这就需要新增一个标志—dirty 标志。dirty 标志为 1表示 Cache 的内容被修改和内存的内容不一致当该Cacbe line 被移除时数据需要被更新到内存dinty标志位为0(称为clean)表示Cache 的内容和内存的内容一致。 下图为增加了 dinty 标志的 Cache 结构: 程序 Cache 不会被修改不需要 dirty 标志数据 Cache 需要 dirty 标志。
2 Cache 一致性
2.1一致性问题的产生——信息不对称导致的问题
现实生活中常常会出现因为沟通不畅而导致的扯皮一方改变了某些东西又没有及时通知到另一方导致两方掌握的信息不一致这就是一致性问题。多核处理器也有这样的问题在下面这个简单的多核处理器示例中内存中有一个数据x它的值为3它被缓存到Core0和Core1中不过Core0将x改为5如果 Core 1不知道x已经被修改了还在使用旧的值就会导致程序出错这就是Cachc 的不一致。
2.2 Cache 一致性的底层操作
为了保证 Cache的一致性处理器提供了两个保证Cache致性的底层操作:Writeinvalidate 和 Write update 。 Write invalidate(置无效):当一个内核修改了一份数据其他内核上如果有这份数据的复制就置成无效(invalid)。 在下面的这个例子中3个Core都使用了内存中的变量xCore0将它修改为5其他Core 就将自己对应的Cache line置成无效(invalid)。 Write update(写更新):当一个内核修改了一份数据其他地方如果有这份数据的复制就都更新到最新值。Write update 示例如下:
Write invalidate 和 Write update 比较:Write invalidate 是–种很简单的方式不需要更新数据如果Core1和Core2以后不再使用变量x这时候采用 Write invalidate 就非常有效。不过由于一个 valid 标志对应一个 Cache line,将 valid 标志置成invalid 后这个 Cacheline 中其他的本来有效的数据也不能被使用了。Write update 策略会产生大量的数据更新操作不过只用更新修改的数据如果Core1和Core2会使用变量x那么 Write update 就比较有效。由于 Write invalidate 简单大多数处理器都使用 Write invalidate 策略。
2.3 Cache一致性协议
Write invalidate 提供了实现 Cache 一致性的简单思想处理器上会有一套完整的协议来保证 Cache 一致性。比较经典的Cache一致性协议当属MESI协议奔腾处理器有使用它很多其他的处理器都是使用它的变种。 前面介绍的 Cache 中每个 Cache line 有两个标志:dinty和 valid 标志它们很好的描述了Cache和 Memory(内存)之间的数据关系(数据是否有效、数据是否被修改)而在多核处理器中多个核会共享一些数据MESI协议就包含了描述共享的状态。 在MESI协议中每个Cacheline有4个状态可用两个bit 表示它们分别是:
状态描述M(Modified)这行数据有效数据被修改了和内存中的数据不一致数据只存在于本Cache中E(Exclusive)这行数据有效数据和内存中的数据一致数据只存在于本Cache中S(Shared)这行数据有效数据和内存中的数据一致数据存在于很多Cache中I(Invalid)这行数据无效
M(Modified)和E(Excusive)状态的Cacheline数据是独有的不同点在于M状态的数据是 dirty的(和内存的不一致)E状态的数据是 clean 的(和内存的一致)。 S(Shared)状态的 Cache line数据和其他的 Cache 共享。只有 clean 的数据才能被多个 Cache 共享。 I(Invalid)表示这个Cache line 无效。 E状态示例如下: 只有Core0访问变量x它的Cache line状态为E(Exclusive)。
S 状态示例如下: 3个Core都访问变量x它们对应的Cacheline为S(Shared)状态。 M 状态和1状态示例如下: Core0修改了x的值之后这个Cache line变成了M(Modified)状态其他 Core 对应的Cache line 变成了I(Invalid))状态。在 MESI协议中每个Cache 的 Cache 控制器不仅知道自己的读写操作而且也监听(snoop)其他Cache的读写操作。每个Cache line所处的状态根据本核和其他核的读写操作在4个状态间进行迁移。MESI协议状态迁移图如下 在上图中,LocalRead表示本内核读本Cache中的值,Local Write表示本内核写本Cache中的值Remote Read 表示其他内核读其他Cache 中的值Remote Write 表示其他内核写其他 Cache 中的值箭头表示本 Cache line 状态的迁移环形箭头表示状态不变当内核需要访问的数据不在本Cache中,而其他 Cache有这份数据的备份时,本 Cache既可以从内存中导入数据也可以从其他Cache中导入数据不同的处理器会有不同的选择。MESI协议为了使自己更加通用没有定义这些细节只定义了状态之间的迁移。
3 片内可寻址存储器——软件管理的Cache
在 x86 处理器中处理器内部的存储器全部作为Cache 使用不纳入存储空间的编址Cache 对程序员是透明的Cache完全由处理器硬件来管理程序员不需要关心Cache编程也简单。 而在 DSP等性能要求很高的嵌入式处理器中,处理器内部的存储器一部分作为Cache;另一部分作为可寻址存储器程序员可直接访问这部分空间。
为什么在处理器内部需要可寻址存储器呢?因为Cache miss 是不可避免的当发生 Cache miss 时处理器要花大量的时间等待数据而可寻址存储器可以由程序员自己管理也就可以有效地控制数据 miss。
有3个原因会导致Cachemiss: Compulsory(必须的)miss第一次访问程序或数据时这些数据没有在Cache中于是就导致了 Cache miss。这种 Cache miss是不可避免的因此叫做Compulsory miss。 Capacity(容量)missCache容量毕竞有限当Cache已满新数据又要进来就必须重新搬移这就叫做 Capacity miss。 Conflict(冲突)miss,有时候 Cache虽然还有空闲空间,但是这个地址对应的 Cache line已经被使用了也会导致Cachemiss这就叫做Conflict miss。
Cache 要等到CPU 访问数据时才从内存中将数据取进来而此时CPU能等待。如果处理器内部有了可寻址存储器就可以通过软件控制 DMA(DirectMemory Access)将以后需要的数据提前搬到处理器内部,这就省去了不少CPU的等待时间。DMA 是处理器中专业负责数据搬移的模块。 在上面的这个例子中程序知道 CPU什么时候要访问数组x,于是通过控制 DMA 提前搬移数据,而 Cache 不知道它没法提前搬。因此使用 DMA的方式程序总的执行时间要比使用Cache的方式少。DMA 的任务就是快速的搬移数据而数据的组织形式千差万别。例如在多媒体领域语音数据通常采用一维数组的形式存储图像数据采用二维数组来存储彩色图像包含多个分量(如RGB、YCbCr等)各个分量又独立存储。DSP的DMA 也相应提供了 1D、2D、3D 的数据搬移方式如下图所示:
1D方式搬运一块连续地址的空间2D方式可看作由多个规则的1D方式组合而成完成一个 1D操作后地址加上一个固定偏移继续下一个 1D操作3D 搬移也就是多个规则的 2D 搬移。 使用 DMA 程序的效率较高不过程序员不仅要关注代码和数据的逻辑关系还要关心代码和数据的存储位置这对程序员来说是一个不小的挑战。通用处理器为了简化编程难度通常只提供 Cache 这一种方式DSP 对程序性能要求很高通常提供了Cache 和DMA 的组合方式。 现在的处理器认识到传统Cache的缺陷,于是也产生了很多 Cache预取机制,如当CPU在访问本行数据时自动取下一行的Cache 数据。处理器也提供了指令让程序员更灵活地控制 Cache以提高程序的效率。
