计算机系统结构 复件 复习.ppt

1、计算机系统结构复习,计算机系统结构（第二版）华中科技大学出版社,计算机系统结构（第二版)华中科技大学出版社,复习,一、考试方式笔试，开卷二、考试时间100分钟三、考试题型（1）填空题（2）单选题（3）判断题（4）名词解释（5）简答题（6）设计与计算题四、复习范围与重点,计算机系统结构（第二版)华中科技大学出版社,第1章计算机系统结构的基本概念,1、层次结构（P1）从计算机语言的角度，可将通用计算机系统划分成多级层次结构，每一层以一种不同的语言为特征。按由低层到高层的顺序，各层分别是：,微程序机器级传统机器语言机器级操作系统机器级汇编语言机器级高级语言机器级应用语言机器级,计算机系统结构（第二版

2、)华中科技大学出版社,2、透明性(P3)从计算机系统的某一层的使用者角度看，只需通过该层的语言就可以使用机器，而不必关心其下层的机器级是如何工作和如何实现对上层的支持。计算机系统的“透明”是看不到的意思，即对某一层的使用者来说，他看不到该层以下各层的机器属性。,计算机系统结构（第二版)华中科技大学出版社,12、并行性(P5)同一时刻或同一时间间隔内发生两种或两种以上性质相同或不相同的事件。13、同时性(P6)两个或多个事件在同一时刻发生。14、并发性(P6)两个或多个事件在同一时间间隔内发生。,计算机系统结构（第二版)华中科技大学出版社,15、提高计算机系统的并行性的3类技术途径(P6):时间

3、重叠资源重复资源共享,计算机系统结构（第二版)华中科技大学出版社,第2章指令系统,1、操作码编码的3种方法(P30)定长（等长）编码哈夫曼编码扩展编码2、定长编码(P30)所有指令的操作码长度都是相等的编码方法。如果需要编码的操作码有n个，定长操作码的位数最少需要位。,计算机系统结构（第二版)华中科技大学出版社,3、哈夫曼（Huffman）编码(P30):使用哈夫曼算法构造哈夫曼树来进行编码的编码方法。构造哈夫曼树的算法：从结点集中选择出2个频度最小的结点，将其合并成频度为这两个频度之和的父结点;若结点集不为空集，就将生成的新结点放到结点集中，继续从这个新的结点集中选择出2个频度最小的结点生成

4、其父结点;若结点集为空集，就生成了一棵哈夫曼树。对每个结点的两个分支分别用“0”和“1”标识.从根结点到一个叶结点的路径（由0和1组成的序列）就是这个叶结点的哈夫曼编码。,计算机系统结构（第二版)华中科技大学出版社,4、扩展编码的2种表示方法(P30)码长表示法:用短横线前后的数字分别表示短码码长和长码码长。码点数表示法:用斜线前后的数字分别表示短码码点个数和长码码点个数5、平均码长(P30),计算机系统结构（第二版)华中科技大学出版社,【例2.3】【2.15】【2.16】【2.17】,计算机系统结构（第二版)华中科技大学出版社,第3章流水技术与流水处理机3.1指令重叠与先行控制,1、指令顺序

5、执行方式(P44)指令之间顺序串行，且指令内的各个阶段之间也是顺序串行执行的方式。2、指令重叠执行方式(P45)如果处理机在结构上能使执行指令各阶段功能的部件或段（segment）相互独立，而且各段完成相应功能的所需时间尽可能相等，那么，就可以把一个指令序列中的多条指令在时间上重叠起来执行。,计算机系统结构（第二版)华中科技大学出版社,3.2流水线的分类与时空图,3、流水处理方式(P47)把一个需要反复进行的过程分离为若干独立的子过程，每个子过程与其他子过程同时处理不同的对象。流水处理方式是利用时间重叠的并行技术来开发计算机系统的并行性。,计算机系统结构（第二版)华中科技大学出版社,3.2.1

