1. 为什么我们需要多级先行进位加法器记得我第一次设计一个32位加法器的时候用的是最基础的串行进位方式。结果测试时发现延迟高得离谱简直像在等蜗牛爬行。这就是传统串行进位的致命伤——每一位的进位都要等前一位算完才能开始32位加法要等32个门延迟这时候并行进位也叫先行进位就派上用场了。它的精髓在于所有进位信号同时生成不再需要等待前一位。比如计算C1G1P1C0和C2G2P2G1P2P1C0时C1和C2可以同步产生因为它们都只依赖初始进位C0。实测下来4位并行加法器的速度能比串行快3倍以上。但问题又来了——当我尝试做64位全并行加法器时发现最高位的进位表达式长得能绕地球一圈电路复杂度呈指数级增长这在实际芯片设计中根本不可行。于是工程师们想出了折中方案分组并行进位。就像把一栋高楼分成几个单元单元内用电梯并行单元间可以用楼梯串行或者更多电梯多级并行。2. 多级先行进位的工作原理2.1 分组策略的艺术假设我们要设计一个16位加法器可以把它切成4个4位小组。每个小组内部采用4位CLACarry Look-Ahead先行进位电路这时候会产生两个关键信号组生成信号G*表示这个小组自己就能产生进位比如小组内发生了37这样的运算组传播信号P*表示这个小组会传递来自低位的进位比如小组内发生了64这样的运算我用Verilog写过的一个典型案例module CLA_4bit( input [3:0] G, input [3:0] P, input C0, output [3:0] C, output G_group, output P_group ); assign C[0] G[0] | (P[0] C0); assign C[1] G[1] | (P[1] G[0]) | (P[1] P[0] C0); // ...更高位进位类似 assign G_group G[3] | (P[3] G[2]) | (P[3] P[2] G[1]) | (P[3] P[2] P[1] G[0]); assign P_group P[3] P[2] P[1] P[0]; endmodule2.2 两级进位网络设计当小组内部的CLA搞定后小组之间怎么连接才是真正的技术活。这里有个经典的两级方案第一级每个小组内部并行计算自己的进位第二级用小组的G和P生成小组间的进位具体实现时我们会用到一个叫**BCLABlock CLA**的电路来处理组间进位。这就像公司里的层级管理——小组长管组员大组长管小组长。实测在28nm工艺下这种设计能让64位加法器的延迟从原来的2.3ns降到0.8ns。3. 从理论到电路实现3.1 CLA电路的门级实现先看一个4位CLA的核心电路结构。以C4为例它的逻辑表达式是 C4 G3 P3G2 P3P2G1 P3P2P1G0 P3P2P1P0C0对应的门电路需要4个AND门三级1个5输入OR门在实际布局时我习惯用动态电路来优化速度。比如下面这个用Domino逻辑实现的进位链G3 / \ P3 G2 / \ / \ ... ... / \ C0 OR_tree3.2 版图设计中的坑第一次画CLA版图时我犯了个低级错误——把所有的PG信号线都走同一层金属。结果芯片回来测试发现时序不收敛因为金属拥挤导致RC延迟超标。后来改用M2层走垂直方向的进位信号M3层走水平方向的PG信号关键路径用更宽的金属线还有个经验在65nm以下工艺晶体管的漏电流会成为大问题。需要在非关键路径插入睡眠晶体管把静态功耗从15mW降到2mW左右。4. 实战设计一个9位两级CLA加法器4.1 架构设计按照3×3的分组方案第一级3个3位CLA模块第二级1个3位BCLA模块求和部分9个全加器关键信号连接每个3位CLA生成自己的G和PBCLA接收各组的G*、P*和C0输出组进位C3、C6将C3、C6反馈回各小组4.2 关键电路实现这是BCLA模块的核心代码module BCLA_3group( input [2:0] G_group, input [2:0] P_group, input C0, output [2:0] C_out ); assign C_out[0] G_group[0] | (P_group[0] C0); assign C_out[1] G_group[1] | (P_group[1] G_group[0]) | (P_group[1] P_group[0] C0); assign C_out[2] G_group[2] | (P_group[2] G_group[1]) | (P_group[2] P_group[1] G_group[0]) | (P_group[2] P_group[1] P_group[0] C0); endmodule4.3 时序优化技巧在FPGA上实现时我发现Xilinx的UltraScale架构有个特性每个SLICE有8个F7MUX。利用这个特点可以把4位CLA的关键路径优化为第一级用LUT6计算G和P第二级用F7MUX实现进位选择第三级用CARRY4链完成最终求和这样布局后关键路径延迟从原来的1.2ns降到了0.7ns。不过要注意的是Vivado有时会把进位链优化掉需要加(* keep_hierarchy yes *)属性来保护关键结构。5. 进阶优化策略5.1 混合进位方案在最新的RISC-V芯片设计中我采用了一种混合方案低位8位用全并行CLA速度快中间16位用两级CLA面积小高位8位用串行进位功耗低实测在TSMC 7nm工艺下这种设计比纯CLA方案节省15%的面积功耗降低22%而性能只损失3%。5.2 异步进位技术对于超长位宽如512位加密运算可以考虑异步进位。原理是每个小组独立工作通过握手信号传递进位用弹性管道存储中间结果我在一个密码协处理器上试过这种设计虽然最坏情况延迟较高但平均延迟比同步设计低40%。不过要注意解决亚稳态问题需要在跨时钟域处加两级同步器。
多级先行进位加法器设计与实现：从理论到电路实践
1. 为什么我们需要多级先行进位加法器记得我第一次设计一个32位加法器的时候用的是最基础的串行进位方式。结果测试时发现延迟高得离谱简直像在等蜗牛爬行。这就是传统串行进位的致命伤——每一位的进位都要等前一位算完才能开始32位加法要等32个门延迟这时候并行进位也叫先行进位就派上用场了。它的精髓在于所有进位信号同时生成不再需要等待前一位。比如计算C1G1P1C0和C2G2P2G1P2P1C0时C1和C2可以同步产生因为它们都只依赖初始进位C0。实测下来4位并行加法器的速度能比串行快3倍以上。但问题又来了——当我尝试做64位全并行加法器时发现最高位的进位表达式长得能绕地球一圈电路复杂度呈指数级增长这在实际芯片设计中根本不可行。于是工程师们想出了折中方案分组并行进位。就像把一栋高楼分成几个单元单元内用电梯并行单元间可以用楼梯串行或者更多电梯多级并行。2. 多级先行进位的工作原理2.1 分组策略的艺术假设我们要设计一个16位加法器可以把它切成4个4位小组。每个小组内部采用4位CLACarry Look-Ahead先行进位电路这时候会产生两个关键信号组生成信号G*表示这个小组自己就能产生进位比如小组内发生了37这样的运算组传播信号P*表示这个小组会传递来自低位的进位比如小组内发生了64这样的运算我用Verilog写过的一个典型案例module CLA_4bit( input [3:0] G, input [3:0] P, input C0, output [3:0] C, output G_group, output P_group ); assign C[0] G[0] | (P[0] C0); assign C[1] G[1] | (P[1] G[0]) | (P[1] P[0] C0); // ...更高位进位类似 assign G_group G[3] | (P[3] G[2]) | (P[3] P[2] G[1]) | (P[3] P[2] P[1] G[0]); assign P_group P[3] P[2] P[1] P[0]; endmodule2.2 两级进位网络设计当小组内部的CLA搞定后小组之间怎么连接才是真正的技术活。这里有个经典的两级方案第一级每个小组内部并行计算自己的进位第二级用小组的G和P生成小组间的进位具体实现时我们会用到一个叫**BCLABlock CLA**的电路来处理组间进位。这就像公司里的层级管理——小组长管组员大组长管小组长。实测在28nm工艺下这种设计能让64位加法器的延迟从原来的2.3ns降到0.8ns。3. 从理论到电路实现3.1 CLA电路的门级实现先看一个4位CLA的核心电路结构。以C4为例它的逻辑表达式是 C4 G3 P3G2 P3P2G1 P3P2P1G0 P3P2P1P0C0对应的门电路需要4个AND门三级1个5输入OR门在实际布局时我习惯用动态电路来优化速度。比如下面这个用Domino逻辑实现的进位链G3 / \ P3 G2 / \ / \ ... ... / \ C0 OR_tree3.2 版图设计中的坑第一次画CLA版图时我犯了个低级错误——把所有的PG信号线都走同一层金属。结果芯片回来测试发现时序不收敛因为金属拥挤导致RC延迟超标。后来改用M2层走垂直方向的进位信号M3层走水平方向的PG信号关键路径用更宽的金属线还有个经验在65nm以下工艺晶体管的漏电流会成为大问题。需要在非关键路径插入睡眠晶体管把静态功耗从15mW降到2mW左右。4. 实战设计一个9位两级CLA加法器4.1 架构设计按照3×3的分组方案第一级3个3位CLA模块第二级1个3位BCLA模块求和部分9个全加器关键信号连接每个3位CLA生成自己的G和PBCLA接收各组的G*、P*和C0输出组进位C3、C6将C3、C6反馈回各小组4.2 关键电路实现这是BCLA模块的核心代码module BCLA_3group( input [2:0] G_group, input [2:0] P_group, input C0, output [2:0] C_out ); assign C_out[0] G_group[0] | (P_group[0] C0); assign C_out[1] G_group[1] | (P_group[1] G_group[0]) | (P_group[1] P_group[0] C0); assign C_out[2] G_group[2] | (P_group[2] G_group[1]) | (P_group[2] P_group[1] G_group[0]) | (P_group[2] P_group[1] P_group[0] C0); endmodule4.3 时序优化技巧在FPGA上实现时我发现Xilinx的UltraScale架构有个特性每个SLICE有8个F7MUX。利用这个特点可以把4位CLA的关键路径优化为第一级用LUT6计算G和P第二级用F7MUX实现进位选择第三级用CARRY4链完成最终求和这样布局后关键路径延迟从原来的1.2ns降到了0.7ns。不过要注意的是Vivado有时会把进位链优化掉需要加(* keep_hierarchy yes *)属性来保护关键结构。5. 进阶优化策略5.1 混合进位方案在最新的RISC-V芯片设计中我采用了一种混合方案低位8位用全并行CLA速度快中间16位用两级CLA面积小高位8位用串行进位功耗低实测在TSMC 7nm工艺下这种设计比纯CLA方案节省15%的面积功耗降低22%而性能只损失3%。5.2 异步进位技术对于超长位宽如512位加密运算可以考虑异步进位。原理是每个小组独立工作通过握手信号传递进位用弹性管道存储中间结果我在一个密码协处理器上试过这种设计虽然最坏情况延迟较高但平均延迟比同步设计低40%。不过要注意解决亚稳态问题需要在跨时钟域处加两级同步器。
