计算机体系结构第五章-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存储系统每个二进制位的平均价格为：212211SSSCSCC当S2S1时，C≈C2。3.访问周期T也被称为平均访存时间或等效访问时间等。命中率H被定义为CPU产生的逻辑地址能在M1中访问到的概率。（其中，S为容量，C为单位容量价格。）5.1存储器的层次结构模拟实验的方法得到命中率：选择一组有代表性的程序，在执行过程中分别统计对M1存储器的访问成功次数N1和对M1存储器访问不成功的次数N2，则命中率H为：211NNNH不命中率F：也称为失效率，是指CPU访存时，在M1中找不到所需信息的概率。HF15.1存储器的层次结构平均访存时间T一般分两种情况来考虑CPU的一次访存：1）当命中时，访问时间即为T1（称为命中时间）。2）当不命中时，若访问的字不在M1中，就必须从M2中把包含所要访问的字的块传送到M1，之后CPU才可在M1中访问到这个字。此时访问时间为：T2＋TB＋T1＝T1＋TMTM＝T2＋TB（TM称为不命中开销/失效开销：从向M2发出访问请求到把整个数据块调入M1中所需的时间。）则该存储系统的平均访存时间为：MMMFTTTTHTTTHHTT1111)1())(1(或：TB传送一个信息块所需的时间5.1存储器的层次结构存储器的层次结构第四层CPU内部通用寄存器堆指令与数据缓冲栈高速缓冲存储器第一层第二层第三层主存储器(DRAM)联机外部存储器(硬磁盘机)脱机外部存储器(磁带、光盘存储器等)第五层第六层访问速度递增方向存储容量递增并每位价格递减方向三.层次式存储系统1980年以来存储器和CPU性能随时间而提高的情况（以1980年时的性能作为基准）局部性原理是解决问题的基本思路5.1存储器的层次结构局部性原理：从大量的统计中得到的一个规律是，程序中对于存储空间90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在存储空间的其余90%的区域中。这就是通常说的局部性原理。访存的局部性规律包括两个方面：时间局部性:如果一个存储项被访问,则该存储项可能很快再次被访问.空间局部性:如果一个存储项被访问,则该项及其相邻项可能很快被一起访问.解决思路：时间局部——把经常用的指令和数据放入M1（快速的）空间局部——把相邻的指令和数据放入M15.1存储器的层次结构1.“Cache—主存”层次目的：弥补主存速度的不足2.“主存—辅存”层次目的：弥补主存容量的不足5.1存储器的层次结构“Cache－主存”与“主存－辅存”层次的区别存储层次CPU对第二级的访问方式比较项目目的存储管理实现访问速度的比值(第一级和第二级)典型的块(页)大小失效时CPU是否切换“Cache－主存”层次“主存－辅存”层次为了弥补主存速度的不足为了弥补主存容量的不足主要由专用硬件实现主要由软件实现几比一几百比一几十个字节几百到几千个字节可直接访问均通过第一级不切换切换到其他进程5.1存储器的层次结构由此，形成了两种存储系统：Cache存储系统：由Cache和主存储器构成虚拟存储系统：由主存储器和磁盘存储器构成系统程序员看：速度接近Cache的速度，存储容量是主存的容量，每位价格接近主存储器。Cache存储系统Cache主存储器应用程序员看：速度接近主存储器的速度，存储容量是虚拟地址空间，每位价格接近磁盘存储器。虚拟存储系统主存储器磁盘存储器5.1存储器的层次结构四.存储层次的4个问题1.当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?（映像规则）2.当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）3.当发生失效时，应替换哪一块？（替换算法）4.当进行写访问时，应进行哪些操作？（写策略）5.1存储器的层次结构一.基本概念Cache具有与CPU相匹配的存取速度，是界于CPU和主存之间的一个子系统。根据其结构可分为：(1)一体化Cache指程序和数据公用一个Cache。(2)分离Cache指程序和数据高速缓冲存储器分别独立设置。5.2高速缓冲存储器(Cache)二.基本工作原理主存储器块号B块内地址W主存-Cache地址变换命中未命中块号b块内地址wCacheCache替换算法已满未满调出块装入块一个字数据送CPU地址来自CPU主存地址Cache地址Cache与主存之间以“块”为单位进行数据交换。5.2高速缓冲存储器(Cache)三.地址映象与地址变换地址映象是指把主存储器地址空间映象到Cache地址空间，具体地说，就是把存放在主存储器中的指令和数据按照某种规则装入Cache中，并建立主存储器地址与Cache地址之间的对应关系。地址变换是指当程序已经装入到Cache中之后，在实际运行过程中，将主存储器地址转换为Cache地址的过程。5.2高速缓冲存储器(Cache)块地址块内地址主存地址：存储空间分割与地址计算Cache和主存均被分割成大小相同的块。在进行地址映象和地址变换过程中，都以块为单位进行调度。访存地址被分割成两个部分：用于查找该块在Cache中的位置用于确定数据在块内的位置5.2高速缓冲存储器(Cache)1．全相联映象及变换全相联映象方式主存储器中的任意一块可以映象到Cache中的任意一块上。5.2高速缓冲存储器(Cache)全相联映象方式的地址变换过程命中Cache地址主存地址相联比较目录表（存放在相联存储器中）块号B块内地址W块号b块内地址wBb1主存块号BCache块号b有效位为“1”，表示映象关系有效；为“0”，表示映象关系无效。(标识)5.2高速缓冲存储器(Cache)地址变换过程：当CPU要访问Cache时送出主存地址，Cache的控制逻辑用主存地址中的块号B与目录表中的主存块号字段进行相联比较。①如果发现有相等的，表示要访问的数据已经被装入到Cache里了，称为命中。②如果在相联比较中没有发现相等，表示要访问的那个块不在Cache中，也称为未命中/Cache失效。优点：块冲突小，Cache的利用率高。缺点：需相联存储器，代价很高。5.2高速缓冲存储器(Cache)2．直接映象方式及其地址变换直接映象方式直接映象是一种最简单，最直接的方法。主存中一块只能映象到Cache的一个特定的块中。(循环分配)区0区1…5.2高速缓冲存储器(Cache)对于主存的第i块，若它映象到Cache的第j块，则j＝imod(M)（M为Cache的总块数）块号j主存块地址：m位区号ECache块数：M=2m5.2高速缓冲存储器(Cache)直接映象方式的地址变换过程区号区表存储器(按地址访问)相等有效位E1相等比较区号E块号B块内地址W块内地址w块号b主存地址Cache地址块失效若比较结果相等且有效位为“1”，则用Cache地址访问Cache。读出的数据送CPU。(标识)B=b5.2高速缓冲存储器(Cache)Cache地址与主存地址的低位（块号）完全相同。需增加：区表存储器。地址变换过程：①首先用主存地址中块号B去访问区号存储器；②把读出来的区号与主存地址中的区号E比较，根据比较结果和有效位进行处理。优点：硬件实现简单，不需相联存储器，并且只需比较区号，速度较快。缺点：块的冲突率较高。5.2高速缓冲存储器(Cache)3．组相联映象及其地址变换组相联映象方式块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中的一组建立直接映象关系，两个对应的组内部采用全相联映象。组号主存块地址：g位组内块号区号Cache组数：G＝2g5.2高速缓冲存储器(Cache)n路组相联：每组中有n个块(n＝M/G)。n称为相联度。相联度越高，Cache空间的利用率就越高，块冲突概率就越低，失效率也就越低。绝大多数计算机的Cache:n≤4想一想：相联度一定是越大越好？全相联直接映象组相联n(路数)G(组数)MM111＜n＜M1＜G＜M5.2高速缓冲存储器(Cache)组相联映象方式的地址变换过程块表区号E组号G组内块号B块内地址W主存地址Cache地址组号g组内块号b块内地址w相等比较不等相等V个字区号E组内块号B组内块号bG=g5.2高速缓冲存储器(Cache)地址变换过程：用主存地址中的组号G按地址访问块表，读出一组字；把这些字中区号和块号与主存地址中的区号E和组内块号B进行关联比较：①如果发现有相等的，表示要访问的数据已经被装入到Cache里了，称为命中。②如果在相联比较中没有发现相等，表示要访问的那个块不在Cache中，也称为未命中/Cache失效。分组方式并不改变主存与Cache之间以块为单位调入调出的基本操作方式。增加：块表存储器。优点：块的利用率大大提高，块的冲突率大大降低，并且实现比全相联方式容易。5.2高速缓冲存储器(Cache)四.Cache置换策略Cache的容量总是比主存储器小得多，因此，必然会出现CPU需要访问的数据不在Cache中的情况。这时，就要从主存中调入新的数据块。如果这时可以装入新块的几个Cache块都已经装满时，就必须淘汰其中某块中的数据以装入新数据，选择被淘汰块的方法称为Cache置换策略（替换算法）。在直接映象方式下，不存在块替换的算法，因为每一块的位置映象是固定的，需要哪一块数据就可直接确定地将该块数据调入上层确定位置。而其他两种映象就存在替换策略的问题，就是要选择替换到哪一个Cache块。置换策略直接影响Cache—主存体系的命中率。应尽可能避免替换掉立即要用到的信息。5.2高速缓冲存储器(Cache)1．随机法随机数产生器产生一个随机数，以此确定要被替换的块。2．先进先出法（FIFO）这种算法的思想是不管已调入块的使用频率如何，选择最早调入的块作为替换的对象。3．最近最少使用法（LRU）这种算法又称为最久未使用法。选择近期最久没有被访问的块作为被替换的块.5.2高速缓冲存储器(Cache)LRU算法的实现方法：（1）寄存器栈法组相联Cache中为每一个组设置一个与组内数据块数相等的寄存器堆栈，存放每个块的块号。最近使用过的块始终保持在栈的顶部，最久未使用过的块放在栈的底部。块访问时，从栈顶向栈底顺序查找该块的块号，如果找到，将该块号抽出来放在栈顶，如果没有找到，栈顶压入该该块号，栈底的块号出栈。5.2高速缓冲存储器(Cache)寄存器栈法示意图（4块/组）如果主存块号11，6访问时：21197111129721197662119栈底单元为被替换块号。（经相联比较找到）没找到压入全部顺序下压5.2高速缓冲存储器(Cache)（2）计数法为Cache中每个块设置一个计数器（块表中），计数器字段的长度与Cac