6、流水线的分类,（1）部件级流水线、处理机级流水线和系统级流水线(P47)部件级流水线由部件内各子部件组成的流水线。处理机级流水线处理机内的各部件之间的流水线。系统级流水线处理机之间的流水线，它又称为宏流水线。,计算机系统结构（第二版)华中科技大学出版社,（2）线性流水线与非线性流水线(P48)线性流水线流水线的各个段之间串行连接，处理对象顺序流经流水线各段最多一次的流水线。非线性流水线流水线的各段之间除有串行连接之外，还有反馈回路，从而使处理对象流经某个段或某几个段多次的流水线。,计算机系统结构（第二版)华中科技大学出版社,（3）单功能流水线与多功能流水线(P48)单功能流水线流水线的各段之间

7、的连接固定不变，因此只能完成一种固定功能的流水线。多功能流水线流水线的各段之间可以实现不同的连接，流水线能通过不同的连接实现不同的处理功能。,计算机系统结构（第二版)华中科技大学出版社,（4）静态流水线与动态流水线(P48)静态流水线在同一段时间内，多功能流水线只能实现一种连接，从而只能执行一种功能，且只有在按照这种连接已流入的所有处理对象都流出流水线后，才能重新连接以实现另一种功能。动态流水线在同一段时间内，多功能流水线的各段可以实现多种连接，从而同时执行多种功能。流水线中的任何一个功能段只能参加到一种连接中。,计算机系统结构（第二版)华中科技大学出版社,3.3线性流水线的性能计算,流水线的

8、吞吐率(P51)流水线单位时间输出结果的数量。（1）各段执行时间相等的吞吐率(P51)流水线的实际吞吐率（2）各段执行时间不等的吞吐率(P52),计算机系统结构（第二版)华中科技大学出版社,消除流水线的瓶颈段的方法(P52)分离瓶颈段：把流水线中的瓶颈功能段分离成为几个独立的子功能段，消除各段执行时间的“瓶颈”。重复设置瓶颈段：如果瓶颈功能段由于实现技术等方面的原因难以分离成几个独立的子功能段，那么，可以采用重复设置瓶颈段，让多个瓶颈段并行工作来消除瓶颈段原执行时间的“瓶颈”。这两种方法只要完全消除了“瓶颈”，提高吞吐率的程度是相同的。,计算机系统结构（第二版)华中科技大学出版社,流水线的加速

9、比(P54)使用顺序处理方式处理一批对象所用的时间与流水线使用流水处理方式处理同一批对象所用的时间之比。（1）各段执行时间相等的加速比(P54)（2）各段执行时间不等的加速比(P54),计算机系统结构（第二版)华中科技大学出版社,流水线的效率(P54)（1）各段执行时间相等的效率(P55)（2）各段执行时间不等的效率(P55),计算机系统结构（第二版)华中科技大学出版社,【例3.2】【例3.3】【3.11】【3.13】【3.14】【3.16】【3.18】,计算机系统结构（第二版)华中科技大学出版社,3.4非线性流水线的调度与性能计算,1.单功能非线性流水线的最优调度方法最优调度方法获得最优调度

10、策略的步骤(P58)根据处理对象对流水线各段的使用要求建立一个预约表。由预约表得出禁止表，禁止表是禁止后续对象流入流水线的时间间隔的集合。由禁止表得出初始冲突向量,计算机系统结构（第二版)华中科技大学出版社,由初始冲突向量得出状态有向图。后继状态的冲突向量用下式计算由状态有向图得出最优调度策略。有向图的任何一条环路都是一个可循环执行的无冲突调度策略，从中选择一个平均时间间隔最小的调度策略就是最优调度策略。,计算机系统结构（第二版)华中科技大学出版社,3.5流水线的相关问题与相关处理,局部相关(P66):对程序执行过程的影响较小的相关，它仅涉及到相关指令前后的一条或几条指令的执行。全局相关(P6

11、6):是指影响整个程序执行方向的相关，主要是转移类指令和中断引起的相关。,计算机系统结构（第二版)华中科技大学出版社,3.5.1局部相关及处理方法,1.顺序流动的“先写后读”相关及处理顺序流动(P66):对象从流水线流出的次序同它们流入流水线的次序一样。先写后读相关(P67):如果指令h写入结果的目的地址同指令j读取操作数的源地址是同一个存储单元或寄存器，那么，称这两条指令有“先写后读”的要求。如果当指令j到达读段时，指令h还没有到达写段完成写入操作，那么，指令j读出的数据就是错误的，这就是“先写后读”相关。解决顺序流动的“先写后读”相关的方法(P67)：延迟、异步流动和建立相关通路。,计算机

