《计算机系统结构》电子教案.ppt
《《计算机系统结构》电子教案.ppt》由会员分享,可在线阅读,更多相关《《计算机系统结构》电子教案.ppt(94页珍藏版)》请在三一办公上搜索。
1、计算机系统结构,1,第7章 存储层次(P188)Memory Hirarchy,长期存在的问题:在合理的总价格限制下,单一型主存器件的速度跟不上CPU的发展,容量不能满足软件尺寸扩大。本章学习提高主存系统性能/价格比的几种结构化方法,重点是“Cache-主存层次”,焦点问题是如何使流水线每拍完成一次访存。本章基本公式:(1)平均时间 T=P1T1+P2T2其中 P1+P2=100%,并且 T1 和T2 都可以再用该式迭代展开,复杂时,可用概率树来表示(全概率公式);(2)实际时间 T=理想时间+P3 每次额外开销时间其中 P3 是不利事件发生概率。,计算机系统结构,2,7.1 存储层次原理及性
2、能指标(P188),7.1.1 基本原理“存储层次”的定义:(参见P189第3段)由2种或多种存储部件构成的复合存储系统,通过内部管理机构的自动更换机制,能够不断将大容量低速存储部件中的活跃内容复制到小容量高速存储部件中(后者作为前者的局部副本)。它既能满足CPU的快速存取需要,又有很大的存储容量,平均单位价格也很低,等效于同时满足3方面要求的理想单一存储部件。,依据:程序访问的局部化原理(时间局部化,空间局部化)。模型:如右图所示,存储层次由n层组成,满足3个不等式:TAici+1,SiSi+1。,计算机系统结构,3,存储层次的基本术语,逻辑地址(又称为相对地址、虚地址)是程序员在编写和编译
3、一个程序模块时分配指令和数据的空间单位序号,总是从0开始(可以按字节编址、按CPU字编址等)。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。物理地址(又称为绝对地址、实地址)是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。从M1到Mn各层都有自己的物理地址空间,而对当前执行的程序模块来说,逻辑地址空间只有一个。地址映象方式指的是虚页集合与实页集合的对应规则,或者说是约束关系。地址变换(又叫虚实变换)指逻辑地址到物理地址的变换过程或者算法。页失效指当前被访问存储级中没有所需的信息,也就是不命中现象。实页争用又叫实页冲突,指虚页调入时,根据地址映象方式
4、划定的实空间范围内已没有空闲实页的状况。页和块:前者用于主-辅层次,后者用于Cache-主存层次,意义相同。,计算机系统结构,4,存储层次的管理方式(P230),根据程序的局部化性质,存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同,存在3种存储层次管理方式。目前在主存辅存层次实现中,具体机器可能采用3种方式中的某1种,而Cache-主存层次普遍只采用第2种,因为它简单,便于硬件实现。(1)段式管理。段是程序中的一个逻辑单位,可以是一个程序模块,或者是一个数据结构。段的长度不一,但段内所有数据的信息属性一般是相同的,便于统一进行信息保护。每段使用独立的逻辑地址空间
5、,即都从0开始计算地址。段式管理方法的主要缺点是各段长短不一,调进调出之后容易形成大量不规则的零碎空间。段式管理方法的虚实变换算法是查段表。因其实现较复杂,仅用于主存辅存层次。,计算机系统结构,5,存储层次的管理方式(续),(2)页式管理。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。我们把用户文件划分得到的一个长度单位称为“虚页”,因为它的页号是在虚地址空间中编排的;实地址空间按页的大小划分得到的一个长度单位称为“实页”。页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息,不便于信息保护的实现。页式管理方法的虚实变换算法是查页表。两种层次都用此技术。
6、(3)段页式管理。它把上述两种管理方式结合起来,首先将整个文件分段,然后在各段内分页,所以有一个段表和若干个页表。其虚实变换算法是先查段表,查出该段的页表起始地址再查相应的页表。段页式管理的主要缺点是多查一次表,虚实变换费时较多,占用空间也较大。它的实现最复杂,仅用于主存辅存层次。段页式管理方法的最小调度单位仍是页,基本操作可归于页式管理。,计算机系统结构,6,课堂练习7.1,一个页式虚拟存储器按字节编址,页面大小为1K字节,每个数据的字长为4个字节。现有一个程序的页表如下:,表中的装入标志为“1”表示该虚页已经装入主存,为“0”则表示还未装入主存。修改标志为“0”表示该页还没有被修改过,为“
7、1”则表示该页已经被修改过。访问方式“RW”表示该页可以读可以写,但不能作为指令来执行;“R”表示该页只能读,不能写和执行;“X”表示该页只能作为指令来执行,不能读和写。,计算机系统结构,7,课堂练习7.1(续),虚地址经变址寻址和基址寻址(B)+(X)+D形成。现有一个程序,出现下列访问主存的操作:,(1)列出产生主存页面失效的操作序号。(2)如果不发生主存页面失效的话,计算访问主存的物理地址。(3)列出非法操作的序号。(4)列出被修改过的主存页面号。,计算机系统结构,8,7.1.3“主辅”层次与“Cache主存”层次的对比,(P192表7.1,P231表7.7)“主存-辅存”层次目的:提高
8、等效容量。基本调度单位:页,几百Byte到几千Byte。速度比:几万倍。虚实转换:页表(以虚页号为索引)“Cache-主存”层次目的:提高等效速度。基本调度单位:块,几十Byte。速度比:几倍。虚实转换:目录表(以实页号为索引),计算机系统结构,9,存储层次的基本问题(P192),映象规则一个虚块(页)被允许放到哪些实块(页)上;查找算法如何在实存中找到指定的虚块(页)(主要是虚实变换);替换算法块(页)争用时,调出哪个虚块(页);写策略写存储层次的具体操作。典型存储层次(PC计算机,以Intel芯片组为例),计算机系统结构,10,存储层次的性能指标(P189),先以2级存储层次为例进行公式推
9、导,并且只考虑各级存储器件自身的操作,忽略控制机构的附加开销。多级层次以及附加开销留到以后讨论。(1)容量:S=S2(理论上)(2)单价:(美分/bit),计算机系统结构,11,(3)速度,表现访问速度的参数较多。命中率 H:被访问数据事先已在M1的概率 不命中率 F:不命中的概率,又称失效率,F=1-H 平均访存时间:命中时的访存时间为TA1,不命中时的访存时间为TA2,平均访存时间则是它们的概率均值其中TM是失效开销,TM=TA2+TB2,计算机系统结构,12,访问效率e(补充),访问效率 e 受 H 和 r 的影响(参见右图):,e 是一个相对值,便于不同系统之间的比较。,计算机系统结构
10、,13,假设:TAi表示第i级器件读/写时间;TBi表示第i级向上级传送时间。根据模型有:命中M1时:TA=TA1 命中M2时:TA=TA1+TA2+TB2 TA2 命中Mn时:TA=TA1+TA2+TB2+TAn+TBn Tan区别:单次访问总时间近似等于本次到达的最低一层的访问时间,因为每层都只访问一次;大量访问的平均时间则由各层访问时间共同构成,因为较高层的一次访问时间虽短,但它们被访问的百分比远远大于较低层。,多级存储层次的单次访问时间,计算机系统结构,14,课堂练习7.2,设计“Cache-主存”层次,Cache的容量有三种选择,如上表所示。忽略平均访存时间TA公式中的TB。(1)分
11、别计算三种方案的等效访问时间;(2)分别计算三种方案每KB的平均价格;(3)分别根据等效访问时间、每KB的平均价格排序;(4)根据等效访问时间和平均价格的乘积排序。,计算机系统结构,15,多级存储层次的平均访问时间1,M1 103B TA1=1us 103B M2 106B TA2=10usM3 109B TA3=100us 109B(a)(b),例7.0 有一个109字节的程序被装入右图所示的M3准备运行。假定指令字长=1字节,程序中无转移指令和内存读/写指令。忽略传送时间TB。,(1)按图(a)求TA和e;(2)按图(b)推导三层体系的TA公式;(3)按图(b)求TA和e;(4)比较(1)
12、(3)结果,有何结论?解:,计算机系统结构,16,多级存储层次的平均访问时间2,由这2式合并得 此公式参见教材P214倒数第12行。,计算机系统结构,17,多级存储层次的平均访问时间3,(4)结论:插入中间层后,层间速度差减少,访问效率提高。,计算机系统结构,18,(1)问中,为什么?答:每当CPU访问M1不命中时,存储系统会从M3装入1000字节到M1,再从M1取1个字节送给CPU,所以本次访问结果为“失效”,但是紧接着的999次访问将“命中”,以后又是如此重复,。同学们不要把访问“失效”理解为访问“失败”,认为CPU在M1找不到数据就会放弃本次访问。“失效”的定义是经过等待后完成的访问,而
13、“命中”是不需要等待即完成的访问,仅此不同。(3)问中,为什么?答:M2接受M1的数据请求,每次是1000字节。M2的初始状态为“空”,对于M1的首次请求不能立即满足,需要先从M3索取1000000字节数据填满自己,再向M1提供所要的1000字节数据。这次访问称为“失效”。此后M1向M2发出的999次请求都能立即响应,而再下一次请求又需要等待。如此重复,所以H2=999/1000。,例题说明:,计算机系统结构,19,刚才推导中使用的不命中率都是局部不命中率。为了避免混淆,有必要分清两种不命中率:全局不命中率是一个比局部不命中率更有意义的指标,它指出了在CPU发出的所有访存请求中,究竟有多大比例
14、是穿过该级,到达下一级存储器的。,局部不命中率与全局不命中率(P214),计算机系统结构,20,因为:所以:依此类推,,局部不命中率与全局不命中率(续),计算机系统结构,21,多级存储层次的平均访问时间公式重写,将这些局部不命中率、全局不命中率的定义式代入到前面的多级存储层次平均访问时间公式中,我们可以得到更容易记忆的公式形式:,计算机系统结构,22,例7.3 考虑某一两级Cache:第一级Cache为L1,第二级Cache为L2。(1)假设在1000次访存中,Cache1的不命中是40次,Cache2的不命中是20次。求各种局部不命中率和全局不命中率;(2)假设Cache1的命中时间是1个时
15、钟周期,Cache2的命中时间是10个时钟周期,不命中开销是100时钟周期,平均每条指令访存1.5次,不考虑写操作的影响。问:平均访存时间是多少?每条指令的平均停顿时间(即失效开销)是多少个时钟周期?解:(1)第一级Cache的不命中率(全局和局部)是40/1000,即4%;第二级Cache的局部不命中率是20/40,即50%;第二级Cache的全局不命中率是20/1000,即2%。,例7.3,计算机系统结构,23,(2)TATA1F1(TA2F2TM2)14%(1050%100)14%603.4个时钟周期式中后面部分4%60为每次访存的平均停顿时间(即失效开销):每次访存的平均停顿时间(即失
16、效开销)4%602.4由于平均每条指令访存1.5次,所以:每条指令的平均停顿时间2.41.53.6个时钟周期习题7.9,例7.3(续),计算机系统结构,24,各次作业应交的内容,作业8(第9次课),7.9,计算机系统结构,25,地址映象问题的提出,1.页表占用空间过大问题页表必须存放在实存M1里。实际上,命中情况下的访存时间等于查表时间加上访问目标数据的时间,所以页表不能放在M2。页表占用空间=页表行数 每行宽度其中,页表行数=虚存容量/页面大小以Win2K为例,虚存页表=4 4G/4K=22 232/212=222=4MBCache-主存层次的页表=4 4G/16=230=1GB,而Cach
17、e1只有32K减少页表空间的思路分减少行数和减少行宽两类。2.相联目录表方法(又称“实页表”)/减少行数仅保留页表中已装入的虚页记录。为避免逐行比对,利用相联存储器存放此表,它具有并行比较功能,但价格远高于普通存储器。P196图7.10示意Cache中用多字并行比较方法实现的相联目录表。此法须严格限制字数。3.快慢表方法(TLB)/减少行数4.改变地址映象/减少行宽,计算机系统结构,26,四种常见的地址映象方式(P193),(1)全相联(fully associative)全相联就是无约束对应,或者说是一个完全关系,意思就是一个虚页可以调入任何一个实页。这种关系可用下页示意图(a)、(b)表示
18、。全相联的虚实变换信息完全来自于变换表,查表过程如图(c)所示。全相联映象方式使虚页调入有最大的选择范围,发生实页争用的可能性最小,调入/调出的操作开销也最少,有利于命中率提高。但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高,在命中情况下花费在虚实变换上的时间也比较多。由于页表必须常驻在实存中,而主存-辅存层次的实存(即主存)相对Cache-主存层次的实存(即Cache存储器)容量大得多,所以全相联映象方式一般用于主存-辅存层次。一个虚页被允许进入的实页集合称为“候选位置”(P195),全相联的“候选位置”为整个实存。,计算机系统结构,27,全相联的地址映象方式与地址变
19、换原理示意图(a)(b),计算机系统结构,28,全相联的地址映象方式与地址变换原理示意图(c),计算机系统结构,29,(2)直接相联(direct mapped),直接相联是一种最强的约束关系,它规定每个虚页只对应唯一的实页。为了便于虚实变换,用求模运算作为变换关系式:将虚页号对实页总数求模得到实页号。实现起来非常简单,因为在二进制中,任何数X对2的整次幂n求模等价于截取X的最低log2n位,如下页示意图(c)所示。例5.2 已知虚页号=7,实页总数=4,用直接相联求实页号。解:可用十进制形式求:7 mod 4=3;也可用二进制形式求:由于n=4,所以log2n=2,取7的二进制形式111B的
20、最低2位,得11B,即3。直接相联映象方式不需要借助页表来进行虚实变换,显然大大节省了相应的空间与时间(当然页表中的装入位和修改位还得保留),但是由于每个虚页的选择范围太小,实页争用的发生频率较高,常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况,这使系统的命中率和运行效率下降。这种映象方式主要用于对实存价格、速度敏感的Cache-主存层次。直接相联的“候选位置”为1个实页,它又被简称为“1路Cache”。,计算机系统结构,30,直接相联的地址映象方式与地址变换原理,计算机系统结构,31,(3)组相联(set associative,P194),组相联映象方式是全相联与直接
21、相联的一个折中方案,性能也是二者的折中。具体做法是先将实存分组,每组内有若干实页,然后将虚存空间也以同样大小分组。所有虚组按照直接相联方式映射到实组集合,对应的虚实组之间各页则用全相联映射,如下页示意图(a)、(b)所示(设实组数为2)。由于包含了两层不同的映射关系,页表须按虚组划分成许多子表。在虚实变换时,首先根据虚页号所在的虚组号,通过求模运算确定实组号,再按虚组号在相应的子表内读出组内页号,拼接在一起就是实页号。简记为“组号计算、组内查表”。如图(c)所示。采用组相联映象方式时,每个虚页在对应实组范围内有若干映象实页可供选择,实页争用的发生频率比直接相联要低;另一方面,由于页表内原来存放
22、的实页号改成存组内页号,省略了实组号字段,所以页表占用空间也减少了。当然这两方面优点是互相抵触的:组内页数越多,实存空间划分的组数就越少,实组号字段所占位数也少,这时改善实页争用现象的效果较好,而节省页表空间的效果较差,反之亦然。实际使用中可根据性能要求选取合适参数。这种映象方式性价比较好,在Cache-主存层次中被普遍使用。实组内页数被称为“路数”,又称为“相联度”(associativity),它表明一个虚页的选择范围。下页图示为2路组相联(2-way set associative)。,计算机系统结构,32,组相联的地址映象方式与地址变换原理(a)(b),组相联的“候选位置”为组内页数,
23、即“路数”。,计算机系统结构,33,组相联的地址映象方式与地址变换原理(c),计算机系统结构,34,(4)位选择组相联(P194图7.7c),位选择组相联映象方式映象关系中,实存分组,虚存按实组数分区,区内不分组。虚块号与实组号之间是直接映象关系,而虚块与该实组内的各个实块之间是全相联映象方式。例如,虚块0可以映象到实组0的任意一块中。在一般组相联映象方式中,一个虚组与一个实组之间是多个块到多个块的映象。而在位选择组相联映象方式中,改成了一个虚块到实组中多个块的映象。映象关系明显简单,实现起来可以容易些。另外,从数据的分布情况看。对于一般组相联映象方式,虚存中的几个连续块映象到实存中可能也是连
24、续的,而对于位选择组相联映象方式,虚存中的连续块映象到实存中肯定是不连续的,它们被分散到实存的各个组中。由于在虚存与实存之间是以块为单位进行调度的,而实存是以字为单位访问的,只要实存中的一个字不跨越两个块,在实存内部的块与块之间的分布是否连续对实存的正常工作是没有关系的。由于虚存每个区中的块数与实组数相等,而且它们之间采用直接映象方式,因此,虚存地址中的区内块号可以直接作为实组号。位选择组相联的地址变换过程比一般组相联映象方式简单,而与全相联映象方式基本相同。,计算机系统结构,35,位选择组相联的地址映象方式与地址变换原理(a)(b),计算机系统结构,36,位选择组相联的地址映象方式与地址变换
25、原理(c),计算机系统结构,37,(1)页表法每个虚页对应1项,虚页号就是项号,项内存储实页号,如课堂练习7.2。这种方法原理简单,但是占用空间非常大。当页表尺寸超过1页时,它本身还要按页面尺寸分割成许多分散存放的子表,再造一个“表上表”来找到当前需要的子表。进一步发展就会形成“多级页表”,导致虚实变换分多步进行,时间大大延长。,虚实变换基本方法(P195),计算机系统结构,38,(2)部分虚实表法(P195图7.8)这是一种统称,指表项数少于虚页数的情形,下面要介绍的3种方法都属于这一类。(与Hash查表有点相似)表项数少于虚页数意味着查表时会有多个虚页查到表中同一项的情况发生,另外也意味着
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机系统结构 计算机系统 结构 电子 教案
链接地址:https://www.31ppt.com/p-5051858.html