并行除法运算市公开课一等奖百校联赛获奖课件.pptx

计算机组成原理计算机组成原理1计计 算算 机机 组组 成成 原原 理理Sunday,October 10,定点除法运算定点除法运算第1页计算机组成原理计算机组成原理2被除数被除数 x，其原码为，其原码为x原原xf.xn1 x1 x0除数除数 y，其原码为，其原码为y原原yf.yn1 y1 y0 则有商则有商q/，其原码为，其原码为q原原(xf yf)+(0.xn1x1x0 /0.yn1 y1y0)商符号运算商符号运算qfxf yf 与原码乘法一样与原码乘法一样;商数值部分运算，实质上是两个正数求商运算。商数值部分运算，实质上是两个正数求商运算。设有设有n位定点小数：位定点小数：定点除法运算定点除法运算原码除法运算原理原码除法运算原理原码除法运算第2页计算机组成原理计算机组成原理30.100100.010110.0011100.0010110.00001100.00010110.000011000.000010110.00000001不够减，商上零，-0.10110.1101除数右移1位，够减，减除数，商上1除数右移1位，够减，减除数，商上1除数右移1位，不够减，商上零除数右移1位，够减，减除数，商上1定点除法手工计算定点除法手工计算第3页计算机组成原理计算机组成原理4原码一位除法原码一位除法 结果与手算相同结果与手算相同，但余数不是真正余数但余数不是真正余数，多乘了多乘了2n，故正确余数应为故正确余数应为2-nrn，即：，即：0.0000000100.0001 第四次余数第四次余数r4 01.0010 被除数左移一位，被除数左移一位，2xy，商，商1+11.0101 减减y，即，即+-y补补00.0111 第一次余数第一次余数r1 00.1110 r1左移一位左移一位，2r1y，商，商1+11.0101 减减y00.0011 第二次余数第二次余数r2 00.0110 r2左移一位左移一位，2r2y，商，商1+11.0101 减减y00.1011 00.1001 xy，商，商000.1101x=0.1001,y=0.1011，-y补补=1.0101第4页计算机组成原理计算机组成原理5原码恢复余数除法恢复余数除法n怎样判断是否够减n原码运算判断借位n利用补码作减法，判断余数符号即可n余数为负数时，必须恢复余数n即将余数加除数，恢复成原来值。n求下一位商，必须将余数左移一位，再与除数比较n比较，上商（恢复），余数移位，再比较，直到取得商所需要位数为止。第5页计算机组成原理计算机组成原理600.100101.001011.0101被除数被除数/余数余数00.011100.111011.010100.001100.011011.0101商商上商位上商位说明说明减Y比较左移一位减Y比较余数R00，商上1左移一位减Y比较R20，商上1左移一位减Y比较R30，商上111.111000.101100.000100.011000.110011.010111.101100.1011 0.1100.11010.110 0.1 00 0.11 00.100111.0101+Y补+Y补+Y补+Y补+Y补+第6页计算机组成原理计算机组成原理7恢复余数乘法问题恢复余数乘法问题n需要进行恢复余数操作n恢复余数操作次数不确定，故运算时间不固定，所以控制比较复杂。n实际中惯用不恢复余数法，又称加减交替法。其特点是运算过程中如出现不够减，则无须恢复余数，依据余数符号，能够继续往下运算，所以步数固定，控制简单。第7页计算机组成原理计算机组成原理8加减交替法加减交替法 上述恢复余数法因为要恢复余数，使得除法步数不固定，上述恢复余数法因为要恢复余数，使得除法步数不固定，控制比较复杂。实际上惯用是控制比较复杂。实际上惯用是加减交替法加减交替法。特点：特点：当运算过程中出现不够减情况，无须恢复余数，而是当运算过程中出现不够减情况，无须恢复余数，而是依据余数符号，继续往下运算，所以步数固定，控制简单。依据余数符号，继续往下运算，所以步数固定，控制简单。不恢复余数法：不恢复余数法：若第若第i-1i-1次商余数为次商余数为R Ri-1i-1，下一次求商方法是：，下一次求商方法是：Ri=2RRi=2Ri-1i-1-Y-Y当当Ri0Ri0时，第时，第i i位商位商0 0，恢复余数法结果为（，恢复余数法结果为（RiRi=R=Ri i+Y+Y）第第i+1i+1次商余数为次商余数为R Ri+1i+1，R Ri+1i+1=2=2R Ri i-Y-YR Ri+1i+1=2(=2(R Ri i+Y+Y)-Y=2R)-Y=2Ri i+Y+Y原码加减交替法原码加减交替法 ：通式：通式 Ri+1=2Ri+(1-2Qi)Y Ri+1=2Ri+(1-2Qi)YQiQi为为第第i i次次所得商。若部分所得商。若部分余数为正，则余数为正，则Qi=1 加（加（-y）若部分若部分余数为负，则余数为负，则Qi=0 加加 y2Ri+y 2Ri+y 结果与恢复余数后左移一位再减结果与恢复余数后左移一位再减y y是等效是等效第8页计算机组成原理计算机组成原理911.111011.110000.1011被除数被除数/余数余数00.011100.111011.010100.001100.011011.0101商商上商位上商位说明说明减Y比较R0 0，商上1左移一位，减Y比较R20，商上1左移一位，减Y比较R30，商上100.000111.101111.011000.1011 0.1100.1101 0.1 0 0.11 00.100111.0101+Y补+Y补+Y补+Y补+Y补第9页计算机组成原理计算机组成原理10上商位移位控制R001 1控制逻辑R2 除数加法器cR0 被除数/余数 R1 商不恢复余数除法逻辑结构不恢复余数除法逻辑结构Qn=1 1计数器第10页计算机组成原理计算机组成原理11例n用原码不恢复余数法计算X补Y补。(1)X=0.10101，Y=0.11011 -Y补=1.00101第11页计算机组成原理计算机组成原理1211.1101011.1010000.11011被除数被除数/余数余数00.0111100.1111011.0010100.0001100.0011011.00101商商上商位上商位说明说明减Y比较R0 0，商上1左移一位，减Y比较R20，商上1左移一位，减Y比较R30 商上零左移一位，加Y比较R40，商上0左移一位，加Y比较11.1000111.0001000.1101111.0101110.1011000.11011 0.1100.1100 0.1 0 0.11 00.1010111.00101+Y补+Y补+Y补+Y补+Y补 +Y补 11.111010.11000R50 商上零第12页计算机组成原理计算机组成原理13阵列阵列除法器除法器1.1.可控加法可控加法/减法减法(CAS)(CAS)单元单元阵列除法器有各种多样形式，如不恢复余数阵列除法器，阵列除法器有各种多样形式，如不恢复余数阵列除法器，补码阵列除法器等等。补码阵列除法器等等。首先介绍可控加法首先介绍可控加法/减法减法(CAS)(CAS)单元，它将用于并行除法流单元，它将用于并行除法流水逻辑阵列中，它有四个输出端水逻辑阵列中，它有四个输出端S Si i、C Ci i1 1、B Bi i、P P和四个输入和四个输入端端A Ai i、B Bi i、P P、C Ci i 。当输入线当输入线P P0 0时，时，CASCAS作加法运算作加法运算；当；当P P1 1时，时，CASCAS作减法运算作减法运算。CAS CAS单元输入与输出关系可用以下一组逻辑方程来表示：单元输入与输出关系可用以下一组逻辑方程来表示：S Si iA Ai i(B(Bi iP)CP)Ci i C Ci i1 1(A(Ai iC Ci i)(B)(Bi iP)P)A Ai iC Ci i 当当P P0 0时，上式即是我们熟悉一位全加器时，上式即是我们熟悉一位全加器(FA)(FA)公式：公式：S Si iA Ai iBBi iCCi iC Ci i1 1A Ai iB Bi iB Bi iC Ci iA Ai iC Ci i 第13页计算机组成原理计算机组成原理14当当P P1 1时，则得求差公式：时，则得求差公式：S Si iA Ai iBBi iCCi iC Ci i1 1A Ai iB Bi iB Bi iC Ci iA Ai iC Ci iCi+1PCiSiYiXi(a)电路 =1 1FAiPCiYiXiCi+1Si(b)符号表示CASi第14页计算机组成原理计算机组成原理15Q4Q3CASCASCASCASCAS0.Q1Q2P=10.Y1Y2Y3Y40.X1X2X3X4X5X6X7X8R4R5R6R7R8CASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCAS原码阵列除法器原码阵列除法器1.Cf=Qn 符号位进位=商 第15页计算机组成原理计算机组成原理16Q40.Q1Q2P=10.Y1Y2Y3Y40.X1X2X3X4X5X6X7X8R4R5R6R7R8Q3原码阵列除法器延迟原码阵列除法器延迟CASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCAS1.Cf=Qn 符号位进位=商 第16页计算机组成原理计算机组成原理17除法器延迟除法器延迟nn*n个CAS延迟单元n每一个CAS包含4级门电路延迟Tn故总延迟为n(n*n)4T第17页