天津大学数字集成电路第十讲加法器

第十讲数据通路设计TianJinUniversityshizaifeng@TJU.ASICCenter---ArnoldShi大多数数字电路按功能划分数据通路（如加法器、乘法器、移位器）存储器控制电路I/O、互连TJU.ASICCenter---ArnoldShi回顾:基本的功能块Datapath运算单元Adder,multiplier,divider,shifter,etc.寄存器页、流水线多路选择器、译码器ControlFinitestatemachines(PLA,ROM,randomlogic)Interconnect交换器,仲裁器,总线MemoryCaches(SRAMs),移位寄存器,DRAMs,buffersTJU.ASICCenter---ArnoldShiIntel微处理器的数据通路Itanium有6个如下的整数执行单元TJU.ASICCenter---ArnoldShiItanium处理器的整数数据通路TJU.ASICCenter---ArnoldShiCELL处理器架构TJU.ASICCenter---ArnoldShiPS3多核心处理器CELL性能强劲

Cell处理器是东芝、IBM和索尼联合研发的。目前用于索尼公司的PS3。该处理器性能强劲，被称之为“芯片上的超级计算机”。不过，除了游戏机外，合作三方至今并未为Cell找到其他更好的用途。Cell内的1个PPE和8个SPE

Cell处理器将给电视机带来超强性能。据称，电视机将可以在一个屏幕上显示48个独立的电影画面，此外可以提供超高清的画质。TJU.ASICCenter---ArnoldShiCBEA-Compliant处理器CBEA-Compliant处理器TJU.ASICCenter---ArnoldShiCell内部有一条768bit位宽的“EIB单元互联总线环（ElementInterconnectBUSRing，EIBRing）”，它实际上是一个强大的内部总线控制逻辑—Cell内所有的功能单元都通过EIB总线环连接在一起，包括PPE、八个SPE、XDR内存控制器以及外部总线接口，它们所采用的无一例外都是全双工的128bit连接总线。若Cell工作在4GHz频率上，Cell内部的各个功能单元便都拥有4GHz×128bit／Hz×2（全双工）÷8Byte/bit＝128GBps带宽TJU.ASICCenter---ArnoldShi位片式（Bit-Sliced）设计完全相同的位片式处理单元TJU.ASICCenter---ArnoldShi位片式（Bit-Sliced）数据通路TJU.ASICCenter---ArnoldShi数据通路的特点数据通路它在很大程度上决定了整个系统的性）规整性：（Bit-slice）优化版图局域性：（时间、空间，算子相邻布置）版图紧凑正交性：（数据流、控制流）规整的布线层次化：高位－低位，多位－少位模块化：包括各种IP模块TJU.ASICCenter---ArnoldShi加法器加法器设计加法器常常是限制速度的部件。加法器的优化可在逻辑级和电路级进行TJU.ASICCenter---ArnoldShi二进制加法运算TJU.ASICCenter---ArnoldShiFA的门级实现结构ABSCoutCint1t0t2t0t1ABSCoutCint2TJU.ASICCenter---ArnoldShi互补静态CMOS逻辑实现的FA28TransistorsTJU.ASICCenter---ArnoldShi1位全加器定义ABCinCoutScarrystatus00000取消00101取消01001传播01110传播10001传播10110传播11010产生11111产生ABCoutSumCinFulladderTJU.ASICCenter---ArnoldShi进位产生、进位取消、进位传播信号为了利于具体实现，常常定义一些中间信号（注意它们与Cin

无关）：进位产生（Generate）信号：G=A&B进位取消（Delete)

信号：D=!A&!B进位传播(Propagate)

信号：P=AB有时候，也写成P=A+BTJU.ASICCenter---ArnoldShi逐位（行波、串行）进位Ripple-CarryAdder结构：由N个一位加法器串联而成，第i级的Carry-out用来产生第i+1级的Sum和Carry特点：结构直观简单，运行速度慢，最坏情形下关键路径的延时：Tadder=(N-1)Tcarry+TsumN位逐位进位加法器的延时正比于加法器位数N：Td=O(N)设计时优化Tcarry比优化Tsum更为重要TJU.ASICCenter---ArnoldShi进位路径中取消反相器!Cout(A,B,Cin)=Cout(!A,!B,!Cin)!S(A,B,Cin)=S(!A,!B,!Cin)ABSCoCiFAABSCoCiFATJU.ASICCenter---ArnoldShi消除反相器的进位链A3FAFAFAEvencellOddcellFAA0B0S0A1B1S1A2B2S2B3S3Ci,0Co,0Co,1Co,3Co,2TJU.ASICCenter---ArnoldShi镜像（Mirror）加法器的设计BBBBBBBBAAAAAAAACinCinCinCinCin!Cout!Skillgenerate0-propagate1-propagateCout=A&B|B&Cin|A&CinSUM=A&B&Cin|COUT&(A|B|Cin)44444888882223336664444224+4

