3并行乘法运算演示教学.ppt

计算机组成原理1计计 算算 机机 组组 成成 原原 理理*定点乘法运算计算机组成原理2借助加法器配置相应部件实现乘法运算设置专用乘法器实现乘法运算执行乘法运算子程序实现乘法运算定点乘法运算原码乘法运算方法原码乘法运算实现补码乘法运算方法补码乘法运算实现计算机组成原理3 设n位被乘数和乘数用定点小数表示 被乘数 x原xf . xn1 x1x0 乘数 y原yf . yn1 y1y0 则乘积 z原(xfyf)(0. xn1 x1x0)(0. yn1 y1y0) 式中：xf为被乘数符号，yf为乘数符号 原码乘法1. 乘法的手工算法一、原码串行乘法运算符号位直接异或即可得到乘积的符号仅仅需要考虑其数值部分的计算以定点小数为例进行讨论计算机组成原理4计算机组成原理5 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) 从内向外逐次进行移位累加计算机组成原理6形成递推公式： 令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)计算机组成原理7开始i = 0, 0Yn=1 + 0 + X Y右移一位i+1i i = nX0Y0P0结束YNNY原码乘法算法流程图原码乘法算法流程图 n加法次数，n次n作为加法，一定移位n符号位单独计算计算机组成原理8部分积乘数说明最后结果 ： 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 。

计算机组成原理94.原码一位乘硬件逻辑原理图 R0 R1 ynR2 计数器i 部分积 z 被乘数x 乘数 y LDR0LDR1 T1， T2， Ti 加法器RS启动ynCx 早期计算机中为了简化硬件结构，采用串行的1位乘法方案，即多次执行“加法移位”操作来实现这种方法并不需要很多器件然而串行方法毕竟太慢，自从大规模集成电路问世以来，出现了各种形式的流水式阵列乘法器，它们属于并行乘法器计算机组成原理10 设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算法计算机组成原理11 在补码机器中，一个数不论其正负，连同符号位向右移一位，符号位保持不变，就等于乘1/2 设 x补 = x0.x1x2xn x = -x0 + x = - x0 +121212= -x0 + x0 + 1212= -x0 + 写成补码的形式，即得：要得到2-ix补，连同符号位右移i位即可。

2) 补码的右移12 x 补 = x0.x0 x1x2xn计算机组成原理12 设被乘数 x补 = x0.x1x2xn 乘数 y补 = y0.y1y2yn 均为任意符号，则有补码乘法算式： xy 补 = x补 y或： xy 补 = x补 (3) 补码乘法规则计算机组成原理13 为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式 yn+1是增加的附加位，初值为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 yn1 =1 则 yi1-yi =1 做加x补运算；ynyn1 = 则 yi1-yi= - 做加-x补运算；ynyn1 =1ynyn1= 0则 yi1-yi= 0 zi加0，即保持不变； 计算机组成原理16补码一位乘的运算规则(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为尾数位数计算机组成原理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 xy补=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 xy补 = 101111110部分积乘数 yn yn+1说明例：x=13， y=-10 求xy=？ xy = -01000 0010 = -82H = -130计算机组成原理204.补码一位乘逻辑原理图 R0 R1 ynyn+1R2 计数器i 部分积z 被乘数x乘数y +1LDR0LDR1 T1, T2, +1 Ti 加法器RS启动Cxf +-yn+1ynyn+1yn多开关路原反1001计算机组成原理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 = 1n1 0 = 0n0 1 = 0n0 0 = 0一个与门即可实现一位乘法计算机组成原理23a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a3b4a2b4a1b4a0b4a4b4a4b0a3b0a2b0a1b0a0b0p8 p2 p1p0+0+0+a1b1a0b1a3b1a2b1a4b1+ p6+ p7+ p30+p40+p5+0COUT COUT COUT p9COUT横向进位的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位无符号数阵列乘法器电路+a3b2a2b2a1b2a0b2a4b2a3b3a2b3a1b3a0b3a4b3a4b0a3b0a2b0a1b。