计算机系统-从应用程序到底层实现 课件 第21讲 Cache

《计算机系统》Cache篇《计算机系统》课程教学组2025年春季学期本讲内容替换算法查找算法写策略映像规则Cache2134访问Cache当把一个块调入高一层（近CPU）存储器时，可以放在什么位置上?

（映像规则）当所要访问的块在高速缓存中，如何找到该块? （查找算法）当不命中，且高一层存储器已满时，应替换哪一块？

（替换算法）当进行写访问时，应进行哪些操作? （写策略）映像规则1

全相联映象所谓全相联：主存中的任一块可以被放置到Cache中的任意一个位置对比：教室位置──随便坐特点：空间利用率最高，冲突概率最低，实现最复杂。映像规则2

直接映象所谓直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置（循环分配）对比：教室位置──只有一个位置可以坐特点：空间利用率最低，冲突概率最高，实现最简单映像规则3

组相连映象所谓组相连映象：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置一种直接映象和全相联的折中再看一个例子intsum_array_rows(doublea[16][16]){inti,j;doublesum=0;for(i=0;i<16;i++)for(j=0;j<16;j++)sum+=a[i][j];returnsum;}intsum_array_cols(doublea[16][16]){inti,j;doublesum=0;for(j=0;j<16;j++)for(i=0;i<16;i++)sum+=a[i][j];returnsum;}32B=4doubles设若:cold(empty)Cache,a[0][0]goeshereIgnorethevariablessum,i,j再看一个例子intsum_array_rows(doublea[16][16]){inti,j;doublesum=0;for(i=0;i<16;i++)for(j=0;j<16;j++)sum+=a[i][j];returnsum;}32B=4doubles设若:cold(empty)Cache,a[0][0]goeshereIgnorethevariablessum,i,ja[0][0]~[0][3]a[0][4]~[0][7]a[0][8]~[0][11]a[0][12]~[0][15]a[1][0]~[1][3]a[1][4]~[1][7]a[1][8]~[1][11]a[1][12]~[1][15]再看一个例子intsum_array_cols(doublea[16][16]){inti,j;doublesum=0;for(j=0;j<16;j++)for(i=0;i<16;i++)sum+=a[i][j];returnsum;}32B=4doubles设若:cold(empty)Cache,a[0][0]goeshereIgnorethevariablessum,i,ja[0][0]~[0][3]a[1][0]~[1][3]a[2][0]~[2][3]a[3][0]~[3][3]a[4][0]~[4][3]a[5][0]~[5][3]a[6][0]~[6][3]a[7][0]~[7][3]再看一个例子intsum_array_cols(doublea[16][16]){inti,j;doublesum=0;for(j=0;j<16;j++)for(i=0;i<16;i++)sum+=a[i][j];returnsum;}32B=4doublesa[0][0]~[0][3]a[1][0]~[1][3]a[2][0]~[2][3]a[3][0]~[3][3]a[4][0]~[4][3]a[5][0]~[5][3]a[6][0]~[6][3]a[7][0]~[7][3]……intsum_array_rows(doublea[16][16]){inti,j;doublesum=0;for(i=0;i<16;i++)for(j=0;j<16;j++)sum+=a[i][j];returnsum;}32B=4doublesa[0][0]~[0][3]a[0][4]~[0][7]a[0][8]~[0][11]a[0][12]~[0][15]a[1][0]~[1][3]a[1][4]~[1][7]a[1][8]~[1][11]a[1][12]~[1][15]……命中率？存储层次产生的四个问题当把一个块调入高一层存储器时，可以放在什么位置上?

（映像规则）当所要访问的块在高速缓存中，如何找到该块?

（查找算法）当不命中，且高一层存储器已满时，应替换哪一块？

（替换算法）当进行写访问时，应进行哪些操作? （写策略）高速缓存的通用组织每组有E=2e

行S=2s

个组组set行line012B-1tagv每块有B=2b

字节(数据)若存储器地址有m位；Cachesize:C=SxExBdatabytes有效位validbit(S,E,B,m)读高速缓存E=2elinespersetS=2ssets012B-1tagv有效位validbitB=2bbytespercacheblock(thedata)tbitssbitsbbitsAddressofword:标记tag组索引setindex块内偏移Blockoffsetdatabeginsatthisoffset定位到组检查组内任意行是否与标记匹配

如果匹配且行有效，即命中

以偏移量定位数据

示例直接映像Cache

