chapter6 | 运算方法和运算部件

Yama-lei2025年3月26日大约 14 分钟

[TOC]

第一讲 | 基本运算部件

想要实现高级语言程序设计的各种运算，需要将表达式转换成指令。

比如

int a,b=5;

将数据以补码的形式存入寄存器中。指令->汇编->机器指令。

软件（高级语言设计），指令（ISA），硬件设计，环环相扣。

所有的运算都可以通过ALU+逻辑部件实现。

有关门延迟这一部分,建议阅读：全加器以及行波进位加/减法器时延的计算 - 知乎，因为ppt就是一坨。

串行(行波)进位加法器:

我们先回顾一下什么是全加器FA：

在这个全加器里，Cout的延迟是2，F的延迟是3；

由多个全加器相连接，前一个全加器的进位作为这一个加法器的cin。

效率慢

每一个FA（全加器）需要经过两级门延迟，n位的串行进位加法器就需要2n个门延迟得到Cn进位，2n+1个延迟得到Fn。

生成最后一位的Cout在2n时生成，因此最后一位的F在2n+1位生成。

并行(先行)进位加法器 CLA

先行进位部件：（CLU)

一共需要6级延迟就能得到最终的和。

其中xi和yi在第一个时间段生成gi和pi

接着两个门延迟后，生成了Ci1

最后三个门延迟生成和Fi。

因此c4其实在第三个

局部先行进位加法器

比如：使用4个4位先行进位加法器进行串行，实现一个16位的加法器。

（图中的数字代表的是时刻）

多级先行进位加法器

组内并行，组间仍然并行。

n位带标志加法器

我们在加法器中加入一些标志输出，用于指示一些特殊状态（如：溢出）

对于signed类型，有意义的是：

ZF：0标志位
OF：代表是否出现溢出。
判断是否出现Overflow的方法：
1. 看X+Y的和，如果$C_n$(符号位的进位)和$C_{n-1}$(即X和Y相加之后得到的符号位)的相同，则没有发生溢出。即$OF= C_n \oplus C_{n-1}$
2. 看X，Y，以及X+Y的符号位。如果$X_{n-1}=Y_{n-1} \neq C_{n-1}$ 那么$OP=1$.
SF:符号位标志。

对于unsigned类型，有意义的是：

ZF
CF借位进位标志 ($CF= cin \oplus cout$)

溢出标志$OF=C_n \oplus C_{n-1}$
符号标志SF $SF=F_{n-1}$ (即，最高位)
零标志$ZF=1 \space \text{if F=0 else 0}$
进位借位标志$CF=Cout \oplus Cin$

ALU：算数逻辑运算单元

通过一个操作控制端（ALUop），来决定ALU进行什么样的运算

通过多路选择器来决定输出哪一个信号。

核心是加减运算，输出结果和标志信息

第二讲 | 定点数运算

加减法

$[x+y]_补 =2^n+x+y= 2^n+x+2n+y= [x]_补+[y]_补 (mod 2n )$

$[x-y]_补=2^n+x-y= 2^n+x+2n-y= [x]_补+[-y]_补 (mod 2n )$

补码的和就是和的补码，差的补码也是补码的和。

因此补码可以实现加减法的统一.

上面这个部件十分的神奇！Sub为1的时启动加法，sub还同时作为cin输入，相当于计算$A+\overline B+1 (mod \space 2^n)$ ； sub为0的时候，就正常计算就好。

有符号数singed整数加减法：

用上述加减法器件进行运算signed整数，例子如下：

OF: overflow; SF: 符号标志位 ZF: 零标志位。

如果用减法来判断两个数的大小，那么在这里我们要看是否有OF=SF，如果满足的话，说明前一个操作数大于后一个操作数。即$less= OF \cdot SF$ (如果OF=SF，那么前一个数大于后一个数)

无符号数unsigned整数的加减法：

用这个部件对补码进行加减法显然是可以实现的：都是将输入的两个机器码输入，如果加法，则直接相加并取模；如果是减法，那么将第二个操作数取反再相加取模。

这个部件实际上也可以实现无符号数的加减法。

对于加法很好理解，无非是一位一位相加，求进位。

如果比较两个数的大小，那么就看溢出位，$less=cin \oplus cout$，即，如果有借位就说明前者比后者小。

乘法运算

无符号数 unsigned乘法

Warning:在学习的过程中，我不慎将无符号位，原码补码两个概念搞混：

无符号数：没有符号位。无符号数乘法默认是1位

有符号：原码或者补码表示，都带有符号！！！前者有1位或者2位，后者的算法称为布斯（Booth)算法！

无符号数乘法可以由加法和移位实现：
$$
X×Y= \sum_{i=1}^{i=n}(X × yi×2^{-i})
$$
利用递归的方法，可以得到如下的算法：

