《计算机体系结构》PPT课件.ppt

《《计算机体系结构》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《计算机体系结构》PPT课件.ppt（66页珍藏版）》请在三一办公上搜索。

1、4通道（CH）一、CH的基本工作原理 CH执行CH程序的过程 CH的任务二、CH流量计算和时空图绘制 CH的类型 CH流量计算 字节多路CH响应处理时空图的绘制1）计算每个子CH提供一个字节时间（1/f）2）画出一个完整申请周期时空图3）计算字节多路CH对每个字节响应的最长用时,子CH 5 4 3 2 1 0 10 20 30 40 50 60 70 80 90 100 t(s),等待5s,第四章 存贮体系1 引言,一、存贮体系原理1 存贮器的参数不足1）容量不足的解决办法 直接增加主存容量（S）这种办法从第一代到现在都采用，但只有此法不够，因此法随容量S增加，总价格C总，C位不变，用 此法不

2、能使C位，因而不可能提高性能价格比。,采用两级存贮器 利用低价格的辅存扩充存贮容量，三种信息：活跃的信息，即当前正在使用的；待命的信息，将要使用的；静止的信息，已被使用而不再处理。可将活跃的和部分待 命的信息放在主存，其余放在辅存，以减少主存容量的要求，从而可降低C位。在采用两级存贮器后，主辅存之间的信息调出与调进的问题。）由程序员考虑和安排增加了程序员的负担。）用辅助机构自动定位，从而引出了虚拟存贮器。,虚拟存贮器 将高速辅存（如磁盘）伪装成主存访问，信息在主存、辅存之间的调进（与调出）完全由辅助机构自动完成，象这种将主存与辅存作为有机整体的存贮系统称为虚拟存贮器。2）速度不足存贮器的速度往

3、往是整个计算机系统速度的一个瓶颈。办法之一是直接提高主存速度，此法也在采用，但此法随存贮器速度的提高位价格 C位。在CPU和主存之间加入高速缓存（cache）。,CPU,主存,cache,让CPU直接面对与它的速度相匹配的cache访问，此法也需要在CPU与cache之间利用辅助机构完成cache与主存之间的信息调进调出，cache与主存作为一个有机整体，这也是一种存贮体系结构，称C-主存体系。2 存贮体系中的辅助机构功能1）地址映象功能：解决将M2中的信息采用何种规则调入到M1中（即调入规则问题）。CPUM1M22）地址变换功能：根据映象规则，如何将包括M2在内的大空间的地址变换为CPU能直

4、接访问的M1中的地址（即地址变换问题）。3）替换算法功能：在M1中装满信息的条件下，采用何种算法，算出调出M1的部分信息，使M2中的部分能调到M1中（即替换算法问题）。,3 存贮器中的有关术语1）存贮器：凡是能存放信息的记忆装置，称存贮器。2）存贮系统：要有两种或两以上的存贮器，才能称存贮系统，如主存与辅存。3）存贮体系：只有将两（多）种不同的存贮器作为一个有机整体的存贮系统，才能称为存贮体系。4）存贮体系的两个分支虚拟存贮器，为扩充主存容量。Cache-主存体系，为提高访问速度。存储系统 存储体系 存储器 虚存 C-主,4 对存贮体系的基本要求 1）容量S：S2 S1（有足够的扩充空间）2）

5、存取周期tm：tm1 tm2（提高访问速度）3）位价格C位：C位2 C位1（才能降低C总，提高性能价格比）二、存贮器中的页式管理1 页的概念 页式管理中将虚拟存贮空间和实际存贮空间等分成固定大小的页，使虚拟页可装入主存中不同的实际页面位置。,2 页式管理的地址表示1）虚地址（逻辑地址，程序地址）：包括M2在内的大空间地址。NvNr Nv：虚页号 Nr：页内地址2）实地址（物理地址）：为CPU能直接访问的M1中的地址。nvnr nv：实页号 nr：页内地址,3 页表 1）页表所需行数与虚页号数相等，虚页号与页表行号对应，因此无需虚页号字段。2）页表中每行内容可认为两个字段：实页号nv及装入位（1

6、位），0表示虚页未装入，1表示已装入。,4 页式管理的地址变换 1）根据Nv去查页表中的某一行m。2）查该行的装入位。3）装入位=1时，命中。表示该虚页已装入。从该行中送出nv（实页号）。再将Nr直送nr，即完成NvNr nv nr。4）装入位=0时，失效，表示 该虚页未装入M1中。,实页号 装入位,0 1 2 3 4 5 6 7,5 页式管理中的表层次结构1）产生页表层次的条件 当用一页放不下页表时，就要用两页或两个以上的页面来放页表，此时会出现页表层次结构。2）页表层次的计算 设 虚页面数为2N，页面容量（大小）2P 则 页表层次数=N/P 如：某虚存空间有220个虚页面，页面容量 512