12、系统结构（第二版)华中科技大学出版社,3.5.3相关对流水线性能的影响,用时空图来表示流水处理过程和分析相关对流水线性能的影响。【例3.4】【例3.6】【例3.8】【3.21】【3.22】【3.23】【3.24】,计算机系统结构（第二版)华中科技大学出版社,3.6多发射处理机及其性能,单发射(P74):处理机在一个时钟周期只从存储器取出一条指令（IF）、只对一条指令译码（ID）、只执行一条指令（EX）和只写回一个运算结果（WR），因此，平均一个时钟周期只解释一条指令。单发射处理机的指令级并行度ILP1。多发射(P74):处理机在一个时钟周期可发射多条指令。多发射处理机的指令级并行度ILP2。属

13、于多发射处理机范畴的处理机有：超标量处理机、超流水处理机、超标量超流水处理机和超长指令字处理机。,计算机系统结构（第二版)华中科技大学出版社,3.6.5多发射处理机的性能比较（表3.6）,计算机系统结构（第二版)华中科技大学出版社,第4章存储系统4.1存储系统的层次结构与性能指标4.1.1存储系统的层次结构,1.程序访问局部性时间局部性(P94):程序在最近的未来要用到的信息很可能是现在正在使用的信息。空间局部性(P94):程序在最近的未来要用到的信息很可能同现在正在使用的信息在存储空间位置上是相邻近的。,计算机系统结构（第二版)华中科技大学出版社,4.1.2存储系统的性能指标,1、虚拟地址空

14、间(P96):虚拟存储技术为用户设计了一个虚拟地址空间，这个虚拟地址空间比主存的实际地址空间要大得多，并采用像主存一样的随机访问方式。2、存储器最大带宽(P97):存储器被连续访问时能提供的数据传输速率称为存储器的最大带宽。,计算机系统结构（第二版)华中科技大学出版社,3、命中率(P97):若逻辑地址流指定的信息能在M1中被访问到的次数为N1，在M1中未被访问到的次数为N2，则命中率为4、二级存储系统的等效访问周期(P97):,计算机系统结构（第二版)华中科技大学出版社,5、二级存储系统的访问效率(P97),计算机系统结构（第二版)华中科技大学出版社,4.2并行存储器,并行存储器(P98):在

15、一个存储器访问周期能并行访问到多个存储字的存储器，能有效地提高存储器的带宽。并行存储器主要有2种，一种是单体多字并行存储器，另一种是低位交叉编址多体并行存储器。,计算机系统结构（第二版)华中科技大学出版社,4.2.1单体多字并行存储器,1、单体多字并行存储器(P98):把存储器的存储字字长增加n倍，以存放n个指令字或数据字，单体多字并行存储器的最大带宽比单体单字存储器的最大带宽提高n倍。单体多字并行存储器访问冲突概率大。2、低位交叉编址方法(P99)：若每个存储体的容量均为n个存储字，则存储单元地址的低log2m位称为体号k，地址的高log2n位称为体内地址i。低位交叉编址的存储单元地址A的计

