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

1、计算机系统结构电子教案1计算机系统结构电子教案2教学计划 教材：计算机系统结构（第二版）郑纬民等清华大学出版社 参考书：计算机系统结构复习与考试指导郑纬民等高等教育出版社总学时：40第1章：4第2章：4第3章：10第4章：4第5章：6第6章：2第7章：6第8章：2第9、10章：2计算机系统结构电子教案3第一章第一章 基本概念（基本概念（P1P1） 本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。 定性知识：本课程经常使用的一些名词概念，以及对计算机的定性认识、分析方法。 定量知识：对计算机性能进行定量评价的几个重要公式。计

2、算机系统结构电子教案4 1.1 定性知识几个基本概念 1.1.1 什么是计算机系统结构计算机系统结构？（P4） 英文名称：Computer ArchitectrueComputer Architectrue 计算机系统结构（也叫“计算机体系结构计算机体系结构”）课程：传授计算机整机（硬软件统一条件下）设计的重大技术知识。 Architectrue的英文原义是“建筑学”。 “计算机系统结构”作为事物名称：使用者必须了解的机器外部特性知识（广义定义）。在本课程中“使用者”目前特指最低级语言的程序员，“外部特性”特指整个硬件的外部特性（狭义定义）。 透明性概念透明性概念：使用者可以不了解的知识。计算

3、机系统结构电子教案5“计算机系统结构”狭义定义包含的内容（P4）1.数据表示（硬件能够直接识别和处理的数据类型和格式等）；2.寻址方式（包括最小寻址单位、寻址方式的种类、表示和地址计算等）；3.寄存器组织（包括各种寄存器的配置数目和功能定义）；4.指令系统（包括机器指令的操作类型和格式、指令间的排序方式和控制机构等）；5.存储系统（包括编址方式、存储容量、最大编址空间等）；6.中断机构（中断源的分类管理和中断服务功能设计）；7.机器工作状态（如管态、目态等）的定义和切换；8.输入/输出子系统结构与管理；9.信息保护手段及其实现。计算机系统结构电子教案61.1.2 计算机系统的多级层次模型（P3

4、）第5级 专用应用语言机器 特定应用用户 （使用特定应用语言） （经应用程序翻译成高级语言）第4级 通用高级语言机器 高级语言程序员（使用通用高级语言） （经编译程序翻译成汇编语言）第3级 汇编语言机器 汇编语言程序员（使用汇编语言） （经汇编程序翻译成机器语言、操作系统原语）第2级 操作系统语言机器 操作系统用户 （使用操作系统原语） （经原语解释子程序翻译成机器语言）第1级 传统机器语言机器 传统机器程序员（使用二进制机器语言） （由微程序解释成微指令序列）第0级 微指令语言机器 微指令程序员 （使用微指令语言） （由硬件译码器解释成控制信号序列） 图1.1 计算机系统的多级层次模型计算机

5、系统结构电子教案71.1.3 其他重要名词概念（自学）计算机组成计算机组成计算机系统结构的逻辑实现。（P5）计算机实现计算机实现计算机组成的物理实现。 （P5）计算机系统设计的计算机系统设计的3 3种主要方法种主要方法：“由下往上”、“由上往下”、“由中间开始”。（P14）系列机系列机 （P23）兼容性兼容性 （P24）模拟模拟 （P24）仿真仿真 （P24）虚拟机虚拟机 （P24）宿主机宿主机 （P24）并行性并行性 求解一个问题的若干操作在时间安排上的可重叠性。计算机系统结构电子教案81.1.4 冯.诺依曼（Von Neumann）型机器的特点（P22） 传统计算机又称为冯冯. .诺依曼型

6、机器诺依曼型机器，它由运算器、控制器、存储器、输入设备和输出设备5部分组成，并具有如下特点： 1.以运算器为数据流动中枢，以控制器为控制命令中枢； 2.存储程序并且执行，程序象数据一样可以修改； 3.存储器按地址访问，线性顺序编址； 4.程序顺序执行； 5.指令由操作码与操作数两部分组成； 6.数据用二进制编码； 7.机器由硬件与软件组成，硬件功能不能改变。计算机系统结构电子教案91.1.5 现代计算机系统的分类（FlynnFlynn分类法，分类法，P6P6）按照指令流和数据流的多倍性状况把计算机分为：1.单指令流单数据流（SISD-Single Instruction Stream Sing

7、le Data Stream）2.单指令流多数据流单指令流多数据流（SIMD-Single Instruction Stream Multiple Data Stream）3.多指令流单数据流多指令流单数据流（MISD-Multiple Instruction Stream Single Data Stream）4.多指令流多数据流多指令流多数据流（MIMD-Multiple Instruction Stream Multiple Data Stream）例题：P32，题7，题8 ，题9 。计算机系统结构电子教案101.2 定量知识3个性能公式1.2.1 AmdahlAmdahl定律定律（加快