7、=29个单元 则 页面层次数=20/9=3,3）计算每层表的单元数底层表页的单元数与虚页面数2n=220相等，即220行。再计算底层页表号占多少页面：22029=211个页面中层页表单元数与底层页表页面数相等，即211行，而中层又占用多少页面：21129=22个页面上层页表单元数与中层页表的页面数相等22行。4）画出各层页表层次结构示意图。,上层(22行)0 1 2 511 0 1 2 511 0 1 2 511 0 1 2 511 中层(2n行4页)底层(220行 211页)0 1 211-1总页面单元数：220+211+22,5）设所有页面数都放在主存，计算从查表开始 到最后实现访问所需时

8、间为：访存次数*tm=（表层次数+1）*tm=（N/P+1）*tm 访最后的数据信息三、并行主存系统1 定义：凡在一个存取周期之内，能向CPU提供多个字的存贮系统都可称为并行主存系统。2 实现方法1）单体多字结构 利用增加一个单元中的字数来实现，只需增加存贮器中的数据线而地址线可不增加，且控制难度并未增加，但对同时取出的多个字的利用不一定充分。,2）多体单字结构利用增加独立的存贮体数来实现，每个体内的数据线未增加，但增加了控制复杂度和地址线数。如：4K字（每字32位）单体多字 可用1K单元，每单元4字，则地址线10条（210=1K），数据线32条*4=128条。多体单字每个体内数据线32条，4

9、个体共128条，但地址线要12条（212=4K）。,3）多体多字结构 将上述1）、2）两结构组合而成，控制难度大，但每个tm向CPU提供的字最多，不过也存在对同 时取出的字利用不一定充分的问题。3 多体单字的编址方式（设有4个体，每个体1K单元）1）体内连续编址（基本不用）,特点：编址容易，控制方便；由于指令执行时，顺序执行的情况较多，上条指令与下一条指令往往来自同一个体，因而在一个tm时间内，不能向CPU提供2条或2条以上指令。2）体内断续，体间连续（流水线技术在存贮器中的应用）。,1 某辅存共8个页面，每页1024字，实际主存为4096字，采用页表法进行地址映象，映象表内容如下表所示：1）

10、列出会发生页面失效的全部虚页号。2）列出命中页面的全部虚页号。3）以下地址计算主存实地址：0，3728，1023，1024，2055，7800，4096，6800。,1 解：失效的虚页号：2、3、5、7。命中的虚页号：0、1、4、6。查地址 Nv Nr nv 实地址 装入位 命中否0 0 0 3 3072 1 命中3728 3 656 3 3728 0 失效1023 0 1023 3 4095 1 命中1024 1 0 1 1024 1 命中2055 2 7 2 2055 0 失效7800 7 632 0 632 0 失效4096 4 0 2 2048 1 命中6800 6 656 0 656

11、 1 命中,虚页,01234567,存贮器的参数不足:容量不足=虚拟存贮器 速度不足=C-主存体系存贮体系中的辅助机构功能:地址映象功能 地址变换功能 替换算法功能存贮器中的页式管理:页式管理的地址变换 虚地址=实地址变换 虚地址=页式虚地址=页式实地址=实地址 页表层次的计算,2地址映象及其变换 有四种映象规则：全相联、直接、组相联和段相联，为便于介绍以主、辅存体系为例。一、全相联映象及其变换1 含义：对辅存中的任何一个页面都可以放到主存中的任何一个页面上的映象规则，称全相联映象。2 映象规则示意图 NV辅 主nV,3 地址变换 1)地址表示 2)全相联页表法。与前面介绍的页式管理中的地址变

12、换过程相同。,Nv Nr,nv nr,虚地址,实地址,3）全相联目录表法 要求用相联存贮器作目录表（相联存贮器是一种 可按内容的特征字段来访问的一种存贮器）。目录表的行数与主存页面数相等（本例四行）。目录表中每行的内容：）NV为相联比较字段；）nV为主存页号（非相联比较字段）。,地址变换过程）将虚地址中的NV送目录表中去进行相联比较（一个tm）。）当有某个比较器比较相等时，将该行nV送出，同时Nrnr，实现了NvNrnvnr的变换（命中）.）若设有相等的，不命中，等待调入。这种办法，可降低表的容量，但要求有相联存贮器，（目录表的行数与主存页数相等）。4 特点：1）产生页面冲突的可能性极小；2）

