计算机系统结构》电子教案

单击此处编辑母版标题样式,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次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间（