计算机体系结构期末辅导201303

1、1 计算机体系结构期末辅导计算机体系结构期末辅导 主讲：何志杰主讲：何志杰 2 1. 期末考试题题型期末考试题题型 一、填空题（每空一、填空题（每空1分，共分，共14分）分） 二、名词解释（每题二、名词解释（每题2分，共分，共16分）分） 三、简答题（每题三、简答题（每题5分，共分，共30分）分） 四、问答与计算题四、问答与计算题(第第1题题10分分,第第2、3题每题题每题15分共分共40分分) 2. 期末考试内容分布期末考试内容分布 第第1章章 基础知识基础知识 第第2章章 指令系统指令系统 第第3章章 存储系统设计存储系统设计 第第4章章 流水线计算机设计技术流水线计算机设计技术 第第5章

2、章 并行处理技术（互连网络部分）并行处理技术（互连网络部分） 第第8章章 非冯非冯.诺依曼计算机有关概念诺依曼计算机有关概念 计算机体系结构期末辅导计算机体系结构期末辅导 3 按照弗林（Flynn）分类法，计算机系统可以分为4类：SISD计算机、 （SIMDSIMD计算机）、（计算机）、（MISDMISD计算机）和（计算机）和（MIMDMIMD计算机）。计算机）。 早期冯诺依曼计算机的主要特点是（程序存储）、（指令驱动）、程序存储）、（指令驱动）、 （集中控制）。（集中控制）。 目前向量处理机的系统结构有两种：（存储器存储器型和寄存器寄存储器存储器型和寄存器寄 存器型）。存器型）。 通用计算机

3、基本指令分为5类，它们分别是：（数据传送类，运算类，数据传送类，运算类， 程序控制类，输入输出类，处理机控制和调试类）。程序控制类，输入输出类，处理机控制和调试类）。 传统的冯诺依曼计算机是以控制驱动方式工作，以数据驱动方式工作的 典型计算机是（数据流计算机），（数据流计算机），以需求驱动方式工作的典型计算机是 （归约机），（归约机），以模式匹配驱动方式工作的典型计算机是（人工智能计算（人工智能计算 机）。机）。 3、填空题（举例）、填空题（举例） 4 4、名词解释、名词解释(举例举例) 计算机体系结构计算机体系结构 透明性透明性 系列机系列机 兼容机兼容机 模拟模拟 仿真仿真 程序的局部性原

4、理程序的局部性原理 MIPS 基准测试程序基准测试程序 高速缓冲存储器高速缓冲存储器 虚拟存储器虚拟存储器 快表快表 程序定位程序定位 延迟转移技术延迟转移技术 窗口重叠技术窗口重叠技术 流水线技术流水线技术 先行控制技术先行控制技术 动态流水线动态流水线 静态流水线静态流水线 线性流水线线性流水线 非线性流水线非线性流水线 流水线的吞吐率流水线的吞吐率 超标量计算机超标量计算机 向量的分段开采技术向量的分段开采技术 5 1、简述冯、简述冯.诺依曼计算机的特征诺依曼计算机的特征 。 2、什么是存储系统？、什么是存储系统？ 3、简述组相联映象规则。、简述组相联映象规则。 4、引起、引起Cache

5、与主存内容不一致的原因是什么？为了保持与主存内容不一致的原因是什么？为了保持Cache的一致的一致 性，在单计算机系统中一般采取哪些措施？性，在单计算机系统中一般采取哪些措施？ 5、影响虚拟存储器命中率的因素有哪些？它们是如何影响的？、影响虚拟存储器命中率的因素有哪些？它们是如何影响的？ 6、在指令编码中，缩短地址码的方法很多，请列出三种缩短地址码的、在指令编码中，缩短地址码的方法很多，请列出三种缩短地址码的 方法，并说明理由。方法，并说明理由。 7、什么是指令的重叠解释方式？重叠解释方式有哪三种？、什么是指令的重叠解释方式？重叠解释方式有哪三种？ 8、试述页式管理虚拟存储器的工作过程、试述页