13、不能实现查表与访存同时进行，不利于访问速度提高。,二、直接映象及其变换 含义：先将辅存按主存大小分为若干块，在辅存的每块内都有与主存相同的页面数，辅存每块内的页面只能调入到与主存相同的页面上的映象规则称直接映象。映象示意图 d：块号 Nv：块内页号,3 地址变换1）地址表示2）块表块表长度与主存页面数相等（本例四行）。块表行中的内容：块号d。3）地址变换过程根据Nv去查块表中的Nv行；将虚地址中的块号d与所选块表中的d比较；比较相同时命中，直接将Nvnv，Nrnr。比较不相同时，不命中。,4 特点1）可将查表与访问同时进行，有利于访问速度的提高（命中时）。2）产生页面冲突的可能性极大（因无灵活

14、的存放余地）。三、组相联映象及其变换 1 含义：先将主存分为页面数相同的若干组，再将辅存按主存划分为若干区，组内采用全相联映象，组间采用直接映象。,2 示意图其中：Nd区号 q 组号 s 组内页号辅存 q组号 s组内页号主存,3 地址变换过程1）地址表示辅（虚）Nd q s Nr主（实）q s nr,2）随机存贮器表表的行数与组数相等（本例2组，即2行）。每行大字段数与组内页面数相等（本例2个）。每个大字段又分为三个小字段。Nd：区号；s：组内页号；s：主存组内页号。每个大字段还有一个比较器。,3）地址变换过程根据虚地址中的q去查随机存贮器表中的某一行。将虚地址中的Nd、s同时送各比较器与所选

15、行中的Nd、s进行比较。当有一个比较器相等时：）将qq（组间直接）。）将相等大字段中S送出作S。）再将Nrnr,即实现了将虚址Nd q s Nr qsnr命中时的地址变换。4.特点：即有直接映象中对号入座部分(组间直接)，可减少查表范围，缩短查表时间，又有全相联中的灵活存放规则(组内全相联)，从而可降低页面冲突。但控制机构复杂。,组间直接映象Nd q s qs0 0 0 0 0 0 1 组内全相联映象,四、段相联映象简介 对主辅的划分与组相联映象相同，但为区分两种不同的映象规则，将组相联中的组改为段，段间采用全相联，段内采用直接映象。,段间全相联 可映象Nd q s qs0 0 0 0 0 1

16、 0 段内直接映象,五、四种映象规则关系1）在组相联映象中，当每组只有一页时，此时的组相联就是直接映象。当把主存只分为一个组时，此时的组相联也就是全相联映象，即直接映象和全相联映象是组相联映象的两个特例。2）在段相联映象中，当每段只有一页时，此时的段相联映象就是全相联映象。当把主存只分为一个段时，此时的段相联也就是直接映象。,3 替换算法及其实现一、概述（以主辅存页式管理）1 含义：在主存装满页面时，采用何种算法，计算出主存中的被替换页面，以便辅存中的页面能调入到主存，为此而采用的算法称替换算法。2 对替换算法的评价 1）要利于实现，某种算法其命中率很高，但它实现 不了，因此不能采用。2）要保

17、证有一定的命中率，某种算法很好实现，但命中率无保证，因而不能采用。3 为保证一定的命中率，对被替换页面的要求：1）以后不再使用的页面，（很难确定以后是否不会使用，除非固定页面地址流）。2）都要使用时，先替换最后使用的页面。3）替换最久没有使用的页面（可以统计出来）。,4 有哪些替换算法 1）随机替换算法（利用随机函数发生器产生一个被替换页面号）。不能反映程序的局部性，命中率低。2）FIFO替换算法：最早进入实存的页替换出去，出现了“历史”信息，但并没能正确反映程序的局部性。3）LRU替换算法：近期最少使用（Least Recently Used），替换最久未被使用的页面。4）OPT优化替换算法

18、：是一种理想的算法，实现不了，只能作为衡量其它算法优劣的标 准。,二、地址流，算法，调进替换页面变化时空图1 第一组地址流A：2,3,2,1,5,2,4,5,3,2,5,2 1）几个符号 i：调入第i页；i：第i页命中(已在主存中的页面，重新被使用称命中)i#：第i页将被替换 i：在主存中的普通页面 n：主存页面数。2）分别写出FIFO、LRU、OPT随时间推移页面变化示意图（设n=3，主存开始为空）。3）计算命中率H。H=命中页数/访问时间,第二种地址流A:1,2,3,4,1,2,5,1,2,3,4,5 分析n对H的影响：n=3与4。,2地址映象及其变换四种映象规则及地址变换：全相联映象：页

