《并行乘法运算》PPT课件.ppt
计 算 机 组 成 原 理,2023年7月14日,定点乘法运算,借助加法器配置相应部件实现乘法运算设置专用乘法器实现乘法运算执行乘法运算子程序实现乘法运算,定点乘法运算,原码乘法运算方法原码乘法运算实现补码乘法运算方法补码乘法运算实现,设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.y1y2.yn)=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=11 0=00 1=00 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位求补器,数值同原码,相加数,积绝对值,（补码乘积）,=1,A补=af.an1 a1 a0,相加数产生电路,n位求补器,n位求补器,包括求补级的乘法器又称为符号求补的阵列乘法器。在这种逻辑结构中，共使用三个求补器：两个算前求补器 作用：将两个操作数A和B在被不带符号的乘法阵列(核心部件)相乘以前，先 变成正数。算后求补器 作用：当两个输入操作数的符号不一致时，把运算结果变成带符号的数。,结构：,在必要的求补操作以后，A和B的码值输送给nn位不带符号的阵列乘法器，并由此产生2n位的乘积：ABPp2n1p1p0p2nanbn 其中，P2n为符号位。,