6、式管理虚拟存储器的工作过程 。 5、简答题（举例）、简答题（举例） 6 6、典型例题分析与解答、典型例题分析与解答 例例1如有一个经解释实现的计算机，可以按功 能划分成4级。每一级为了执行一条指令需要下 一级的N条指令解释。若执行第一级的一条指令 需K(ns)时间，那么执行第2、3、4级的一条指令 各需要用多少时间(ns)? 解：解：第二级的一条指令需第第二级的一条指令需第1级的级的N条指令解释条指令解释 第二级的一条指令执行时间为第二级的一条指令执行时间为NKns； 第三级的一条指令执行时间为第三级的一条指令执行时间为N2Kns； 第四级的一条指令执行时间为第四级的一条指令执行时间为N3Kn

7、s。 7 本题有两个问题应特别注意：第一个问题是“上一级”与 “下一级”的关系，即哪是上一级，哪是下一级？在下图 中第3级是第2级的“上一级”，第1级又是第2级的“下一 级”。第二个问题是该计算机是一个“经解释实现的计算 机”，上一级的程序在下一级上实现不是经翻译完成，只 能是解释。 第第1级级 N3条指令解释条指令解释 第第2级级 N2条指令解释条指令解释 第第3级级 N条指令解释条指令解释 第第4级级 一条指令一条指令上级上级 下级下级 8 例例2假设将某系统的某一部件的处理速度加快到10 倍，但该部件的原处理时间仅为整个运行时间的40%， 则采用加快措施后能使整个系统的性能提高多少？ 解

8、：由题意可知解：由题意可知 fe=0.4, re=10, 根据根据Amdahl定律定律 11 1.56 (1 0.4)0.4/100.64 e P o T S T 9 例例3用一台4OMHz处理机执行标准测试程序，它 含的混合指令数和相应所需的时钟周期数如下： 指令类型 指令条数指令条数 时钟周期数 整数运算 45000 1 1 数据传送 32000 2 浮点运算 15000 2 控制传送 8000 2 求有效CPI、MIPS速率和程序的执行时间。 10 解：依题意可知解：依题意可知 I IN N=10=105 5条，条，n=4n=4 1 4 1 () (1 0.4520.3220.1520.

9、08) 1.55 n i i i N i I CPICPI I 6 66 4010 25.8 101.5510 C f MIPS CPI 56 101.551 / 40103.875() CPUNC TICPIT ms 11 例例4若某机要求有：三地址指令4条，单地址指令 192条，零地址指令16条。设指令字长为12位，每个 地址码长3位。问能否以扩展操作码为其编码？ 12 解：解： 三种指令格式字如下：三种指令格式字如下： OPC A1 A2 A3 OPC A1 OPC 000 xxx xxx xxx 011 xxx xxx xxx 000 000 xxx 111 101 xxx 111 1

10、11 110 000 111 111 111 111 三地址4条 一地址192条 零地址16条 3333 三地址指令4条 单地址指令192条 零地址指令16条 13 例例5假设一台模型计算机共有10种不同的操作码， 如果采用固定长操作码需要4位。已知各种操作码在 程序中出现的概率如下表所示，计算采用Huffman编 码法的操作码平均长度，并计算固定长操作码和 Huffman操作码的信息冗余量（假设最短平均长度H 3.1位） 指令序号指令使用频度Pi指令序号指令使用频度Pi I10.17I60.09 I20.15I70.08 I30.15I80.07 I40.13I90.03 I50.12I10

11、0.01 14 答：构造答：构造Huffman树如下：树如下： 1.00 0.40 0.23 0.11 0.04 0.010.030.070.120.170.080.090.130.150.15 0.60 0.300.30 0.17 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 15 Huffman编码如下表： 指令 号 指令使 用频度Pi Huffman 编码 码长 指令 号 指令使 用频度Pi Huffman 码 码长 I10.17102I60.0901104 I20.150003I70.0801114 I30.150013I80.0711104 I40.1301