19、表、目录表直接映象：块表组相联和段相联：随机存贮器表3 替换算法及其实现FIFO、LRU、OPT上述算法在给定地址流及主存页面数下页面变化时空图主存页面数n的大小对命中率的影响,3 堆栈型替换算法1）两个符号 Lt:某题目,随时间t推移所出现过的不同页面数.L1=1,L2=2,L12=5。Bt(n):在t时刻，某算法在所分配的n个页面中，当前的页面集。如FIFO：B3(3)=1,2,3 B7(4)=5,2,3,42)定义：当页面nLt时，Bt(n)=Bt(n+1)当页面nLt时，Bt(n)Bt(n+1)凡是同时满足上述两条件的算法都可称为堆栈型算法。,3）哪些替换算法属于堆栈型算法 FIFO:

20、不属于 B7(3)B7(4)LRU:属于 OPT:属于 4）堆栈型算法的意义：可利用堆栈技术，真实模拟LRU在不同n条件下页面变化时空图及命中率。调入的页面放入栈顶，栈中其余页面均向栈底方向移动一个单元。处于栈中的页面命中时，将它从栈中抽出放在栈顶，处于它之上的页面同时向栈底挪动一个单元。,例：也用上次的第二组地址流模拟n=3、4、5，此外，用3行分别描述命中页。,1,2,三、LRU算法的实现1 堆栈法1）设置，需要有一定容量的堆栈。2）替换页面的条件，处于栈底的页面将被替换。3）堆栈功能要求：相联比较；全下移及部分下移；从中间取出一项。4）用处 当采用存贮器堆栈时，用于主-辅存体系中；当采用

21、寄存器堆栈时，用于C-主体系中。,2 比较对法1）设置，每两个页面设一个比较对触发器，比较对触 发器的数目N与页面数P的关系：N=P*（P-1）/2 如P=3时，N=3，即有A、B、C三个页面，触发器 为TAB、TAC、TBC。(左置0，右置1）2）记录页面使用状况,3）页面替换条件 A页替换条件 ALKU=TAB*TAC B页替换条件 BLKU=TAB*TBC C页替换条件 CLKU=TAC*TBC4）页面替换电路 触发器左输入端置0，触发器右输入端置1 TAB表示Q端的状态 5）用处：电路简单，速度快，在页面数不多的 条件下，替换条件形成快，可用于 C-主体 系中。,4 存贮体系的两个分支

22、一、虚拟存贮器1 含义：将高速辅存伪装成主存来访问的一种体系结 构，称虚拟存贮器，在主辅存之间的信息调进与调出都由辅助机构自动完成。2 主要结构1）主存，是CPU直接访问的存贮器。2）辅存：用来扩充访存空间。3）地址寄存器（以页式管理为例）。虚地址寄存器，存放虚地址；实地址寄存器，存放实地址。4）页表机构（按映象规则安排）内页表，页面放在主存中的页表。外页表，页面放在辅存中的页表。,5）替换算法机构 页面满否判别机构及LRU替换算法机构 6）I/O通道用来实现主辅存之间的页面交换。3 虚拟存贮器的简单工作过程 1）用虚地址中的NV去查内页表，并检查相应页表行中 装入位；2）当装入位=1时，表示

23、该页已在主存。从该页表行中送出nV；再将Nrnr；即完成命中时的NV Nrnv nr。3）用变换好的nv nr实地址访问主存；4）当装入位=0时，表示不命中。此时要产生失页中断，CPU也要响应此失页中断，且可在指令执行途中响应，若为多用户系统时还要产 生用户切换。,5）再用Nv去查外页表，并查出该页在辅存中的位置。6）查主存装满页面否？7）当主存页面未满时（主存有空页），将辅存页面经 I/O通道调入到主存的页面上。8）当主存已装满时，利用LRU替换算法机构算出调出 主存的页面号。9）再将辅存页面经I/O通道调入到主存被替换的页面上。注：通常主存中的页面是辅存中某些页面的副本，但当它从辅存调到主

24、存时，若有修改，且需保存修改，还应先将被替换的页面经I/O通道调回到辅存保存，然后再调入。4 性能评价除命中率H外，还有存贮空间利用率：=(Ss-Su)/Ss其中Ss：分配给某用户的所有存贮单元数；Su：开销，包括所有页表单元数及最后一页未用完的零头，通常用1/2页面容量Sp表示。,例：某虚存空间共有220个虚页面，页面容量Sp=512，若某用户占据整个虚存空间，采用页式管理，全部页表均在主存，计算存贮空间利用率。解：Ss=220512=229 Su=220+(22029)+(22029)29+Sp/2=220+211+22+28=(Ss-Su)/Ss=229-(220+211+22+28)2

25、29 511/512,二、Cache主存体系1.与虚拟存储器相同之处1）都属于存储体系结构。2）都有地址映象及其变换机构。3）都有替换算法机构，且都采用LRU算法。4）都要求有高的命中率H。2.不同之处,3.tA的计算 tA=H*tc+(1-H)*tm tc：访问cache的时间 tm：访问主存的时间,6 解：1）,主存,Cache,2）,01234567,主存页号,1位 1位 1位,1位 1位,3)可放入Cache 0组的主存块号:0 1 4 5 可放入Cache 1组的主存块号:2 3 6 7,t 块流,失 失 失 中 失 失 失 中 失 争 争 失 中 失 争,4)块失效:凡是不命中都属