16、算公式为：A=mi+k,计算机系统结构（第二版)华中科技大学出版社,3.多体并行存储器的错位存储方法对错位存储的nn二维数组可以实现以下4种并行访问方式的无存储体冲突访问(P99)：并行访问数组任意一行的n个元素。并行访问数组任意一列的n个元素。并行访问数组对角线的n个元素或任意一条子对角线的所有元素。并行访问数组中任意一个子数组的n个元素。,计算机系统结构（第二版)华中科技大学出版社,4、无存储体冲突访问方法(P100):对nn的二维数组错位存储时，要求存储体的个数，且m取质数。二维数组的任意元素aij存储的体号和体内地址分别是：其中，p是满足的任意自然数；k是数组的第一个元素a00所在存储

17、体的体号，一般取k=0。,计算机系统结构（第二版)华中科技大学出版社,计算机系统结构（第二版)华中科技大学出版社,4.3虚拟存储器,在虚拟存储技术中，把程序经编译生成的访存地址称为虚拟地址（或称为虚地址），由虚地址表示的存储空间称为虚空间(P100)。程序代码运行时，必须先把虚地址转换成主存物理地址,或称为主存实地址，才能按实地址访问主存。虚地址与实地址之间对应关系的规则称为地址映像(P100)。程序在运行时，虚拟存储系统按照某种地址映像把虚地址转换成实地址称为地址变换(P100)。地址变换对应用程序员是透明的，由存储系统自动完成。,计算机系统结构（第二版)华中科技大学出版社,如果按虚地址要访

18、问的数据不在主存中（未命中），则称为发生访问失效(P100)，那么就需要访问磁盘存储器。这时，先要把虚地址变换成磁盘存储器物理地址，称之为外部地址变换，然后才能访问磁盘存储器，将要访问的数据块调入主存。外部地址变换更多地依靠软件来实现。当有新的数据块要调入主存时，如果主存中已经没有空闲的位置，则称为发生实存冲突(P101)，那么就要采用某种替换算法来确定新数据块调入主存的位置。,计算机系统结构（第二版)华中科技大学出版社,4.3.1虚拟存储器的地址变换,1、页式虚拟存储器的地址变换页式管理(P102):把虚拟地址空间和主存地址空间都划分成同样大小的页，程序以页为单位调入调出主存。虚拟空间的页称

19、为虚页，主存空间的页称为实页。页表(P102):每个程序都用一个页表来存放该程序的各个虚页装入主存实页位置（实页号）等有关信息，一个虚页占用页表中的一行，虚空间的虚页数就是页表的行数（存储字数）。,计算机系统结构（第二版)华中科技大学出版社,图4.6页式虚拟存储器的地址变换,计算机系统结构（第二版)华中科技大学出版社,4.3.2页面替换算法与命中率的计算,1、几种页面替换算法(P108)随机替换算法:（RAND算法）用软件或硬件随机产生被替换的虚页号。先进先出替换算法:（FIFO算法）选择最早装入主存的虚页作为被替换页。近期最久使用替换算法:（LRU算法）该算法选择过去近期最久访问的虚页作为被

20、替换页。最优替换算法:（OPT算法）选择将来一段时间内最久被访问的页作为被替换页。,计算机系统结构（第二版)华中科技大学出版社,2、页面替换算法的命中率计算方法通过典型程序的虚页地址流模拟使用某个替换算法的替换过程，来得出命中主存的次数，从而求出该虚页地址流使用该替换算法时的主存命中率。【例4.2】,计算机系统结构（第二版)华中科技大学出版社,4.3.3堆栈型替换算法及其堆栈处理过程,1、堆栈型替换算法(P109):如果替换算法具有下述性质：随着分配给程序的主存实页数n的增加，替换算法的主存命中率H也随之提高，至少不下降。那么，这种替换算法就称为堆栈型替换算法。2、H(n)随n变化的计算方法：

21、用一个堆栈对程序的访存虚页地址流处理一次，就可以获得H(n)随n变化的关系，从而可以根据程序访存需要达到的主存命中率H来确定应分配给该程序的实页数n，使有限的主存空间资源的使用达到较高的性价比。【例4.4】【4.19】【4.23】,计算机系统结构（第二版)华中科技大学出版社,4.4高速缓冲存储器,1、Cache存储系统与虚拟存储系统的不同(P114)：Cache与主存之间以块为单位进行数据交换。两级存储器间的速度比不同。CPU与Cache存储器之间和CPU与主存之间都有直接通路，若CPU对Cache存储器中的块访问未命中，则CPU可直接访问主存。Cache存储系统以提高整个存储系统的速度为目标