E=1直接映射:每组只有一行设若:高速缓存块大小为8字节S=2ssetstbits0…01100Addressofint:0127tagv36540127tagv36540127tagv36540127tagv3654findset示例直接映像Cachetbits0…01100Addressofint:0127tagv3654match:assumeyes=hitvalid?+blockoffsettagtbits0…01100Addressofint:0127tagv3654match:assumeyes=hitvalid?+int(4Bytes)ishereblockoffset若不匹配:旧行被替换——替换策略？直接映像Cache模拟M=16Byte地址空间S=4sets,E=1Blocks/setB=2bytes/block,访问地址十进制二进制读是否命中:

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]xt=1s=2b=1xxxmiss0??vTagBlock000Set0Set1Set2Set3存放设定：一个是一个字节01234567第1块第2块第3块第4块直接映像Cache模拟M=16byteaddressesS=4sets,E=1Blocks/setB=2bytes/block,Addresstrace(reads,onebyteperread):

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]xt=1s=2b=1xxxmisshitmiss0??vTagBlock00010M[0-1]11M[8-9]10[0-1]Set0Set1Set2Set3存放设定：一个是一个字节01234567第1块第2块第3块第4块直接映像Cache模拟M=16byteaddressesS=4sets,E=1Blocks/setB=2bytes/block,Addresstrace(reads,onebyteperread):

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]xt=1s=2b=1xxxmisshitmiss0??vTagBlock0010M[0-1]10[6-7]11M[8-9]10[0-1]Set0Set1Set2Set3存放设定：一个是一个字节01234567第1块第2块第3块第4块直接映像Cache模拟M=16byteaddressesS=4sets,E=1Blocks/setB=2bytes/block,Addresstrace(reads,onebyteperread):

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]xt=1s=2b=1xxxmisshitmiss0??vTagBlock0010M[0-1]10[6-7]11[8-9]10[0-1]Set0Set1Set2Set3missmiss存放设定：一个是一个字节01234567第1块第2块第3块第4块设若高位作为位索引，则地址上连续的块将会被映射的相同的高速缓存组具有良好的空间局部性的程序却会产生大量冲突不命中不用高位做（组）索引为什么？不用高位做（组）索引为什么？设若高位作为位索引，则地址上连续的块将会被映射的相同的高速缓存组具有良好的空间局部性的程序会产生大量冲突不命中E-路组相连Cache

E=2即每组两行设若:高速缓存块大小8bytestbits0…01100Addressofshortint:0127tagv36540127tagv36540127tagv36540127tagv36540127tagv36540127tagv36540127tagv36540127tagv3654findsetE-路组相连Cachetbits0…01100Addressofshortint:0127tagv36540127tagv3654comparebothvalid?+match:yes=hitblockoffsettagtbits0…01100Addressofshortint:0127tagv36540127tagv3654comparebothvalid?+match:yes=hitblockoffsetshortint(2Bytes)Nomatch:选中组内一行被替换

替换策略：?E=2:即每组两行设若:高速缓存块大小8bytes2-路组相连Cache模拟xxt=2s=1b=1xxAddresstrace(reads,onebyteperread):

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]missSet10??vTagBlock000Set0M=16byteaddressesspace,B=2bytes/block,S=2sets,E=2blocks/set（S，E，B，m）=（2，2，2，4）2-路组相连Cache模拟xxt=2s=1b=1xxAddresstrace(reads,onebyteperread):

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]misshitSet10??vTagBlock000100M[0-1]Set0M=16byteaddresses,B=2bytes/block,S=2sets,E=2blocks/set（S，E，B，m）=（2，2，2，4）miss2-路组相连Cache模拟xxt=2s=1b=1xxAddresstrace(reads,onebyteperread):

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]misshitSet10??vTagBlock000100M[0-1]Set0M=16byteaddresses,B=2bytes/block,S=2sets,E=2blocks/set（S，E，B，m）=（2，2，2，4）miss2-路组相连Cache模拟xxt=2s=1b=1xxAddresstrace(reads,onebyteperread):

0 [00002], 1 [00012], 7 [01112], 8 [10002], 0 [00002]misshitSet10??vTagBlock000100M[0-1]Set0M=16byteaddresses,B=2bytes/block,S=2sets,E=2blocks/set（S，E，B，m）=（2，2，2，4）missmisshit全相连Cache

E=C/B即一个组包含所有高速缓存行，仅含一组设若:高速缓存块大小8bytestbits0…00…01Addressofshortint:0127tagv36540127tagv36540127tagv36540127tagv36540127tagv36540127tagv36540127tagv36540127tagv3654存储层次产生的四个问题当把一个块调入高一层存储器时，可以放在什么位置上?

（映像规则）当所要访问的块在高速缓存中，如何找到该块? （查找算法）当不命中，且高一层存储器已满时，应替换哪一块？

（替换算法）当进行写访问时，应进行哪些操作? （写策略）替换算法可选替换方法优势缺点RND实现简单命中率低FIFO实现简单易出现抖动LRU命中率高需要“计数器“LFU命中率可能较好需要“计数器”存储层次产生的四个问题当把一个块调入高一层存储器时，可以放在什么位置上?

（映像规则）当所要访问的块在高速缓存中，如何找到该块? （查找算法）当不命中，且高一层存储器已满时，应替换哪一块？

（替换算法）当进行写访问时，应进行哪些操作? （写策略）对Cache写策略数据存在多重备份:CacheL1,CacheL2,主存,硬盘如果写命中……

直写

(立即将数据被写回到主存)Write-through写回(延迟写回主存，直到数据被替换时才更新主存内容)Write-back每个高速缓存行维护一个额外的修改位dirtybit如果写不命中……写分配

(加载相应的低一层中的块入高速缓存，然后更新高速缓存)Write-allocate若空间局部性好，则性能好非写分配

(直接写到低一层的主存中)No-write-allocate一般设定

Write-through+No-write-allocateWrite-back+Write-allocateIntelCorei7Cache层次结构RegsL1d-cacheL1i-cacheL2unifiedcacheCore0RegsL1d-cacheL1i-cacheL2unifiedcacheCore3…L3unifiedcache(sharedbyallcores)MainmemoryProcessorpackageL1指令Cache与

数据Cache:32KB,8-way,Access:4cyclesL2统一Ca