transistorsTJU.ASICCenter---ArnoldShi镜像（Mirror）加法器版图结构StickDiagramTJU.ASICCenter---ArnoldShi镜像（Mirror）加法器的特点消除了进位输出的反相门。巧妙实现进位“传播／产生／消除”功能，同时减少面积和延时。不同于传统的“对偶”拓扑，而是“对称”或“镜像”，有利于版图实现。选择合适的P管和N管的尺寸，可保证相同的上升和下降时间。在进位产生电路中，最多两个管子串联。共24个晶体管在设计该加法器的版图时，应当使！CARRY节点上的电容较小。该节点上的电容包括本级的四个扩散电容和两个栅电容，以及下一级加法器的六个栅电容。减少扩散电容特别重要。连接Cin的管子连到接近门的输出端处。只有在进位电路中的管子需要优化尺寸以改善速度，在“和”位电路中的管子可以采用最小尺寸TJU.ASICCenter---ArnoldShi传输门加法器ABPCiVDDAAAVDDCiAPABVDDVDDCiCiCoSCiPPPPP和产生进位产生产生中间信号,和反相信号共24个晶体管TJU.ASICCenter---ArnoldShi曼彻斯特进位链（ManchesterCarryChain）静态实现，采用进位产生和进位消除动态实现，只用进位产生和进位传播TJU.ASICCenter---ArnoldShi曼彻斯特动态进位链特点采用动态逻辑降低复杂性和加快速度预充电时所有中间节点被预充至VDD，求值时有条件放电。进位链传输管只用N管，节点电容很小，为四个扩散电容。进位链的分布RC本质使传播延时与位数N的平方成正比，因此有必要插入缓冲器。从输出端到输入端通过进位链管子的放电电流逐步加大，因此从输出端到输入端逐步加大进位链管子的尺寸可提高速度。TJU.ASICCenter---ArnoldShi曼彻斯特进位链的动态实现TJU.ASICCenter---ArnoldShi4-bit位片式MCC加法器GP!C0clkGPGPGP&&&&A0B0A1B1A2B2A3B3S0S1S2S3!C1!C2!C3!C4TJU.ASICCenter---ArnoldShi曼彻斯特进位链的动态实现Ci,0G0clkclkP0P1P2P3G1G2G3Ci,41234563333312233445!(G0|P0Ci,0)!(G1|P1G0|P1P0Ci,0)!(G2|P2G1|P2P1G0|P2P1P0Ci,0)!(G3|P3G2|P3P2G1|P3P2P1G0|P3P2P1P0Ci,0)TJU.ASICCenter---ArnoldShi曼彻斯特进位链版图TJU.ASICCenter---ArnoldShi进位旁路加法器（carry-bypass）也称为

Carry-SkipFAFAFAFAP0G1P0G1P2G2P3G3Co,3Co,2Co,1Co,0Ci,0FAFAFAFAP0G1P0G1P2G2P3G3Co,2Co,1Co,0Ci,0Co,3MultiplexerBP=PoP1P2P3原理:如果(P0、P1、P2和P3均=1) 则CO,3=Ci,0,否则主路径进位消除或进位产生TJU.ASICCenter---ArnoldShiCarry-BypassAdder(cont.)N位串行加法器分成N/M组，每组M位，若每位加法器的进位产生时间为tcarry

，旁路进位时间为tbypass,则加法器总的求和时间为：tadder=tsetup+Mtcarry+(N/M-1)tbypass+(M-1)tcarry+tsumTJU.ASICCenter---ArnoldShi逐位（行波）进位与旁路进位（CarryBypass）比较增加进位旁路一般使面积增加10%至20%进位旁路加法器的总进位传播时间仍与位数N成正比，但比例系数较逐位进位加法器为小。N较小时，旁路的额外开销使采用旁路进位的收益不大一般N在4~8之间采用旁路进位。TJU.ASICCenter---ArnoldShiCBA进一步减少延时的方法各组的位数依次递增可进一步减少分组数和延时旁路还可以嵌套（各组位数可以不同）。每一旁路级的最优位数取决于旁路进位路径的延时旁路进位延时与逐位进位延时的比对进位链的缓冲要求等。TJU.ASICCenter---ArnoldShi不均匀分组的CBA各段长度TJU.ASICCenter---ArnoldShi进位选择AdderSetup"0"CarryPropagation"1"CarryPropagationMultiplexerSumGenerationCo,k-1Co,k+3"0""1"P,GCarryVector线性进位选择加法器的关键路径与求和时间TJU.ASICCenter---ArnoldShi16位CSA关键路径TJU.ASICCenter---ArnoldShi线性进位选择加法器

