并行乘法运算.pptx

计算机组成原理计算机组成原理1计计 算算 机机 组组 成成 原原 理理2024年9月6日定点乘法运算定点乘法运算计算机组成原理计算机组成原理2借助加法器配置相应部件实现乘法运算借助加法器配置相应部件实现乘法运算设置专用乘法器实现乘法运算设置专用乘法器实现乘法运算执行乘法运算子程序实现乘法运算执行乘法运算子程序实现乘法运算定点乘法运算定点乘法运算原码乘法运算方法原码乘法运算方法原码乘法运算实现原码乘法运算实现补码乘法运算方法补码乘法运算方法补码乘法运算实现补码乘法运算实现计算机组成原理计算机组成原理3 设设n n位位被乘数和乘数用定点小数表示被乘数和乘数用定点小数表示 被乘数被乘数 x x 原原x xf f.x.xn n1 1 x x1 1x x0 0 乘数乘数 y y 原原y yf f.y.yn n1 1 y y1 1y y0 0 则乘积则乘积 z z 原原(x xf fy yf f)(0.(0.x xn n1 1 x x1 1x x0 0)(0.)(0.y yn n1 1 y y1 1y y0 0)式中：式中：x xf f为被乘数符号，为被乘数符号，y yf f为乘数符号。为乘数符号。原码乘法原码乘法1.1.乘法的手工算法乘法的手工算法一、原码串行乘法运算一、原码串行乘法运算符号位直接异或即可得到乘积的符号符号位直接异或即可得到乘积的符号仅仅需要考虑其数值部分的计算仅仅需要考虑其数值部分的计算以以定点小数定点小数为例进行讨论为例进行讨论计算机组成原理计算机组成原理4(2)(2)手工运算过程：手工运算过程：设设0.11010.1101，0.10110.1011 0.1 1 0 1 (0.1 1 0 1 (x 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 (0.1 0 0 0 1 1 1 1 (z z)(1)(1)乘积符号的运算规则：乘积符号的运算规则：同号相乘为正，异号相乘为负。同号相乘为正，异号相乘为负。(1)(1)机器通常只有机器通常只有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 x0.0 0 0 1 1 0 1 x共共3 3次右移次右移 0.0 0 0 0 0 0 x0.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 10.1 0 0 0 1 1 1 1 2.2.适合定点机的形式适合定点机的形式 为了适合两个操作数相加的加法器，为了适合两个操作数相加的加法器，将将 x x y y 改写成下面形式：改写成下面形式：x x y=xy=x(0.1011)(0.1011)=0.1 =0.1 x+0.00 x+0.00 x+0.001 x+0.001 x+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 =2-1-1 x+2 x+2-1-1 0+20+2-1-1(x+2(x+2-1-1x)x)从内向外从内向外逐次进行逐次进行移位累加移位累加计算机组成原理计算机组成原理6形成形成递推公式：递推公式：令令z zi i表示第表示第i i次部分积，则根据从内到外的原则有：次部分积，则根据从内到外的原则有：z z0 0=0=0 z z1 1=2=2-1-1(y(yn nx+zx+z0 0)z z2 2=2=2-1-1(y(yn-1n-1x+zx+z1 1)z zi i=2=2-1-1(y(yn-i+1n-i+1x+zx+zi-1i-1)z zn n=x=x y=2y=2-1-1(y(y1 1x+zx+zn-1n-1)特点：特点：每每次次只只需需要要相相加加两两个个数数，然然后后右右移移一一位位。且且相相加加的的两两个个数数（部部分分积积和和位位积）都只有积）都只有n n位，因而不需要位，因而不需要2n2n位的加法器。位的加法器。一般而言，设被乘数一般而言，设被乘数x x，乘数，乘数y y都是小于都是小于1 1的的n n位定点正数：位定点正数：其乘积为：其乘积为：xy=x(0.yxy=x(0.y1 1y y2 2.y.yn n)=x(y =x(y1 12 2-1-1+y+y2 22 2-2-2+y+yn n2 2-n-n)=2 2-1-1(y(y1 1x+x+2 2-1-1(y(y2 2x+x+2 2-1-1(+(+2 2-1-1(y(yn-1n-1x+x+2 2-1-1(y(yn nx+0)x+0)计算机组成原理计算机组成原理7开始i=0,0Yn=1+0 +X Y右移一位i+1i i=nX0Y0P0结束YNNY原码乘法算法流程图原码乘法算法流程图原码乘法算法流程图原码乘法算法流程图 n加法次数，n次n作为加法，一定移位n符号位单独计算计算机组成原理计算机组成原理8部分积部分积乘数乘数说明说明最后结果最后结果：x y=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=x y例：例：x=0.1101，y=0.1011，求求 x xy y。计算机组成原理计算机组成原理94.4.原码一位乘硬件逻辑原理图原码一位乘硬件逻辑原理图 R R0 0 R R1 1 y yn nR R2 2 计数器计数器i i 部分积部分积 z z 被乘数被乘数x x 乘数乘数 y y LDRLDR0 0LDRLDR1 1 T1T1，T2T2，T Ti i Q QQ Q加法器加法器R RS S启动启动y yn nC Cx x 早期计算机中为了简化硬件结构，采用串行的早期计算机中为了简化硬件结构，采用串行的1 1位乘法方案，即多次位乘法方案，即多次执行执行“加法加法移位移位”操作来实现。这种方法并不需要很多器件。然而串操作来实现。这种方法并不需要很多器件。然而串行方法毕竟太慢，自从大规模集成电路问世以来，出现了各种形式的流行方法毕竟太慢，自从大规模集成电路问世以来，出现了各种形式的流水式水式阵列乘法器阵列乘法器，它们属于并行乘法器。，它们属于并行乘法器。计算机组成原理计算机组成原理10 设设xx补补 =x=x0 0.x.x1 1x x2 2xxn n 当当x x 0 0时，时，x x0 0=0=0，xx补补=0.x=0.x1 1x x2 2xxn n=x=x=-1+0.x=-1+0.x1 1x x2 2xxn n=-1+=-1+x=-xx=-x0 0+真值与补码的关系：真值与补码的关系：当当x x 0 0时，时，x x0 0=1=1，xx补补=1.x=1.x1 1x x2 2xxn n=2+x=2+x x=1.x x=1.x1 1x x2 2xxn n-2-2(1)(1)真值和补码之间的关系真值和补码之间的关系补码乘法补码乘法 一、补码串行乘法一、补码串行乘法 采用比较法。比较法是采用比较法。比较法是BoothBooth夫妇首先提出来的，又称夫妇首先提出来的，又称BoothBooth算法。算法。计算机组成原理计算机组成原理11 在在补补码码机机器器中中，一一个个数数不不论论其其正正负负，连连同同符符号号位位向向右右移移一一位位，符符号号位位保保持不变，就等于乘持不变，就等于乘1/21/2。设设 xx补补 =x=x0 0.x.x1 1x x2 2xxn n x=-x0 +x=-x-x0 0+121212=-x0+x0+1212=-x0+写成补码的形式，即得：写成补码的形式，即得：要得到要得到22-i-ixx补补，连同符号位右移，连同符号位右移i i位即可。位即可。(2)(2)补码的右移补码的右移12 x 补补 =x x0 0.x.x0 0 x x1 1x x2 2x xn n计算机组成原理计算机组成原理12 设被乘数设被乘数 xx补补 =x=x0 0.x.x1 1x x2 2xxn n 乘数乘数 yy补补 =y=y0 0.y.y1 1y y2 2yyn n 均为任意符号，则有补码乘法算式：均为任意符号，则有补码乘法算式：xy 补补=x补补 y或：或：xy 补补=x补补(3)(3)补码乘法规则补码乘法规则计算机组成原理计算机组成原理13 为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。(y(yn+1n+1是增加的附加位，初值为是增加的附加位，初值为0)0)计算机组成原理计算机组成原理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-+=+最后一步不移位最后一步不移位计算机组成原理计算机组成原理15由此可见：由此可见：每次都是在前次部分积的基础上，由每次都是在前次部分积的基础上，由（yi+1-yi)决定对决定对x补补的操作，然后再右移一位，得到新的部分积；重复进行。的操作，然后再右移一位，得到新的部分积；重复进行。yn+1，yn的作用：的作用：开始操作时，补充一位开始操作时，补充一位yn+1,使其初始为使其初始为0。由。由yn+1 yn 判断进判断进行什么操作；然后再由行什么操作；然后再由ynyn-1 判断第二步进行什么操作判断第二步进行什么操作。若若 yn n yn n1 1=1 1 则则 yi1 1-yi=1 =1 做加做加xx补运算；补运算；yn nyn n1 1=则则 yi1 1-yi=-做加做加-x-x补运算补运算；yn nyn n1 1=1 1yn nyn n1 1=0=0则则 yi1 1-yi=0 zzi i 加加0 0，即保持不变；，即保持不变；计算机组成原理计算机组成原理16补码一位乘的运算规则补码一位乘的运算规则(1)如果如果 yn=yn+1，则部分积则部分积 zi 加加0，再右移一位；，再右移一位；(2)如果如果 yn yn+1=01，则部分积，则部分积 zi 加加x补补，再右移一位；，再右移一位；(2)如果如果 yn yn+1=10，则部分积，则部分积 zi 加加-x补补,再右移一位；再右移一位；如此重复如此重复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=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 x xyy补补=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 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 x xyy补补 =101111110=101111110部分积部分积乘数乘数 y yn n y yn+1n+1说明说明例例：x=13，y=-10 求求xy=？xy=-01000 0010=-82H=-130计算机组成原理计算机组成原理204.4.补码一位乘逻辑原理图补码一位乘逻辑原理图 R0 R1 y yn ny yn+1n+1R2 计数器计数器i i 部分积部分积z 被乘数被乘数x x乘数乘数y+1LDR0LDR1 T1,T2,+1 Ti QQ加法器加法器RS启动启动Cx f+-yn+1ynyn+1yn多开关路多开关路原原反反1001QQ计算机组成原理计算机组成原理21a3b1a2b1a1b1a0b1a4b1a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p9p8 p7 p6p5p4 p3 p2 p1p0 p p9 9p p8 8p p7 7p p6 6p p5 5p p4 4p p3 3p p2 2p p1 1p p0 0a a4 4a a3 3a a2 2a a1 1a a0 0 x x b b4 4b b3 3b b2 2b b1 1b b0 0先计算相加数，然后逐列相加先计算相加数，然后逐列相加原码阵列乘法器原码阵列乘法器设置专用乘法器实现乘法运算设置专用乘法器实现乘法运算计算机组成原理计算机组成原理22相加数产生部件相加数产生部件a4b4a1b0a0b0 A=0.a4 a3 a2 a1 a0 B=0.b4 b3 b2 b1 b0&经过一级门电路延迟，即可得到所有的相加数经过一级门电路延迟，即可得到所有的相加数一位乘法逻辑实现一位乘法逻辑实现R=X*Yn1 1=11 1=1n1 0=01 0=0n0 1=00 1=0n0 0=00 0=0一个一个与门与门即可实现一位乘法即可实现一位乘法计算机组成原理计算机组成原理23a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p8 p2 p1p0+0+0+a1b1a0b1a3b1a2b1a4b1+p6+p7+p30+p40+p5+0COUT COUT COUT p9COUT横向进位的横向进位的5 5位无符号数阵列乘法器电路位无符号数阵列乘法器电路计算机组成原理计算机组成原理24a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p8 p2 p1p000a1b1a0b1a3b1a2b1a4b1 p6 p7 p30p40p50COUT COUT COUT p9COUT横向进位无符号数阵列乘法器电路时延分析计算机组成原理计算机组成原理25a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p8 p2 p1p0103079a1b1a0b1a3b1a2b1a4b12B p689 p7A p30345p404567p567850COUT COUT COUT p9COUTnn+2(n-2)*3T+Tn(3n-4)*3T+T横向进位无符号数阵列乘法器电路时延分析横向进位无符号数阵列乘法器电路时延分析计算机组成原理计算机组成原理26p8 p2 p1p05位无符号数阵列乘法器电路+a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a4b0a3b0a2b0a1b0a0b0a1b1a0b1a3b1a2b1a4b1+p6 p7 p3p4p5p900a3b4a2b4a0b4a4b4a1b4000 p p9 9p p8 8p p7 7p p6 6p p5 5p p4 4p p3 3p p2 2p p1 1p p0 0a a4 4a a3 3a a2 2a a1 1a a0 0 x x b b4 4b b3 3b b2 2b b1 1b b0 0演示演示计算机组成原理计算机组成原理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(相加数产生时间)计算机组成原理计算机组成原理29n n n n位原码乘法器框图位原码乘法器框图相加数产生部件A=af.an1 an2a1 a0B=bf.bn1 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”，例如，例如a ai i1 1，00i in n。这样，。这样，a ai i以左的每一个输入位都求反，以左的每一个输入位都求反，即即1 1变变0 0，0 0变变1 1。补码阵列乘法器补码阵列乘法器计算机组成原理计算机组成原理311 0 1 0 0 1 1 0 1对对2求补电路求补电路 当控制信号线当控制信号线E E为为“1”1”时，启动对时，启动对2 2求补的操作。当控制信号线求补的操作。当控制信号线E E为为“0”0”时，输出将和输入相等。显然，我们可以利用时，输出将和输入相等。显然，我们可以利用符号位符号位来作为控制信号。来作为控制信号。用这种对用这种对2 2求补器来转换一个求补器来转换一个(n n1)1)为带符号的数，所需的总时间延迟为：为带符号的数，所需的总时间延迟为：t tn n22T T5 5T T(2(2n n5)5)T T 其中每个扫描级需其中每个扫描级需2 2T T延迟，而延迟，而5 5T T则是由于则是由于“与与”门和门和“异或异或”门引起的。门引起的。计算机组成原理计算机组成原理32补码乘法器原理图补码乘法器原理图 B补=bf.bn1 b1 b0不带符号乘法阵列（nn阵列）2n位求补器数值同原码相加数积绝对值P2n1P1P0（补码乘积）=1 1Pf.A补=af.an1 a1 a0相加数产生电路n位求补器n位求补器计算机组成原理计算机组成原理33 包括求补级的乘法器又称为包括求补级的乘法器又称为符号求补的阵列乘法器。符号求补的阵列乘法器。在这种逻辑结构中，共使用三个求补器：在这种逻辑结构中，共使用三个求补器：两个算前求补器两个算前求补器 作用：作用：将两个操作数将两个操作数A A和和B B在被不带符号的乘法阵列在被不带符号的乘法阵列(核心部件核心部件)相乘以前，先相乘以前，先 变成正数。变成正数。算后求补器算后求补器 作用：作用：当两个输入操作数的符号不一致时，把运算结果变成带符号的数。当两个输入操作数的符号不一致时，把运算结果变成带符号的数。结构：结构：在必要的求补操作以后，在必要的求补操作以后，A A和和B B的码值输送给的码值输送给nnnn位不带符号的阵列乘法器，位不带符号的阵列乘法器，并由此产生并由此产生2 2n n位的乘积：位的乘积：ABABP Pp p2 2n n1 1p p1 1p p0 0p p2 2n na an nb bn n 其中，其中，P P2 2n n为符号位。为符号位。