3并行乘法运算ppt课件

1、计算机组成原理计算机组成原理12021年12月25日定点乘法运算定点乘法运算计算机组成原理计算机组成原理2借助加法器配置相应部件实现乘法运算借助加法器配置相应部件实现乘法运算设置专用乘法器实现乘法运算设置专用乘法器实现乘法运算执行乘法运算子程序实现乘法运算执行乘法运算子程序实现乘法运算定点乘法运算定点乘法运算原码乘法运算方法原码乘法运算方法原码乘法运算实现原码乘法运算实现补码乘法运算方法补码乘法运算方法补码乘法运算实现补码乘法运算实现计算机组成原理计算机组成原理3 设设n n位被乘数和乘数用定点小数表示位被乘数和乘数用定点小数表示 被乘数被乘数 x x原原xf . xnxf . xn1 x1x

2、01 x1x0 乘数乘数 y y原原yf . ynyf . yn1 y1y01 y1y0 则乘积则乘积 z z原原(xfyf)(xfyf)(0. xn(0. xn1 x1x0)(0. yn1 x1x0)(0. yn1 y1y0) 1 y1y0) 式中：式中：xfxf为被乘数符号，为被乘数符号，yfyf为乘数符号。为乘数符号。 原码乘法原码乘法1. 1. 乘法的手工算法乘法的手工算法一、原码串行乘法运算一、原码串行乘法运算符号位直接异或即可得到乘积的符号符号位直接异或即可得到乘积的符号仅仅需要考虑其数值部分的计算仅仅需要考虑其数值部分的计算以定点小数为例进行讨论以定点小数为例进行讨论计算机组成原

3、理计算机组成原理4(2) (2) 手工运算过程：手工运算过程： 设设0.11010.1101，0.10110.1011 0. 1 1 0 1 (x) 0. 1 1 0 1 (x) 0. 1 0 1 1 (y) 0. 1 0 1 1 (y) 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0+ 1 1 0 1+ 1 1 0 1 0. 1 0 0 0 1 1 1 1 (z) 0. 1 0 0 0 1 1 1 1 (z) (1) (1)乘积符号的运算规则：同号相乘为正，异号相乘为负。乘积符号的运算规则：同号相乘为正，异号相乘为负。(1) (1) 机器通常只

4、有机器通常只有n n位长，两个位长，两个n n位数相乘，乘积可能为位数相乘，乘积可能为2n2n位。位。(2) (2) 只有两个操作数相加的加法器难以胜任将只有两个操作数相加的加法器难以胜任将n n位积一次相加起来的运算。位积一次相加起来的运算。机器与人们习惯的算法不同之处：机器与人们习惯的算法不同之处：计算机组成原理计算机组成原理5 0.1 1 0 1 x 0.1 1 0 1 x 0.1 0 1 1 y 0.1 0 1 1 y 0.0 0 0 0 1 1 0 1 x 0.0 0 0 0 1 1 0 1 x共共4 4次右移次右移 0.0 0 0 1 1 0 1 x 0.0 0 0 1 1 0 1

5、 x共共3 3次右移次右移 0.0 0 0 0 0 0 x 0.0 0 0 0 0 0 x共共2 2次右移次右移 + 0.0 1 1 0 1 x + 0.0 1 1 0 1 x共共1 1次右移次右移 0.1 0 0 0 1 1 1 1 0.1 0 0 0 1 1 1 1 2. 2. 适合定点机的形式适合定点机的形式 为了适合两个操作数相加的加法器，将为了适合两个操作数相加的加法器，将 x x y y 改写成下面形式：改写成下面形式：x xy = xy = x(0.1011)(0.1011) = 0.1 = 0.1x + 0.00 x + 0.00 x + 0.001 x + 0.001 x +

6、 0.0001 x + 0.0001 x x = 0.1 = 0.1 x+0.1 0 + 0.1 x+0.1 0 + 0.1 (x+0.1 (x+0.1 x) x) = 2-1 x+ 2-1 0 + 2-1(x+2-1x) = 2-1 x+ 2-1 0 + 2-1(x+2-1x) 从内向外从内向外逐次进行逐次进行移位累加移位累加计算机组成原理计算机组成原理6形成递推公式：形成递推公式： 令令zizi表示第表示第i i次部分积，则根据从内到外的原则有：次部分积，则根据从内到外的原则有： z0 = 0 z0 = 0 z1 = 2-1(ynx+z0) z1 = 2-1(ynx+z0) z2 = 2-