22、，虚拟存储系统以扩大存储系统的容量为目标。Cache存储系统对系统程序员和应用程序员都是透明的，虚拟存储系统仅对应用程序员是透明的。,计算机系统结构（第二版)华中科技大学出版社,4.4.1Cache的地址映像与地址变换,1.全相联地址映像及其地址变换全相联地址映像(P115):主存中的任意一块可以装入到Cache中任意的块位置上。全相联映像的块冲突概率最低，Cache空间利用率最高。全相联映像的地址变换(P115):采用目录表来实现，目录表需存放在相联存储器中，目录表的行数（即相联存储器的存储单元数）是Cache的块数。,计算机系统结构（第二版)华中科技大学出版社,图4.15全相联映像地址变换

23、,计算机系统结构（第二版)华中科技大学出版社,【例4.6】2.直接地址映像及其地址变换直接地址映像(P116):把主存空间按Cache的大小划分为若干区，主存各区和Cache再划分为若干块，主存各区中的区内块号B只能装入到与Cache块号b相同的那个块位置上。直接映像的块冲突概率最高，Cache空间利用率最低。,计算机系统结构（第二版)华中科技大学出版社,3.组相联地址映像及其地址变换组相联映像(P118):把主存按Cache的容量分区，主存中的各区和Cache再按同样大小划分成数量相同的组，组内按同样的大小划分成数量相同的块，主存的组到Cache的组之间采用直接映像，两个对应组的块之间采用全

24、相联映像。,计算机系统结构（第二版)华中科技大学出版社,【例4.6】【例4.7】【4.25】【4.27】,计算机系统结构（第二版)华中科技大学出版社,4.4.3Cache的性能分析,1、Cache的加速比Cache系统的加速比S(P125):设置Cache后的访存速度相对于没有设置Cache而直接访问主存的访存速度的提高倍数，即：,计算机系统结构（第二版)华中科技大学出版社,【例4.10】,计算机系统结构（第二版)华中科技大学出版社,第5章互连网络5.1互连函数,互连函数(P133):将互连网络的N个输入端和N个输出端的端号分别用整数0，1，N-1来表示，互连函数表示相互连接的输出端号和输入端

25、号之间的对应关系。,.,计算机系统结构（第二版)华中科技大学出版社,5.1.1互连函数的表示方法,互连函数(P133):表示互连网络的输入端X与输出端之间可实现的连接。如果互连函数是单值函数，相互连接的输入端与输出端是一对一的，则称这种连接是置换连接(P133)。如果互连函数是多值函数，一个输入端连接到多个输出端，则称这种连接是播送连接(P133)。输入输出对表示法图形表示法循环互连函数,计算机系统结构（第二版)华中科技大学出版社,5.1.2几种基本的互连函数,1.恒等置换恒等置换实现的互连(P134)：输入端X连接的输出端号就是输入端号X。2.交换置换交换置换实现的互连(P134)：把输入端

26、的二进制地址的最低位变反就是连接的输出端的二进制地址。交换置换的互连函数为,计算机系统结构（第二版)华中科技大学出版社,3.方体置换方体置换（Cube）(P135)有个互连函数它们共同表示一个n维立方体的双向互连。其中，Ck的互连函数为方体置换也是分组循环互连。方体置换的个互连函数分别表示N/2对结点沿n维方向的双向互连。,计算机系统结构（第二版)华中科技大学出版社,4.均匀洗牌置换均匀洗牌置换（Shuffle）(P135)又称为混洗置换。混洗置换实现的互连：把输入端二进制地址循环左移一位就是连接的输出端的二进制地址。混洗置换的互连函数为子洗牌置换实现的互连：把输入端二进制地址从第k位到最低位

