《并行乘法运算》PPT课件.ppt

计 算 机 组 成 原 理,2019年8月7日,定点乘法运算,借助加法器配置相应部件实现乘法运算 设置专用乘法器实现乘法运算 执行乘法运算子程序实现乘法运算,定点乘法运算,原码乘法运算方法 原码乘法运算实现 补码乘法运算方法 补码乘法运算实现,设n位被乘数和乘数用定点小数表示 被乘数 x原xf . xn1 x1x0 乘数 y原yf . yn1 y1y0 则乘积 z原(xfyf)(0. xn1 x1x0)(0. yn1 y1y0) 式中：xf为被乘数符号，yf为乘数符号。,原码乘法,1. 乘法的手工算法,一、原码串行乘法运算,符号位直接异或即可得到乘积的符号 仅仅需要考虑其数值部分的计算 以定点小数为例进行讨论,(2) 手工运算过程：,设0.1101，0.1011,0. 1 1 0 1 (x) 0. 1 0 1 1 (y) 1 1 0 1 1 1 0 1 0 0 0 0 + 1 1 0 1 0. 1 0 0 0 1 1 1 1 (z),(1)乘积符号的运算规则：同号相乘为正，异号相乘为负。,(1) 机器通常只有n位长，两个n位数相乘，乘积可能为2n位。 (2) 只有两个操作数相加的加法器难以胜任将n位积一次相加起来的运算。,机器与人们习惯的算法不同之处：,0.1 1 0 1 x 0.1 0 1 1 y 0.0 0 0 0 1 1 0 1 x共4次右移 0.0 0 0 1 1 0 1 x共3次右移 0.0 0 0 0 0 0 x共2次右移 + 0.0 1 1 0 1 x共1次右移 0.1 0 0 0 1 1 1 1,2. 适合定点机的形式,为了适合两个操作数相加的加法器，将 xy 改写成下面形式：,xy = x(0.1011) = 0.1x + 0.00 x + 0.001 x + 0.0001 x = 0.1 x+0.1 0 + 0.1 (x+0.1 x) = 2-1 x+ 2-1 0 + 2-1(x+2-1x) ,从内向外逐次进行移位累加,形成递推公式：,令zi表示第i次部分积，则根据从内到外的原则有： z0 = 0 z1 = 2-1(ynx+z0) z2 = 2-1(yn-1x+z1) zi = 2-1(yn-i+1x+zi-1) zn = xy = 2-1(y1x+ zn-1) 特点： 每次只需要相加两个数，然后右移一位。且相加的两个数（部分积和位积）都只有n位，因而不需要2n位的加法器。,一般而言，设被乘数x，乘数y都是小于1的n位定点正数：,其乘积为：xy=x(0.y1y2yn ) =x(y12-1 +y22-2 + yn2-n ) =2-1(y1x+2-1(y2x+2-1(+2-1(yn-1x+2-1(ynx+0),开始,i = 0, 0,Yn=1, + 0 , + X , Y右移一位 i+1i,i = n,X0Y0P0,结束,Y,N,N,Y,原码乘法算法流程图,加法次数，n次 作为加法，一定移位 符号位单独计算,部分积,乘数,说明,最后结果 ： xy=0.10001111,0 0.0 0 0 0 yf 1 0 1 1 z0=0 + 0 0.1 1 0 1 y4=1， +x 0 0.1 1 0 1 0 0.0 1 1 0 1 yf 1 0 1 右移，得z1 + 0 0.1 1 0 1 y3=1， +x 0 1.0 0 1 1 0 0.1 0 0 1 1 1 yf 1 0 右移，得z2 + 0 0.0 0 0 0 y2=0， +0 0 0.1 0 0 1 0 0.0 1 0 0 1 1 1 yf 1 右移，得z3 + 0 0.1 1 0 1 y1=1， +x 0 1.0 0 0 1 0 0.1 0 0 0 1 1 1 1 yf 右移，得z4=xy,例：x=0.1101 ， y=0.1011 ， 求 xy 。,4.原码一位乘硬件逻辑原理图,早期计算机中为了简化硬件结构，采用串行的1位乘法方案，即多次执行“加法移位”操作来实现。这种方法并不需要很多器件。然而串行方法毕竟太慢，自从大规模集成电路问世以来，出现了各种形式的流水式阵列乘法器，它们属于并行乘法器。,设x补 = x0.x1x2xn 当x0时， x0=0，,x补=0.x1x2xn = = x,= -1+ 0.x1x2xn = -1+,x = -x0 +,真值与补码的关系：,当x0时， x0=1， x补=1.x1x2xn=2 + x x=1.x1x2xn-2,(1)真值和补码之间的关系,补码乘法,一、补码串行乘法 采用比较法。比较法是Booth夫妇首先提出来的，又称Booth算法。,在补码机器中，一个数不论其正负，连同符号位向右移一位，符号位保持不变，就等于乘1/2。 设 x补 = x0.x1x2xn, x = -x0 +,= -x0 +,写成补码的形式，即得：,要得到2-ix补，连同符号位右移i位即可。,(2) 补码的右移,设被乘数 x补 = x0.x1x2xn 乘数 y补 = y0.y1y2yn 均为任意符号，则有补码乘法算式：, xy 补 = x补 y,(3) 补码乘法规则,为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。,( yn+1是增加的附加位，初值为0 ),将上式改为接近于分步运算逻辑实现的递推关系。,M,M,递推公式,最后一步不移位,由此可见： 每次都是在前次部分积的基础上，由（yi+1-yi ) 决定对x补的操作，然后再右移一位，得到新的部分积；重复进行。,yn+1，yn的作用： 开始操作时，补充一位yn+1 , 使其初始为0。由yn+1 yn 判断进行什么操作；然后再由ynyn-1 判断第二步进行什么操作 。,若 yn yn1 =1 则 yi1-yi =1 做加x补运算；,ynyn1 = 则 yi1-yi= - 做加-x补运算；,则 yi1-yi= 0 zi加0，即保持不变；,补码一位乘的运算规则,(1) 如果 yn=yn+1 ， 则部分积 zi 加0，再右移一位；,(2) 如果 yn yn+1=01 ，则部分积 zi 加x补，再右移一位；,(2) 如果 yn yn+1=10 ，则部分积 zi 加-x补, 再右移一位；,如此重复n + 1步，但最后一步不移位。 包括一位符号位，所得乘积为2n+1位，其中n为尾数位数。,开始,i = 0, 0 , + X补, + X补,结束,01,10,00或11,Y,N,不变,、Y补右移一位 i + 1,加法次数，n+1次 最后一次加法不需移位 符号位直接参与运算,算法流程图,0 0.0 0 0 0 1. 0 0 1 1 0 yn+1=0 + 0 0.1 0 1 1 ynyn+1=10， 加-x补 0 0.1 0 1 1 0 0.0 1 0 1 1 1 0 0 1 1 右移一位 + 0 0.0 0 0 0 ynyn+1=11， 加0 0 0.0 1 0 1 0 0.0 0 1 0 1 1 1 0 0 1 右移一位 + 1 1.0 1 0 1 ynyn+1=01， 加x补 1 1.0 1 1 1 1 1.1 0 1 1 1 1 1 1 0 0 右移一位 + 0 0.0 0 0 0 ynyn+1=00， 加0 1 1.1 0 1 1 1 1.1 1 0 1 1 1 1 1 1 0 右移一位 + 0 0.1 0 1 1 ynyn+1=10， 加-x补 0 0.1 0 0 0 1 1 1 1 1 0 最后一位不移位,例：x补=1.0101，y补=1.0011， 求xy补=？ -x补=0.1011,xy补=0.10001111,部分积,乘数 yn yn+1,说明,0 0 0 0 0 0 1 0 1 1 0 0 yn+1=0 + 0 0 0 0 0 0 ynyn+1=00， 加0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 右移一位 + 1 1 0 0 1 1 ynyn+1=10， 加-x补 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 1 右移一位 + 0 0 0 0 0 0 ynyn+1=11， 加0 1 1.1 0 0 1 1 1.1 1 0 0 1 1 0 1 0 1 右移一位 + 0 0 1 1 0 1 ynyn+1=01， 加x补 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 右移一位 + 1 1 0 0 1 1 ynyn+1=10， 加-x补 1 1 0 1 1 1 1 1 1 0 1 0 最后一位不移位,x补=001101， y补=10110， -x补=110011,xy补 = 101111110,部分积,乘数 yn yn+1,说明,例：x=13， y=-10 求xy=？,xy = -01000 0010 = -82H = -130,4.补码一位乘逻辑原理图,p9,p3,p2,p1,p0,p9p8p7p6p5p4p3p2p1p0,a4a3a2a1a0,x b4b3b2b1b0,先计算相加数，然后逐列相加,原码阵列乘法器,设置专用乘法器实现乘法运算,相加数产生部件,经过一级门电路延迟，即可得到所有的相加数,一位乘法逻辑实现,R=X*Y,1 1 = 1 1 0 = 0 0 1 = 0 0 0 = 0,一个与门即可实现一位乘法,p8,p2,p1,p0,+,+,+,+,+,横向进位的5位无符号数阵列乘法器电路,a3b2,a2b2,a1b2,a0b2,a4b2,a3b3,a2b3,a1b3,a0b3,a4b3,a3b4,a2b4,a1b4,a0b4,a4b4,a4b0,a3b0,a2b0,a1b0,a0b0,p8,p2,p1,p0,0,0,a1b1,a0b1,a3b1,a2b1,a4b1,p6,p7,p3,0,p4,0,p5,0,COUT,COUT,COUT,p9,COUT,横向进位无符号数阵列乘法器电路时延分析,a3b2,a2b2,a1b2,a0b2,a4b2,a3b3,a2b3,a1b3,a0b3,a4b3,a3b4,a2b4,a1b4,a0b4,a4b4,a4b0,a3b0,a2b0,a1b0,a0b0,p8,p2,p1,p0,1,0,3,0,7,9,a1b1,a0b1,a3b1,a2b1,a4b1,2,B,p6,8,9,p7,A,p3,0,3,4,5,p4,0,4,5,6,7,p5,6,7,8,5,0,COUT,COUT,COUT,p9,COUT,n+2(n-2)*3T+T (3n-4)*3T + T,横向进位无符号数阵列乘法器电路时延分析,p8,p2,p1,p0,5位无符号数阵列乘法器电路,+,+,+,p6,p7,p3,p4,p5,p9,p9p8p7p6p5p4p3p2p1p0,a4a3a2a1a0,x b4b3b2b1b0,演示,p8,p2,p1,p0,a3b2,a2b2,a1b2,a0b2,a4b2,a3b3,a2b3,a1b3,a0b3,a4b3,a4b0,a3b0,a2b0,a1b0,a0b0,a4b1,p6,p7,p3,p4,p5,p9,0,a3b4,a2b4,a0b4,a4b4,a1b4,4*5个全加器, 8个全加器延迟,原码阵列乘法器时间延迟,n(n-1)个FA 延迟时间 (n-1)FA +(n-1)FA 每一个FA包含三级门电路延迟T 故总延迟为 2(n-1)*3T T(相加数产生时间),nn位原码乘法器框图,相加数产生部件,A = af. an1 an2a1 a0,B = bf. bn1 bn2b1 b0,nn乘法阵列,=1,.,3.带符号的阵列乘法器,对2求补器电路,例1： 对1010求补。,1 0 1 0 0 1 0 1 1 0 1 1 0,方法：从数的最右端开始，由右向左， 直到找出第一个“1”，例如ai1， 0in。这样， ai以左的每一个输入位都求反， 即1变0， 0变1。,补码阵列乘法器,对2求补电路,当控制信号线E为“1”时，启动对2求补的操作。当控制信号线E为“0”时，输出将和输入相等。显然，我们可以利用符号位来作为控制信号。 用这种对2求补器来转换一个(n1)为带符号的数，所需的总时间延迟为： tn2T5T(2n5)T 其中每个扫描级需2T延迟，而5T则是由于“与”门和“异或”门引起的。,补码乘法器原理图,B补 = bf. bn1 b1 b0,不带符号乘法阵列（nn阵列）,2n位求补器,数值同原码,相加数,