7、1(yn-1x+z1) z2 = 2-1(yn-1x+z1) zi = 2-1(yn-i+1x+zi-1) zi = 2-1(yn-i+1x+zi-1) zn = x zn = xy = 2-1(y1x+ zn-1)y = 2-1(y1x+ zn-1) 特点：特点： 每次只需要相加两个数，然后右移一位。且相加的两个数部分积和位每次只需要相加两个数，然后右移一位。且相加的两个数部分积和位积都只有积都只有n n位，因而不需要位，因而不需要2n2n位的加法器。位的加法器。一般而言，设被乘数一般而言，设被乘数x x，乘数，乘数y y都是小于都是小于1 1的的n n位定点正数：位定点正数：其乘积为：其乘

8、积为：xy=x(0.y1y2.yn )xy=x(0.y1y2.yn ) =x(y12-1 +y22-2 + yn2-n ) =x(y12-1 +y22-2 + yn2-n ) =2-1(y1x+2-1(y2x+2-1(+2-1(yn-1x+2-1(ynx+0) =2-1(y1x+2-1(y2x+2-1(+2-1(yn-1x+2-1(ynx+0)计算机组成原理计算机组成原理7开场i = 0, 0Yn=1 + 0 + X Y右移一位i+1i i = nX0 Y0P0终了YNNYn加法次数，n次n作为加法，一定移位n符号位单独计算计算机组成原理计算机组成原理8部分积部分积乘数乘数阐明阐明最后结果最后

9、结果 ： xy=0.10001111 0 0.0 0 0 0 yf 1 0 1 1 0 0.0 0 0 0 yf 1 0 1 1 z0=0z0=0 + 0 0.1 1 0 1 + 0 0.1 1 0 1 y4=1y4=1， +x +x 0 0.1 1 0 1 0 0.1 1 0 1 0 0.0 1 1 0 1 yf 1 0 1 0 0.0 1 1 0 1 yf 1 0 1 右移，得右移，得z1z1 + 0 0.1 1 0 1 + 0 0.1 1 0 1 y3=1y3=1， +x +x 0 1.0 0 1 1 0 1.0 0 1 1 0 0.1 0 0 1 1 1 yf 1 0 0 0.1 0

10、0 1 1 1 yf 1 0 右右移，得移，得z2z2 + 0 0.0 0 0 0 + 0 0.0 0 0 0 y2=0y2=0， +0 +0 0 0.1 0 0 1 0 0.1 0 0 1 0 0.0 1 0 0 1 1 1 yf 1 0 0.0 1 0 0 1 1 1 yf 1 右移，得右移，得z3z3 + 0 0.1 1 0 1 + 0 0.1 1 0 1 y1=1y1=1， +x +x 0 1.0 0 0 1 0 1.0 0 0 1 0 0.1 0 0 0 1 1 1 1 yf 0 0.1 0 0 0 1 1 1 1 yf 右移，得右移，得z4=xz4=xy y例：例：x=0.1101

11、 ， y=0.1011 ， 求求 xy 。计算机组成原理计算机组成原理94.4.原码一位乘硬件逻辑原理图原码一位乘硬件逻辑原理图 R0R0 R1R1 yn ynR2R2 计数器计数器i i 部分积部分积 z z 被乘数被乘数x x 乘数乘数 y y LDR0LDR0LDR1LDR1 T1T1， T2 T2， TiTi Q QQ Q加法器加法器R RS S启动启动ynynCxCx 早期计算机中为了简化硬件结构，采用串行的早期计算机中为了简化硬件结构，采用串行的1 1位乘法方案，即多次位乘法方案，即多次执行执行“加法加法移位操作来实现。这种方法并不需要很多器件。然而串移位操作来实现。这种方法并不需

12、要很多器件。然而串行方法毕竟太慢，自从大规模集成电路问世以来，出现了各种形式的流行方法毕竟太慢，自从大规模集成电路问世以来，出现了各种形式的流水式阵列乘法器，它们属于并行乘法器。水式阵列乘法器，它们属于并行乘法器。计算机组成原理计算机组成原理10 设设xx补补 = x0.x1x2xn = x0.x1x2xn 当当x x0 0时，时， x0=0 x0=0， niiix12xx补补=0.x1x2xn = = x=0.x1x2xn = = x niiix12= -1+ 0.x1x2xn= -1+ 0.x1x2xn= -1+= -1+niiix12x = -x0 + x = -x0 + 真值与补码的关

13、系：真值与补码的关系： 当当x x0 0时，时， x0=1 x0=1， x x补补=1.x1x2xn=2 + x=1.x1x2xn=2 + x x=1.x1x2xn-2 x=1.x1x2xn-2(1)(1)真值和补码之间的关系真值和补码之间的关系补码乘法补码乘法 一、补码串行乘法一、补码串行乘法 采用比较法。比较法是采用比较法。比较法是BoothBooth夫妇首先提出来的，又称夫妇首先提出来的，又称BoothBooth算法。算法。计算机组成原理计算机组成原理11 在补码机器中，一个数不论其正负，连同符号位向右移一位，符号位保在补码机器中，一个数不论其正负，连同符号位向右移一位，符号位保持不变，

14、就等于乘持不变，就等于乘1/21/2。 设设 x x补补 = x0.x1x2xn = x0.x1x2xn niiix12 x = -x0 + x = - x0 +121212 niiix12= -x0 + x0 + 1212 niiix12= -x0 + ni)i (ix012写成补码的形式，即得：写成补码的形式，即得：要得到要得到2-ix2-ix补，连同符号位右移补，连同符号位右移i i位即可。位即可。(2) (2) 补码的右移补码的右移12 x 补补 = x0.x0 x1x2xn计算机组成原理计算机组成原理12 设被乘数设被乘数 x x补补 = x0.x1x2xn = x0.x1x2xn

15、乘数乘数 y y补补 = y0.y1y2yn = y0.y1y2yn 均为任意符号，则有补码乘法算式：均为任意符号，则有补码乘法算式： xy 补补 = x补补 y或：或： xy 补补 = x补补 niiiyy102(3) (3) 补码乘法规则补码乘法规则计算机组成原理计算机组成原理13 为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。( yn+1( yn+1是增加的附加位，初值为是增加的附加位，初值为0 )0 )补补yx )(nnyyyyx 22222110补补)()()()(nnnnyyyyyyyx 222221

16、22121110补补)()()()()(nnnnnyyyyyyyx 20221111201补补)()()(nnnyyyyyyx 22111201补补 niiiiyyx012)(补补计算机组成原理计算机组成原理14 将上式改为接近于分步运算逻辑实现的递推关系。将上式改为接近于分步运算逻辑实现的递推关系。补补z 00 补补补补补补x)yy(zz nn12112 补补补补补补x)yy(zz ininii12112 补补补补补补x)yy(zz nn11122 补补补补补补x)yy(zz nn 10112 MM递推公式递推公式补补补补补补补补x)yy(z z yxnn011 最后一步不移位最后一步不移位

17、计算机组成原理计算机组成原理15由此可见：由此可见： 每次都是在前次部分积的基础上，由每次都是在前次部分积的基础上，由yi+1-yi ) 决定对决定对x补的操作，然后再右移一位，得到新的部分积；重复进行。补的操作，然后再右移一位，得到新的部分积；重复进行。yn+1，yn的作用：的作用： 开始操作时，补充一位开始操作时，补充一位yn+1 , 使其初始为使其初始为0。由。由yn+1 yn 判判断进行什么操作；然后再由断进行什么操作；然后再由ynyn-1 判断第二步进行什么操判断第二步进行什么操作作 。 假设假设 yn yn yn yn1 =1 =1 1 那么那么 yi yi1-yi =1 1-yi

18、 =1 做加做加xx补运算；补运算；ynyn1 = 那么那么 yi1-yi= - 做加做加-x补运补运算；算；ynyn1 =1ynyn1= 0那么那么 yi yi1-yi= 0 zi1-yi= 0 zi加加0 0，即保持不，即保持不变；变； 计算机组成原理计算机组成原理16补码一位乘的运算规则补码一位乘的运算规则(1) 假设假设 yn=yn+1 ， 则部分积则部分积 zi 加加0，再右移一位；，再右移一位；(2) 假设假设 yn yn+1=01 ，则部分积，则部分积 zi 加加x补，再右移一位；补，再右移一位；(2) 假设假设 yn yn+1=10 ，则部分积，则部分积 zi 加加-x补补,

19、再右移一位；再右移一位； 如此重复如此重复n + 1n + 1步，但最后一步不移位。步，但最后一步不移位。 包括一位符号位，所得乘积为包括一位符号位，所得乘积为2n+12n+1位，其中位，其中n n为尾数位数。为尾数位数。计算机组成原理计算机组成原理17开场i = 0, 0 Yn Yn+1=? + X补 + X补终了011000或11YN不变、Y补右移一位i + 1i=n+1n加法次数，n+1次n最后一次加法不需移位n符号位直接参与运算算法流程图算法流程图计算机组成原理计算机组成原理18 0 0.0 0 0 0 1. 0 0 1 1 0 yn+1=0+ 0 0.1 0 1 1 ynyn+1=1

20、0， 加加-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，

21、加加-x补补 0 0.1 0 0 0 1 1 1 1 1 0 最后一位不移位最后一位不移位例：例：x补补=1.0101，y补补=1.0011， 求求xy补补=？ -x补补=0.1011 xy xy补补=0.10001111=0.10001111部分积部分积乘数乘数 yn yn+1阐明阐明计算机组成原理计算机组成原理19 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

22、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 xy补补

23、= 101111110 = 101111110部分积部分积乘数乘数 yn yn+1 yn yn+1阐明阐明例：例：x=13， y=-10 求求xy=？ xy = -01000 0010 = -82H = -130计算机组成原理计算机组成原理204.4.补码一位乘逻辑原理图补码一位乘逻辑原理图 R0 R1 ynyn+ynyn+1 1R2 计数器计数器i i 部分积部分积z 被乘数被乘数x x乘数乘数y +1LDR0LDR1 T1, T2, +1 Ti QQ加法器加法器RS启动启动Cx f +- -yn+1ynyn+1yn多开关路多开关路原原反反1001QQ计算机组成原理计算机组成原理21a3b1

24、a2b1a1b1a0b1a4b1a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p9p8 p7 p6p5p4 p3 p2 p1p0先计算相加数，然后逐列相加先计算相加数，然后逐列相加原码阵列乘法器原码阵列乘法器设置专用乘法器实现乘法运算设置专用乘法器实现乘法运算计算机组成原理计算机组成原理22相加数产生部件相加数产生部件a4b4a1b0a0b0 A = 0. a4 a3 a2 a1 a0 B = 0. b4 b3 b2 b1 b0经过一级门电路延迟，即可得到所有的相加数经过一级门电路

25、延迟，即可得到所有的相加数一位乘法逻辑实现一位乘法逻辑实现R=X*Yn1 1 1 = 1 1 = 1n1 1 0 = 0 0 = 0n0 0 1 = 0 1 = 0n0 0 0 = 0 0 = 0一个与门即可实现一位乘法一个与门即可实现一位乘法计算机组成原理计算机组成原理23a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p8 p2 p1p0+0+0+a1b1a0b1a3b1a2b1a4b1+ p6+ p7+ p30+p40+p5+0COUT COUT COUT p9COUT横向进位

26、的横向进位的5 5位无符号数阵列乘法器电路位无符号数阵列乘法器电路计算机组成原理计算机组成原理24a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p8 p2 p1p000a1b1a0b1a3b1a2b1a4b1 p6 p7 p30p40p50COUT COUT COUT p9COUT横向进位无符号数阵列乘法器电路时延分析计算机组成原理计算机组成原理25a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b

27、0a2b0a1b0a0b0p8 p2 p1p0103079a1b1a0b1a3b1a2b1a4b12B p689 p7A p30345p404567p567850COUT COUT COUT p9COUTnn+2(n-2)*3T+Tn(3n-4)*3T + T横向进位无符号数阵列乘法器电路时延分析横向进位无符号数阵列乘法器电路时延分析计算机组成原理计算机组成原理26p8 p2 p1p05位无符号数阵列乘法器电路+a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a4b0a3b0a2b0a1b0a0b0a1b1a0b1a3b1a2b1a4b1+ p6 p7 p3p4

28、p5p900a3b4a2b4a0b4a4b4a1b4000演示演示计算机组成原理计算机组成原理27p8 p2 p1p0a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a4b0a3b0a2b0a1b0a0b0a4b1 p6 p7 p3p4p5p90a3b4a2b4a0b4a4b4a1b4a1b1a0b1a3b1a2b100004*5个全加器, 8个全加器延迟计算机组成原理计算机组成原理28原码阵列乘法器时间延迟nn(n-1)个FAn延迟时间n(n-1)FA +(n-1)FAn每一个FA包含三级门电路延迟Tn故总延迟为n2(n-1)*3T T(相加数产生时间)计算机

29、组成原理计算机组成原理29n nn n位原码乘法器框图位原码乘法器框图相加数产生部件A = a f . a n1 an2a1 a0B = b f . b n1 bn2b1 b0nn乘法阵列an1bn1a1b0a0b0Pf=1.P2n1P2n2P2n3P1P0计算机组成原理计算机组成原理303.3.带符号的阵列乘法器带符号的阵列乘法器对对2 2求补器电路求补器电路例例1 1： 对对10101010求补。求补。 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0方法：从数的最右端开始，由右向左，方法：从数的最右端开始，由右向左， 直到找出第一个直到找出第一个“1”“1”，例如，例如aiai1 1， 0in 0in。这样，。这样， ai ai