? 采用Huffman编码法所得到的操作码的平均长度
=0.45×1+0.30×2+0.15×3+0.05×4 +0.03×5+0.01×6+0.01×6=1.97(位)
? 采用最优Huffman编码法，操作码的最短平均长度
=0.45×1.152+0.30×1.737+0.15×2.737 +0.05×4.322+0.03×5.059+0.01×6.644 +0.01×6.644=1.95(位)
采用3位固定长操作码的信息冗余量为：
1.95Huffman编码法的信息冗余量仅为： R?1??1.0%1.971.97与3位定长操作码的冗余量35%相比要小得多 1?HR??1??35%log73?2?Huffman操作码的优点：平均长度最短，信息的冗余量最小；
(2) 等长扩展法
? 为了便于实现分级译码，一般采用等长扩展法；
? 根据不同的扩展标志，对于等长扩展法还可以有多种不同的扩展方法，衡量
的标准主要看这种编码方法的操作码的平均长度是否最短，或信息量的冗余量是否最小；
? 用码长表示：例如4-8-12法。
? 这并不能说明具体编码方法，
? 如下面两种编码方法都是4-8-12法。
? 用码点数表示：例如15/15/15法，8/64/512法 15/15/15法
① 每一种码长都有4位可编码位(前面可以有相同的扩展标识前缀)，可产生16个码点
(即编码组合)；
② 使用其中15个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识前缀；
8/64/512法
① 每一种码长按4位分段
② 每一段中至少要留下1位或多位作为扩展标识，各段剩余的码位一起编码，所产生
的码点用来对应被编码事件
③ 每一段中的标识位指出后面还有没有后续段。 (3) 不等长编码法
不等长操作码扩展编码法(4-6-10扩展
编码) 各种不同长度操作码的指令 编码方法 指令种类 4位操作码 6位操作码 10位操作
码 15/3/16 15 3 16 34
8/31/16 8 31 16 55
8/30/32 8 30 32 70 8/16/256 8 16 256 280 4 32 256 292 4/32/256
小结
? 操作码优化的主要目的：尽可能地减少各种信息冗余，即：
? 空间、时间少、短，尽可能不要跨断；
? 要想程序占地空间小，则应使操作码尽可能短。
第五章：时空图
为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。
记c1=A1×B1，……，c6=A6×B6，下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。
根据时空图(b)得
? TP = 11/(22Δt) = 1/(2Δt)
? S = (6×4Δt + 5×4Δt)/(22Δt) = 2 ? E = (6×4Δt + 5×4Δt)/(6×22Δt) = 1/3
非线性流水线的调度技术
? 非线性流水线的调度问题：在非线性流水线的输入端，究竟每间隔多少个时钟周期
向流水线输入一个新任务才能使流水线的各个功能段都不发生冲突。
? 非线性流水线的调度的任务：找出一个最小的循环周期，按照这个周期向流水线输
入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。 ? 以下首先介绍非线性流水线的表示方法，然后分析冲突情况，最后介绍无冲突调度
方法。
非线性流水线的表示
? 一条非线性流水线的一般需要一个各功能段间的 连接图和一张预约表共同表
示。
? 下图是一条4个功能段组成的非线性流水线，它有从S1到S4 的单方向传输线。
但它有两条反馈线和一条前馈线；输出端不一定在最后一个功能段，而可能从任意一个功能段输出。
非线性流水线的预约表
对于非线性流水线预约表的说明
? 预约表的横坐标表示流水线的时钟周期，纵坐标表示流水线的功能段，中间有“× ”
的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这一个时钟周期不处于工作状态。
? 预约表行数是非线性流水线的段数；而列数是一个任务从进入流水线到从流水线中
输出所经历的时钟周期数。
? 一张非线性流水线的预约表可能与多个非线性流水线连接图相对应；同样，一个非
线性流水线的连接图也可能对应有多张预约表。
非线性流水线的冲突
? 非线性流水线的启动距离：向一条非线性流水线的输入端连续输入两个任务之间的
时间间隔。
? 非线性流水线的冲突：当以某一个启动距离向一条非线性流水线连续输入任务时，
可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况。
? 上图所示的非线性流水线中，当启动距离为3时，冲突情况如图：
无冲突调
度方法
? 目标：找出具有最小平均启动时间的启动循环，按照这样的启动循环向非线性流水
线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。
? 步骤：1、根据预约表求禁止向量进而得到冲突向量。冲突向量是一个M位 的二进
制数表示，其中M是禁止向量中的最大值。一般的禁止向量用C=（CmCm-1 … C2C1 )表示。如果I在禁止表中，则 Ci=1，否则Ci=0。其中Cm一定为1，因为m必定在禁止表中。如上图所示的预约表，其冲突向量C=（101100）。
3.2 虚拟存储器
? 虚拟存储器由主存储器和联机工作的外部存储器共同组成。 ? 在目前的计算机系统中，
? 主存储器通常用动态随机存储器(DRAM)实现，它的存储容量相对比较小，
速度比较快，单位容量的价格比较贵。
? 联机工作的外部存储器通常为磁盘存储器，它的存储容量很大，与主存储器
相比，速度很低，单位容量的价格很便宜。
? 这两个存储器在硬件和系统软件的共同管理下，对于应用程序员，可以把它们看来
是一个单一的存储器，是一个存储容量非常大的主存储器。 ? 虚拟存储器又称虚拟存储系统，或虚拟存储体系等，
? 其概念是1961年英国曼彻斯特大学的Kilbrn等人提出的。 ? 到了70年代被广泛地应用于大中型计算机系统中。
? 目前，许多小型计算机，甚至微型机也使用虚拟存储器。
虚拟存储器工作原理
? 页式、段式和段页式三种虚拟存储器 ? 页式虚拟存储器
? 把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的页， ? 主存储器的页称为实页，
虚拟存储器中的页称为虚页。 地址变换
? 一个用户程序要访问虚拟存储器时，必须给出多用户虚拟地址Av。 ? 在操作系统和有关硬件的共同管理下，首先进行内部地址变换。如果变换成功(命中)，
得到主存实页号p。而多用户虚拟地址中的页内偏移D可以直接作为主存实地址中的页内偏移d，这样，只要把主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A。于是，就可以用这个主存实地址A去访问主存储器 ? 如果内部地址变换失败(未命中)，表示要访问数据不在主存储器中，必须访问磁盘存
储器。这时，要进行外部地址变换。外部地址变换主要用软件实现，首先查外页表得到与虚页号P相对应的磁盘存储器的实地址，然后再查内页表(主存实页表)，看主存储器中是否有空页。如果主存储器中还有空页，只要找到空页号。把磁盘存储器的实地址和主存储器的实页号送入输入输出处理机(输入输出通道)等，在输入输出处理机的控制下，把要访问数据所在的一整页都从磁盘存储器调入到主存储器。