计算机体系结构第五章-1

第五章第五章 存存储层次次5.1 存储器的层次结构5.2 高速缓冲存储器(Cache)5.3 降低Cache不命中率的方法5.4 减少Cache不命中开销5.5 减少Cache命中时间5.7 虚拟存储器5.1 存储器的层次结构存储器的层次结构一一.存储系统的基本构成存储系统的基本构成存储系统由两部分构成:(1)存放程序和数据的存储器(多个)(2)控制存储器工作的存储控制部件(包括用硬件、软件或软硬件结合)存储系统对于应用程序员是透明的，并且，从应用程序员看它是一个存储器。多级存储层次多级存储层次速度提高速度提高容量增大，价格降低容量增大，价格降低二二.存储系统的性能指标存储系统的性能指标 评价存储系统性能的主要指标有三个：速度速度-T、容量、容量-S、和、和价格价格-C。1.存储容量存储容量S存储系统的容量是处理机能直接寻址的存储器容量。一般来说，整个存储系统容量即是第二级存储器M2的容量，即S=S2。(T1,S1,C1)M1M2 (T2,S2,C2)处理机处理机 存储系统存储系统由两个存储体构成的存储系统由两个存储体构成的存储系统5.1 存储器的层次结构存储器的层次结构2.单位容量的平均价格单位容量的平均价格C存储系统每个二进制位的平均价格为：当S2S1时，CC2。3.访问周期访问周期T 也被称为也被称为平均访存时间平均访存时间或或等效访问时间等效访问时间等。等。命中率命中率H被定义为被定义为CPU产生的逻辑地址能在产生的逻辑地址能在M1中访问到的概中访问到的概率。率。（其中，（其中，S为容量，为容量，C为单位容量价格。）为单位容量价格。）5.1 存储器的层次结构存储器的层次结构模拟实验的方法得到命中率：模拟实验的方法得到命中率：选择一组有代表性的程序，在执行过程中分别统计对M1存储器的访问成功次数N1和对M1存储器访问不成功的次数N2，则命中率H为：不命中率不命中率F：也称为也称为失效率失效率，是指，是指CPU访存时，在访存时，在M1中找不中找不到所需信息的概率。到所需信息的概率。5.1 存储器的层次结构存储器的层次结构n平均访存时间平均访存时间T T一般分两种情况来考虑CPU的一次访存：1）当命中时，访问时间即为T1（称为命中时间命中时间）。2）当不命中时，若访问的字不在M1中，就必须从M2中把包含所要访问的字的块传送到M1，之后CPU才可在M1中访问到这个字。此时访问时间为：访问时间为：T T2 2T TB BT T1 1T T1 1T TM M T TM M T T2 2T TB B （T TM M称为不命中开销不命中开销/失效开销失效开销：从从向向M M2 2发出访问请求到把整个数据块调入发出访问请求到把整个数据块调入M M1 1中所需的时间。中所需的时间。）n则该存储系统的平均访存时间为：则该存储系统的平均访存时间为：TB传送一个信息传送一个信息块所需的时间块所需的时间5.1 存储器的层次结构存储器的层次结构 存储器的层次结构存储器的层次结构第四层第四层 CPU内部内部 通用寄存器堆通用寄存器堆 指令与数据缓冲栈指令与数据缓冲栈 高速缓冲存储器高速缓冲存储器第一层第一层第二层第二层第三层第三层 主存储器主存储器(DRAM)联机外部存储器联机外部存储器(硬磁盘机硬磁盘机)脱机外部存储器脱机外部存储器(磁带、光盘存储器等磁带、光盘存储器等)第五层第五层第六层第六层访访问问速速度度递递增增方方向向存存储储容容量量递递增增并并每每位位价价格格递递减减方方向向三三.层次式存储系统层次式存储系统 1980年以来存储器和CPU性能随时间而提高的情况（以1980年时的性能作为基准）局部性原理是解决问题的基本思路局部性原理是解决问题的基本思路5.1 存储器的层次结构存储器的层次结构n局部性原理：局部性原理：从大量的统计中得到的一个规律是，程序中对于存储空间90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在存储空间的其余90%的区域中。这就是通常说的局部性原理。访存的局部性规律包括两个方面：时间局部性时间局部性:如果一个存储项被访问,则该存储项可能很快再次被访问.空间局部性空间局部性:如果一个存储项被访问,则该项及其相邻项可能很快被一起访问.n解决思路：解决思路：时间局部把经常用的指令和数据放入M1（快速的）空间局部把相邻的指令和数据放入M15.1 存储器的层次结构存储器的层次结构1.“Cache主存”层次 目的：弥补主存速度的不足2.“主存辅存”层次 目的：弥补主存容量的不足5.1 存储器的层次结构存储器的层次结构“Cache主存”与“主存辅存”层次的区别存储层次存储层次CPU对第二级的对第二级的访问方式访问方式比较项目比较项目目的目的存储管理实现存储管理实现 访问速度的比值访问速度的比值(第一级和第二级第一级和第二级)典型的块典型的块(页页)大小大小失效时失效时CPU是否切换是否切换“Cache 主存主存”层次层次“主存辅存主存辅存”层次层次为了弥补主存速度的不足为了弥补主存速度的不足为了弥补主存容量的不足为了弥补主存容量的不足主要由专用硬件实现主要由专用硬件实现主要由软件实现主要由软件实现几比一几比一几百比一几百比一几十个字节几十个字节几百到几千个字节几百到几千个字节可直接访问可直接访问均通过第一级均通过第一级不切换不切换切换到其他进程切换到其他进程5.1 存储器的层次结构存储器的层次结构由此，形成了两种存储系统：nCache存储系统：由Cache和主存储器构成n虚拟存储系统：由主存储器和磁盘存储器构成5.1 存储器的层次结构存储器的层次结构四四.存储层次的存储层次的4 4个问题个问题 1.当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?（映像规则）2.当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）3.当发生失效时，应替换哪一块？（替换算法）4.当进行写访问时，应进行哪些操作？（写策略）5.1 存储器的层次结构存储器的层次结构一一.基本概念基本概念 Cache具有与CPU相匹配的存取速度，是界于CPU和主存之间的一个子系统。根据其结构可分为：(1)一体化一体化Cache 指程序和数据公用一个Cache。(2)分离分离Cache 指程序和数据高速缓冲存储器分别独立设置。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)二二.基本工作原理基本工作原理 主存储器主存储器 块号块号B 块内地址块内地址W 主存主存-Cache 地址变换地址变换 命中命中 未命中未命中 块号块号b 块内地址块内地址wCache Cache 替换算法替换算法 已满已满 未满未满 调出块调出块 装入块装入块 一个字数据一个字数据 送送CPU 地址地址 来自来自CPU主存地址主存地址Cache地址地址Cache与主存之间以与主存之间以“块块”为单位进行数据交换。为单位进行数据交换。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)三三.地址映象与地址变换地址映象与地址变换n地址映象地址映象 是指把主存储器地址空间映象到Cache地址空间，具体地说，就是把存放在主存储器中的指令和数据按照某种规则装入Cache中，并建立主存储器地址与Cache地址之间的对应关系。n地址变换地址变换 是指当程序已经装入到Cache中之后，在实际运行过程中，将主存储器地址转换为Cache地址的过程。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n存储空间分割与地址计算存储空间分割与地址计算nCache和主存均被分割成大小相同的块。和主存均被分割成大小相同的块。n在进行地址映象和地址变换过程中，都以块为单位进行调在进行地址映象和地址变换过程中，都以块为单位进行调度。度。n访存地址被分割成两个部分：访存地址被分割成两个部分：用于查找该块在用于查找该块在Cache中的位置中的位置用于确定数据用于确定数据在块内的位置在块内的位置5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)1全相联映象及变换全相联映象及变换n全相联映象方式全相联映象方式 主存储器中的任意一块可以映象到主存储器中的任意一块可以映象到Cache中的中的任意一块上。任意一块上。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n全相联映象方式的地址变换过程全相联映象方式的地址变换过程命中命中Cache地址地址主存地址主存地址相联比较相联比较目录表（存放在相联存储器中）目录表（存放在相联存储器中）块号块号B块内地址块内地址W块号块号b块内地址块内地址wBb1主存块号主存块号BCache块号块号b 有效位有效位 为为“1”，表示映象，表示映象关系有效；关系有效；为为“0”，表示映象关表示映象关系无效。系无效。(标识标识)5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n地址变换过程：当CPU要访问Cache时送出主存地址，Cache的控制逻辑用主存地址中的块号B与目录表中的主存块号字段进行相联相联比较比较。如果发现有相等的，表示要访问的数据已经被装入到Cache里了，称为命中命中。如果在相联比较中没有发现相等，表示要访问的那个块不在Cache中，也称为未命中未命中/Cache失效失效。n优点：块冲突小，Cache的利用率高。n缺点：需相联存储器，代价很高。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)2直接映象方式及其地址变换直接映象方式及其地址变换n直接映象方式直接映象方式 直接映象是一种最简单，最直接的方法。主存中一直接映象是一种最简单，最直接的方法。主存中一块只能映象到块只能映象到Cache的一个特定的块中。的一个特定的块中。(循环分配循环分配)区区0区区15.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n对于主存的第对于主存的第i i 块，若它映象到块，若它映象到CacheCache的第的第j j 块，则块，则 j ji mod(M)i mod(M)（M M为为CacheCache的总块数）的总块数）块号块号j主存块地址主存块地址：m位位区号区号ECache块数：块数：M=2m5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n直接映象方式的地址变换过程直接映象方式的地址变换过程区号区号区区表表存存储储器器(按地址访问按地址访问)相等相等有效位有效位E1相等比较相等比较区号区号E块号块号B块内地址块内地址W块内地址块内地址w块号块号b主存地址主存地址Cache地址地址块失效块失效若比较结果相等且有效位为若比较结果相等且有效位为“1”，则用则用Cache地址访问地址访问Cache。读出的数据送读出的数据送CPU。(标识标识)B=b5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)nCache地址与主存地址的低位（块号）完全相同。n需增加：区表存储器。n地址变换过程：首先用主存地址中块号B去访问区号存储器；把读出来的区号与主存地址中的区号E比较，根据比较结果和有效位进行处理。n优点：硬件实现简单，不需相联存储器，并且只需比较区号，速度较快。n缺点：块的冲突率较高。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)3组相联映象及其地址变换组相联映象及其地址变换n组相联映象方式组相联映象方式块块0块块V-1块块V块块2V-1块块(K-1)V块块KV-1组组0组组1组组K-1区区0块块(t-1)KV块块(t-1)KV+V-1块块(t-1)KV+V块块(t-1)KV+2V-1块块(tK-1)V块块tKV-1块块0块块V-1块块V块块2V-1块块(K-1)V块块KV-1组组0组组1组组K-1组组(t-1)K组组(t-1)K+1组组tK-1区区t-1主存储器主存储器Cache5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)把主存和Cache按同样大小划分成组，每组有同样的块数。主存中的一组与Cache中的一组建立直接映象关系，两个对应的组内部采用全相联映象。组号组号主存块地址：主存块地址：g位位组内组内块号块号区号区号Cache组数：组数：G2g5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)nn n路路组相联：组相联：每组中有每组中有n n个块个块(n nM M/G G)。n n称为称为相联度。相联度。相联度越高，Cache空间的利用率就越高，块冲突概率就越低，失效率也就越低。n绝大多数计算机的绝大多数计算机的Cache:Cache:n n 44想一想：想一想：相联度一定是越大越好？相联度一定是越大越好？全相联全相联直接映象直接映象组相联组相联n n(路数路数)G G(组数组数)M MM M1 11 11 1n nM M1 1G GM M5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n组相联映象方式的地址变换过程组相联映象方式的地址变换过程块表块表区号区号E组号组号G组内块号组内块号B块内地址块内地址W主存地址主存地址Cache地址地址组号组号g组内块号组内块号b块内地址块内地址w相等比较相等比较不等不等相等相等V个字个字区号区号E组内块号组内块号B组内块号组内块号bG=g5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n地址变换过程：n用主存地址中的组号G按地址访问块表，读出一组字；n把这些字中区号和块号与主存地址中的区号E和组内块号B进行关联比较：如果发现有相等的，表示要访问的数据已经被装入到Cache里了，称为命中命中。如果在相联比较中没有发现相等，表示要访问的那个块不在Cache中，也称为未命中未命中/Cache失效失效。n分组方式并不改变主存与Cache之间以块为单位调入调出的基本操作方式。n增加：块表存储器。n优点优点：块的利用率大大提高，块的冲突率大大降低，并且实现比全相联方式容易。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)四四.Cache.Cache置换策略置换策略nCache的容量总是比主存储器小得多，因此，必然会出现CPU需要访问的数据不在Cache中的情况。这时，就要从主存中调入新的数据块。如果这时可以装入新块的几个Cache块都已经装满时，就必须淘汰其中某块中的数据以装入新数据，选择被淘汰块的方法称为Cache置换策略（替换算法）。置换策略（替换算法）。n在直接映象方式下，不存在块替换的算法，因为每一块的位置映象是固定的，需要哪一块数据就可直接确定地将该块数据调入上层确定位置。而其他两种映象就存在替换策略的问题，就是要选择替换到哪一个Cache块。n置换策略直接影响Cache主存体系的命中率。应尽可能避免替换掉立即要用到的信息。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)1随机法随机法 随机数产生器产生一个随机数，以此确定要被替换的块。2先进先出法（先进先出法（FIFO）这种算法的思想是不管已调入块的使用频率如何，选择最早调入的块作为替换的对象。3最近最少使用法（最近最少使用法（LRU）这种算法又称为最久未使用法。选择近期最久没有被访问的块作为被替换的块.5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)LRU算法的实现方法：算法的实现方法：（1）寄存器栈）寄存器栈法法 组相联Cache中为每一个组设置一个与组内数据块数相等的寄存器堆栈寄存器堆栈，存放每个块的块号。最近使用过的块始终保持在栈的顶部，最久未使用过的块放在栈的底部。块访问时，从栈顶向栈底顺序查找该块的块号，如果找到，将该块号抽出来放在栈顶，如果没有找到，栈顶压入该该块号，栈底的块号出栈。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)寄存器栈法示意图（4块/组）如果主存块号11，6 访问时：21197111129721197662119栈底单元为栈底单元为被替换块号。被替换块号。（经相联比（经相联比较找到）较找到）没找到没找到压入压入全全部部顺顺序序下下压压5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)（2）计数）计数法法n为Cache中每个块设置一个计数器（块表中），计数器字段的长度与Cache地址中的组内块号字段的长度相同。n计数器的使用规则：n被装入块，其对应的计数器清为“0”，同组中其他块的计数器都加“1”。n命中的块，其对应的计数器清为“0”。同组中其他所有其他所有计数器中，凡是计数值小于命中块原有的计数值的，都计数器中，凡是计数值小于命中块原有的计数值的，都加加“1”，其他计数器不变。，其他计数器不变。n需要替换时，同组中选择计数值最大的计数器，它所对应的块就是要被替换的块。被替换时，其对应的计数器清为“0”，同组中其他块的计数器都加“1”。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)n例如：例如：某系统的Cache采用组相联映象方式，每组有4块，为实现LRU替换算法，块表中为每块设置一个2位的计数器。计数器的工作情况如下表：5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)（3）比较对）比较对法法让各个Cache块成对组合，用一个触发器的状态表示该比较对内两块被访问的时间的远近程度，再经门电路可找到LRU块。如：A、B、C三块，TAB、TAC、TBC分别表示各对中数据块被访问的顺序，TAB为1表示块A比块B更近被访问过。最近未被访问的数据块表示为：CLRU=TACTBC BLRU=TABTBC ALRU=TABTAC5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)五主存更新策略五主存更新策略 由于Cache中的内容取自主存储器，从原则上讲两者的内容应保持一致。但是考虑到系统运行过程可能出现的情况，可能会在一段时间内，两者之间出现不一致现象。CPUCache主存储器主存储器 I/O设备设备 X X （b）I/O写主存写主存 CPUCache主存储器主存储器 I/O设备设备 X X （a）CPU写写Cache 当处理机当处理机对对Cache中中的内容进行的内容进行改写后，没改写后，没有及时地改有及时地改写主存，使写主存，使两者出现不两者出现不一致。一致。由于由于I/O操作时，有操作时，有新的数据送新的数据送入主存中，入主存中，而而Cache中中还是原来装还是原来装入的内容。入的内容。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)1.写写策略策略 写回法（写回法（Write-back）这种方法的要点有二，一是当CPU写数据时，只写Cache，不写主存；二是当已改写的块被替换出Cache 时，将其内容写回主存。Cache 中每块增设“修改位”。写直达法（写直达法（Write-through）也叫写贯穿法，这种方法所实行的是，当CPU进行写操作时，在写Cache的同时也将内容写入到相应的主存单元中，即两个内容同时改写。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)两种方案比较两种方案比较:（1）写直通法是在每次写Cache时都有写主存的操作，能始终保持数据块的一致性保持数据块的一致性。写回法则仅在数据块被置换时写入主存，可减少访问主减少访问主存的开销存的开销，但存在Cache块与主存块的瞬间不一致。（2）写直达法一次写入一个字，仅需一个奇/偶校验位；而写回法一次写入一个数据块，需要多个校验位。（3）写直达法需要较多的缓冲寄存器存放需要写入主存的数据；而写回法相应要简单些。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)2.“写写”操作时的调块（写失效时）操作时的调块（写失效时）（1）按写分配法）按写分配法(写时取写时取)：写不命中时，先把所写单元所在的块调入Cache，再行写入。（2）不按写分配法）不按写分配法(绕写法绕写法)：写不命中时，直接写入下一级存储器而不调块。3.3.写策略与调块写策略与调块n写回法 按写分配n写直达法 不按写分配5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)练 习 有一个“Cache-主存”存储层次。主存共分为8个块（07），Cache为4个块（03），采用直接映像方式。（1）画出主存各块与Cache各块之间的映像关系。（2）对于如下主存块地址流：1，2，4，1，3，7，0，1，2，5。如主存中内容一开始未装入Cache，请列出每次访问后Cache中各块的分配情况。并求出此期间的Cache命中率。根据块地址计算出每一主存块在Cache中的块号：主存块地址 1 2 4 1 3 7 0 1 2 5Cache块号 1 2 0 1 3 3 0 1 2 1解：解：块块0 块块1 块块3 块块0 块块1 块块3 块块4 块块5 块块7 区区0 区区1 Cache 主存储器主存储器 块块2 块块2 块块6（1）根据块地址计算出每一主存块在Cache中的块号：块地址 1 2 4 1 3 7 0 1 2 5 块号 1 2 0 1 3 3 0 1 2 1时间：时间：1 2 3 4 5 6 7 8 9 10块地址流：块地址流：1 2 4 1 3 7 0 1 2 5Cache：块块0 块块1 块块2 块块3112124124命中命中124312471207120712075207命中命中命中命中（2）命中率为：）命中率为：3/10作作业(下次下次课提交提交)n有一个Cache存储器，主存有8块(0-7)，Cache有4块(0-3)，采用组相联映像，组内块数为2块，每块大小为16个字节。采用LRU（近期最久未使用）替换算法。(1)写出主存地址的格式，并标出各字段的长度。(2)写出Cache地址的格式，并标出各字段的长度。(3)画出主存各块与Cache各块之间的映像关系。(4)某程序运行过程中，访存的主存块地址流为：6,2,4,1,4,6,3,0,4,5,7,3列出该程序每次访存对Cache块位置的使用情况，并计算Cache命中率。六六.Cache.Cache性能分析性能分析1平均访存时间n通常，在存储系统中，平均访存时间（又称为AMAT）为：平均访存时间=命中时间+不命中率不命中开销5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)2CPU时间 执行一个程序所需的CPU时间能更好地反映存储系统的性能。CPU时间时间=（CPU执行周期数执行周期数+存储器停顿周期数）存储器停顿周期数）时钟周期时间时钟周期时间n通常，将Cache命中所用的时钟周期数看作是CPU执行周期数的一部分。n存储器停顿周期数近似为：存储器停顿周期数存储器停顿周期数=访存次数访存次数失效失效率率失效失效开销开销5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)则：CPU时间=（CPU执行周期数+访存次数失效率失效开销）时钟周期时间进一步：CPU时间时间=IC（CPIexecution+每条指令的平均访存次数每条指令的平均访存次数失效失效率率失效失效开销开销）时钟周期时间时钟周期时间 其中，IC为指令条数。5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)例：假设执行一段包含100条指令的程序，不命中开销50个时钟周期，当不考虑存储器停顿，所有指令执行时间为2个时钟周期，CACHE不命中率2%，平均每条指令访存1.33次。分析CACHE对性能的影响。解：由于CPU时间=IC（CPIexecution+每条指令的平均访存次数失效率失效开销）时钟周期时间1）系统加入CACHE后：CPU时间=100（2+1.332%50）=333时钟周期2）系统加入CACHE前（不命中100%）：CPU时间=100（2+1.33*100%*50）=6850时钟周期5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)3改进Cache性能平均访存时间=命中时间+失效率失效开销 因此，可以从以下三个方面进行改进：1）降低失效率2）减少失效开销3）减少命中时间n本章介绍了17种Cache优化技术（选择讲解）n8种用于降低不命中率n5种用于减少不命中开销n4种用于减少命中时间5.2 高速缓冲存储器高速缓冲存储器(Cache)(Cache)