并行加法器

今天是坐轮渡来海岛开启夏日度假的第一天,坐了轮渡看了海鸥,吃了海鲜赶了海,换了泳衣洗了海澡(海水真凉啊…),炫了烧烤造了啤酒,唱完最后一场露天卡拉ok,结束一天的欢乐行程,回酒店后一时兴起,启动图灵完备决定冲一下”快速加法器”成就 成就要求:加法器总延迟小于等于35(划重点) 背景:所有基础逻辑门(与非,或非,与或非)延迟=2

我原来做的加法器就是计算机教科书的标准串行加法器,原来加法器的延迟为12(两个异或门串联导致),八个全加器串联在一起,每个全加器继承上一位的进位,延迟=12*8=96.我想出一个解决方案: 这个高延迟主要是因为每个全加器运算前都在等待上一个全加器出结果 把第1位往后的7个位,每个位都并行进行两次运算:一次是假设进位=0,一次是假设进位=1 然后等待第1位出结果,再选择这两个运算结果中的一个

这样就将后面7个全加器的延迟变成了单刀双掷开关(延迟=4)的延迟,于是总延迟就等于12+4*7=40>35,不对,超出了目标延迟.

由于这个改进方案看起来很优越,我决定先改动全加器内部的延迟找突破口.我制作的全加器是获得成就的最佳结构,全加器本身应该没有什么提升空间,于是我把目标放在了全加器的主要延迟成分:两个串联的异或门.

我回到异或门那关,发现是当初装杯用四个与非门联合造的…于是我果断改进了一下异或门,把它改成或门和与非门做一次与,延迟优化到了4,这样整个全加器的延迟变成了4*2=8.

于是,总延迟变成了8+4*7=36>35,OMG,就差一个门的距离,却是世界上最遥远的距离…

整个电路至此已经没有了优化空间,至此我开始寻求其他提高加法器效率的更加架构.

通过查阅相关资料,我了解到:我的并行加法器设计方案属于进位选择加法器,这个加法器方案所需门数量多是缺陷.我认为,其限制速率的关键问题在于,通过预先并行计算,将全加器的延迟量变成了常数8,但是进位的传播链条本身仍然是串行的,只不过本来由全加器承担的串行开销变成了单刀双掷,延迟仍然是线性增长的,只是增长系数从全加器的8变成了单刀双掷的4.业界一般使用的加法器设计模式,就要从并行化进位来开刀.

打破全加器抽象

之前的提升手段依赖于全加器这层按位加法的抽象,它在简化电路复杂度的同时也限制了我们提升效率的途径,因此首先要打破全加器这层抽象,从更底层的角度寻找提升效率的方式 目标:实现进位处理的并行化

既然是并行化处理,就要直接根据某一位和最开始给的进位的关系进行运算,而尽可能避免中间量.观察每一位的加和,注意到如下特性:

1. 设$P_i=A_i\oplus B_i$为每位的传递信号(Pass),这个信号为1,则该位可以传递来自上一位的进位
2. 设$G_i=A_i\wedge B_i$为每位的生成信号(Generate),这个信号为1,则该位必然产生一个进位符号. 我们可以并行计算每一位的P和G,就产生了一个值为常量4的延迟 接着,我们可以基于P,G这两个信号对每位的进位进行如下并行运算: $C_i=G_i+P_i\cdot G_{i-1}+P_i\cdot P_{i-1}\cdot G_{i-2}+\cdots +P_i\cdot P_{i-1}\cdot P_{i-2}\cdot P_{i-3}\dots P_1\cdot C_0$ 最后用每一位异或的结果$P_i$,再对$C_{i-1}$进行一次异或(产生延迟常数4),就得到每一位的最终结果.

延迟推导:

这个加法器的延迟仍然与位数线性相关,但增长系数进一步降低了:

1. 每高一位,与门层数增加一层,产生增长系数2
2. 对于第i位共(i+1)个项进行或运算,共需要$\lceil {\log }_2(i+1)\rceil$层或门,每层或门产生延迟2,增长是对数的,产生的为下一位的进位. 于是整个加法器的延迟增长系数为2+log,延迟常数为两次异或的8,设延迟为y,位数为x,则有 $y=2(x-1)+8+2\lceil {\log }_2((x-1)+1)\rceil =2x+6+2\lceil {\log }_{2}x\rceil$ 代入x=8,得$y=28$,在图灵完备中组装电路后测试得到延迟28,成功通过所有测试 恭喜,成功获得成就!

总结

我尝试的三个加法器方案,其实都是线性增长的复杂度,但是增长系数不同.串行的增长系数为8,进位选择加法器的增长系数为4,而最终做成的超前进位加法器的增长系数为2+log. 这次优化的过程中为取得增长系数从4到2+log的突破,采取了打破全加器抽象,重构整个加法器架构的做法,没有抽象保护是有代价的,那就是超前进位全加器的电路复杂度也是随着位的增加爆炸性增长.要在复杂度,芯片门数目和效率间权衡,可能在未来芯片设计的路程中是一个很关键的课题.