27、共k+1位的低端地址循环左移一位就是连接的输出端的二进制地址。子洗牌置换的互连函数为,计算机系统结构（第二版)华中科技大学出版社,逆均匀洗牌置换函数是均匀洗牌置换函数的逆函数(P136)。逆均匀洗牌置换实现的互连：把输入端二进制地址循环右移一位就是连接的输出端的二进制地址。逆均匀洗牌置换的互连函数为,计算机系统结构（第二版)华中科技大学出版社,7.移数置换移数置换实现的互连(P138)：把输入端的端号序列循环左移或循环右移若干位就是对应连接的输出端的端号序列。移数置换的互连函数为其中，循环左移k位得出连接输入端X的输出端号为，循环右移k位得出连接输入端X的输出端号为。,计算机系统结构（第二版)

28、华中科技大学出版社,8.加减2I置换加减2I置换（PM2I）是一种特殊的移数置换加减2I置换实现的互连(P139)：个输入端的端号序列循环左移或循环右移位,就是对应连接的输出端的端号序列。加减2I置换的互连函数为,计算机系统结构（第二版)华中科技大学出版社,移数置换和加减2I置换都是可用循环互连函数的形式来表示的置换连接(P139)。N=8的PM2I置换，共有2n=6个互连函数，分别用循环互连函数表示为,计算机系统结构（第二版)华中科技大学出版社,【例5.1】【5.2】,计算机系统结构（第二版)华中科技大学出版社,5.2互连网络的结构参数与性能指标5.2.1互连网络的结构参数,(P141)1、

29、网络规模：网络能连接的结点数。2、结点度：一个结点射入或射出的边数。3、结点距离：两个结点之间相连的最少边数。4.网络直径：一个互连网络中任意两个结点之间距离的最大值。5、最小对剖平面：一个有N个结点的网络对剖平面把网络分为两个各有N/2个结点的网络。由对剖平面切开的边数最少的对剖平面。6、网络对剖宽度：由最小对剖平面切开的边数。7、对称网络：若从网络的任意结点来看，网络的结构都是相同的，则称网络是对称网络。,计算机系统结构（第二版)华中科技大学出版社,5.2.2互连网络的性能指标,1.通信延时(P142)通信时延是指从源结点到目的结点传送一条消息所需的总时间，通信时延包括以下4部分：软件开销

30、:在源结点和目的结点用于收发消息的软件所需的执行时间。通道时延:通道带宽除以消息长度即通道时延。选路时延:消息在传送路径上所需的一系列选路决策所需的时间开销。竞争时延:多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间为竞争时延。,计算机系统结构（第二版)华中科技大学出版社,2.网络延时(P142)由网络硬件特征决定的网络时延是通道时延与选路时延之和，网络时延与程序行为和网络传输状态无关。3.端口带宽(P142)网络中从任意一个端口单位时间传送到其他端口的最大信息量称为该端口的端口带宽。在对称网络中，端口带宽与端口位置无关。对称网络的各端口带宽也称为网络的端口

31、带宽。非对称网络的端口带宽是所有端口带宽的最小值。4.聚集带宽(P143)网络的聚集带宽是指网络从一半结点到另一半结点，单位时间传送的最大信息量。,计算机系统结构（第二版)华中科技大学出版社,5.3静态互连网络,静态互连网络(P143):各结点之间有专用的连接通路，且在运行中不能改变连接的互连网络。【例5.2】,计算机系统结构（第二版)华中科技大学出版社,5.4动态互连网络,动态互连网络(P149):通过设置有源开关且根据连接需求来动态改变开关的连接，从而实现结点之间的不同连接。,计算机系统结构（第二版)华中科技大学出版社,5.4.3多级互连网络,多级互连网络(P153):把重复设置的多套动态单级网络串联起来，单级网络级间采用固定的级间连接模式，通过动态控制各单级网络的开关状态来实现多级互连网络的输入端和输出端之间所需的连接。,计算机系统结构（第二版)华中科技大学出版社,1.Omega网络(P154)网络n个开关级从网络