计算机组成原理 [袁春风]chap3

1 第三章运算器组织与运算方法 南京大学计算机系多媒体技术研究所袁春风 南京大学计算机系多媒体技术研究所袁春风 2 数据通路 运算器 的概念运算器的基本功能是进行数据运算 ALU是其核心部件 是数据加工中心 但加工数据需由寄存器供给 加工后的数据要移位 对于双操作数和乘除运算还要提供联合移位功能 数据传送还要有传送线路 即内部总线 等等 因此 CPU中的运算部件除ALU外 还必须有其他一些部件 这些部件总称为数据通路 数据通路是指计算机的数据信息从一个部件传输到另一个部件所经过的路径 连同路径上的设备 如 寄存器 暂存器 多路选择器 移位器 加工部件等 一个简单数据通路实例一个四位数据通路芯片 AM2901A现代计算机所用数据通路 流水线 超标量 3 1运算器的基本组成 南京大学计算机系多媒体技术研究所袁春风 3 3 2算术逻辑部件 ALU ALU ArithmeticLogicUnit 用来执行各种算术和逻辑运算 位ALU行波进位ALU先行进位ALUALU的核心是加法器 以下围绕加法器介绍 说明 因为资料来源不同 以下的运算符号用了两种不同的表示方式 请不要混淆 特此说明 南京大学计算机系多媒体技术研究所袁春风 4 ALU功能描述 南京大学计算机系多媒体技术研究所袁春风 5 全加器逻辑图 Gi aibiPi ai biSi ai bi Ci 延迟为6ty Ci 1 aibi ai bi Ci 延迟为5ty 南京大学计算机系多媒体技术研究所袁春风 6 一个n位ALU可以由n个一位ALU串行构成 这种ALU称为行波进位ALU Ripple CarryALU 全加逻辑方程 i 0 1 n Si ai bi CiCi 1 aibi ai bi Ci 延迟为2ty 上述进位逻辑与下列逻辑等价 Ci 1 aibi ai bi Ci 延迟为5ty 下面是一个4位行波进位ALU 3 2 2行波进位ALU 南京大学计算机系多媒体技术研究所袁春风 7 4位行波进位ALU 和的所有位全部产生的延迟为 2n 1 ty当n 4时 为9ty 当n 8时 为17ty 南京大学计算机系多媒体技术研究所袁春风 8 3 2 3先行进位ALU 1 为什么用先行进位方式 行波进位是串行逐级传递的 整个和的生成受到行波进位的影响 因此 现代计算机采用一种先行进位 Carrylookahead 方式 2 如何产生先行进位 定义两个辅助函数 Gi aibi 进位生成Pi ai bi 进位传递通常把实现上述逻辑的电路称为进位生成 传递部件全加逻辑方程 Si Pi CiCi 1 Gi PiCi i 0 1 n 设n 4 则 C1 G0 P0C0C2 G1 P1C1 G1 P1G0 P1P0C0C3 G2 P2C2 G2 P2G1 P2P1G0 P2P1P0C0C4 G3 P3C3 G3 P3G2 P3P2G1 P3P2P1G0 P3P2P1P0C0由上式可知 各进位之间无等待 相互独立并同时产生 通常把实现上述逻辑的电路称为4位CLA部件由此 根据Si Pi Ci 可并行求出各位和 通常把实现Si Pi Ci的电路称为求和部件CLA加法器由 进位生成 传递部件 CLA部件 和 求和部件 构成 南京大学计算机系多媒体技术研究所袁春风 9 8位全先行进位加法器 进位生成 传递部件 A7 A0 B7 B0 P7 P1 P0 G7 G1 G0 8位CLA部件 C0 求和部件 P7 P1 P0 C0 C1 C7 C8 S7 S0 S1 3ty 2ty 3ty 和的总延迟 3 2 3 8ty 进位C8的延迟 3 2 5ty 南京大学计算机系多媒体技术研究所袁春风 10 局部先行进位加法器 所有和数产生的延迟为 5 2 2 5 14ty 南京大学计算机系多媒体技术研究所袁春风 11 3 多级先行进位加法器单级 局部 先行进位加法器的进位生成方式 组内并行 组间串行 所以 单级先行进位加法器虽然比行波加法器延迟时间短 但高位组进位依赖低位组进位 故仍有较长的时间延迟 通过引入组进位生成 传递函数来实现 组内并行 组间也并行 的进位生成方式 设n 4 则 C1 G0 P0C0C2 G1 P1C1 G1 P1G0 P1P0C0C3 G2 P2C2 G2 P2G1 P2P1G0 P2P1P0C0G3 G3 P3C3 G3 P3G2 P3P2G1 P3P2P1G0P3 P3P2P1P0所以C4 G3 P3 C0 把实现上述逻辑的电路称为4位BCLA部件 多级先行进位加法器 南京大学计算机系多媒体技术研究所袁春风 12 两级先行进位加法器 南京大学计算机系多媒体技术研究所袁春风 13 先行进位ALU 4 快速先行进位ALUSN74181是国际流行的四位ALU芯片 是中规模集成电路 它在原有先行进位加法器的基础上再附加部分线路 实现了按位逻辑运算 因此具有基本的算术运算和逻辑运算功能 SN74181的逻辑图和功能表SN74182是4位BCLA 成组先行进位 芯片 用4个4位ALU芯片与1个4位BCLA芯片可构成16位ALU用16个4位ALU芯片与4个4位BCLA芯片可构成64位ALU 南京大学计算机系多媒体技术研究所袁春风 14 SN74181的引脚 输入端 Ai和Bi分别为第一和第二操作数 Cn为低位进位 M为功能选择线 Si为操作选择线 输出端 Fi为运算结果 Cn 4 P和G为进位 A B 为相等标志 P 输入端 输出端 南京大学计算机系多媒体技术研究所袁春风 15 SN74181和SN74182组成16位先行进位加法器 4位ALU 4位ALU 4位ALU 4位ALU 南京大学计算机系多媒体技术研究所袁春风 16 3 3定点加 减运算 计算机内的加减运算一般用补码实现1 补码定点加减法规则假设A B是带符号的n位二进制定点整数 其补码形式为 A 补 an 1an 2 a0 B 补 bn 1bn 2 b0 则 A B 补和 A B 补的运算表达式为 对于整数 A B 补 A 补 B 补 MOD2n A B 补 A 补 B 补 MOD2n对于小数 A B 补 A 补 B 补 MOD2 A B 补 A 补 B 补 MOD2 南京大学计算机系多媒体技术研究所袁春风 17 3 3定点加减运算 在补码系统内 n位补码加 减法的原则是 加法规则 两个n位数的补码相加 来自最高位的进位可丢掉 取模 所以可用一个无符号加法器生成各位的和 减法规则 一个数的补码与另一个负数的补码相加 其和数就是这个数减去另一个数的绝对值的补码 即 求两个数差的补码可用第一个数的补码加上另一数负数的补码得到 溢出规则 运算的结果必须考虑是否产生了溢出 若两个同号数相加 其结果的符号与两个加数的符号不同 则发生溢出 通常将 结果大于最大能表示的正数 称为正溢出 而把 结果小于最小能表示的负数 称为负溢出 书上提的上溢和下溢的概念用于浮点数溢出 特此说明 南京大学计算机系多媒体技术研究所袁春风 18 3 3定点加减运算 2补码加 减法器由上述规则可知 补码加减法器只要在原无符号加法器的基础上增加 求负数补码 的电路和 溢出检查 电路 无符号加法器 可实现补码加法 实现无符号数A和B相加 考虑低位进位C0 生成和数S和向高位的进位Cn 前面介绍的行波加法器 先行进位加法器等都是无符号加法器 南京大学计算机系多媒体技术研究所袁春风 19 无符号加法器实现补码加法举例 设 A 11011 B 01001则 A和B的值分别为 0101 1001A加B的值为 0100若用6位无符号加法器实现 则A 11011B 01001A B 100100即 和数S 00100 进位C6 1和数S的值为 0100 同A加B的值 南京大学计算机系多媒体技术研究所袁春风 20 3 3定点加减运算 求负数补码 电路 B 补 增加取反电路 再加适当控制 设 bi bi C0 则C0 0 则bi bi 且做加法 C0 1 则bi bi 且做减法 因此 C0有两个作用 功能控制 用于求反操作的启动信号 求负数的补码时 进行加1操作 B 加法器 A C0 Cn 和数S N位补码加 减法器 求负数补码 的电路 南京大学计算机系多媒体技术研究所袁春风 21 3 3定点加减运算 补码加 减法器判断溢出的方法 方法1 若两个同号数相加 其结果的符号与两个加数的符号不同 则发生溢出 OVR an 1bn 1Sn 1 an 1bn 1Sn 1方法2 采用 变形补码 进行补码运算和溢出检测 其结论为 当结果的两个符号位不同时 发生溢出 溢出判断逻辑 OVR Sn 1 Sn举例 采用8位加法器 即 n 8 用变形补码计算 例1 x 010101y 001001 x y 解 x 补 00010101 y 补 00001001 x y 补 00011110所以x y 011110例2 x 011001y 000110 x y 解 x 补 11100111 y 补 11111010 x y 补 11100001所以x y 011111 00001001 00010101 00011110 11111010 11100111 111100001 南京大学计算机系多媒体技术研究所袁春风 22 3 3定点加减运算 举例 采用8位加法器 即 n 8 用变形补码计算 例3 x 101100 44 y 100101 37 x y 解 x 补 00101100 y 补 00100101 x y 补 01010001 溢出 第一符号是真符 说明和为正数 01 表示正溢出 81 63 001111112 例4 x 101100 44 y 100101 37 x y 解 x 补 11010100 y 补 11011011 x y 补 10101111 溢出 第一符号是真符 说明和为负数 10 表示负溢出 81 64 110000002 00101100 00100101 01010001 11011011 11010100 110101111 两符相异 结果溢出 两符相异 结果溢出 南京大学计算机系多媒体技术研究所袁春风 23 3 4定点乘法运算 乘除运算的三种实现方案 采用软件实现乘 除运算在原有数据通路的基础上增加一些硬件逻辑来实现 加法器 移位器 设置专门的乘除法器 可加快运算速度 这里主要讨论计算机实现乘除法运算的基本算法及基本硬件配置 南京大学计算机系多媒体技术研究所袁春风 24 3 4 1无符号数乘法 南京大学计算机系多媒体技术研究所袁春风 25 第一种乘法器如何工作 南京大学计算机系多媒体技术研究所袁春风 26 用加法 部分积右移实现乘法 假定 A an 1an 2 a1a0B bn 1bn 2 b1b0对乘数B作位移函数 B向右移n位 得 B 2n bn 1 2 1 bn 2 2 2 b1 2 n 1 b0 2 nAB 2n Abn 1 2 1 Abn 2 2 2 Ab1 2 n 1 Ab0 2 n 2 1 Abn 1 2 1 Abn 2 2 1 Ab0 0 即 Pi 2 1 Abi Pi 1 Pi被称为部分积展开后 得 P 1 0P0 2 1 Ab0 P 1 Pn 1 2 1 Abn 1 Pn 2 所以 乘法操作可分解为 加法 右移 南京大学计算机系多媒体技术研究所袁春风 27 第三种乘法硬件 南京大学计算机系多媒体技术研究所袁春风 28 第3种乘法算法 南京大学计算机系多媒体技术研究所袁春风 29 3 4 2有符号数乘法 定点有符号数乘法原码乘法将符号与数值分开处理积符用两个乘数的符号异或得到数值部分用无符号乘法运算补码乘法方法1 两数都变成正数 用无符号乘法运算 最后根据两个乘数是否异号确定是否对结果取负 方法2 用Booth乘法 其速度更快 符号位和数值位可一起参加运算 南京大学计算机系多媒体技术研究所袁春风 30 1 原码乘法 设 设A 和B 是两个原码表示 A asAB bsB 其中as bs为数A 和B 的符号位 A B为数值则 积符ps as bs积的绝对值P A B乘积P psP ps A B 求P A B 用无符号乘法 南京大学计算机系多媒体技术研究所袁春风 31 2 补码乘法 假定 A 补 an 1an 2 a1a0 B 补 bn 1bn 2 b1b0求 AB 补 Booth算法基于以下补码性质 令 A 补 an 1an 2 a1a0 则 A an 1 2n 1 an 2 2n 2 a1 21 a0 20当n 32时 A a31 231 a30 230 a1 21 a0 20 a30 231 a30 230 南京大学计算机系多媒体技术研究所袁春风 32 Booth乘法算法推导 部分积 Pi 2 1 ai 1 ai b Pi 1 南京大学计算机系多媒体技术研究所袁春风 33 Booth算法要点 南京大学计算机系多媒体技术研究所袁春风 34 Booth算法要点 中 南京大学计算机系多媒体技术研究所袁春风 35 Booth算法要点 南京大学计算机系多媒体技术研究所袁春风 36 Booth算法举例1 南京大学计算机系多媒体技术研究所袁春风 37 Booth算法举例2 南京大学计算机系多媒体技术研究所袁春风 38 3 5定点除法运算 计算机中的除法运算过程一般分为三个部分 操作数的预置 商符和商值的确定 余数的确定设A和B分别为被除数和除数 令 A a2n 1a2n 2 anan 1 a1a0 A为2n位 若为n位 则可用扩展操作将位数扩展成2n位 B bn 1bn 2 b1b0 B为n位 做除法之前 先要判断A 0 商为0 B 0 除数为0 2n B A 溢出 无符号数的除法恢复余数法和不恢复余数法有符号数的除法原码除法和补码除法 南京大学计算机系多媒体技术研究所袁春风 39 3 5 1恢复余数除法 算法思想 类似于手工除法计算 通过做减法来试商若余数为正 则表示够减 商 下次继续做减法 若余数为负 则表示不够减 商 下次做加法 恢复余数 南京大学计算机系多媒体技术研究所袁春风 40 第三种除法算法 南京大学计算机系多媒体技术研究所袁春风 41 第三种除法算法举例 南京大学计算机系多媒体技术研究所袁春风 42 第三种除法算法 南京大学计算机系多媒体技术研究所袁春风 43 第三种除法算法的启示 南京大学计算机系多媒体技术研究所袁春风 44 3 5 2不恢复余数除法 加减交替法 基本思想 根据恢复余数法 设B为除数 Ri为第i次中间余数 有 若Ri0 则商上 1 不需恢复余数 即 Ri 1 2Ri 2n B 由上式可知 正 减 省去了恢复余数的过程注意 最后一次上商为 的话 需要 纠余 处理 即把试商时被减掉的除数加回去 恢复真正的余数 不恢复余数法也称为加减交替法 南京大学计算机系多媒体技术研究所袁春风 45 3 5 3有符号数除法 有符号数的除法原码除法商符和商值分开处理 商的数值部分由无符号数除法求得 商符由被除数和除数的符号确定 同号为 异号为 余数的符号同被除数的符号 补码除法方法1 先转换为正数 用无符号数除法 然后修正商和余数 方法2 直接用补码除法 南京大学计算机系多媒体技术研究所袁春风 46 设 x 原 100100110 y 原 00111求 x y 原 R 原解 y 补 1001 x 00100110AQ上商说明001001101001试商 做减法101101100不够减 商00111做加法 恢复余数0010011001001100左移一位1001试商 做减法110111000不够减 商00111做加法 恢复余数0100110010011000左移一位1001试商 做减法001010001够减 商101010001左移一位1001试商 做减法111000010不够减 商00111做加法 恢复余数0101000110100010左移一位1001试商 做减法001100101够减 商1 例1 恢复余数法 x y 原 10101 R 原 10011x y 5余数R 3验证 38 5 x 7 3 若事先判断出不溢出 则第一次可以不试商而直接左移 南京大学计算机系多媒体技术研究所袁春风 47 设 x 原 100100110 y 原 00111求 x y 原 R 原解 y 补 1001 x 00100110AQ上商说明001001101001试商 做减法101101100负 0 加01101100左移一位0111做加法110111000负 0 加10111000左移一位0111做加法001010001正 1 减01010001左移一位1001做减法111000010负 0 加11000010左移一位0111做加法001100101正 1 减 最后一步 运算结果同前面的恢复余数法 例2 不恢复余数法 最后一次上商为 1 故不需恢复余数 第一次上的商不是真正的商 只是用来判断是否溢出 故最终的商应是Q和Q 1一起左移一位后在Q中的数 即 商的数值为0101 南京大学计算机系多媒体技术研究所袁春风 48 举例 7 3 7 3 被除数 00000111除数0011AQM 001100000111000011101101减110111100011恢复 加 商000001110000111001101减111011000011恢复 加 商000011100001110001101减00001001符同商1000100101101减111000100011恢复 加 商000010010 余 0001 商 0010 被除数 11111001除数0011AQM 001111111001111100100011加001000101101恢复 减 商011110010111001000011加000101001101恢复 减 商011100100110010000011加11111001符同商1111100100011加001000101101恢复 减 商011110010 余 1111 商 1110 南京大学计算机系多媒体技术研究所袁春风 49 3 6浮点运算 浮点数运算及结果浮点数的加减运算浮点数的乘除运算精度考虑IEEE754中几个特殊值的含义浮点运算部件的设置 南京大学计算机系多媒体技术研究所袁春风 50 3 6 1浮点数运算及结果 设两个规格化浮点数分别为A Ma 2EaB Mb 2Eb 则 A B Ma Mb 2 Ea Eb 2Ea 假设Ea Eb A B Ma Mb 2Ea EbA B Ma Mb 2Ea Eb上述运算结果可能出现以下几种情况 阶码上溢 一个正指数超过了最大允许值 溢出阶码下溢 一个负指数超过了最小允许值 0 0尾数上溢 最高有效位有进位 右规尾数下溢 左规或对阶时 右段有效位丢失 尾数舍入IEEE建议实现时为每种异常情况提供一个自陷允许位 当具有允许自陷处理程序的一个异常情况发生时 就调用一个用户自陷处理程序执行 南京大学计算机系多媒体技术研究所袁春风 51 3 6 2浮点数的加减运算 步骤 A B Ma Mb 2 Ea Eb 2Ea 假设Ea Eb 1 查0 一个数为0 结果为另一个数 2 对阶 小阶向大阶看齐 小阶码增大 相应尾数右移直到两数阶码相等 循环增量 移位 实现对阶时也可直接计算 Ea Eb 补 Ea Eb 补 Ea 移 Eb 移 补 Ea 补 Eb 补 3 尾数相加减 对阶后 进行尾数求和 差 4 规格化 结果出现尾数上溢时 进行右规结果出现尾数高位有非有效数时 进行左规 在对阶和右规时 要考虑保留附加位在左规和确定最终结果时 要考虑舍入方式 5 阶码溢出判断 阶码上溢 则置 溢出 阶码下溢 则置 0 南京大学计算机系多媒体技术研究所袁春风 52 浮点数加减运算 举例 例1 x 0 5y 0 4375求x y 解1 假定尾数用2 4位变形补码表示 阶码用3位移码表示x 0 5 1 2 0 1000 2 0 1000 2x20y 0 4325 0 0111 2 0 1110 2x2 1 x 浮 100 00 1000 y 浮 011 11 0010对阶 Ex Ey 补 100 011 补 100 101 001故Ex Ey 1对y进行对阶 y 浮 100 11 1001尾数相加 00 1000 11 1001 00 0001 x y 浮 100 00 0001规格化 左规 x y 浮 001 00 1000 x y 0 1 2x2 3 0 5x1 8 0 0625 e 001 2 100 2 3 南京大学计算机系多媒体技术研究所袁春风 53 x 0 5y 0 4375求x y 解2 假定用IEEE754标准单精度格式表示x 0 5 1 2 0 100 0 2 1 00 0 2x2 1y 0 4325 0 01110 0 2 1 110 0 2x2 2 x 浮 001111110 00 0 y 浮 101111101 110 0对阶 E 补 01111110 10000011 00000001 E 1故对y进行对阶 y 浮 1011111101110 0 高位补隐藏位 尾数相加 01 0000 0 10 1110 0 00 00100 0 原码加法 左规 0 00100 0 2x2 1 1 00 0 2x2 4 阶码减3 x y 浮 00111101100 0 x y 1 0 2x2 4 1 16 0 0625 浮点数加减运算 举例 南京大学计算机系多媒体技术研究所袁春风 54 3 6 3浮点数的乘除运算 A B Ma Mb 2Ea EbA B Ma Mb 2Ea Eb结果的阶码计算移码 Ea Eb 移 Ea 移 Eb 移 偏置常数 Ea Eb 移 Ea 移 Eb 移 偏置常数补码 Ea Eb 补 Ea 补 Eb 补 Ea Eb 补 Ea 补 Eb 补结果的尾数计算定点整数的乘 除法运算 补码 原码 书中有流程图 自学 南京大学计算机系多媒体技术研究所袁春风 55 3 6 4浮点运算的精度考虑 保护位 附加位 又称警戒位 的增设为了使数据有效位在右移时最大限度地保证不丢失 一般在运算中间值后面增加若干数据位 这些位用来保存右移后的有效数据 例如 可用一个32位寄存器保存IEEE754单精度的尾数部分 此时 保护位数为32 25 7位 IEEE754单精度的尾数部分装入寄存器时 符号位和隐含的最高位 被同时装入 故数据位数为1 1 23 25位 舍入方式的选择增设保护位 在较长的寄存器中运行后 最终必须将结果的保护位去掉 以得到格式规定的浮点数 此时要考虑舍入 南京大学计算机系多媒体技术研究所袁春风 56 1 保护位 附加位 的增设 南京大学计算机系多媒体技术研究所袁春风 57 影响精度的另一个因素是舍入策略原则 1 尽量使误差范围对称 使得平均误差为0即 有舍有入 以防误差积累 2 要简单 以加快速度方法 1 截取 快 但有误差积累 2 恒1法 快 平均误差小 3 0舍1入 慢 但精度高 2 舍入方式的选择 南京大学计算机系多媒体技术研究所袁春风 58 8 9十进制数的加减运算 有的机器有十进制加减法指令 用于对二进制编码的十进制数进行加减运算 所以这些机器中必须要有相应的十进制加减运算逻辑 以NBCD码 8421码 为例 讨论十进制整数的加减运算 一般规定数符在最高位1100 正 1101 负或0 正 1 负例如 203911000010000000111001或00010000000111001 12651101000100100110010110001001001100101 南京大学计算机系多媒体技术研究所袁春