Setup"0"Carry"1"CarryMultiplexerSumGeneration"0""1"Setup"0"Carry"1"CarryMultiplexerSumGeneration"0""1"Setup"0"Carry"1"CarryMultiplexerSumGeneration"0""1"Setup"0"Carry"1"CarryMultiplexerSumGeneration"0""1"Bit0-3Bit4-7Bit8-11Bit12-15S0-3S4-7S8-11S12-15Ci,0(1)(1)(5)(6)(7)(8)(9)(10)(5)(5)(5)(5)TJU.ASICCenter---ArnoldShi进一步优化方法考虑到前级的进位输出要经过一个MUX才到达本级的进位输入，因此在两条信号路径之间相差一个延时时间，故本级的位数可以比前一级多一级。假设N位的加法器含有P个级，且第一级加是M位，后续级逐级增加一位，TJU.ASICCenter---ArnoldShi平方根进位选择加法器TJU.ASICCenter---ArnoldShi三种加法器延时比较

SquarerootselectLinearselect行波2040Ntp(inunitdelays)60010020304050TJU.ASICCenter---ArnoldShi超前进位加法器

AN-1,BN-1A1,B1P1S1••••••SN-1PN-1Ci,N-1S0P0Ci,0Ci,1A0,B0TJU.ASICCenter---ArnoldShi超前进位加法器镜像实现超前进位加法推导展开得:TJU.ASICCenter---ArnoldShi版图实现TJU.ASICCenter---ArnoldShi超前进位加法器算法TJU.ASICCenter---ArnoldShi超前进位加法递归树结构可以继续推导，到高次进位实现部分TJU.ASICCenter---ArnoldShi布尔运算点操作点操作符但不符合交换率TJU.ASICCenter---ArnoldShiKogge-Stone16位超前进位对数加法器16-bitradix-2Kogge-StonetreeTJU.ASICCenter---ArnoldShiTreeAdders16-bitradix-4Kogge-StoneTreeTJU.ASICCenter---ArnoldShiSparseTrees16-bitradix-2sparsetreewithsparsenessof2TJU.ASICCenter---ArnoldShiTreeAddersBrent-KungTreeTJU.ASICCenter---ArnoldShiExample:DominoAdderPropagateGenerateTJU.ASICCenter---ArnoldShiBrent-KungPPAParallelPrefixComputation€G0P0G1P1G2p2G3P3G4P4G5P5G6P6G7P7G8P8G9p9G10P10G11p11G12P12G13p13G14p14G15p15€€€€€€€€€€€€€€€€€€€€€€€€€C1C2C3C4C5C6C7C8C9C10C11C12C13C14C15C16Cin€T=log2NT=log2N-2A=2log2NA=N/2TJU.ASICCenter---ArnoldShiKogge-StonePPFAdderParallelPrefixComputation€G0P0G1P1G2P2G3P3G4P4G5P5G6P6G7P7G8P8G9P9G10P10G11P11G12P12G13P13G14P14G15P15€€€€€€€€€€€€€€€C1C2C3C4C5C6C7C8C9C10C11C12C13C14C15C16Cin€T=log2NA=log2NA=N€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€Tadd=tsetup+log2Nt€+tsumTJU.ASICCenter---ArnoldShiExample:DominoAdderPropagateGenerateTJU.ASICCenter---ArnoldShiExample:DominoSumTJU.ASICCenter---ArnoldShi第十二讲数据通路设计

---乘法器TianJinUniversityshizaifeng@TJU.ASICCenter---ArnoldShi乘法器的应用与实现应用：硬件乘法器可大大提高运算速度，超过软件实现数字信号处理（DSP）相关（Correlation）、滤波（Filtering）卷积（Convolution）、频率（Frequency）与其它运算电路集成，组成功能很强的协处理器实现：求部分积移位相加TJU.ASICCenter---ArnoldShi乘法器的分类分类：1.并行：组合阵列、波茨编码、WallaceTree、脉动阵列、流水线式2.串行3.串并行选择乘法器的原则：速度数据处理量（Throughput）精度面积TJU.ASICCenter---ArnoldShi二进制乘法TJU.ASICCenter---ArnoldShi二进制乘法的例子x+部分积被乘数乘数结果1010101010101010101110011100000001010101011TJU.ASICCenter---ArnoldShi阵列乘法法器TJU.ASICCenter---ArnoldShiRCA阵列乘法器结构对N*N位乘法器N个半加器（HA）N*（N-2）个全加器（FA）N*N个与门（AND）对M*N位乘法器，需要N个半加器（HA）M*N-M-N个全加器（FA）M*N个与门（AND设计原则：乘法器存在许多延时几乎相同的关键路径，因此重点放在Adder上，使加法器的Sum和Carry的传输时间相同！TJU.ASICCenter---ArnoldShiMxN阵列乘法器的关键路径CriticalPath1&2TJU.ASICCenter---ArnoldShi（进位保留乘法器）Carry-SaveMultiplierTJU.ASICCenter---ArnoldShi进位保留乘法器矩形平面布置图SCSCSCSCSCSCSCSCSCSCSCSCSCSCSCSCZ0Z1Z2Z3Z4Z5Z6Z7X0X1X2X3Y1Y2Y3Y0向量和并单元HAMultiplierCel