26、于失效;块争用:换出了不该换出的页面.所以:即失效又争用的时刻是:t10,t11及t155)tA=H*tc+(1-H)*tm=0.2*2+0.8*15=12.4(ns)李学干：,例1 考虑一个920个字的程序，其访问辅存的地址流为20，22，208，214，146，618，370，490，492，868，916，728。(1)若页面大小为200字，主存容量为400字，采用FIFO替换算法，请按访存的各个时刻，写出其虚页地址流，计算主存的命中率；(2)若页面大小改为100字，再做一遍；(3)若页面大小改为400字，再做一遍；,解 虚页号虚地址页面大小(1)页面大小为200字，主存容量为400字，

27、可知主存页数为2页。其虚页地址流为 0，0，1，1，0，3，1，2，2，4，4，3 下图给出了采用FIFO替换算法替换时的实际装入和替换过程。其中，“#”标记的是候选替换的虚页页号，H表示命中。,虚地址虚页流,H=6/12=0.5,(2)页面大小为100字，主存容量为400字，可知主存页数为4页。其虚页地址流为 0，0，2，2，1，6，3，4，4，8，9，7 下图给出了采用FIFO替换算法的时空图。,虚地址虚页流,H=3/12=0.25,(3)页面大小为400字，主存容量为400字，可知主存页数为1页。其虚页地址流为 0，0，0，0，0，1，0，1，1，2，2，1 下图给出了采用FIFO替换算

28、法页面装入和替换过程。,虚地址虚页流,H=6/12=0.5,由(1)、(2)、(3)的结果可以看出，在分配给程序的实存容量一定(400字)的条件下，页面容量Sp过小时，命中率H较低；页面容量增大后，两个地址在同页内的机会增大，使命中率H有所上升，由于指令之间因远距离的跳转引起命中率H下降的因素不起主要作用，还未出现随页面容量增大，而使命中率H下降的情况。如果页地址流有大量的远距离转移，随页面容量增大，因在主存中的页面数过少，而导致出现虚存页面被轮流替换出去的“颠簸”现象时，命中率H反而会下降。,例2 用组相联映象的Cache存贮器，页的大小为28个单元，主存容量是Cache容量的4倍。映象表用

29、单体多字按地址访问存贮器构成，已装入内容如下表所示。用四套外比较电路实现组内相联查找块号。各字段用四进制编码表示。(1)给出四进制码表示的主存地址3122203，问主存该单元内容能否在Cache中找到。(2)给出四进制码表示的主存地址1210000及2310333，问主存该单元内容能否在Cache中找到。若能找到，指出相应的Cache地址。,分析 根据题意，主存容量是Cache容量的4倍，区号Nd字段为2位。页的大小为28个单元，Nr字段为8位。4套外比较电路实现组内相联查找块号，组内页号S字段为2位。映象表的行数为组数，所以，表中行号0、1、2、3，对应于组号q的取值，q为2位。可见，主存的

30、二进制地址各字段的划分和位数为：(2位)(2位)(2位)(8位)Cache的二进制地址各字段的划分和位数为：(2位)(2位)(8位),例2 解(1)由主存地址中的q1，到映象表中的第1行里去查各个Nd、S，在表中均未找到有Nd3、S2 的内容，所以主存的该页不在Cache中，发生Cache块失效，无物理Cache地址。(2)由主存地址(121000)4知：q2，在映象表的第2行中的最右面找到（命中）有Nd1、S1、S=3 其Cache中物理单元的地址为 q=q=2,S=3,nr=0000 即：2*1024+3*256+0=2048+768=2816 由主存地址(2310333)4知：q=3，在映象表的第3行中的第3部分找到有Nd2、S1、S=1其Cache中物理单元的地址为q=3,S=1,nr=(0333)4即：3*1024+1*256+(333)4=3072+256+63=3391,