以32位原码的乘法为例，两个32位的原码相乘，至少需要64位存储积。

注意在高级语言程序中，有溢出的可能，比如只要32位，那么只会从64位中取低32位。

在实际的硬件实现中：1. C存储循环次数 2. 一个寄存器存储一个乘数 3. 一个存储器同时存储一个乘数和积。

即每一次都将高32位和原先的X相加，如果Y的最后一位是0，那么直接将高32位返回，如果是1，那么相加。循环32次。

原码两位乘法

前面介绍的都是一位乘法，即一位一位的运算，如果运算32位就需要32次循环，实际上，可以一次运算两位。

类似的，我们一次性从乘数Y中取两位，如果Y=00，那么无需相加，直接右移；如果为01，则加上X并右移两位；10则加上2个X并右移；11的话按理是加上3个X并右移。但是实际上采取的是先减去一个X右移两位，并通知下一位多加一个X。

因此，考虑到前一位的标志，一共分成了8种情况。

原码2位乘法举例：

（由于移位2位需要用到减法，因此采取补码实现加法）

采取模8补码，算术移位。

（此处看ppt）

推导过程（过个眼瘾就行）:
$$
\space y= -y_{n-1}2^{{n-1}+\sum_{i=0}}y_i2^i
$$
If we define that $y_{-1}=0$, then we can get that
$$
y=\sum_{i=0}^{{i=1}(y_{i-1}-y_i)*2}i
$$
可以得到部分积公式：
$$
P_n=2^{-1}(P_{n-1}+(y_{i-1}-y_i)x)
$$
根据当前的位数和前一次的位数可以分成下面这四种可能：

一个运算的例子：

那么什么时候会出现溢出呢？
- 如果高四位都是符号位，那么结果不会溢出
如果[-x]的补码溢出了呢？
1. 方法1，增加符号位，（比如-8四位补码无法表示，但是我们可以加一位符号位）
2. 方法2，移位实现（因为我不清楚，所以略去）

补码两位乘法

类似原码两位乘法，需要根据当前的位数去查表，确定在右移之前需要加多少X，or 多少个X的补码（自行看ppt）

补充：快速乘法

流水快速乘法器
- n位运算需要n个ALU
- 完全采取组合逻辑电路，不需要clk的控制，速度快
CRA整列乘法器

溢出判断

两个n位的机器数通过无符号和有符号乘法算出的低n位其实是相同的，WHY？

硬件: 在硬件中

如果结果只保留n位：

无符号：高n位全为0。
有符号：高n位全是低n位的符号位（比如1111 1001,or 0000 0011，容易验证均没有溢出）。

应该要能判断这个表中的溢出与否情况

乘法与指令

机器指令包括：无符号成绩指令和有符号乘积指令

在 RISC-V 中：
- mul 指令执行普通的乘法，返回低 32 位乘积。
- mulh 和 mulhu 分别处理带符号整数乘法和无符号整数乘法，返回高 32 位乘积。
  这里的乘法运算其实只有一次，而不是两次，只是在ISA中用两条指令来分别取出高32位和低32位。

两个n位的数相乘在硬件中会保留2n位的乘积，但是只会取n位。如果是无符号乘法，那么看高n位，不全位0，那么溢出；如果有符号位，那么看高n位是否全为低n位的符号位，如果不是，那么溢出。

溢出指的都是只保留低n位的情况

如何判断两个int类型的乘积是否溢出？

1.   bool overflow(int a, int b){return (a*b)/b!=a;}

2.   bool overflow(int a, int b){
		long long mul=(long long)a*b;
    	return mul!=(int)mul
     }

**The End: **

注意：只有原码的一位乘法才是逻辑又移，其他的都是算术右移。因为原码的两位补码需要用到补码来表示负数。而补码乘法显然使用算术移码。

除法运算

定点数的除法运算

在除之前：

被除数=0，除数！=0，或者在定点除法中abs(dividend)<abs(divisor),结果均为0
如果除数为0，那么除0错误
如果是浮点数，可以用阶码全为1，尾数全为0来表示infinite
如果dividend and divisor both are 0, then the result is "NAN".
The NAN 在浮点数中用阶码全为1，尾数不全为0来表示

定点数除法的步骤：

将被除数补位到2n位。
如果是定点小数，那么补低n位，；如果是定点整数，那么补高n位。
将这个2n位数和被除数相除。
进行恢复余数除法或者不恢复余数除法

硬件实现：