8、经常性事件原理，P9）eeenonSFFTTS)1 (1其中：Sn 全局加速比； To 原执行时间（old）； Tn 新执行时间（new）； Se 被改进部分的局部加速比； Fe 被改进部分原执行时间占原来总时间的百分比。计算机系统结构电子教案11Amdahl定律的推导eeenoneeeoneeooSFFTTSSFFTTFFTT)1 (1 )1 ( )1 (根据加速比定义，有：操作加快，总时间降为改进之后由于其中部分，间可写为：改进之前程序运行总时计算机系统结构电子教案12Amdahl定律的图形 Sn 极限 2 = 211eF 极限 1 = 111eF Fe=Fe2 Fe=Fe1 1.0 （设

9、 Fe2 Fe1） 0.0 1.0 Se图 1.2 Amdahl 定律的图形 从图1.2可以看出，增大Se和Fe对Sn都有提升作用；但当Fe固定时，一味增大Se对Sn的作用会越来越不显著。计算机系统结构电子教案131.2.2 CPI与程序执行时间Te（P11）CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti，易知的加权平均值。为所有，它表明）（或者写为）（的关系与一式，可以得到比较上面第一式与最后写另一方面，我们又可以，iniiiniiiniiiniiiniieniiiiieCPICPICPIICICCPICPIICCP

10、IICCYCLECPIICCYCLECPIICTTICICfCYCLECYCLECPIICTCYCLECPIICT CPICPI)()( 1 其中： 11i1111计算机系统结构电子教案141.2.3 每秒百万指令数MIPS与每秒百万浮点数MFLOPS（P11）。，主要用于向量计算机条数每次浮点运算所需指令；，主要用于标量计算机MIPSMFLOPSCPIfCYCLECPIICICTICMIPSe666101010例题：P10，例1.1例1.5。 P33，题12 ，题13 ，题14 。计算机系统结构电子教案15例题选讲（1） 例1.1（P10）Amdahl定律公式，已知：Fe=0.4，Se=10

11、，求Sn。它说明局部（40%）的大幅度改进（10倍）对全局的作用要小得多（1.56倍）。 例1.2（P10）Amdahl定律公式，已知方案1 ：Fe1=0.2，Se1=10，求Sn1；已知方案2 ：Fe2=0.5，Se2=2，求Sn2 。它说明大范围的小幅度改进（方案2）效果可能更好。计算机系统结构电子教案16例题选讲（2） 例1.3（P11）CPI公式，注意该公式中的指令数百分比不同于Amdahl定律中的时间百分比Fe，避免用错。已知： ICFP / IC = 25%，IC非FP / IC = 75%； IC FPSQR / IC = 2%，IC非FPSQR / IC = 98%。改进前：C

12、PI FP = 4.0，CPI非FP = 1.33； CPI FPSQR = 20，CPI非FPSQR = ？改进后：CPI FP = 2.0， CPI非FP = 老值； CPI FPSQR = 2.0，CPI非FPSQR = 老值。求： 两种方案改进后的CPI。分析： 方案2缺一个条件CPI非FPSQR ，但改进前用两种方法算出 的CPI应该是相同的，所以由 CPI 老 = CPI FP ICFP / IC+ CPI非FP IC非FP / IC = CPI FPSQR ICFPSQR / IC+ CPI非FPSQR IC非FPSQR / IC计算机系统结构电子教案17例题选讲（3）解出CPI

13、非FPSQR = 80 / 49 现在分别用两种方案改进后的参数代入公式，算出新的CPI为1.64和1.5，显然CPI值较小的方案2较好。 教材的解法中有两个小公式值得注意，一个是：iiiiiiICCPICPIICCPICPICPICPIICICCPICPI)()( )( _老新老新新老老新时钟周期数总改变量它的实质就是 另一个公式较容易理解：新老新老CPICPITTSeen_计算机系统结构电子教案18例题选讲（4） 例1.4（P12）Te公式，其中CPI用相应的公式代换CYCLEICICICCPITniiie1)(对A机器，已知CPI转=2，IC转/ICA=20%，CPI非转=1，IC非转/

14、ICA=80%，Te_A=1.2ICA CYCLEA；对B机器，从题义可知， IC比转= IC转， ICB = ICA 80% ， CYCLEB =1.25 CYCLEA，CPI比转=2，所以IC比转/ICB= IC转/（ICA 80% ）=25% ，CPI非比转=1，IC非比转/ICB=75%，Te_B = 1.25ICB CYCLEB = 1.2580%ICA1.25CYCLEA = 1.25ICACYCLEA Te_A显然A机器快一些。计算机系统结构电子教案19例题选讲（5） 例1.5（P12）Te公式，改动上题中CYCLEB =1.1 CYCLEA，则最后Te_B = 1.25ICB

15、CYCLEB = 1.2580%ICA1.1CYCLEA = 1.1ICACYCLEA Te_A这时B机器快一些。 题12 （P33）Amdahl定律公式，代入已知量Se=20变成一元函数Sn=20/(20-19Fe)用三点作图法作出关系曲线。 Sn 2010.51.8 1 0 0.5 1 Fe计算机系统结构电子教案20例题选讲（6） 题13 （P33）Amdahl定律公式，代入已知量Se=20，Sn=2，解出Fe=10/19 题14 （P33）Amdahl定律公式，代入已知量Se=20，Sn=10，解出Fe=18/19计算机系统结构电子教案21本章小结本章小结 本章从定性知识和定量知识两个方

16、面介绍计算机系统结构的基本概念。有关重点如下：(1) 计算机系统结构的广义定义与狭义定义（9项内容），计算机系统结构与计算机组成的主要分工；(2) 计算机系统的多级层次模型（6级），以及基于该模型的透明性判断方法；(3) 计算机实现、计算机系统设计的主要思路、模拟、仿真、虚拟机、宿主机、系列机、兼容性、并行性等重要名词的含义；(4) 冯.诺依曼型机器的7个特点；(5) 现代计算机系统分类的Flynn法（4类）；(6) Amdahl定律；(7) 平均周期数CPI公式，程序执行时间Te公式；(8) 每秒百万指令数MIPS公式，每秒百万浮点数MFLOPS公式。习题：P33，题15，题19 ；P392

17、，题10，题11，题12 。计算机系统结构电子教案22第二章第二章 指令系统（指令系统（P36P36） 本章介绍指令系统设计中2个最基本的内容：数据表示、操作码优化。2.1 数据表示 数据表示数据表示就是计算机硬件能够直接辨认与处理的数据类型。人们通常使用的数据类型有整数、实数、逻辑数（布尔数）、字符串、队列、堆栈、链表、文件等，它们的运算方法各不相同。 所谓“硬件能够直接辨认与处理”，指的是对该数据类型的各种运算操作都有相应的实现硬件电路。 硬件不能直接辨认与处理的数据类型就要根据数据结构的知识编制软件转化为硬件能处理的数据类型。 下面介绍通用型计算机数据表示集合中的一个基本成员 浮点数据的

18、分析与设计。计算机系统结构电子教案232.1.1 浮点数据表示（P38，P39） 浮点数据就是高级语言课程中所说的“实型数”。 2.1.1.1 浮点数的组成 浮点数的组成与人们通常所说的“科学记数法”非常相似，唯一不同的是各部分均为有限位数，如下所示emrmN它的主要参数有8个： m 尾数，一般为纯小数，符合规格化原则（即最高位的绝对值不为0），用原码原码或补码补码表示； e 阶码，整数，常用移码移码表示（见下文解释）； rm 尾数的基值，简称尾基，常见的有2进制、8进制、16进制、10进制等，选定以后不变； re 阶码的基值，简称阶基，目前都采用2，也是选定以后不变； p 尾数的位数，未将符

19、号位计入； q 阶码的位数，未将符号位计入。 mf 尾数的符号，表示数的正负，简称数符； ef 阶码的符号，表示阶码的正负，简称阶符。但对移码表示来说，这仅仅是额外的1位2进制数，不决定正负。计算机系统结构电子教案24移码（P41） 移码是一种2进制记数方法，它的真值等于相同编码的无符号数加上一个指定的偏移量d。例如，同样是2进制编码000000 111111，看作6位无符号数时的取值范围是0 63，而看作6位移 -10码的取值范围就是 10 53。如下图所示。 移码是一种有符号数，但它的最高位通常不决定数的正负，不应称为符号位。它的独特之处在于其最小取值的2进制编码是全0，这给机器零的判断和

20、处理电路设计带来很大方便。十进制真值 63 无符号数 53 移 -10 码 0 111111-10 二进制编码图 2.1 移码与无符号数的比较实例计算机系统结构电子教案252.1.1.2 浮点数的机内格式（P39） 一种浮点数中每个数据的尾基rm、阶基re都是相同的，在设计运算电路已经作为默认值来使用，各个具体数据在存储时只需要存入如下参数即可：各字段位数： 1 位 1 位 阶码 q位 尾数 p位浮点数字段： mf ef eq-1 e0 . . m1 mp对应位的权： req-1 re0 rm-1 rm-p 隐含小数点 图 2.2 浮点数的机内格式计算机系统结构电子教案262.1.1.3 浮点

21、数的性能（P38） 浮点数的性能主要用表数范围、表数精度和表数效率来刻画，下面分别进行分析。 (1) 表数范围（P39） 表数范围由这样一些参数构成：最小负数、最大负数、最小正数、最大正数、最小绝对值|N|min、最大绝对值|N|max。它们几何意义可以在数轴上表示，如下图。 - 最小负数 最大负数 0 最小正数 最大正数 + 图 2.3 数轴上的表数范围示意图 图中阴影部分为浮点数的表数范围。 根据浮点数的组成表达式可知，图2.3中4个边界值分别由尾数m、阶码e各自的边界值两两组合而成，如下所示。 最大正数 最大正尾数/最大阶码； 最小正数 最小正尾数/最小阶码； 最大负数 最大负尾数/最小

22、阶码； 最小负数 最小负尾数/最大阶码。计算机系统结构电子教案27 例2.1 对规格化浮点数，尾数为原码，阶码为移 码，写出表数范围。（P40）11)1 (qeqermpmrmmrrNrrqer解：由于原码在数轴的零点两边对称分布，即最大正数与最小负数的绝对值相等、最小正数与最大负数的绝对值相等，所以可以用最小、最大绝对值来描述它的分布。首先根据图2.2和式2.1以及移码的基本定义，可以确定绝对值的极值表达式：。，又；，drmpmqepmdmmmqerrNdrermrrNderm12maxmaxmax1minmin1min)1 (12)1 (写在一起就是：drmpmdmmqerrNrr121)

