当前位置：首页 > news >正文

计算机组成原理笔记(十六)——4.1基本算术运算的实现

news 来源：原创 2025/8/3 19:55:42

计算机中最基本的算术运算是加法运算，加、减、乘、除运算最终都可以归结为加法运算。

4.1.1加法器

一、加法器的基本单元

加法器的核心单元是 全加器（Full Adder, FA），而所有加法器都由 半加器（Half Adder, HA） 组合实现。

1. 半加器（HA）

功能：实现两个1位二进制数相加（不考虑低位进位）。
输入：A（加数）、B（被加数）
输出：Sum（和）、Carry（进位）
真值表：

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

逻辑表达式：
$\text{Sum} = A \oplus B \\ \text{Carry} = A \cdot B$

电路图：

在这里插入图片描述

2. 全加器（FA）

功能：实现两个1位二进制数与一个低位进位相加。
输入：A（加数）、B（被加数）、C_in（低位进位）
输出：Sum（和）、C_out（进位）
真值表：

A	B	C_in	Sum	C_out
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

逻辑表达式：
$\text{Sum} = A \oplus B \oplus C_{in} \\ C_{out} = A \cdot B + (A \oplus B) \cdot C_{in}$

电路结构示意图（由两个半加器组合）：

在这里插入图片描述

二、加法器的类型与工作原理

1. 串行加法器

结构：通过移位寄存器依次处理每一位，每次计算1位。
电路图：

在这里插入图片描述

特性：

优点：电路简单，成本低。
缺点：速度极慢，需n个时钟周期完成n位加法。
关键问题：进位信号需逐级传递（行波进位）。

2. 并行加法器

所有位同时计算，但进位传递是关键瓶颈。分为两类：

(1) 串行进位加法器

结构：多个全加器串联，前级的C_out作为后级的C_in。
电路示意图：

在这里插入图片描述

延迟分析：

若每级进位延迟为2t，则n位加法总延迟为2n t。
例：32位加法需要64t耗时。

(2) 超前进位加法器（CLA）

核心思想：提前计算各级进位，消除级联依赖。
进位生成公式：
$C_i = G_i + P_i \cdot C_{i-1} \\ \text{其中：} \quad G_i = A_i \cdot B_i \quad (\text{生成进位}) \\ P_i = A_i \oplus B_i \quad (\text{传播进位})$

4位CLA示例：

在这里插入图片描述

优点：极快完成所有位的计算，但电路复杂度高。

三、关键对比

特性	串行加法器	并行串行进位	超前进位
速度	极慢（O(n)）	较快（O(n)）	极快（O(1)）
硬件复杂度	极简	中等	复杂
适用场景	嵌入式低功耗设备	通用CPU	高性能计算
典型延迟	32位需64t	32位需64t	4位仅需4t

四、应用实例

现代CPU中，ALU的加法器采用 分组超前进位 结构：

16位加法器：4个4位CLA模块 + 一级CLA控制。
延迟：仅需计算组内和组间的并行进位。

在这里插入图片描述

通过这种分层设计在速度和复杂度之间取得平衡。

4.1.2进位的产生和传递

进位逻辑是加法器设计中影响运算速度的核心部分。

一、进位信号的基本逻辑

全加器的进位输出由两部分构成：

本地进位（本地生成）： $G_i = A_i \cdot B_i$
当 $A_i$ 和 $B_i$ 均为1时，必然产生进位（与低位无关）。
传递进位（传递依赖）： $P_i = A_i \oplus B_i$
当 $A_i$ 或 $B_i$ 为1时，低位进位可传递至高位。

进位表达式可简化为：
$C_i = G_i + P_i \cdot C_{i-1}$

逻辑电路图：
在这里插入图片描述

二、并行进位技术

1. 完全并行进位（CLA）

所有进位直接由原始输入和最低位进位 $C_0$ 同时生成，不依赖相邻进位。
4位CLA的进位表达式：
$\begin{aligned} C_1 &= G_1 + P_1 C_0 \\ C_2 &= G_2 + P_2 G_1 + P_2 P_1 C_0 \\ C_3 &= G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 C_0 \\ C_4 &= G_4 + P_4 \text{(嵌套前3位进位生成逻辑)} \end{aligned}$
优点：延迟固定为 $2t_y$ （1级 $G_i/P_i$ 计算 +1级逻辑门）。
缺点：硬件复杂度随位宽指数增长，实际应用中需分组实现。

2. 分组并行进位

两层设计思想：组内并行（Group Carry Lookahead）+ 组间并行。

组内并行（如4位一组）：组内所有进位同时生成。
组间并行：通过“组生成函数” $G^*$ 和“组传递函数” $P^*$ 加速跨组进位。

关键公式：
$\begin{aligned} \text{组生成函数} \quad G^* &= G_4 + P_4 G_3 + P_4 P_3 G_2 + P_4 P_3 P_2 G_1 \\ \text{组传递函数} \quad P^* &= P_4 P_3 P_2 P_1 \\ \text{组进位输出} \quad C_4 &= G^* + P^* C_0 \end{aligned}$

