定点数运算及溢出检测
- 补码加法：[X＋Y]补 = [X]补＋ [Y]补
- 和的补码 = 补码的和
- 补码减法：[X−Y]补 = [X]补＋ [−Y]补 = [X]补−[Y]补
- 差的补码 = 补码的差
- 减法变加法，关键是求[−Y]补
- 求补公式：[−Y]补= [ [Y]补 ]补
- 对 [Y]补逐位取反, 再在最低位加 1
单符号数溢出检测
方法I
溢出只可能发生在同符号数相加时，包括[X]补与[Y]补； [X]补与[-Y]同号；
方法1：对操作数和运算结果的符号位进行检测 当结果的符号位与操作数的符号不相同时就表明发生了溢出
- 正正得负 负负得正
- 设两数符号位为 f0 f1 ，和数符号位 fs
- 溢出检测信号Overflow (OF)
OF = !f0·!f1·fs + f0·f1·!fs
方法II
方法2：对最高数据位进位和符号进位进行检测 •设运算时最高数据位产生的进位为C1，符号位产生的进位为C0， 溢出检测电路为： V= C0 ^ C 1
方法III
方法3：用变型补码 [X]补 = Xf1Xf2. X1X2X3…Xn mod 2^n+2 溢出的判断: V= Xf1 ^ Xf2
例6 已知 X=- 10010 Y= -10101 求X+Y
解: [X]补=1101110 [Y]补= 1101011
[X+Y]补=[X]补+[Y]补= 1101110 + 1101011 =1 10 10001
V= 1 ^ 0 =1 故发生溢出！
无符号数运算的溢出判断
- 无符号数加法的溢出可用ALU的进位表示
- 无符号数减法的溢出也可用带加/减功能的ALU的进位取反后表示。
定点数补码加减运算器设计
带进位链的一位全加器
Si = Xi ⊕ Yi ⊕ Ci
Ci+1 = Xi Yi + (Xi ⊕ Yi )Ci
- n位加法器包含n个全加器
- 将n个一位全加器串联
- 低位进位输出连接到高位进位输入
串行加法器时间延迟
n个全加器延迟，3n个门电路延迟？
考虑片内并行性，2n+1个门电路延迟
四位串行加/减法器设计
补码减法可以变加法
[X]补 − [Y]补 = [X]补 + [−Y]补
关键是求[−Y]补
方法：将Y补连同符号位一起逐位取反末位加一
[−Y]补= [ [Y]补 ]补 注意补码区间不对称？
- 引入运算控制位 Sub
- Sub=0 时作加法，送入加法器的是Y补
- Sub=1 时作减法，送入加法器的是[−Y]补
- 对 Y补 逐位取反，末位加一
[−Y]补= [ [Y]补 ]补
Input = Yi ^ Sub
并行加法器进位链(carry-lookahead)
Si = Xi⊕Yi⊕Ci-1
Ci = XiYi+(Xi⊕Yi)Ci-1
Gi = XiYi 进位生成函数 Generate
Pi = Xi⊕Yi 进位传递函数 Propagate
Ci = Gi + Pi·Ci-1
高位运算依赖于低位进位 -> 计算不能并行
Cn = Gn＋PnGn-1＋PnPn-1Gn-2＋PnPn-1Pn-2Gn-3 …＋PnPn-1…P1C0
- 进位输出仅与最低位进位输入C0有关
- 位数越长，进位链电路复杂度越高
- 通常按照4位一组进行分组运算
①生成P*，G*需3T -> ②生成C3/C12需2T -> ③求和需3T
原码一位乘法
- 符号单独运算：直接异或
- 绝对值相乘： 仅需考虑数值部分的计算
补码一位乘法
设[X]补 = X0X1X2X3…Xn [Y]补 = Y0Y1Y2Y3…Yn
可证明：
[X•Y]补 = [X]补•( 0.Y1Y2Y3…Yn ) –Y0• [X]补
进一步展开合并后可得：
[x•y]补=[x] 补•Σ(yi+1 - yi)2^-i ( 符号位参加运算 )
补码一位乘法的运算规则如下:
(1)如果yn+1=yn,部分积加0，部分积算术右移1位；
(2)如果yn+1yn=10,部分积加[x]补，部分积算术右移1位；
(3)如果yn+1yn=01,部分积加[-x]补，部分积算术右移1位. 重复进行n＋1步，但最后一步不移位。
包括一位符号位，所得乘积为2n＋1位，其中n为数据位位数.
几个特殊问题的处理
(1) i=n时 ,yn+1= ？yn+1= 0
(2) yn+1 是哪个寄存器？在乘数寄存器Y后增加的一位
(3)算术右移的对象有哪些？ 部分积和乘数寄存器均右移
乘法运算器设计
阵列乘法器
而对于相加数运算，就变成了一位乘法运算，一位乘法运算很简单，从真值表看，这就是一个简单的与逻辑，也就是逻辑与门就可以实现一位乘法，对于上一页的5*5的乘法运算，需要25个相加数，所以我们可以采用25个与门并发，如图所示，经过一级门电路延迟后，就可以得到所有的相加数，下面我们只需要考虑逐列相加的逻辑就可以实现乘法器
- 与门实现一位乘法
- 25个与门并发
- 一级门延迟，生成所有相加数
经过一级门电路延迟后，生成了所有相加数，这里X。。就是，将第二列用一个全加器进行相加，由于全加器有三个输入，所以这里进位位我们给一个零，当然大家也可以使用半加器完成，去掉进位输入，可以减少硬件成本，相加得到的结果就是乘积的P1位，进位输出横向向高位列传递，这就是所谓的横向进位阵列乘法器，将第三列的三个数用两个全加器串联进行运算，就可以得到P2，同样，全加器的进位输出都横向向左侧传递。，最后一个全加器进位输入为零，依次类推，得到P3，P4，P5，对于P6列，这个进位信号直接传递到下一层的全加器，同理得到P7，P。。。。。 如果采用斜向进位，就可以有另外一种连接方法。
前面我们给出了横向进位和斜向进位两种阵列乘法器，首先我们来看看横向进位阵列乘法器，5*5的横向阵列乘法器包括4行全加器，每行5个，需要20个全加器，进位信号横向传递，每一行都是一个5位串行进位加法器，串行加法器的特点就是性能差，各全加器之间存在着进位依赖，所以这个全加器运算完毕后，这个才能运算，然后是这个，第一行运算完毕后，第二行才能开始运算，所以看上去所有全加器都只能串行工作，整个运算需要20个全加器时延。
但仔细分析，这个横向进位阵列乘法器还存在这一定的并行性，首先是这个全加器运算，运算完毕后这个全加器运算，当第二个全加器运算完毕后，这两个全加器的输入就绪，两个全加器可以并发，当这两个全加器运算完毕后，这两个全加器运算，然后是这三个全加器并发，所以沿着对角线法线方向上的全加器是可以并发的，我们来看看乘法器的关键路径
(T是计算X1Y1，X0Y0的那个时延)
斜向进位乘法器和横向进位乘法器结构有一些区别，加法器一共5行，每行4个全加器，横向进位是4行，每行5个，硬件电路成本相同，都是n。 由于斜向进位的引入，同一行的全加器可以并发，行与行之间有结果依赖，所以前面4行需要4个全加器延迟，也就是n-1个全加器延迟，最后一行由于采用的是横向进位，所以这部分如果不做优化，器时间延迟也是n-1个全加器延迟，电路运行的关键路径如下，一共需要。。。。。。。 斜式时间复杂度优于横向进位阵列乘法器，由3n个全加器延迟结标变成2n级别，性能明显由于横向进位阵列乘法器
最后对比一下横向进位阵列乘法器，和斜向阵列乘法器，两个电路硬件成本都是n*n-1个全加器，只不过一个是4行5列，一个是5行4列但由于内部进位信号传递方式不同，直接导致性能差异加大，大约是1.5倍的差异， 不同结构硬件实现方式就和软件的算法一样，好的算法可以得到优秀的性能
计算机中的流水线
- 流水思想：复杂问题分解成细粒度任务并发
- 乘法流水线，浮点流水线，指令流水线
- 流水线 = 寄存器 + 组合逻辑 + 寄存器 + 组合逻辑 + 寄存器 … 数据通路串联
- 流水线时钟频率取决于组合逻辑的关键路径
回到阵列乘法器上，如果简单的5*5将阵列乘法器看做4个5位串行加法器的级联，我们可以将运算过程细分为4个步骤，第一步计算Y+。。。。 得到部分积，为了简化设计，我们这里可以直接采用10位的加法器进行运算，不足的位补零即可， 第二部将第一步运算的结果累加上Y2X*4，*4是考虑权值对齐的问题，同理第三部。。。。第四部是。。。。。。完成第四部运算后10位加法器的运算结果就是最终的成绩，如果吧这里绿色的横线当做流水接口，实际上就可以演变成一个乘法流水线，这里流水接口本质上就是一堆寄存器，用于锁存当前步骤运算的部分积，，，以及后续步骤运算所需要的Yi*X。 后续我们实验中要求大家按照这个思路实现一个乘法流水线。
刚刚我们给出的第一种流水线改造办法将乘法运算细分成了4部，实际上我们还可以按照横向进位阵列乘法器的关键路径进行流水细分，比如这里我们可以按照关键路径将乘法运算细分成11步，每一步中的全加器都可以完全并行，和刚刚介绍的方案1相比，这里流水线每一步的时间延迟更短，由10位全加器时延变成了一个全加器时延，流水线的时钟频率更高，流水线的性能更优。
这两种方法都是将乘法运算细分成若干更小的步骤，让后引入流水接口部件——寄存器锁存中间结果构成运算流水线，实际上浮点运算流水线也是采用了类似的方法。 真是计算机中的乘法器也是采用流水线实现的，目前大多采用布斯两位乘法+华莱士树的方式构成，如果你有兴趣可以研究一下。
变量与常数之间的乘法运算
- 整数乘法比移位和加法运算慢很多
- 编译器在处理变量与常数相乘时，用其它快速运算指令代替乘法
x\*20 -> (x<<4)+(x<<2) 乘法转换成了2次移位和1次加法 x\*15 -> (x<<4) – x 乘法转换成了1次移位和1次减法 - 移位加减组合运算和直接相乘结果一样的（包括溢出）
- 是否优化取决于组合运算周期数是否小于乘法开销
定点数除法
恢复余数除法
- 如何判断是否够减
- 利用补码作减法，判断余数符号即可
- 余数为负数时，必须恢复余数
- 将余数加除数，恢复成原值
- 求下一位商，必须将余数左移一位，再与除数比较
- 手工运算将除数右移？
- 注意这里余数放大了，最后结果要缩小
- 比较，上商（恢复），余数移位，再比较，
- 直到商的位数足够
问题：
- 需要进行恢复余数的操作
- 余数是负数，必须恢复余数
- 绝对值运算，余数不可能是负数
- 恢复余数的操作次数不确定
- 运算时间不固定
- 最慢除法（每次都不够除），拖慢除法速度
- 实际应用通常采用不恢复余数除法
不恢复余数除法
- n设某次余数为Ri，求下位商需将Ri左移一位，再减去除数Y进行比较，此过程可表示为
2Ri - Y - 余数Ri小于0时商上0，需要恢复余数，左移一位，再减除数Y比较
(2Ri - Y）+ Y = 2Ri
2*2Ri – Y =4Ri–Y = 2*(2Ri -Y) + Y - 不恢复余数法：余数Ri小于0时商上0，左移一位，再加除数Y比较
- n*n个CAS单元
- (n*n) ×4T
浮点数加减运算
规格化浮点数概念
- 由于浮点数是将数据的表示范围与精确度分别表示的数据表示方法，若不对浮点数的表示作出明确规定，同一个浮点数的表示就不唯一
- 规格化浮点数是指把一个浮点数按指定的格式进行转换，
- 由于浮点数是将数据的表示范围与精确度分别表示的数据表示方法，若不 对浮点数的表示作出明确规定，同一个浮点数的表示就不唯一，
- 以浮点数一般格式为例，规格化浮点数的尾数形式为: 00.1… 或 11.0…。
规格化浮点数方法
- 当尾数结果为 00.0… 或 11.1，需要左规格化即将尾数向左移动， 每移动一次，阶码减1，直到尾数形式为 00.1… 或 11.0…。
- 当尾数的结果为 01.… 或 10.， 表明尾数求和的结果 > 1,此时仅 需要执行一次右移规格化， 阶码加 1 ,尾数形式即为00.1… 或 11.0…
浮点数加减运算方法及其步骤
- 对阶
- 求阶差；
- 右移阶码小的浮点数的尾数并同步增加其阶码，直至两数阶码相等。
尾数加/减
- 尾数加/减运算 （用对阶后的尾数）
- 结果规格化
- 尾数非零时，要求绝对值≥0.5，尾数MSB=1
- 否则修改阶码并移动尾数，使其满足上述要求
- 目的：保证浮点数的编码唯一性
- 右移以实现规格化 向右规格化 右归 阶码+
- 右归时连同符号位进位位一起右移，阶码作加法
- 左移以实现规格化 向左规格化 左归 阶码-
- 左归时LSB位补0，阶码作减法
- 舍入
- 右移规格化时可能丢失一些低位的数值位, 为提高精度, 可采取舍入的方法:
- 0 舍 1 入 : 若右移出的是1则在最低位加1;
- 恒置 1 : 只要数字位1被移掉,就将最后一位恒置成1。
- 溢出处理
- 浮点数的溢出标志: 阶码溢出
- 阶码上溢 ： 阶码的符号位为 01
- 阶码下溢 ： 阶码的符号位为 10
- 尾数上溢 右归
- 尾数下溢 左归
例1 两浮点数 x = 2^101×0.11011011，y = 2^111×(-0.10101100)。假设尾数在计算机中以补码表示，可存储10位尾数，2位符号位，阶码以补码表示，双符号位, 求 x + y。
解：将x , y转换成浮点格式
[x]浮 = 00101, 00.11011011
[Y]浮 = 00111, 11.01010100
步骤1：对阶，阶差为 Ex − Ey = [Ex]补 + [−Ey]补
[−Ey]补=11001 Ex−Ey＝00101＋11001＝11110 = -2 < 0
小阶对大阶， X阶码加2， 尾数右移2位
[x]浮 = 00111,00.0011011011 保留位
[x]浮 = 00111, 00.0011011011 保留位
[Y]浮 = 00111, 11.01010100
步骤2：尾数求和
[X+Y]浮 = 00111, 11.1000101011 保留位参与运算
步骤3：结果规格化
[X+Y]浮 = 00110, 11.000101011 非规数，左归1位, 阶码减1，保留位？
步骤4：舍入处理
[X+Y]浮 = 00110, 11.00010110 (0舍1如法)
[X+Y]浮 = 00110, 11.00010101 (截去法)
步骤5：溢出判断
[X+Y]浮 = 2110 x (-0.11101011) 无溢出
特殊例子：
X=2^111 * 0.11111111，Y=2^111 * 0.10000001
[X]浮 = 0111, 0.1111 1111
+ [Y]浮 = 0111, 0.1000 0001
[X+Y]浮 = 0111, 1.1000 0000
尾数上溢，右归一位，连同符号位进位位一起右移1位，阶码加1
[X+Y]浮 = 1000, 0.1100 0000
阶码正溢出，运算结果上溢
X=2^-1000 * -0.11110000，Y=2^-1000 * 0.10000001
[X]浮 = 1000, 1.0001 0000
+ [Y]浮 = 1000, 0.1000 0001
[X+Y]浮 = 1000, 1.1001 0001
尾数下溢，左归一位， 左移一位，阶码减1
[X+Y]浮 = 1000, 1.0010 0010
1000+1111=0111 =7
阶码负上溢，运算结果下溢
浮点数乘法运算
X=2^m * Mx Y=2^n * My
X * Y = ( 2^m * Mx ) * ( 2^n * My ) = 2^m+n * (Mx * My)
(1) 阶码相加
阶码相加可能产生溢出，要进行溢出判断，如溢出计算机要进行处理
(2) 尾数相乘
尾数相乘可得积的尾数，可按定点乘法运算方法运算
(3) 结果规格化
可按浮点加/减法运算规格化方式处理，舍入方式也相同
浮点数除法运算
如：X=2^m * Mx Y=2^n * My
X / Y = ( 2^m * Mx ) / ( 2n * My ) = 2^m-n * (Mx / My)
尾数调整
如被除数尾数大于除数尾数 (绝对值)，则将被除数尾数右移一位，阶码+1
阶码求差
商的阶码等于被除数的阶码减去除数的阶码
尾数相除
以被除数的尾数除以除数的尾数以获得商的尾数，尾数相除与定点除法运算相同
习题
单符号位补码表示的两个同号数相加或异号数相减时，所得结果的符号位SF和进位标志CF进行（D ）运算为1时，表示运算的结果产生溢出
A.与非 B.与 C.或 D.异或
若采用双符号位补码运算，运算结果的符号位为10，下列结论中错误的是 AB
A.产生了上溢 B.运算结果溢出，结果为正数 C.产生了下溢 D.运算结果溢出，结果为负数
计算机运算溢出检测机制，采用双符号位，00表示正号，11表示负号。如果进位将会导致符号位不一致，从而检测出溢出。结果的符号位为01时，称为上溢；为10时，称为下溢。
以下说法正确的是ABCD
A.n位小数的补码一位乘法（Booth算法），需做n+1次运算，第n+1次不移位
B.浮点运算可由阶码运算和尾数运算两个部分联合实现
C.补码加减交替法是一种不恢复余数法
D.在定点小数补码一位除法中，为了避免溢出，被除数的绝对值一定要小于除数的绝对值