《计算机系统结构》电子教案(课8-11).ppt

单击此处编辑母版标题样式,2014.2.17,计算机系统结构,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第7章 存储层次（,P188,）,Memory,Hirarchy,长期存在的问题：在合理的总价格限制下，单一型主存器件的速度跟不上,CPU,的发展，容量不能满足软件尺寸扩大。,本章学习提高主存系统性能/价格比的几种结构化方法，重点是“,Cache-,主存层次”，焦点问题是,如何使流水线每拍完成一次访存,。,本章基本公式：,(1)平均时间,T=P,1,T,1,+P,2,T,2,其中,P,1,+,P,2,=100%，并且,T,1,和,T,2,都可以再用该式迭代展开，复杂,时，可用概率树来表示（全概率公式）；,(2)实际时间,T=,理想时间+,P,3,每次额外开销时间,其中,P,3,是不利事件发生概率。,2014.2.17,1,计算机系统结构,7.1,存储层次原理及性能指标（,P188）,7.1.1 基本原理,“存储层次”的定义：（参见,P189,第,3,段）,由2种或多种存储部件构成的复合存储系统，通过内部管理机构的,自动更换机制,，能够不断将大容量低速存储部件中的活跃内容复制到小容量高速存储部件中（后者作为前者的,局部副本,）。,它既能满足,CPU,的快速存取需要，又有很大的存储容量，平均单位价格也很低，等效于同时满足3方面要求的理想单一存储部件。,依据：程序访问的局部化原理（时间局部化，空间局部化）。,模型：如右图所示，存储层次由,n,层组成，,满足3个不等式：,T,Ai,c,i,+1,，,S,i,S,i,+1,。,2014.2.17,2,计算机系统结构,存储层次的基本术语,逻辑地址,（又称为相对地址、虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按,CPU,字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。,物理地址,（又称为绝对地址、实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。,从,M,1,到,M,n,各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。,地址映象方式,指的是虚页集合与实页集合的对应规则，或者说是约束关系。,地址变换,（又叫虚实变换）指逻辑地址到物理地址的变换过程或者算法。,页失效,指当前被访问存储级中没有所需的信息，也就是不命中现象。,实页争用,又叫实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。,页和块,：前者用于主-辅层次，后者用于,Cache-,主存层次，意义相同。,2014.2.17,3,计算机系统结构,7.7.1,存储层次的管理方式(,P230),根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在3种存储层次管理方式。,目前在主存辅存层次实现中，具体机器可能采用3种方式中的某1种，而,Cache-,主存层次普遍只采用第2种，因为它简单，便于硬件实现。,(1)段式管理。段是程序中的一个逻辑单位，可以是一个程序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。,每段使用独立的逻辑地址空间，即都从0开始计算地址。,段式管理方法的主要缺点是各段长短不一，调进调出之后容易形成大量不规则的零碎空间。,段式管理方法的虚实变换算法是查段表,。,因其实现较复杂，仅用于主存辅存层次。,2014.2.17,4,计算机系统结构,7.7.1,存储层次的管理方式(续),(2)页式管理。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。,我们把用户文件划分得到的一个长度单位称为“虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页”。,页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。,页式管理方法的虚实变换算法是查页表,。,两种层次都用此技术。,(3)段页式管理。它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表,。,段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。它的实现最复杂，仅用于主存辅存层次。,段页式管理方法的最小调度单位仍是页，基本操作可归于页式管理。,2014.2.17,5,计算机系统结构,课堂练习,7.1,一个页式虚拟存储器按字节编址，页面大小为1,K,字节，每个数据的字长为4个字节。现有一个程序的页表如下：,表中的装入标志为“1”表示该虚页已经装入主存，为“0”则表示还未装入主存。修改标志为“0”表示该页还没有被修改过，为“1”则表示该页已经被修改过。访问方式“,RW”,表示该页可以读可以写，但不能作为指令来执行；“,R”,表示该页只能读，不能写和执行；“,X”,表示该页只能作为指令来执行，不能读和写。,2014.2.17,6,计算机系统结构,课堂练习,7.1,（续,）,虚地址经变址寻址和基址寻址(,B)+(X)+D,形成。现有一个程序，出现下列访问主存的操作：,(1)列出产生主存页面失效的操作序号。,(2)如果不发生主存页面失效的话，计算访问主存的物理地址。,(3)列出非法操作的序号。,(4)列出被修改过的主存页面号。,2014.2.17,7,计算机系统结构,7.1.3,“主辅”层次与“,Cache,主存”层次的对比,（,P192,表7.1，,P231,表7.7）,“,主存,-辅存,”,层次,目的：提高等效容量。,基本调度单位：页，几百,Byte,到几千,Byte。,速度比：几万倍。,虚实转换：页表（以虚页号为索引）,“,Cache-,主存,”,层次,目的：提高等效速度。,基本调度单位：块，几十,Byte。,速度比：几倍。,虚实转换：目录表（以实页号为索引）,2014.2.17,8,计算机系统结构,7.1.4,存储层次的,基本问题(,P192),映象规则,一个虚块（页）被允许放到哪些实块（页）上；,查找算法,如何在实存中找到指定的虚块（页）（主要是虚实变换）；,替换算法,块（页）争用时，调出哪个虚块（页）；,写策略,写存储层次的具体操作。,典型存储层次（,PC,计算机，以,Intel,芯片组为例）,2014.2.17,9,计算机系统结构,7.1.2,存储层次的性能指标（,P189,）,先以2级存储层次为例进行公式推导，并且只考虑各级存储器件自身的操作，忽略控制机构的附加开销。多级层次以及附加开销留到以后讨论。,(1)容量：,S=S,2,（,理论上）,(2)单价：（美分/,bit）,2014.2.17,10,计算机系统结构,(3)速度,表现访问速度的参数较多。,命中率,H：,被访问数据事先已在,M,1,的概率,不命中率,F：,不命中的概率，又称失效率，,F=,1-,H,平均访存时间：命中时的访存时间为,T,A1,，,不命中时的访存时间为,T,A2,，,平均访存时间则是它们的概率均值,其中,T,M,是失效开销，,T,M,=,T,A2,+T,B2,2014.2.17,11,计算机系统结构,访问效率,e（,补充）,访问效率,e,受,H,和,r,的影响（参见右图）：,e,是一个相对值，便于不同系统之间的比较。,2014.2.17,12,计算机系统结构,假设：,T,Ai,表示第,i,级器件读/写时间；,T,Bi,表示第,i,级向上级传送时间。,根据模型有：,命中,M,1,时：,T,A,=T,A1,命中,M,2,时：,T,A,=T,A1,+T,A2,+T,B2,T,A2,命中,M,n,时：,T,A,=T,A1,+T,A2,+T,B2,+,T,An,+,T,Bn,T,an,区别：,单次访问总时间近似等于本次到达的最低一层的访问时间，因为每层都只访问一次；,大量访问的平均时间则由各层访问时间共同构成，因为较高层的一次访问时间虽短，但它们被访问的百分比远远大于较低层。,多级存储层次的单次访问时间,2014.2.17,13,计算机系统结构,课堂练习7.2,设计,“,Cache-,主存,”,层次,，,Cache,的容量有三种选择，如上表所示。忽略平均访存时间,T,A,公式中的,T,B,。,(1),分别计算三种方案的等效访问时间；,(2)分别计算三种方案每,KB,的平均价格；,(3)分别根据等效访问时间、每,KB,的平均价格排序；,(4)根据等效访问时间和平均价格的乘积排序。,2014.2.17,14,计算机系统结构,多级存储层次的平均访问时间1,M,1,10,3,B T,A1,=1us 10,3,B,M,2,10,6,B T,A2,=10us,M,3,10,9,B T,A3,=100us 10,9,B,(,a)(b),例7.0 有一个10,9,字节的程序被装入右图所示的,M,3,准备运行。假定指令字长=1字节，程序中无转移指令和内存读/写指令。忽略传送时间,T,B,。,(1)按图(,a),求,T,A,和,e,；,(2),按图,(,b),推导三层体系的,T,A,公式；,(3)按图(,b),求,T,A,和,e；,(4),比较,(1)(3)结果，有何结论？,解：,2014.2.17,15,计算机系统结构,多级存储层次的平均访问时间2,由这2式合并得,此公式参见教材,P214,倒数第12行。,2014.2.17,16,计算机系统结构,多级存储层次的平均访问时间3,(4)结论：插入中间层后，层间速度差减少，访问效率提高。,2014.2.17,17,计算机系统结构,(1)问中，为什么？,答：每当,CPU,访问,M,1,不命中时，存储系统会从,M,3,装入1000字节到,M,1,，,再从,M,1,取1个字节送给,CPU，,所以本次访问结果为“失效”，但是紧接着的999次访问将“命中”，以后又是如此重复，。同学们不要把访问“失效”理解为访问“失败”，认为,CPU,在,M,1,找不到数据就会放弃本次访问。“失效”的定义是经过等待后完成的访问，而“命中”是不需要等待即完成的访问，仅此不同。,(3)问中，为什么？,答：,M,2,接受,M,1,的数据请求，每次是1000字节。,M,2,的初始状态为“空”，对于,M,1,的首次请求不能立即满足，需要先从,M,3,索取1000000字节数据填满自己，再向,M,1,提供所要的1000字节数据。这次访问称为“失效”。此后,M,1,向,M,2,发出的999次请求都能立即响应，而再下一次请求又需要等待。如此重复，所以,H,2,=999/1000。,例题说明：,2014.2.17,18,计算机系统结构,刚才推导中使用的不命中率都是局部不命中率。为了避免混淆，有必要分清两种不命中率：,全局不命中率是一个比局部不命中率更有意义的指标，它指出了在,CPU,发出的所有访存请求中，究竟有多大比例是穿过该级，到达下一级存储器的。,7.4.1,局部不命中率与全局不命中率（,P214）,2014.2.17,19,计算机系统结构,因为：,所以：,依此类推，,7.4.1,局部不命中率与全局不命中率（续,）,2014.2.17,20,计算机系统结构,多级存储层次的平均访问时间公式重写,将这些局部不命中率、全局不命中率的定义式代入到前面的多级存储层次平均访问时间公式中，我们可以得到更容易记忆的公式形式：,2014.2.17,21,计算机系统结构,例7.3 考虑某一两级,Cache：,第一级,Cache,为,L1，,第二级,Cache,为,L2。,(1)假设在1000次访存中，,Cache1,的不命中是40次，,Cache2,的不命中是20次。求各种局部不命中率和全局不命中率；,(2)假设,Cache1,的命中时间是1个时钟周期，,Cache2,的命中时间是10个时钟周期，不命中开销是100时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间（即,失效开销,）是多少个时钟周期？,解：,(1)第一级,Cache,的不命中率（全局和局部）是40/1000，即4%；,第二级,Cache,的局部不命中率是20/40，即50%；,第二级,Cache,的全局不命中率是20/1000，即2%。,例,7.3,2014.2.17,22,计算机系统结构,(2),T,A,T,A1,F,1,(T,A2,F,2,T,M2,),14%(1050%100),14%603.4,个时钟周期,式中后面部分,4%60,为每次访存的平均停顿时间（即,失效开销,）：,每次访存的平均停顿时间（即,失效开销,）,4%60,2.4,由于平均每条指令访存1.5次，所以：,每条指令的平均停顿时间2.41.53.6个时钟周期,习题7.9,例,7.3,（续）,2014.2.17,23,计算机系统结构,各次作业应交的内容,作业,8,（第9次课）,7.9,2014.2.17,24,计算机系统结构,地址映象问题的提出,1.页表占用空间过大问题,页表必须存放在实存,M,1,里。实际上，命中情况下的访存时间等于查表时间加上访问目标数据的时间，所以页表不能放在,M,2,。,页表,占用空间=,页表行数 每行宽度,其中，页表行数=虚存容量/页面大小,以,Win2K,为例，虚存页表=4 4,G/4K=2,2,2,32,/2,12,=2,22,=4,MB,Cache-,主存层次的页表,=,4 4,G/16=2,30,=1GB，,而,Cache1,只有32,K,减少页表空间的思路分,减少行数,和,减少行宽,两类。,2.相联目录表方法（又称“实页表”）/减少行数,仅保留页表中已装入的虚页记录。为避免逐行比对，利用相联存储器存放此表，它具有并行比较功能，但价格远高于普通存储器。,P196,图7.10示意,Cache,中用多字并行比较方法实现的相联目录表。此法须严格限制字数。,3.快慢表方法（,TLB）,/减少行数,4.改变地址映象/减少行宽,2014.2.17,25,计算机系统结构,7.2.2,四种常见的地址映象方式（,P193）,(1)全相联,(,fully associative),全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。这种关系可用下页示意图(,a)、(b),表示。,全相联的虚实变换信息完全来自于变换表，查表过程如图(,c),所示。,全相联映象方式使虚页调入有最大的选择范围，发生实页争用的可能性最小，调入/调出的操作开销也最少，有利于命中率提高。但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高，在命中情况下花费在虚实变换上的时间也比较多。,由于页表必须常驻在实存中，而,主存-辅存层次的,实存（即主存）相对,Cache-,主存层次的,实存（即,Cache,存储器）容量大得多，所以全相联映象方式一般用于,主存-辅存层次。,一个虚页被允许进入的实页集合称为,“,候选位置,”,（,P195），,全相联的,“,候选位置,”,为整个实存。,2014.2.17,26,计算机系统结构,全相联的地址映象方式与地址变换原理示意图(,a)(b),2014.2.17,27,计算机系统结构,全相联的地址映象方式与地址变换原理示意图(,c),2014.2.17,28,计算机系统结构,(2)直接相联(,direct mapped),直接相联是一种最强的约束关系，它规定每个虚页只对应唯一的实页。为了便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现起来非常简单，因为在二进制中，任何数,X,对2的整次幂,n,求模等价于截取,X,的最低,log,2,n,位，如下页示意图(,c),所示。,例5.2 已知虚页号=7，实页总数=4，用直接相联求实页号。,解：,可用十进制形式求：7,mod 4=3；,也可用二进制形式求：由于,n=4，,所以,log,2,n=2，,取7的二进制形式111,B,的最低2位，得11,B，,即3。,直接相联映象方式不需要借助页表来进行虚实变换，显然大大节省了相应的空间与时间（当然页表中的装入位和修改位还得保留），但是由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率下降。,这种映象方式主要用于对实存价格、速度敏感的,Cache-,主存层次,。,直接相联的,“,候选位置,”,为1个实页，它又被简称为,“,1路,Cache,”,。,2014.2.17,29,计算机系统结构,直接相联的地址映象方式与地址变换原理,2014.2.17,30,计算机系统结构,(3)组相联(,set,associative,，P194),组相联映象方式是全相联与直接相联的一个折中方案，性能也是二者的折中。具体做法是先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。所有虚组按照直接相联方式映射到实组集合，对应的虚实组之间各页则用全相联映射，如下页示意图(,a)、(b),所,示（设实组数为2）。,由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，首先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”。如图(,c),所示。,采用组相联映象方式时，每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低；另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。当然这两方面优点是互相抵触的：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。,这种映象方式性价比较好，在,Cache-,主存层次中被普遍使用,。,实组内页数被称为“路数”,，,又称为“相联度”（,associativity,）,它表明一个虚页的选择范围。下页图示为2路组相联（2-,way set associative）。,2014.2.17,31,计算机系统结构,组相联的地址映象方式与地址变换原理(,a)(b),组相联的,“,候选位置,”,为组内页数，即,“,路数,”,。,2014.2.17,32,计算机系统结构,组相联的地址映象方式与地址变换原理(,c),2014.2.17,33,计算机系统结构,(4)位选择组相联(,P194,图7.7,c),位选择组相联映象方式映象关系中，实存分组，虚存按实组数分区，区内不分组。虚块号与实组号之间是直接映象关系，而虚块与该实组内的各个实块之间是全相联映象方式。例如，虚块0可以映象到实组0的任意一块中。,在一般组相联映象方式中，一个虚组与一个实组之间是多个块到多个块的映象。而在位选择组相联映象方式中，改成了一个虚块到实组中多个块的映象。映象关系明显简单，实现起来可以容易些。另外，从数据的分布情况看。对于一般组相联映象方式，虚存中的几个连续块映象到实存中可能也是连续的，而对于位选择组相联映象方式，虚存中的连续块映象到实存中肯定是不连续的，它们被分散到实存的各个组中。由于在虚存与实存之间是以块为单位进行调度的，而实存是以字为单位访问的，只要实存中的一个字不跨越两个块，在实存内部的块与块之间的分布是否连续对实存的正常工作是没有关系的。,由于虚存每个区中的块数与实组数相等，而且它们之间采用直接映象方式，因此，虚存地址中的区内块号可以直接作为实组号,。,位选择组相联的地址变换过程比一般组相联映象方式简单，而与全相联映象方式基本相同。,2014.2.17,34,计算机系统结构,位选择组相联的地址映象方式与地址变换原理(,a)(b),2014.2.17,35,计算机系统结构,位选择组相联的地址映象方式与地址变换原理(,c),2014.2.17,36,计算机系统结构,(1)页表法,每个虚页对应1项，虚页号就是项号，项内存储实页号，如课堂练习7.2。这种方法原理简单，但是占用空间非常大。当页表尺寸超过1页时，它本身还要按页面尺寸分割成许多分散存放的子表，再造一个“表上表”来找到当前需要的子表。进一步发展就会形成“多级页表”,，,导致虚实变换分多步进行，时间大大延长。,7.2.3,虚实变换基本方法（,P195）,2014.2.17,37,计算机系统结构,(2)部分虚实,表法（,P195,图7.8）,这是一种统称，指表项数少于虚页数的情形，下面要介绍的3种方法都属于这一类。（与,Hash,查表有点相似）,表项数少于虚页数意味着查表时会有多个虚页查到表中同一项的情况发生，另外也意味着区分表中项号的地址位数少于虚页号的位数，虚页号中未用的位数正是造成重复的原因。,表项数少于虚页数的做法既是节省成本的需要，也符合任何时刻只有少部分虚页占用实存的实际，问题是每个表项必须说明它当前记录的是一组共享虚页中的哪一个的信息，这就要用到“标识”字段。,虚页号里用于计算表内地址的部分称为“索引”,index,，用来与查表内容相比较的部分称为“标识”,tag。,下图以组相联为例说明“标识”的意义，它有16个虚页，只用4个表项。,7.2.3,虚实变换基本方法（续1,）,2014.2.17,38,计算机系统结构,(3)快慢表方法（,P231,）,这是页表法的一种加快方案。地址变换缓冲器,TLB（Translation Look-aside Buffer）,是一个专用的高速缓冲器，用于存放近期经常使用的页表项副本，,TLB,利用程序的局部性原理，以小表代替大表，缩短查找时间。,7.2.3,虚实变换基本方法（续2,）,2014.2.17,39,计算机系统结构,(4)目录表法（,P196,第1段）,只对已经装入实存的虚页造表，其项数比页表少得多。,为避免逐行比对，须使用相联存储器来存放，通过并行比较实现一次查遍，器件价格远高于普通存储器。,7.2.3,虚实变换基本方法（续3,）,2014.2.17,40,计算机系统结构,(5),单体多字存储器多比较器查表方法（,P196,第2段,）,这是,目录表,法的一种廉价方案，对组相联非常适用。限制条件是组内页数不太多，下图为4的情况。,7.2.3,虚实变换基本方法（续4,）,2014.2.17,41,计算机系统结构,主辅层次虚实变换实现,主流方案：全相联，页表法（,P232）,2014.2.17,42,计算机系统结构,Cache,主存层次虚实变换实现（直接相联）,快命中方案：直接相联，目录表法（,P196，,图7.9）,举例：为了方便用10进制讨论。设虚块号=000999，实块号=09，于是有索引=09，而标识=0099。,索引=0的实块里装的虚块标识可以是00，01，99，对应的虚块号就是000，010，020，030，990。,2014.2.17,43,计算机系统结构,Cache,主存层次虚实变换实现（组相联）,低失效方案：位选择组相联（2路），目录表法（,P196，,图7.9）,2014.2.17,44,计算机系统结构,7.3.5,伪相联（,P209）,优点,缺点,直接映象,组相联,命中时间小,命中时间大,不命中率高,不命中率低,“伪相联”又称“列相联”，按原理还可称为“伴生,Cache”。,(1),比较直接相联、组相联的优缺点,从例7.4我们将看到，直接相联的命中时间较短，而多路组相联的失效率较低，所以它们的平均访问时间依两个因素的作用大小而互有输赢。有没有什么方法取二者之长呢？,(2)伪相联的优点,伪相联就是直接相联、组相联的一种组合方案。优点是命中时间短、,不命中,率还低，所以它的平均访问时间往往比直接相联、组相联都短,。,2014.2.17,45,计算机系统结构,(3)基本思想及工作原理,在逻辑上把直接,相联,Cache,的空间分为上、下两个区。对于任何一次访问，伪相联,Cache,先按直接,相联,Cache,的方式去处理。若命中，则其访问过程与直接,相联,Cache,的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中。再找不到就只好访问下一级存储器。,显然伪,相联的,“,候选位置,”,=2，,与2路,组相联相同。,每次访问时间有3种可能：,正常命中（快速命中）,伪命中（慢速命中）,不命中,7.3.5,伪相联（续1,）,2014.2.17,46,计算机系统结构,(4)快速命中与慢速命中,要保证绝大多数命中都是快速命中，就是命中率要高。一种简单的办法是在出现伪命中时，交换上下两个区的内容，因为当前在下区的块很可能是“常用块”。伪命中情况下,需要增加2个额外的,时钟,周期（其中1个周期是多找1次花去的，1个周期是交换操作所需）。,(5)伪相联的缺点：,它的多种命中时间使得,CPU,流水线上各指令之间的时间对齐变得困难，所以往往应用在离,CPU,比较远的,Cache,上，比如,L2-Cache。,7.3.5,伪相联（续2,）,2014.2.17,47,计算机系统结构,7.3.5,伪相联（续3,）,折中方案：伪相联（2路）,，,目录表法（,P209）,2014.2.17,48,计算机系统结构,例7.3.5（补充，2版,P198,例5.6）,一个伪相联,Cache,，当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据（伪命中）时需要增加2个额外的周期。其它已知条件如下表所示。,(1)推导伪相联平均访存时间公式；,(2)当,Cache,容量分别为2,KB,和128,KB,时，直接映象、两路组相联和伪相联这三种组织结构中，哪一种,的平均访存时间最短,？,7.3.5,伪相联（续4,）,2014.2.17,49,计算机系统结构,解：,(1)首先按通用形式写出伪相联的平均访存时间公式：,平均访存时间,伪相联,平均命中时间,伪相联,不命中率,伪相联,不命中开销,伪相联,然后根据伪相联原理，可以写出其中的：,平均命中时间,伪相联,命中时间,1路,伪命中率,伪相联,2周期,由于伪相联不命中时，就是2个候选位置都不命中，所以：,不命中率,伪相联,不命中率,2路,又由于伪相联的2个候选位置命中率之和等于2路组相联，所以：,伪命中率,伪相联,命中率,2路,命中率,1路,(1不命中率,2路,)(1不命中率,1路,),不命中率,1路,不命中率,2路,7.3.5,伪相联（续5,）,2014.2.17,50,计算机系统结构,将后3式依次向前代入，得到所需公式：,平均访存时间,伪相联,命中时间,1路,(不命中率,1路,不命中率,2路,)2周期,不命中率,2路,不命中开销,1路,(2)当,Cache,容量为2,KB,时：,平均访存时间,1路,1.0,0.09850,5.90,平均访存时间,2路,1.1,0.07650,4.90,平均访存时间,伪相联，2,KB,1.0(0.0980.076)2(0.07650)4.844,当,Cache,容量为128,KB,时：,平均访存时间,1路,1.0,0.01050,1.50,平均访存时间,2路,1.1,0.00750,1.45,平均访存时间,伪相联，128,KB,1.0(0.0100.007)2(0.00750)1.356,可见，对于这两种,Cache,容量，伪相联,Cache,都是速度最快的。,7.3.5,伪相联（续6,）,2014.2.17,51,计算机系统结构,结论：,从,不命中,率看，,F,2路,=,F,伪相联,F,1路,，伪相联因不命中带来的平均延时与2路一样短（1路较长）；,从命中时间看，伪相联在正常命中时与1路一样短（2路较长），伪命中时要增加2拍，后者概率=,H,2,路,H,1,路,。这种情况下1路要增加50拍。,代入2,KB、128KB,容量的数据，算出平均访存时间,T,A,都是伪相联最短。,缺点：多种命中时间,习题：7.11,7.3.5,伪相联（续7,）,2014.2.17,52,计算机系统结构,各次作业应交的内容,作业,9,（第10次课）,7.11,2014.2.17,53,计算机系统结构,衡量访存时间是否合适的主要标准是处理机速度，具体说是处理机分配来读/写存储器的时间长短。处理机速度越高要求访存时间越短。,衡量处理机速度的常用标准是,CPI，,因为它与程序执行时间成正比。,对顺序执行的处理机，,CPI,定义为每条指令执行所需的平均周期数。对流水执行的处理机，,CPI,定义为相邻两条指令启动时间相差的平均周期数。我们现在只关心流水处理机。,下图说明访存等待（不命中）会延长,瞬时,CPI,。,7.2.7 访存时间对,CPU,性能的影响1（,P203）,IF,ID,EX,Mem,WB,stall,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,CPI=1,CPI=2,2014.2.17,54,计算机系统结构,所以,在计算,平均,CPI,时，应该加上存储器平均“不命中开销”。,本章仅考虑存储器等待在平均,CPI,计算中的作用，暂时不考虑流水线因相关、冲突导致的延迟，所以上式简化写为,又被称为,以下是计算二者关系的几组常用公式。,7.2.7 访存时间对,CPU,性能的影响2,2014.2.17,55,计算机系统结构,(1)第,i,级的不命中率：,特殊地，,F,1,又可以记为,F，,因为,M,1,被访问次数就是,CPU,的总访存次数。,(2),存储系统的平均访问时间（从,CPU,看）：,其中,H,1,H,n,是来自互斥事件的完备群，它们满足关系式：,注意该公式忽略了各级之间的传送时间。,(3),第,i,级的平均访问时间：,其中,T,i,是第,i,级的命中时间，,T,Mi,是第,i,级的失效开销时间。,7.2.7 访存时间对,CPU,性能的影响3,2014.2.17,56,计算机系统结构,(4)程序执行时间（即“,CPU,时间”）：,a.,b.,c.,d.(7.3),e.(7.1),f.(7.2),g.,7.2.7 访存时间对,CPU,性能的影响4,2014.2.17,57,计算机系统结构,例7.1（,P204）,假设,Cache,不命中开销为,50,个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是,2.0,个时钟周期，访问,Cache,不命中率为,2%,，平均每条指令访存,1.33,次。,比较有,Cache,与无,Cache,情况下的,CPU,时间。,解：,已知,T,A1,=2.0，,即理想,CPI,=2.0，T,A2,=50，F=2%，,平均每条指令访存1.33次,CPU,时间,有,cache,IC,（,CPI,execution,每条指令的平均访存次数,不命中率不命中开销）时钟周期时间,IC（2.01.332%50）,时钟周期时间,IC 3.33,时钟周期时间,从此式知，实际,CPI,2.01.332%50,3.33,，,是理想情况下的3.33/2.0,1.67(倍)，,换言之，,CPU,时间,是理想情况下的,1.67,倍。,若不采用,Cache，,则每次访存增加,50,个时钟周期，每条指令的周期数为：,CPI,无,cache,2.01.3350,68.5,，,是理想情况下的,68.5,/,2.0,34.25,倍！,2014.2.17,58,计算机系统结构,例7.2（,P204）,考虑两种不同组织结构的,Cache：,直接映象,Cache,和两路组相联,Cache，,(1)理想,Cache（,命中率为,100%,）情况下的,CPI,为,2.0,，时钟周期为,2,ns,，,平均每条指令访存,1.3,次；,(2)两种,Cache,容量均为,64,KB,，,块大小都是,32,B；,(3)在组相联,Cache,中，,由于多路选择器的存在而使,CPU,的时钟周期增加到原来的,1.10,倍。这是因为对,Cache,的访问总是处于关键路径上，对,CPU,的时钟周期有直接的影响；,(4)这两种结构,Cache,的不命中开销都是,70,ns,（,在实际应用中，应取整为整数个时钟周期）；,(5)命中时间为,1,个时钟周期，,64,KB,直接映象,Cache,的不命中率为,1.4%,，相同容量的两路组相联,Cache,的不命中率为,1.0%,。,分别比较它们的平均访存时间、,CPU,时间。,2014.2.17,59,计算机系统结构,例7.2（续1,）,解：,摘要：理想,CPI=2，,不命中,开销=70,ns,，,每条指令访存,1.3,次,，F,直接,=1.4%，,F,组,=1.0%，,Cycle,直接,=2,ns，Cycle,组,=2.2,ns。,比较直接映象,Cache（,即1路）与2路组相联,Cache,的平均访存时间、,CPU,时间。,(1)平均访存时间为：,平均访存时间命中时间不命中率不命中开销,因此，两种结构的平均访存时间分别是：,平均访存时间,1路,2.0（0.01470）2.98,ns,平均访存时间,2路,2.01.10（0.01070）2.90,ns,两路组相联,Cache,的平均访存时间短一些。,2014.2.17,60,计算机系统结构,例7.2（续2,）,(2),CPU,时间,IC,（,CPI,execution,每条指令的平均访存次数,不命中率不命中开销）时钟周期时间,IC,（,CPI,execution,时钟周期时间每条指令的,平均访存次数不命中率不命中开销时钟周期时间）,代入参数得：,CPU,时间,1路,IC,(2.0,2(1.3,0.014,70)5.27,IC,CPU,时间,2路,IC,(2.0,2,1.10(1.3,0.010,70)5.31,IC,直接映象,Cache,的,CPU,时间短一些。,5.31,IC,CPU,时间,1路,1.01,5.27,IC,CPU,时间,2路,2014.2.17,61,计算机系统结构,欲设计一个,L2-Cache，,已知它的不命中开销,L2,50,个时钟周期，问下列两种映像方式对不命中开销有何影响。,(1),L2-Cache,采用直接相联，局部不命中率,L2,25%,，命中时间,L2,10,个时钟周期；,(2),L2-Cache,采用两路组相联，局部不命中率,L2,20%,，命中时间,L2,10.1,个时钟周期。,解：,（此例与,P204,的例7.2参数相似，注意区别）,题目已经给出了,L2-Cache,恒定的“,不命中开销,L2,”，那么,它的不同映像方式影响的只能是,L1-Cache,的,不命中开销，根据多级存储层次原理，,T,M1,M2,的平均访问时间。所以本题实质上是问哪种映像方式下,L2-Cache,的平均访问时间较小。,另外，在不使用,L3-Cache,情况下，“不命中开销,L2,50,个时钟周期”意思是“主存平均访问时间,50,个时钟周期”。,例,7.4,（,P216）,2014.2.17,62,计算机系统结构,(1),L2-Cache,采用直接,相联,平均访问时间,10.025%50,22.5,个时钟周期,(2),L2-Cache,采用两路组相联,平均访问时间,10.120%50,20.1,个时钟周期,(3)两路组相联的,命中时间之所以比,直接,相联,增加,0.1,个时钟周期，是因为虚实变换按组查表后要进行多路选择（,P199,图7.12和,P198,第8段），需要额外增加时间。具体实现方案可以把时钟周期调慢为1.01倍（这将使所有动作都减慢1%，甚至主存访问），或者仅在命中时增加1个时钟周期。,按,增加1个时钟周期的,方案，,L2-Cache,的命中时间为11，有：,平均访问时间,1120%50,21.0,个时钟周期,(2)(3)情况下,L2-Cache,的,平均访问时间,都比直接,相联,小，所以,L2-Cache,采用两路组相联性能更好。,注：教材中该例中说“幸运的话，取整为10个周期”，就是说,多路选择动作时间有可能“挤”进原有的10周期中，习题中通常不这样给条件,。,习题7.10,例,7.4,（续,）,2014.2.17,63,计算机系统结构,各次作业应交的内容,作业,10,（第11次课）,7.