除数寄存器Y：存放除数。
余数寄存器R：初始时高位部分为高32位被除数；结束时是余数。
余数/商寄存器Q：初始时为低32位被除数；结束时是32位商。
循环次数计数器Cn：存放循环次数。初值是32（不包括第一次试商），每循环（移位）一次，Cn减1，当Cn=0时，除法运算结束。
ALU：除法核心部件。在控制逻辑控制下，对于寄存器R和Y的内容进行“加/减”运算，在“写使能”控制下运算结果被送回寄存器R。

一个例子（恢复余数法）：

因为除法需要用到减法，因此我们用补码来表示无符号数。

X-Y=X+[Y]补; 别把补码和反码弄混了！

如果中间余数够减：整体左移并且上1
如果中间余数不够减：先恢复余数，在左移，补0

最后得到的余数部分要右移一位，将绿色的0给移出。

不恢复余数法（交替加减法）

根据恢复余数法(设D为除数，Ri=2Ri-1-D为第i次中间余数)，有：

l若Ri<0,则商上“0”，做加法恢复余数，即：

Ri+1=2(Ri+D)-D=2Ri + D (“负，左移，上商0，加”)

l若Ri>=0,则商上“1”，不需恢复余数，即：

Ri+1=2Ri - D (“正，左移，上商1，减”)

省去了恢复余数的过程

注意：最后一次上商为“0”的话，需要“纠余”处理，即把试商时被减掉的除数加回去，恢复真正的余数。

不恢复余数法也称为加减交替法

补码最终在寄存器中得到的一位都不能丢，而在无符号的除法运算中，因为采用了补码来实现减法，因而最后得到的也是补码，需要舍弃掉符号位，剩下的是得到的商；

其他内容

除以2^k的快速算法：

无符号整数：逻辑右移，高位补0，低位丢弃。
带符号整数：算术右移，高位补符，低位丢弃。

综合考虑了各类定点运算之后，发现所有的运算都可以通过加和移位来实现；

可以通过ALU（or 加法器）结合寄存器，选择器等部件实现一个运算数据通路；

浮点数运算

浮点数的运算老师说不考，但是考研408会考

先回顾之前的浮点数相关知识：

非规格化数：阶码为0 （代表是-127），尾数不为0，没有前导1；
0，阶码和尾数都为0；
无穷：阶码全为1，尾数全为0；
NAN：阶码全为1，尾数不全为0；
其余的就都是规格化数，阶码的范围是1-254，尾数默认前导1；

浮点数规格化数的范围（以SP的正半部分为例）：
$$
2^{-126}-2*(2-2^{-23})
$$
运算的方法：

可能出现下面的情况：

上述运算结果可能出现以下几种情况：

阶码上溢：一个正指数超过了最大允许值 =〉+∞/-∞/溢出
阶码下溢：一个负指数比最小允许值还小 =〉+0/-0
尾数溢出：最高有效位有进位 =〉右规
非规格化尾数：数值部分高位为0 =〉左规
右规或对阶时，右段有效位丢失 =〉尾数舍入

IEEE754规定的几种异常情况：

① 无效运算（无意义）

运算时有一个数是非有限数，如：加 / 减∞、0 x ∞、 ∞/∞等
结果无效，如：源操作数是NaN、0/0、x REM 0、 ∞ REM y 等

② 除以0（即：无穷大）

③ 数太大（阶码上溢）: 对于SP，阶码 E >1111 1110 (指数大于127)

④ 数太小（阶码下溢）: 对于SP，阶码 E < 0000 0001(指数小于-126-23)

⑤ 结果不精确（舍入时引起），例如1/3，1/10等不能精确表示成浮点数

浮点数加减运算

对阶
采取的都是小阶向大阶表示（都是右移），防止尾数溢出（溢出的几位可以用附加位进行暂时存储）。
尾数相加减
规格化
将尾数进行规格化，左移或右移，使得小数点前有一个隐含的前导1。
如果尾数比规定的数长需要舍入；（舍入有可能导致进位，最终需要右规）
如果尾数全为0（包含隐藏位在内的）那么应该要把阶码也赋值为0，因为这才是浮点数表示0的方法。

附加位的作用：以保护对阶时右移的位或运算的中间结果。提高运算精度。

（比如舍入的时候的精度）

浮点数的乘法

浮点数乘 / 除法步骤

（Xm、Ym分别是X和Y尾数原码， Xe和Ye 分别是X和Y阶移码）

(1)求阶： Xe + Ye + 127

(2)尾数相乘除： Xm */Ym （两个形为1.xxx的数相乘/除）注意有个**隐藏的1 **！！

尾数相乘的时候最多要右规一次，尾数相除的时候左规的次数不定

(3) 两数符号相同，结果为正；两数符号相异，结果为负；

(4) 当尾数高位为0，需左规；当尾数最高位有进位，需右规。

(5) 如果尾数比规定的长，则需考虑舍入。

(6)若尾数是0，则需要将阶码也置0。

(7) 阶码溢出判断