12、03I90.03111105 I50.121103I100.01111115 16 Huffman编码的平均码长为： 冗余量（3.153.10）/3.151.59% 固定码长：log2104 冗余量（43.10）/422.5% 15. 3 5)01. 003. 0(4)07. 008. 009. 0(3)12. 013. 015. 015. 0(217. 0 10 1 i iil P 17 例例66设某用户虚存共有8页, 主存有4页, 每页大 小为1KB. 试根据页表计算出虚地址1023和6800 的主存实地址。 提示：注意页表中虚、 实页对应关系 页表 虚页号虚页号 实页号实页号 装入位装入

13、位 0 3 1 1 1 1 2 2 0 3 3 0 4 2 1 5 1 0 6 0 1 7 0 0 18 每页首地址=页号X每页大小 第第0 0页页0102301023 第第1 1页页1024204710242047 第第2 2页页2048307120483071 第第3 3页页3072409530724095 第第4 4页页4096511940965119 第第5 5页页5120614351206143 第第6 6页页6144716761447167 第第7 7页页7168-81917168-8191 解：页号与地址对应关系解：页号与地址对应关系 虚地址虚地址1023，虚页号为，虚页号为0，

14、页内位移，页内位移 为为1023；根据虚页号查页表得知实；根据虚页号查页表得知实 页号为页号为3，且装入位为，且装入位为1。 主存实地址主存实地址PA=3072+1023=4095 虚地址虚地址6800，虚页号为，虚页号为6，页内位移，页内位移 为为656；根据虚页号查页表得知实页；根据虚页号查页表得知实页 号为号为0，且装入位为，且装入位为1。 主存实地址主存实地址PA=0+656=656 虚页号虚地址虚页号虚地址1024 19 例例7某机主存容量为512KB，Cache的容量为 32KB，每块的大小为16个字（或字节）。划 出全相联方式主、缓存的地址格式、目录表 格式及其容量。 答：全相联

15、映象方式：答：全相联映象方式： 主存与缓存分成相同大小的数据块，主存的某主存与缓存分成相同大小的数据块，主存的某 一数据块可以装入缓存的任意一块空间中。一数据块可以装入缓存的任意一块空间中。 根据已知条件可以求得：根据已知条件可以求得： 主存块数：主存块数：512K/1632K215； 缓存块数：缓存块数：32K/162K211； 块内地址：块内地址：1624 20 容量：与缓冲块数量相同即2112048(或32K/162048)。 主存块号Bi 块内地址 18 4 3 0 主存地址 缓存块号Bi 块内地址 14 4 3 0 缓存地址 主存块地址 缓存块地址 有效位 26 12 11 1 0

16、目录表 21 图图2.6 全相联地址转换全相联地址转换 22 例例8某机主存容量为512KB，Cache的容量为 32KB，每块的大小为16个字（或字节）。划出 直接相联方式主、缓存的地址格式、目录表格式 及其容量。 答：直接相联映象方式：答：直接相联映象方式： 主存与缓存分成相同大小的数据块，将主存空间按缓主存与缓存分成相同大小的数据块，将主存空间按缓 存的容量分成区，主存中某区的一块存入缓存时只能存存的容量分成区，主存中某区的一块存入缓存时只能存 入缓存中块号相同的位置。入缓存中块号相同的位置。 根据已知条件可以求得：根据已知条件可以求得： 主存区数：主存区数：512K/32K1624；缓

17、存块数：；缓存块数：32K/16 2K211；块内地址：；块内地址：1624 23 容量：与缓冲块数量相同即2112048(或32K/162048)。 主存区号 有效位 4 1 0 目录表 缓存块号 块内地址 14 4 3 0 缓存地址 区号 区内块号 块内地址 18 15 14 4 3 0 主存地址 24 高速缓冲存储器高速缓冲存储器 主主存存地地 址址 区区号号 E块块号号 B块块内内地地址址 W Cache 地地址址块块号号 b块块内内地地址址 w 块块失失效效相相等等比比较较 比比较较相相等等且且有有效效为为 1 E1访访问问 Cache 区区号号 E（按按地地址址访访问问）有有效效位

18、位 区区表表存存储储器器 图图2.8 直接相联地址转换直接相联地址转换 25 例例9主存容量为512KB，Cache的容量为32KB，每块为64 个字（或字节），缓存共分128组。划出组相联方式主、 缓存的地址格式、目录表格式及其容量。 答：组相联映象方式：答：组相联映象方式： 主存与缓存分成相同大小的数据块，主存和主存与缓存分成相同大小的数据块，主存和Cache按同按同 样大小划分成组，将主存空间按缓存的容量分成区，样大小划分成组，将主存空间按缓存的容量分成区， 当主存的数据调入缓存时，主存与缓存的组号应相等当主存的数据调入缓存时，主存与缓存的组号应相等 ，但组内各块地址之间则可以任意存放。

19、，但组内各块地址之间则可以任意存放。 根据已知条件可以求得：根据已知条件可以求得： 主存区数：主存区数：512K/32K1624；缓存组数：；缓存组数：12827； 缓存块数：缓存块数：32K/6451229；组内块数：；组内块数：512/128422 块内地址：块内地址：6426 26 容量：29512(或32K/64512)。 区号 块号 缓存块号 有效位 8 5 4 3 2 1 0 目录表 组号 缓存块号 块内地址 14 8 7 6 5 0 缓存地址 区号 组号 块号 块内地址 18 15 14 8 7 6 5 0 主存地址 27 高速缓冲存储器高速缓冲存储器 图图2.10 组相联映象地

20、址转换组相联映象地址转换 区区 号号 E组组 号号 G组组 内内 块块 号号 B块块 内内 地地 址址 W 主主 存存 地地 址址 组组 号号 g组组 内内 块块 号号 b块块 内内 地地 址址 w C ache 地地 址址 不不 等等相相 联联 比比 较较 相相 等等 相相 联联 比比 较较 (Gb个个 块块 ) 区区 号号 E ,组组 内内 块块 号号 B组组 内内 块块 号号 b 块块 表表 28 例例10一个有快表和慢表的页式虚拟存储器，最多有64个 用户，每个用户最多要用1024个页面，每页4K字节，主 存容量8M字节。 （1）写出多用户虚地址的格式，并标出各字段的长度。 （2）写出

21、主存地址的格式，并标出各字段的长度。 （3）快表的字长为多少位？分几个字段？各字段的长度 为多少位？ （4）慢表的容量是多少个存储字？每个存储字的长度为 多少位？ 29 答：用户号：答：用户号：6426，虚页号：，虚页号：1024210，页内地址：，页内地址：4K 212，主存页数：，主存页数：8M/4K211 （1）多用户虚地址：）多用户虚地址： 用户号（用户号（6位）虚页号（位）虚页号（10位）页内地址（位）页内地址（12位）位） 共共28位位 （2）主存地址：）主存地址： 主存实页号（主存实页号（11位）页内地址（位）页内地址（12位）位） 共共23位位 （3）快表字长）快表字长27位；

22、分位；分3个字段：用户号个字段：用户号6位，虚页号位，虚页号10位，位， 实页号实页号11位位 （4）慢表容量为）慢表容量为2(6+10)，每个存储字长为：，每个存储字长为： 主存页号主存页号112位。位。 30 例例11为在页式虚拟存储器中，一个程序由P1P5 共5个页面组成。在程序执行过程中依次访问 的页面如下：P2，P3，P2，P1，P5，P2，P4， P5，P3，P2，P5，P2 假设系统分配给这个程序的主存有3个页面， 分别采用FIFO、LFU和OPT三种页面替换算法 对这3页主存进行调度。 (1) 画出主存页面调入、替换和命中的情况表。 (2) 统计三种页面替换算法的页命中率。 解

23、：解：三种替换算法的替换过程： 31 页地址流页地址流2 23 32 21 15 52 24 45 53 32 25 52 2 FIFO FIFO 命中命中3 3次次 2 22 2 3 3 2 2 3 3 2 2* * 3 3 1 1 5 5 3 3* * 1 1 5 5 2 2 1 1* * 5 5* * 2 2 4 4 5 5* * 2 2 4 4 3 3 2 2* * 4 4 3 3 2 2* * 4 4 3 3 5 5 4 4* * 3 3* * 5 5 2 2 调调 进进 调调 进进 命命 中中 调调 进进 替替 换换 替替 换换 替替 换换 命命 中中 替替 换换 命命 中中 替替

24、 换换 替替 换换 LRULRU 命中命中5 5次次 2 22 2 3 3 2 2 3 3 1 1 2 2 3 3* * 5 5 1 1 2 2* * 2 2 5 5 1 1* * 4 4 2 2 5 5* * 5 5 4 4 2 2* * 3 3 5 5 4 4* * 2 2 3 3 5 5* * 5 5 2 2 3 3* * 2 2 5 5 3 3* * 调调 进进 调调 进进 命命 中中 调调 进进 替替 换换 命命 中中 替替 换换 命命 中中 替替 换换 替替 换换 命命 中中 命命 中中 OPTOPT 命中命中6 6次次 2 22 2 3 3 2 2 3 3 2 2 3 3 1 1

25、* * 2 2 3 3* * 5 5 2 2* * 3 3 5 5 4 4* * 3 3 5 5 4 4* * 3 3 5 5 4 4* * 3 3 5 5 2 2 3 3* * 5 5 2 2 3 3 5 5 2 2 3 3 5 5 调调 进进 调调 进进 命命 中中 调调 进进 替替 换换 命命 中中 替替 换换 命命 中中 命命 中中 替替 换换 命命 中中 命命 中中 32 例例12用一条4段浮点加法器流水线求8个浮点数的和: ZABCDEFGH,求流水线的吞吐率、加 速比和效率,其中t1=t2=t3=t4=t。 输输入入 求求阶阶差差 对对阶阶 尾尾数数加加 规规格格化化 输输出出

26、t t1 t t2 t t3 t t4 解：由于存在数据相关，A+B的运算结果要在第5时钟周期 才能继续做加C运算，这样，每个功能部件都要空闲3个时 钟周期，为此，可对原式作一简单变化，得到： Z（AB）（CD）（EF）（GH） 33 7个加法8个数的流水线时空图如下： 空间空间 周期周期 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 1313 1414 1515 规格化规格化 1 1 2 2 3 3 4 4 5 5 6 6 7 7 尾数加尾数加 1 1 2 2 3 3 4 4 5 5 6 6 7 7 对阶对阶 1 1 2 2 3 3 4

27、 4 5 5 6 6 7 7 求阶差求阶差 1 1 2 2 3 3 4 4 5 5 6 6 7 7 时间时间 加数加数 A C E G A+B E+F A+B+C+DA C E G A+B E+F A+B+C+D 加数加数 B D F H B D F H C+D G+H E+F+G+H C+D G+H E+F+G+H 结果结果 A+B A+B C+D E+F C+D E+F G G+H +H A+B+C+D E+F+G+H A+B+C+D E+F+G+H Z Z 用一条用一条 4 4 段浮点加法器流水线求段浮点加法器流水线求 8 8 个数之和的流水线时空图个数之和的流水线时空图 34 从流水线

28、的时空图中可以很清楚地看到，7个浮点 加法共用了15个时钟周期。 TP n Tttk 7 15 0 47 1 S T T t tk 04 7 15 1 87 E T k T t tk 04 7 4 15 0 47 流水线的吞吐率为： 流水线的加速比为： 流水线的效率为： 35 例例13设有两个向量A，B，各有4个元素，若在如图5-2-16a 所示的静态双功能流水线上，计算向量点积： 其中，1235组成加法流水线，145 组成乘法流水线。 4 1i ii baBA 36 又设每个流水线所经过的时间均为t，而且流水线 的输出结果可以直接返回到输入或暂存于相应的缓 冲寄存器中，其延迟时间和功能切换所

29、需的时间都 可以忽略不计。请使用合理的算法，能使完成向量 点积A*B所用的时间最短，并求出流水线在此期间实 际的吞吐率TP和效率E。 解：首先，应选择适合于静态流水线工作的算法。 对于本题，应先连续计算al*bl、a2*b2、a3*b3和 a4*b4共4次乘法，然后功能切换，按 (albl+a2b2)+(a3b3+a4b4)经3次加法来求得最后 的结果。按此算法可画出流水线工作时的时空图。 如图5-2-16b所示。 37 38 由图可见，总共在15个t的时间内流出7个结果， 所以在这段时间里，流水线的实际吞吐率TP为 7/15t。 若不用流水线，由于一次求积需3t,一次加法需 4 t,产生上述

30、结果就需要43t+34t=24t。 因此,加速比为S=24t/(15t)=1.6。 该流水线的效率可用阴影区面积和全部5个段的总 时空图面积之比求得，即 %32 75 24 155 3443 t tt E 39 例例14什么是方体置换？写出方体置换函数的表达式，假设 互联网有16个结点，请画出4个方体置换函数（即C0， C1，C2，C3）的输入端与输出端的连接关系。 答：方体置换是实现二进制地址编号中第答：方体置换是实现二进制地址编号中第k位位值不同的输位位值不同的输 入端输出端之间的连接。其表达式为：入端输出端之间的连接。其表达式为： )()( 0112101121 XXXXXXXXXXXX

31、C k k knnkkknnk 40 0000 0001 0010 0011 0100 0101 0110 0111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 1000 1001 1010 1011 1100 1101 1110 1111 C0立方置换函数：立方置换函数： )()(0 12301230 XXXXXXXXC 41 C1立方置换函数：立方置换函数： )()( 0 1 2301231 XXXXXXXXC 0001 0010 0011 0100 0101 0110 0111 0001 0010 0011 0100 0101 0110 0111 1001 1010 1011 1100 1101 1110 1111