流程图（16位两级分组CLA）**：

在这里插入图片描述

三、分组方式对比

进位方式	硬件复杂度	最大延迟	适用场景
串行进位	低（简单级联）	$O (n)$	低速低成本芯片
单级分组CLA	中等（组内并行）	$O(\sqrt{n})$	通用CPU（如32位处理器）
多级分组CLA	高（多级逻辑）	$O(\log n)$	高性能计算（如GPU）

四、典型应用与优化

1. 示例：16位两级CLA

组内延迟：每组4位的CLA生成 $C_4$ 需 $2t_y$ 。
组间延迟：通过高层CLA生成跨组进位，再传递回组内，总延迟 $4t_y$ 。

关键优化点：

增量进位计算：组内生成 $G_i$ 和 $P_i$ 后，直接用于高层逻辑，避免重复计算。
专用逻辑电路：使用74181（4位ALU）和74182（CLA扩展器）实现快速级联。

五、总结

并行进位核心：通过预先计算进位生成与传递关系，消除等待相邻进位时间。
工程权衡：硬件资源与速度的平衡，分组策略需根据芯片制程和应用场景调整。
实际应用：现代CPU多采用多级分组（如64位加法器分为4×16位组），配合动态调度优化效率。

4.1.3并行加法器的快速进位

一、快速进位的必要性

传统串行进位的并行加法器（行波进位）进位延迟与位数成正比（如16位加法器延迟32ty）。快速进位技术通过并行化处理减少进位传播时间，核心思路是通过逻辑预判提前生成所有进位。

二、并行进位逻辑表达式

对于每位进位 $C_i$ ，通过进位生成函数 $G_i$ 和进位传递函数 $P_i$ 递归展开：

单级先行进位（完全并行）
$\begin{aligned} C_1 &= G_1 + P_1 C_0 \\ C_2 &= G_2 + P_2 G_1 + P_2 P_1 C_0 \\ C_3 &= G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 C_0 \\ C_4 &= G_4 + P_4 C_3 \quad (\text{依此类推}) \end{aligned}$
硬件实现矛盾：
- 优点：所有进位仅依赖 $G_i/P_i$ 和 $C_0$ ，可同时生成。
- 缺点：公式复杂度随位数指数增长（n位数需 $n$ 级逻辑门），实际需分组分层处理。

三、分组进位技术

1. 单级分组并行进位（组内并行、组间串行）

分组示例：将16位分为4组，每组4位。
每组生成4位进位：

优点：硬件简单，延迟降低为 $8 t y$ （4组 × 2ty/组）。

2. 多级分组并行进位（组间并行）

核心逻辑：
- 每组（如4位）生成组进位生成函数 $G^*$ 和组进位传递函数 $P^*$ ：
  $G^* = G_4 + P_4 G_3 + P_4 P_3 G_2 + P_4 P_3 P_2 G_1 \\ P^* = P_4 P_3 P_2 P_1$
- 高层CLA电路计算跨组进位：
  $C_{4(k+1)} = G^*_k + P^*_k C_{4k} \quad (k=0,1,2,3)$
示例（以16位双重分组为例）：

在这里插入图片描述

- **延迟**：仅 $6ty$（组内2ty + 组间2ty + 二次组内2ty）

四、硬件电路实现

使用 CLA电路生成器（如74182芯片）与 基本加法单元（如74181）：

在这里插入图片描述

五、典型对比

类型	硬件复杂度	最大延迟	适用场景
行波进位	低	$32 t y$	低速设备
单级分组（4位一组）	中等	$8 t y$	通用CPU
多级分组双	高	$6 t y$	高性能计算（GPU）

六、关键流程图

单级分组硬件结构

在这里插入图片描述

多级分组信号流

在这里插入图片描述

通过上述机制，快速进位技术显著降低了加法运算的延迟，在现代CPU与高性能计算中广泛应用。

4.1.1加法器

一、加法器的基本单元

1. 半加器（HA）

2. 全加器（FA）

二、加法器的类型与工作原理

1. 串行加法器

2. 并行加法器

(1) 串行进位加法器

(2) 超前进位加法器（CLA）

三、关键对比

四、应用实例

4.1.2进位的产生和传递

一、进位信号的基本逻辑

二、并行进位技术

1. 完全并行进位（CLA）

2. 分组并行进位

三、分组方式对比

四、典型应用与优化

1. 示例：16位两级CLA

五、总结

4.1.3并行加法器的快速进位

一、快速进位的必要性

二、并行进位逻辑表达式

三、分组进位技术

1. 单级分组并行进位（组内并行、组间串行）

2. 多级分组并行进位（组间并行）

四、硬件电路实现

五、典型对比

六、关键流程图

单级分组硬件结构

多级分组信号流

相关文章：