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

计算机系统结构复习 计算机系统结构 第二版 华中科技大学出版社 计算机系统结构 第二版 华中科技大学出版社 复习 一 考试方式笔试 开卷二 考试时间100分钟三 考试题型 1 填空题 2 单选题 3 判断题 4 名词解释 5 简答题 6 设计与计算题四 复习范围与重点 计算机系统结构 第二版 华中科技大学出版社 第1章计算机系统结构的基本概念 1 层次结构 P1 从计算机语言的角度 可将通用计算机系统划分成多级层次结构 每一层以一种不同的语言为特征 按由低层到高层的顺序 各层分别是 微程序机器级传统机器语言机器级操作系统机器级汇编语言机器级高级语言机器级应用语言机器级 计算机系统结构 第二版 华中科技大学出版社 2 透明性 P3 从计算机系统的某一层的使用者角度看 只需通过该层的语言就可以使用机器 而不必关心其下层的机器级是如何工作和如何实现对上层的支持 计算机系统的 透明 是看不到的意思 即对某一层的使用者来说 他看不到该层以下各层的机器属性 计算机系统结构 第二版 华中科技大学出版社 12 并行性 P5 同一时刻或同一时间间隔内发生两种或两种以上性质相同或不相同的事件 13 同时性 P6 两个或多个事件在同一时刻发生 14 并发性 P6 两个或多个事件在同一时间间隔内发生 计算机系统结构 第二版 华中科技大学出版社 15 提高计算机系统的并行性的3类技术途径 P6 时间重叠资源重复资源共享 计算机系统结构 第二版 华中科技大学出版社 第2章指令系统 1 操作码编码的3种方法 P30 定长 等长 编码哈夫曼编码扩展编码2 定长编码 P30 所有指令的操作码长度都是相等的编码方法 如果需要编码的操作码有n个 定长操作码的位数最少需要位 计算机系统结构 第二版 华中科技大学出版社 3 哈夫曼 Huffman 编码 P30 使用哈夫曼算法构造哈夫曼树来进行编码的编码方法 构造哈夫曼树的算法 从结点集中选择出2个频度最小的结点 将其合并成频度为这两个频度之和的父结点 若结点集不为空集 就将生成的新结点放到结点集中 继续从这个新的结点集中选择出2个频度最小的结点生成其父结点 若结点集为空集 就生成了一棵哈夫曼树 对每个结点的两个分支分别用 0 和 1 标识 从根结点到一个叶结点的路径 由0和1组成的序列 就是这个叶结点的哈夫曼编码 计算机系统结构 第二版 华中科技大学出版社 4 扩展编码的2种表示方法 P30 码长表示法 用短横线前后的数字分别表示短码码长和长码码长 码点数表示法 用斜线前后的数字分别表示短码码点个数和长码码点个数5 平均码长 P30 计算机系统结构 第二版 华中科技大学出版社 例2 3 2 15 2 16 2 17 计算机系统结构 第二版 华中科技大学出版社 第3章流水技术与流水处理机3 1指令重叠与先行控制 1 指令顺序执行方式 P44 指令之间顺序串行 且指令内的各个阶段之间也是顺序串行执行的方式 2 指令重叠执行方式 P45 如果处理机在结构上能使执行指令各阶段功能的部件或段 segment 相互独立 而且各段完成相应功能的所需时间尽可能相等 那么 就可以把一个指令序列中的多条指令在时间上重叠起来执行 计算机系统结构 第二版 华中科技大学出版社 3 2流水线的分类与时空图 3 流水处理方式 P47 把一个需要反复进行的过程分离为若干独立的子过程 每个子过程与其他子过程同时处理不同的对象 流水处理方式是利用时间重叠的并行技术来开发计算机系统的并行性 计算机系统结构 第二版 华中科技大学出版社 3 2 1流水线的分类 1 部件级流水线 处理机级流水线和系统级流水线 P47 部件级流水线由部件内各子部件组成的流水线 处理机级流水线处理机内的各部件之间的流水线 系统级流水线处理机之间的流水线 它又称为宏流水线 计算机系统结构 第二版 华中科技大学出版社 2 线性流水线与非线性流水线 P48 线性流水线流水线的各个段之间串行连接 处理对象顺序流经流水线各段最多一次的流水线 非线性流水线流水线的各段之间除有串行连接之外 还有反馈回路 从而使处理对象流经某个段或某几个段多次的流水线 计算机系统结构 第二版 华中科技大学出版社 3 单功能流水线与多功能流水线 P48 单功能流水线流水线的各段之间的连接固定不变 因此只能完成一种固定功能的流水线 多功能流水线流水线的各段之间可以实现不同的连接 流水线能通过不同的连接实现不同的处理功能 计算机系统结构 第二版 华中科技大学出版社 4 静态流水线与动态流水线 P48 静态流水线在同一段时间内 多功能流水线只能实现一种连接 从而只能执行一种功能 且只有在按照这种连接已流入的所有处理对象都流出流水线后 才能重新连接以实现另一种功能 动态流水线在同一段时间内 多功能流水线的各段可以实现多种连接 从而同时执行多种功能 流水线中的任何一个功能段只能参加到一种连接中 计算机系统结构 第二版 华中科技大学出版社 3 3线性流水线的性能计算 流水线的吞吐率 P51 流水线单位时间输出结果的数量 1 各段执行时间相等的吞吐率 P51 流水线的实际吞吐率 2 各段执行时间不等的吞吐率 P52 计算机系统结构 第二版 华中科技大学出版社 消除流水线的瓶颈段的方法 P52 分离瓶颈段 把流水线中的瓶颈功能段分离成为几个独立的子功能段 消除各段执行时间的 瓶颈 重复设置瓶颈段 如果瓶颈功能段由于实现技术等方面的原因难以分离成几个独立的子功能段 那么 可以采用重复设置瓶颈段 让多个瓶颈段并行工作来消除瓶颈段原执行时间的 瓶颈 这两种方法只要完全消除了 瓶颈 提高吞吐率的程度是相同的 计算机系统结构 第二版 华中科技大学出版社 流水线的加速比 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 单功能非线性流水线的最优调度方法最优调度方法获得最优调度策略的步骤 P58 根据处理对象对流水线各段的使用要求建立一个预约表 由预约表得出禁止表 禁止表是禁止后续对象流入流水线的时间间隔的集合 由禁止表得出初始冲突向量 计算机系统结构 第二版 华中科技大学出版社 由初始冲突向量得出状态有向图 后继状态的冲突向量用下式计算 由状态有向图得出最优调度策略 有向图的任何一条环路都是一个可循环执行的无冲突调度策略 从中选择一个平均时间间隔最小的调度策略就是最优调度策略 计算机系统结构 第二版 华中科技大学出版社 3 5流水线的相关问题与相关处理 局部相关 P66 对程序执行过程的影响较小的相关 它仅涉及到相关指令前后的一条或几条指令的执行 全局相关 P66 是指影响整个程序执行方向的相关 主要是转移类指令和中断引起的相关 计算机系统结构 第二版 华中科技大学出版社 3 5 1局部相关及处理方法 1 顺序流动的 先写后读 相关及处理顺序流动 P66 对象从流水线流出的次序同它们流入流水线的次序一样 先写后读相关 P67 如果指令h写入结果的目的地址同指令j读取操作数的源地址是同一个存储单元或寄存器 那么 称这两条指令有 先写后读 的要求 如果当指令j到达读段时 指令h还没有到达写段完成写入操作 那么 指令j读出的数据就是错误的 这就是 先写后读 相关 解决顺序流动的 先写后读 相关的方法 P67 延迟 异步流动和建立相关通路 计算机系统结构 第二版 华中科技大学出版社 3 5 3相关对流水线性能的影响 用时空图来表示流水处理过程和分析相关对流水线性能的影响 例3 4 例3 6 例3 8 3 21 3 22 3 23 3 24 计算机系统结构 第二版 华中科技大学出版社 3 6多发射处理机及其性能 单发射 P74 处理机在一个时钟周期只从存储器取出一条指令 IF 只对一条指令译码 ID 只执行一条指令 EX 和只写回一个运算结果 WR 因此 平均一个时钟周期只解释一条指令 单发射处理机的指令级并行度ILP 1 多发射 P74 处理机在一个时钟周期可发射多条指令 多发射处理机的指令级并行度ILP 2 属于多发射处理机范畴的处理机有 超标量处理机 超流水处理机 超标量超流水处理机和超长指令字处理机 计算机系统结构 第二版 华中科技大学出版社 3 6 5多发射处理机的性能比较 表3 6 计算机系统结构 第二版 华中科技大学出版社 第4章存储系统4 1存储系统的层次结构与性能指标4 1 1存储系统的层次结构 1 程序访问局部性时间局部性 P94 程序在最近的未来要用到的信息很可能是现在正在使用的信息 空间局部性 P94 程序在最近的未来要用到的信息很可能同现在正在使用的信息在存储空间位置上是相邻近的 计算机系统结构 第二版 华中科技大学出版社 4 1 2存储系统的性能指标 1 虚拟地址空间 P96 虚拟存储技术为用户设计了一个虚拟地址空间 这个虚拟地址空间比主存的实际地址空间要大得多 并采用像主存一样的随机访问方式 2 存储器最大带宽 P97 存储器被连续访问时能提供的数据传输速率称为存储器的最大带宽 计算机系统结构 第二版 华中科技大学出版社 3 命中率 P97 若逻辑地址流指定的信息能在M1中被访问到的次数为N1 在M1中未被访问到的次数为N2 则命中率为4 二级存储系统的等效访问周期 P97 计算机系统结构 第二版 华中科技大学出版社 5 二级存储系统的访问效率 P97 计算机系统结构 第二版 华中科技大学出版社 4 2并行存储器 并行存储器 P98 在一个存储器访问周期能并行访问到多个存储字的存储器 能有效地提高存储器的带宽 并行存储器主要有2种 一种是单体多字并行存储器 另一种是低位交叉编址多体并行存储器 计算机系统结构 第二版 华中科技大学出版社 4 2 1单体多字并行存储器 1 单体多字并行存储器 P98 把存储器的存储字字长增加n倍 以存放n个指令字或数据字 单体多字并行存储器的最大带宽比单体单字存储器的最大带宽提高n倍 单体多字并行存储器访问冲突概率大 2 低位交叉编址方法 P99 若每个存储体的容量均为n个存储字 则存储单元地址的低log2m位称为体号k 地址的高log2n位称为体内地址i 低位交叉编址的存储单元地址A的计算公式为 A m i k 计算机系统结构 第二版 华中科技大学出版社 3 多体并行存储器的错位存储方法对错位存储的n n二维数组可以实现以下4种并行访问方式的无存储体冲突访问 P99 并行访问数组任意一行的n个元素 并行访问数组任意一列的n个元素 并行访问数组对角线的n个元素或任意一条子对角线的所有元素 并行访问数组中任意一个子数组的n个元素 计算机系统结构 第二版 华中科技大学出版社 4 无存储体冲突访问方法 P100 对n n的二维数组错位存储时 要求存储体的个数 且m取质数 二维数组的任意元素aij存储的体号和体内地址分别是 其中 p是满足的任意自然数 k是数组的第一个元素a00所在存储体的体号 一般取k 0 计算机系统结构 第二版 华中科技大学出版社 计算机系统结构 第二版 华中科技大学出版社 4 3虚拟存储器 在虚拟存储技术中 把程序经编译生成的访存地址称为虚拟地址 或称为虚地址 由虚地址表示的存储空间称为虚空间 P100 程序代码运行时 必须先把虚地址转换成主存物理地址 或称为主存实地址 才能按实地址访问主存 虚地址与实地址之间对应关系的规则称为地址映像 P100 程序在运行时 虚拟存储系统按照某种地址映像把虚地址转换成实地址称为地址变换 P100 地址变换对应用程序员是透明的 由存储系统自动完成 计算机系统结构 第二版 华中科技大学出版社 如果按虚地址要访问的数据不在主存中 未命中 则称为发生访问失效 P100 那么就需要访问磁盘存储器 这时 先要把虚地址变换成磁盘存储器物理地址 称之为外部地址变换 然后才能访问磁盘存储器 将要访问的数据块调入主存 外部地址变换更多地依靠软件来实现 当有新的数据块要调入主存时 如果主存中已经没有空闲的位置 则称为发生实存冲突 P101 那么就要采用某种替换算法来确定新数据块调入主存的位置 计算机系统结构 第二版 华中科技大学出版社 4 3 1虚拟存储器的地址变换 1 页式虚拟存储器的地址变换页式管理 P102 把虚拟地址空间和主存地址空间都划分成同样大小的页 程序以页为单位调入调出主存 虚拟空间的页称为虚页 主存空间的页称为实页 页表 P102 每个程序都用一个页表来存放该程序的各个虚页装入主存实页位置 实页号 等有关信息 一个虚页占用页表中的一行 虚空间的虚页数就是页表的行数 存储字数 计算机系统结构 第二版 华中科技大学出版社 图4 6页式虚拟存储器的地址变换 计算机系统结构 第二版 华中科技大学出版社 4 3 2页面替换算法与命中率的计算 1 几种页面替换算法 P108 随机替换算法 RAND算法 用软件或硬件随机产生被替换的虚页号 先进先出替换算法 FIFO算法 选择最早装入主存的虚页作为被替换页 近期最久使用替换算法 LRU算法 该算法选择过去近期最久访问的虚页作为被替换页 最优替换算法 OPT算法 选择将来一段时间内最久被访问的页作为被替换页 计算机系统结构 第二版 华中科技大学出版社 2 页面替换算法的命中率计算方法通过典型程序的虚页地址流模拟使用某个替换算法的替换过程 来得出命中主存的次数 从而求出该虚页地址流使用该替换算法时的主存命中率 例4 2 计算机系统结构 第二版 华中科技大学出版社 4 3 3堆栈型替换算法及其堆栈处理过程 1 堆栈型替换算法 P109 如果替换算法具有下述性质 随着分配给程序的主存实页数n的增加 替换算法的主存命中率H也随之提高 至少不下降 那么 这种替换算法就称为堆栈型替换算法 2 H n 随n变化的计算方法 用一个堆栈对程序的访存虚页地址流处理一次 就可以获得H n 随n变化的关系 从而可以根据程序访存需要达到的主存命中率H来确定应分配给该程序的实页数n 使有限的主存空间资源的使用达到较高的性价比 例4 4 4 19 4 23 计算机系统结构 第二版 华中科技大学出版社 4 4高速缓冲存储器 1 Cache存储系统与虚拟存储系统的不同 P114 Cache与主存之间以块为单位进行数据交换 两级存储器间的速度比不同 CPU与Cache存储器之间和CPU与主存之间都有直接通路 若CPU对Cache存储器中的块访问未命中 则CPU可直接访问主存 Cache存储系统以提高整个存储系统的速度为目标 虚拟存储系统以扩大存储系统的容量为目标 Cache存储系统对系统程序员和应用程序员都是透明的 虚拟存储系统仅对应用程序员是透明的 计算机系统结构 第二版 华中科技大学出版社 4 4 1Cache的地址映像与地址变换 1 全相联地址映像及其地址变换全相联地址映像 P115 主存中的任意一块可以装入到Cache中任意的块位置上 全相联映像的块冲突概率最低 Cache空间利用率最高 全相联映像的地址变换 P115 采用目录表来实现 目录表需存放在相联存储器中 目录表的行数 即相联存储器的存储单元数 是Cache的块数 计算机系统结构 第二版 华中科技大学出版社 图4 15全相联映像地址变换 计算机系统结构 第二版 华中科技大学出版社 例4 6 2 直接地址映像及其地址变换直接地址映像 P116 把主存空间按Cache的大小划分为若干区 主存各区和Cache再划分为若干块 主存各区中的区内块号B只能装入到与Cache块号b相同的那个块位置上 直接映像的块冲突概率最高 Cache空间利用率最低 计算机系统结构 第二版 华中科技大学出版社 3 组相联地址映像及其地址变换组相联映像 P118 把主存按Cache的容量分区 主存中的各区和Cache再按同样大小划分成数量相同的组 组内按同样的大小划分成数量相同的块 主存的组到Cache的组之间采用直接映像 两个对应组的块之间采用全相联映像 计算机系统结构 第二版 华中科技大学出版社 例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来表示 互连函数表示相互连接的输出端号和输入端号之间的对应关系 计算机系统结构 第二版 华中科技大学出版社 5 1 1互连函数的表示方法 互连函数 P133 表示互连网络的输入端X与输出端之间可实现的连接 如果互连函数是单值函数 相互连接的输入端与输出端是一对一的 则称这种连接是置换连接 P133 如果互连函数是多值函数 一个输入端连接到多个输出端 则称这种连接是播送连接 P133 输入输出对表示法图形表示法循环互连函数 计算机系统结构 第二版 华中科技大学出版社 5 1 2几种基本的互连函数 1 恒等置换恒等置换实现的互连 P134 输入端X连接的输出端号就是输入端号X 2 交换置换交换置换实现的互连 P134 把输入端的二进制地址的最低位变反就是连接的输出端的二进制地址 交换置换的互连函数为 计算机系统结构 第二版 华中科技大学出版社 3 方体置换方体置换 Cube P135 有个互连函数它们共同表示一个n维立方体的双向互连 其中 Ck的互连函数为方体置换也是分组循环互连 方体置换的个互连函数分别表示N 2对结点沿n维方向的双向互连 计算机系统结构 第二版 华中科技大学出版社 4 均匀洗牌置换均匀洗牌置换 Shuffle P135 又称为混洗置换 混洗置换实现的互连 把输入端二进制地址循环左移一位就是连接的输出端的二进制地址 混洗置换的互连函数为子洗牌置换实现的互连 把输入端二进制地址从第k位到最低位共k 1位的低端地址循环左移一位就是连接的输出端的二进制地址 子洗牌置换的互连函数为 计算机系统结构 第二版 华中科技大学出版社 逆均匀洗牌置换函数是均匀洗牌置换函数的逆函数 P136 逆均匀洗牌置换实现的互连 把输入端二进制地址循环右移一位就是连接的输出端的二进制地址 逆均匀洗牌置换的互连函数为 计算机系统结构 第二版 华中科技大学出版社 7 移数置换移数置换实现的互连 P138 把输入端的端号序列循环左移或循环右移若干位就是对应连接的输出端的端号序列 移数置换的互连函数为其中 循环左移k位得出连接输入端X的输出端号为 循环右移k位得出连接输入端X的输出端号为 计算机系统结构 第二版 华中科技大学出版社 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 网络规模 网络能连接的结点数 2 结点度 一个结点射入或射出的边数 3 结点距离 两个结点之间相连的最少边数 4 网络直径 一个互连网络中任意两个结点之间距离的最大值 5 最小对剖平面 一个有N个结点的网络对剖平面把网络分为两个各有N 2个结点的网络 由对剖平面切开的边数最少的对剖平面 6 网络对剖宽度 由最小对剖平面切开的边数 7 对称网络 若从网络的任意结点来看 网络的结构都是相同的 则称网络是对称网络 计算机系统结构 第二版 华中科技大学出版社 5 2 2互连网络的性能指标 1 通信延时 P142 通信时延是指从源结点到目的结点传送一条消息所需的总时间 通信时延包括以下4部分 软件开销 在源结点和目的结点用于收发消息的软件所需的执行时间 通道时延 通道带宽除以消息长度即通道时延 选路时延 消息在传送路径上所需的一系列选路决策所需的时间开销 竞争时延 多个消息同时在网络中传送时 会发生争用网络资源的冲突 为避免或解决争用冲突所需的时间为竞争时延 计算机系统结构 第二版 华中科技大学出版社 2 网络延时 P142 由网络硬件特征决定的网络时延是通道时延与选路时延之和 网络时延与程序行为和网络传输状态无关 3 端口带宽 P142 网络中从任意一个端口单位时间传送到其他端口的最大信息量称为该端口的端口带宽 在对称网络中 端口带宽与端口位置无关 对称网络的各端口带宽也称为网络的端口带宽 非对称网络的端口带宽是所有端口带宽的最小值 4 聚集带宽 P143 网络的聚集带宽是指网络从一半结点到另一半结点 单位时间传送的最大信息量 计算机系统结构 第二版 华中科技大学出版社 5 3静态互连网络 静态互连网络 P143 各结点之间有专用的连接通路 且在运行中不能改变连接的互连网络 例5 2 计算机系统结构 第二版 华中科技大学出版社 5 4动态互连网络 动态互连网络 P149 通过设置有源开关且根据连接需求来动态改变开关的连接 从而实现结点之间的不同连接 计算机系统结构 第二版 华中科技大学出版社 5 4 3多级互连网络 多级互连网络 P153 把重复设置的多套动态单级网络串联起来 单级网络级间采用固定的级间连接模式 通过动态控制各单级网络的开关状态来实现多级互连网络的输入端和输出端之间所需的连接 计算机系统结构 第二版 华中科技大学出版社 1 Omega网络 P154 网络n个开关级从网络输入