23、1 (再用阶码的偏移量代换式中的-d得：计算机系统结构电子教案28可以代入具体数字来帮助理解：，如下图所示。，于是有：按此题约定，。，设3101min3min1min31010 101010310410Ndemdqrprem，如下图所示。，1104max3333max4max310)101 (1101011021102)101 (Ndem 1 位 1 位 阶码 3 位 尾数 4 位 x 0 0 0 0 . . 1 0 0 0 1 位 1 位 阶码 3 位 尾数 4 位 x 1 9 9 9 . . 9 9 9 9计算机系统结构电子教案29(2) 表数精度（P42）数轴N k 真实值 x N k+

24、1图 2.4 最大绝对误差示意图empmemkkkkrrrmmNN21)(21)(2111max 表数精度用最大表数误差表示（指相对误差）； 最大绝对误差最大绝对误差是真实值与可表示值之间的可能最大距离，也就是相邻两个可表示值间距的1/2，如图2.4所示。根据浮点数的组成式有其定义：显然它随着阶码e增大而增大，不是一个定数。计算机系统结构电子教案30最大相对误差最大相对误差与阶码e无关，但与尾数m的值有关。它的定义是pmemempmrmrmrrN12121maxmax上式中，当分母|m|取最小值时分式值达到最大。限为，所以最大相对误差上由于 21 )1(max01pmmmrrmr计算机系统结构

25、电子教案31(3) 表数效率（P45）定义：mmmqepmqepmmmrrrrrrrrr1112212) 1(2)(1可以生成的浮点数个数其中规格化浮点数个数此式说明效率之所以低于100%，是因为规格化的尾数最高位m1只能有rm-1种取值的缘故。可以看出， 的极小值与极大值分别是%100)(lim%50112)2(mrrm， 隐藏位技术隐藏位技术是一种提高表数效率的方法，但仅适用于rm=2的情况：尾数最高位m1 在二进制条件下只有0和1两种可能，按照规格化要求， m1 可由其它位推出，。“隐藏”了m1之后，尾数只存储后面p-1位，它们中的任一位都有rm种取值，所以表数效率=100%。计算机系统

26、结构电子教案322.3 指令格式的优化（P90）2.3.2 操作码优化 目前常用的编码方法有3种：定长编码，Huffman编码，扩展编码。2.3.2.1 定长编码定长编码就是所有指令使用相同的代码位数，其最小码长等于nLoglLi2式中 是平均码长， 是第i种指令的码长，n是指令总数。 例2.2 已知 n = 15，求定长编码的最小平均码长。解：Lil4152 LogL计算机系统结构电子教案332.2.1.1 Huffman压缩编码（P91）(1)Huffman压缩概念（最佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码给高概率事件、把长代码给低概率事件的原则分

27、配，可使平均码长达到最低。(2) Huffman编码方法 这种编码方法由两个过程组成。频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树 Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根；码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由于频度高的事件较晚被合并，它的编码位数也就

28、较少，符合Huffman压缩原则。 上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。计算机系统结构电子教案34(3) 编码方法性能指标（P91-P93） 信息量信息量：根据信息论的基本知识，在n种可能发生的事件集合中，报告第i种事件发生的消息中包含的信息量为iaiaiPPIlog)1(log 其中Pi是第i种事件发生的先验概率，a是编码基值。信息量的单位是表示位数（最少所需位数）。 这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大。 熵熵（entropy） 平均信息量平均信息量：一个消息源对n种事件发布的消息的信息量平均值，记为niiainiiiPPIPH

29、11)(log)(计算机系统结构电子教案35 平均码长平均码长：各事件编码长度的数学期望。niiilPL1)( 信息冗余量信息冗余量：它表明消息编码中“无用成分”所占的百分比。%100LHLR 从减少存储与传输量的角度看，编码方法的平均码长越短越好。但是平均码长不可能无限制缩短，它的下限就是熵（即R=0时）。如果短于熵就一定会丢失有用信息（即混淆不同指令），这是不允许的。计算机系统结构电子教案362.2.1.2 扩展编码方法（扩展编码方法（等长扩展法，P93） 用码长表示：例如4-8-12法。这并不能说明具体编码方法，例如下面两种编码方法都是4-8-12法。 用码点数表示：例如15/15/15

30、法，8/64/512法 15/15/15法，每一种码长都有4位可编码位（前头可以有相同的扩展标识前缀），可产生16个码点（即编码组合），但是至多只能使用其中15个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。这就是“非前缀原则”。 8/64/512法，每一种码长按4位分段，每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。计算机系统结构电子教案37 例2.3 已知频度序列为0.1，0.1，0.15，0.15，0

31、.2，0.3，求Huffman编码、等长扩展3/3/3码、定长编码、三者的平均码长、信息冗余量以及熵。解： 熵H= (20.1log20.1+20.15log20.15+0.2log20.2+0.3log20.3)2.47 根据Huffman编码方法作Huffman树如图2.5所示，三种编码方法的结果列于表2.1中。 1.0 0 1 0.4 0.6 0 1 0 1 0.2 0.3 0 1 0 1 0.1 0.1 0.15 0.15 0.2 0.3图 2.5 Huffman 树计算机系统结构电子教案38表2.1 Huffman编码、等长扩展3/3/3码及定长编码指令I1I2I3I4I5I6频度0

32、.10.10.150.150.20.30000011001010111Huffman 码平均码长L=2.5，信息冗余量 R1.2%1110110111001001003/3/3 码平均码长L=2.7，信息冗余量 R7.5%000001010011100101定长编码平均码长L=3.0，信息冗余量 R17.7%计算机系统结构电子教案39 2.2.2 操作数优化寻址方式比较（P95） 指令中操作数占用的位数由操作数的个数与寻址方式决定。 按操作数的个数划分，有零操作数指令、一操作数指令、二操作数指令、三操作数指令共四种形式。应该按机器用途来选择（P99，表2.20）。 缩短操作数长度的常用方法是间

33、址和变址（P99页末）。计算机系统结构电子教案40 本章主要内容有数据表示和操作码优化两个部分。具体细节如下：(1) 浮点数的表数范围（在数轴上的4个端点）、表数精度、表数效率；(2) Huffman编码方法；(3) 等长扩展编码方法（15/15/15法，8/64/512法）；(4) 编码方法性能指标（熵H，平均码长L，信息冗余量R）。习题：P124，题3（忽略P124倒1行 P125第8行文字），题13。本章小结本章小结计算机系统结构电子教案41第三章第三章 存储系统（存储系统（P130P130） 长期存在的问题：在合理的总价格限制下，单纯性主存设备的速度跟不上CPU的发展，容量不能满足软件

34、尺寸扩大。 本章学习两种提高主存系统性能/价格比的结构化方法：并行存储器与存储层次技术。后者为主。计算机系统结构电子教案423.1 并行存储器（并行存储器（P136P136） 并行存储器技术可以提高主存系统的整体等效速度，实际应用中，常将它与存储层次技术组合使用，可以互为补充，获得很高的性能。 并行存储器技术的基本思想是用多个独立的存储部件组成主存系统，让它们并行工作，在一个存储周期内可以访问到多个数据，从而实现较高的存取流量。 并行存储器包括多种类型，我们仅介绍提高访问速度效果最显著的低位交叉访问这一种。计算机系统结构电子教案43低位交叉访问并行存储器的结构： 它由n个存储体组成（一般n为2

35、的整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址低位字段（最低的log2n位）作为体选译码信号，而剩下的高位字段则是体内地址。如图所示（设 n = 4）。 地址总线 体 0 体 1 体 2 体 3地址译码器地址译码器地址译码器地址译码器0123456789101112131415数据缓冲器数据缓冲器数据缓冲器数据缓冲器 数据总线计算机系统结构电子教案44主存地址与结构参数的换算（P139）：nAknAjkjnAmod ，求结构参数：求主存地址：其中：n 存储体个数，A 主存地址， j 体内地址， k 体序号（ k = 0，1，2，n-1 ） 例3.1 已知 n = 4，问主存地址

36、13是在几号体的几号单元？解： 由于 n = 4，体选译码信号使用主存地址的最低 log2n = 2位，所以地址13（其二进制为1101B）对应的体号k = 1（即01B）、体内地址j = 3（即11B），也就是说，地址13位于1号体的3号单元（参看前一页插图）。根据上式，所有k值（即体号）相同的地址之间均相差n的整倍数，称之为“模n同余”。计算机系统结构电子教案45低位交叉访问并行存储器的加速机理： 我们衡量存储器件速度的常用指标是存储周期Tm，它是同一存储单元连续两次启动的最小时间间隔，数值越小表明存储器件速度越快。 传统存储系统只有一套地址译码器和数据缓冲器，所以各单元必须串行工作，也就

37、是说每个Tm周期内至多只能完成一次访问。 由多个存储体构成的并行存储器中，各个存储体都有独立的地址译码器和数据缓冲器，它们可以并行工作，使得一个Tm周期内可完成多次访问，相当于加速了多倍。最好情况下一个Tm周期内可完成n次访问。 当前Tm周期中只要发现有一个新的访问地址与前面地址属于同一个存储体，该地址及其后面的地址就会被阻塞（称为访存冲突）,留到下一个Tm周期访问。 机器地址序列常常具有顺序性，按照低位交叉的规律分配地址可使相继出现的地址落在相同存储体的概率降到最低（参见上图）。 考虑到地址总线与数据总线的拥挤问题，一个Tm周期里发送的多个访问请求最好彼此错开Tm/n时间，如P140图3.1

38、1所示，否则实现的复杂度会增加。计算机系统结构电子教案46 K g=010.0 g=0.24.463.682.00 g=0.51.00 g=1 0 1 10 n计算平均加速倍数（P141）：1.只考虑取指地址序列（假设地址顺序递增，直至出现一条转移指令）：倒数第一行）（ 141 )1 (1PggKn 其中g是指令序列中出现转移指令的概率。此公式在右图中用绿线表示。2.只考虑取数地址序列（假设地址完全随机）28. 02/nK此公式在右图中用红线表示。计算机系统结构电子教案47例题：P203，题5。也对（文字理解差异）取。向下取整，得解出，得依题意有，其中，解：已知161 1528.159 . 0

39、lg2 . 0lg 2 . 09 . 02 . 0)1 (12 . 0)1 (1 1 . 0 )1 (111nnggKggKgggKnnnnnnn计算机系统结构电子教案483.2 存储层次原理及性能指标 3.2.1 基本原理 定义：（参见P131第二段） 由2种或多种存储部件构成的复合存储系统，通过内部管理机构的自动更换机制，能够不断将大容量低速存储部件中的活跃内容复制到小容量高速存储部件中（后者作为前者的局部副本）。 它既能满足CPU的快速存取需要，又有很大的存储容量，平均单位价格也很低，等效于同时满足3方面要求的理想单一存储部件。 依据：程序访问的局部化原理（时间局部化，空间局部化）。 模

40、型：如右图所示，存储层次由n层组成， 满足3个不等式：TiTi+1，Sici+1。CPUM1M2Mn图 3.3 存储层次模型计算机系统结构电子教案493.2.2 性能指标（P132-P134） (1) 容量：S=S2 （理论上） (2) 单价：（美分/bit）2021212121221121lim1ccSSccSSSSScSccSS它的最小值是计算机系统结构电子教案50(3) 速度：表现访问速度的参数很多 命中率：反映被访问数据事先已在M1的发生概率 等效访问时间：命中时的访问时间为T1，不命中时的访问时间为T2，等效访问时间则是它们的概率均值10211HNNNH，21)1 (THTHT1%1

41、00limTTH计算机系统结构电子教案51 访问效率：这是一个相对值，便于不同系统之间的比较。，ereH e r = 11.0 r = 20.5 r = 100.10.0 0 1 HH 和 r 对 e的作用访问效率e受H和r的影响（参见右图）：是邻级速度比）。（，其中rTTre11012HrrrHHTHTHTTTe)1 (1)1 (1)1 (2111计算机系统结构电子教案52 Cache预取技术对命中率的提高作用（P134）： 这里所说的“预取”技术，并不是根据对程序执行的未来趋势进行猜测以提前调入数据，而仅仅是在发生不命中情况时把调入1个数据字改为调入1个数据块的策略。根据程序的局部化原理，

42、在当前使用数据周围的其它数据未来被使用的几率大于远处数据，所以该数据块中被提前调入的邻近数据很可能成为未来的命中点，从而提高命中率。 采用这种预取技术后新的命中率为nnHH1其中：H 原命中率（即按照不命中时取入1字的策略）； H 新命中率（即按照不命中时取入1块的策略）； n 每块数据平均被访问次数。计算机系统结构电子教案53 按照定义，原不命中率 ，新不命中率 ，并且有 。由于预取使得每块数据中的不命中次数由n次降低到1次，所以有 。此式可改写为 ，整理得 。H的推导：2121NNNH1212NNNH2121NNNN221NnN 1122HHNNnnnHH1计算机系统结构电子教案54 加速

43、比（P193） Cache-主存层次的主要作用是提高访问速度，系统的等效速度应高于主存（即M2）的原有速度，两个速度之比称为加速比。rHHTHTHTTTMMSp/)1 (1)1 (212222等效时间时间速度等效速度计算机系统结构电子教案55 M1 103B T1=1us 103B M2 106B TB2=10usM3 109B TB3=100us 109B (a) (b) 例3.2 有一个109字节的程序被装入右图所示的M3准备运行。假定指令字长=1字节，程序中无转移指令和内存读/写指令。 (1)按图(a)求T和e； 增加中间层对e的影响(2)按图(b)推导三层体系的T公式；(3)按图(b)

44、求T和e；(4)比较(1)(3)结果，有何结论？计算机系统结构电子教案56解：32122111322211132222211111323333311131331)1 ()1 ()1 ( )1 ()1 ( 2 )1 ( )1 ( )2(%91 %)101 (1011010100101110110 )1 ( 1011 10110 ) 1 (BBBBBBBTHHTHHTHTHTHHTHTTHTHTTHTHTTTeTsssTHTHTHH式有由上面，计算机系统结构电子教案57效率提高。层间速度差减少，访问结论：插入中间层后， )4(%99 %)11 (101010101010 1001011010110

45、101110110 1011 ,10110 )3(116234633333332332TTeTssssTHH习题： P202，题3。计算机系统结构电子教案58存储层次的管理方式(P148) 根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在3种存储层次管理方式。(1)段式管理段式管理(P148)。段是程序中的一个逻辑单位，可以是一个程序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。 每段使用独立的逻辑地址空间，即都从0开始计算地址。 段式管理方法的主要缺点是各段长短不一，调进调出之后容

46、易形成大量不规则的零碎空间。 段式管理方法的虚实变换算法是查段表(P150)。计算机系统结构电子教案59(2)页式管理页式管理(P151)。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。 我们把用户文件划分得到的一个长度单位称为“虚页虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页实页”。 页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。 页式管理方法的虚实变换算法是查页表(P152)。(3)段页式管理段页式管理(P153)。它把上述两种管理方式结合起来，首先将整个文件分段，然后

47、在各段内分页，所以有一个段表和若干个页表。其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表(P154)。 段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。 由于段页式管理方法的最小调度单位仍是页，或者说它是分段之后的分页管理，为了叙述简单，下面的分析还是以页式管理为模型。计算机系统结构电子教案603.3 地址映象与变换(P174)基本术语：基本术语： 逻辑地址逻辑地址（又称为相对地址相对地址、虚地址虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间逻辑地址

48、空间、虚空间虚空间或虚存虚存。 物理地址物理地址（又称为绝对地址绝对地址、实地址实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间物理地址空间、实空间实空间或实存实存。 从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。 地址映象地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。 地址变换地址变换（又叫虚实变换虚实变换）指逻辑地址到物理地址的变换过程或者算法。 页失效页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。 实页争用实页争用又叫实页冲突实页冲突，指虚页调入时，根据地址映象方式划定的实空间

49、范围内已没有空闲实页的状况。计算机系统结构电子教案614种常见的地址映象方式3.3.1 全相联(P174) 全相联全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。这种关系可用下页示意图(a)、(b)表示。 全相联的虚实变换信息完全来自于变换表，查表过程如图(c)所示。 全相联映象方式使虚页调入有最大的选择范围，发生实页争用的可能性最小，调入/调出的操作开销也最少，有利于命中率提高。但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高，在命中情况下花费在虚实变换上的时间也比较多。 由于页表必须常驻在实存中，而主存-辅存层次的实存（即主存）相对C

50、ache-主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象方式一般用于主存-辅存层次。计算机系统结构电子教案62全相联的地址映象方式与地址变换原理示意图(a)(b) 虚存 实页0123 00 1 实存1 202 31虚 3 42页 4 535 66 77 (a) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系）计算机系统结构电子教案63全相联的地址映象方式与地址变换原理示意图(c)虚地址虚页号 P页内偏移量 D实地址实页号 p页内偏移量d实页号 装入位 修改位表项 0 ： ： ： ： ：表项 P p1 0 ： ： ：表项 7 ： ：(c) 通过查表进行虚实变换计算机系

51、统结构电子教案643.3.2 直接相联(P176) 直接相联直接相联是一种最强的约束关系，它规定每个虚页只对应唯一的实页。为了便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现起来非常简单，因为在二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位，如下页示意图(c)所示。 例3.3 已知虚页号 = 7，实页总数 = 4，用直接相联求实页号。解： 可用十进制形式求：7 mod 4 = 3； 也可用二进制形式求：由于n = 4，所以log2n = 2，取7的二进制形式111B的最低2位，得11B，即3。 直接相联映象方式不需要借助页表来进行虚实变换，显然

52、大大节省了相应的空间与时间（当然页表中的装入位和修改位还得保留），但是由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率大大下降。 这种映象方式主要用于一些对实存价格非常敏感的Cache-主存层次。计算机系统结构电子教案65直接相联的地址映象方式与地址变换原理 虚存 实页0123 00 1 实存1 202 31虚 3 42页 4 535 66 77(a) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系）虚地址 虚页号 1 1 1页内偏移量 D实地址实页号 1 1页内偏移量d(c) 通过

53、求模运算进行虚实变换示例计算机系统结构电子教案663.3.3 组相联(P178) 组相联映象方式是全相联与直接相联的一个折中方案，性能也是二者的折中。具体做法是先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。所有虚组按照直接相联方式映射到实组集合，对应的虚实组之间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。 由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，首先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”。如图(c)所示。 采用组相联映象方式

54、时，每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低；另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。当然这两方面优点是互相抵触的：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。 这种映象方式性价比较好，在Cache-主存层次中被普遍使用。计算机系统结构电子教案67组相联的地址映象方式与地址变换原理(a)(b) 虚存 实页0123虚组 0 00 1 实存1 虚组 1 20 实组 02 31虚

55、3 虚组 2 42 实组 1页 4 535 虚组 3 66 77 (a) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系）计算机系统结构电子教案68组相联的地址映象方式与地址变换原理(c)虚地址 虚组号 1 0 组内页号 1 页内偏移量 D实地址实组号 0 组内页号 0 页内偏移量 d0 组子表 项 0 ： ： ： 项 1 ： ： ：1 组子表 项 0 ： ： ： 项 1 ： ： ：2 组子表 项 0 ： ： ： 项 1 0 装入位 1 ：3 组子表 项 0 ： ： ： 项 1 ： ： ：(c) 求模运算与分组查表结合进行虚实变换示例计算机系统结构电子教案693.3.4 段相联(P

56、184) 段相联映象方式也是全相联与直接相联的一个折中方案。它的分段方法与组相联相同，不同的是所有虚段按照全相联方式映射到实段集合，对应的虚实段之间各页则用直接相联映射（因为虚实段大小相同，所以实际上是一一对应），如下页示意图(a)、(b)所示（设实段数为2）。 段相联的虚实变换与组相联类似，不过可以通过计算来确定的部分不是在段外，而是在段内，即页表内只储存各虚页对应的实段号，段内页号则从虚页号中简单直接复制，拼接在一起就是实页号，简记为“段号查表、段内复制”。如图 (c)所示。 段相联映象方式的虚实段内页号对应关系是固定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相同，所以虚段号

57、比实段号位数多，也就意味着“多少”的映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。计算机系统结构电子教案70段相联的地址映象方式与地址变换原理(a)(b) 虚存 实页0123虚段 0 00 1 实存1虚段 1 20 实段 02 31虚 3虚段 2 42 实段 1页 4 535虚段 3 66 77(a) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系）计算机系统结构电子教案71段相联的地址映象方式与地址变换原理(c)虚地址 虚段号 1 0 段内页号 1 页内偏移量 D实地址实段号 0 段内页号 1 页内偏移量 d0 段子表 项

58、 0： ： ： 项 1： ： ：1 段子表 项 0： ： ： 项 1： ： ：2 段子表 项 0： ： ： 项 10 装入位 1 ：3 段子表 项 0： ： ： 项 1： ： ：(c) 查表求实段号进行虚实变换示例计算机系统结构电子教案72多用户虚地址格式 在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从CPU发出的虚地址还需要在前面拼接上一个“当前用户号”字段，形成“多用户虚地址”，如下图所示(参见P154)。 在虚实变换时，上面所说的各种查表操作之前还得先去查一个“段表基址寄存器组”或“页表基址寄存器组”的小表格(P150，P15

59、2)，确定现在该查哪一张段表或页表。这个小表格建立在CPU里，读写时间很短。当前用户号虚段号虚页号页内偏移量计算机系统结构电子教案733.4 替换算法(P164) 上面所讲的地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。 不命中时需要增加的操作就是首先调出一页，调出之后再调入称为 “替换”。 替换算法要解决的是选择调出对象的问题。 替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。计算机系统结构电子教案743.4.1 几种常用的替

60、换算法(P164)(1)随机算法RAND 在比较范围内任取一页作为淘汰页；(2)先进先出算法FIFO 在比较范围内选取调入最早的一页作为淘汰页；(3)最不经常使用算法LFU 在比较范围内选取最近单位时间内使用次数最少的一页作为淘汰页；(4)最不接近使用算法LRU 在比较范围内选取最后一次使用离现在最久的一页作为淘汰页；(5)最优替换算法OPT 在比较范围内选取下一次使用时间离现在最久的一页作为淘汰页。计算机系统结构电子教案75实例：实存状况图(P166图3.32)例如 LRU 算法（其中*号表示被选中的淘汰页）：已访问次数 t012345678910被访问虚页号无1215413424命中总次数