可以看出,上法是将32位的加法1位1位串行进行的,要缩短进行的时间,就应设法使上叙进行过程并行化。
逐位进位加法器,在每一位的计算时,都在等待前一位的进位。那么不妨预先考虑进位输入的所有可能,对于二进制加法来说,就是0与1两种可能,并提前计算出若干位针对这两种可能性的结果。等到前一位的进位来到时,可以通过一个双路开关选出输出结果。这就是进位选择加法器的思想。提前计算多少位的数据为宜?同为32位的情况:线形进位选择加法器,方法是分N级,每级计算32/N位;平方根进位选择加法器,考虑到使两个路径(1,提前计算出若干位针对这两种可能性的结果的路径,2,上一位的进位通过前面的结构的路径)的延时达到相等或是近似。方法,或是2345666即第一级相加2位,第二级3位,第三级4位,第四级5位,第五级6位,第六级6位,第七级6位;或是345677即第一级相加3位,第二级4位,第三级5位,第四级6位,第五级7位,第六级7位。
进一步分析加法进行的机制,可以使加法器的结构进一步并行化。
令G = AB,P = A⊕B,则COUT(G,P) = G PCIN,S(G,P)=P⊕CIN。由此,A,B,CIN,S,COUT五者的关系,变为了G,P,CIN,S,COUT五者的关系。
再定义点运算(·),(G,P)·(G’,P’)=(G PG’,PP’),可以分解(G 3:2,P3:2) =(G3,P3)·(G2,P2)。点运算服从结合律,但不符合交换律。
点运算只与G,P有关而与CIN无关,也就是可以通过只对前面若干位G,P进行点运算计算,就能得到第N位的GN:M,PN:M值,当取M为0时,获得的GN:0,PN:0即可与初使的CIN一起代入COUT(G,P) = G PCIN,S(G,P)=P⊕CIN,得到此位的COUT,S;而每一位的G,P值又只与该位的A,B值即输入值有关,所以在开始进行运算后,就能并行的得到每一位的G,P值。
以上分析产生了超前进位加法器的思想:三步运算,1,由输入的A,B算出每一位的G,P;2,由各位的G,P算出每一位的GN:0,PN:0;3,由每一位的GN:0,PN:0与CIN算出每一位的COUT,S。其中第1,3步显然是可以并行处理的,计算的主要复杂度集中在了第2步。
第2步的并行化,也就是实现GN:0,PN:0的点运算分解的并行化。