《计算机组成原理第5讲定点除法.ppt》由会员分享，可在线阅读，更多相关《计算机组成原理第5讲定点除法.ppt（31页珍藏版）》请在三一文库上搜索。
1、计算机组成原理,Principles of Computer Organization,广义双语教学课程,http:/211.64.192.109/skyclass25/,青岛理工大学 校级精品课程,http:/ 运算方法和运算部件,( 4 ),Several algorithms exist to perform division in digital designs. These algorithms fall into two main categories: slow division and fast division. Slow division algorithms produc
2、e one digit of the final quotient per iteration.,Examples of slow division include restoring, non-performing restoring, non-restoring, and SRT division.,Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iterati
3、on. Newton-Raphson and Goldschmidt fall into this category.,3,补码一位乘法,Tows complement Multiplication,Booths multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in twos complement notation.,The algorithm was invented by Andrew Donald Booth in 1951 .,比较法（又称B
4、ooth法）是实现补码一位乘法的一种方案。,Modern computers embed the sign of the number in the number itself, usually in the twos complement representation. That forces the multiplication process to be adapted to handle twos complement numbers, and that complicates the process a bit more.,4,补码一位乘法,设 X补= X0 .X1X2Xn-1Xn
5、，Y补= Y0 .Y1Y2Yn-1Yn,根据校正法 XY补 = X补（0. Y1Y2Yn-1Yn）+ -X补Y0,=X补（-Y0 +Y12-1Y22-2Yn 2-n）,式中，Y0是符号位（“0”为正，“1”为负），Yn+1是在乘数最低位Yn后增设的附加位，初值为0。,=X补-Y0+(Y1-Y12-1)+(Y22-1-Y22-2)+( Yn 2(n-1)-Yn 2-n),=X补(Y1-Y0)+( Y2-Y1)2-1+（Yn-Yn-1）2-（n-1） +(0-Yn) 2-n,=X补(Y1Y0)+( Y2Y1)2-1+( Yn+1Yn) 2-n,=X补,则 XY补 = X补（Y0 + ),48页,5
6、,P0补 0,开始时，部分积为0， 然后在上一步的部分积上加 ( Yi+1Yi) X补（i=n,2,1,0），再右移一位，得到新的部分积。如此重复n+1步，最后一次不移位，得到XY补。,从该递推公式可归纳出补码一位比较乘法的运算规则,递推公式（ Booth公式）:,P1补 P0补+( Yn+1Yn)X补21,P2补 P1补+( YnYn1)X补21, Pi补 Pi1补+( Yni+2Yni+1)X补21, Pn补 Pn1补+( Y2Y1)X补21,Pn+1补 Pn补+( Y1Y0)X补,XY补=X补(Y1Y0)+( Y2Y1)2-1+( Yn+1Yn) 2-n,=XY补,部分积的初值0,位积+
7、部分积 然后右移1位,6,补码一位比较乘法的运算规则：, 参加运算的数用补码表示，符号位一并参加运算。, 被乘数和部分积取双符号位，乘数取单符号位。, 乘数末位增设附加位Yn+1，其初始值为0。, 乘数末位Yn与附加位Yn+1构成各步运算的判断位：, 按照上述算法进行n+1步操作，但第n+1步不再移位。,右移必须按补码右移规则进行。,部分积累加时最高有效位产生的进位是有效数值，可以用第二符号位暂存起来，第一符号位表示正确的符号。,0 1 部分积加X补后右移一位 Y i+1- Y i =1,1 0 部分积加-X补后右移一位 Y i+1- Y i = -1,0 0 部分积加0后右移一位 Y i+1
8、- Y i =0,1 1 部分积加0后右移一位 Y i+1- Y i =0,7,【例3】X+0.1011B，Y0.1101B， 用补码一位比较乘法计算XY。,解：,X补,Y补,X补,00.1011,1.0011,11.0101,运算过程中每一个新的部分积都是在上一次部分积的基础上，根据( Yi+1Yi )来决定是加X补或是加-X补或加零。机器不做减法，而是采用比较相邻两位的结果来决定上述操作的，故称比较法。,Tows complement Multiplication,Booths algorithm involves repeatedly adding one of two predeter
9、mined values A and S to a product P, then performing a rightward arithmetic shift on P.,部分积 0 0. 0 0 0 0,部分积/乘数 附加位 1. 0 0 1 1 0,说 明 P0补 0， Yn+10,XY补=11.01110001,1 1 0 1 1 1 0 0 0 1 最后一步不移位,+ 1 1 0 1 0 1 YnYn+1 10，加-X补,0 0 0 0 1 0 0 0 0 1 1 0 右移一位，得P4补,0 0 0 1 0 0,+ 0 0 0 0 0 0 YnYn+1 00，加0,0 0 0 1
10、0 0 0 0 1 1 0 0 右移一位，得P3补,0 0 1 0 0 0,+ 0 0 1 0 1 1 YnYn+1 01，加X补,1 1 1 1 0 1 0 1 1 0 0 1 右移一位，得P2补,1 1 1 0 1 0,+ 0 0 0 0 0 0 YnYn+1 11，加0,1 1 1 0 1 0 1 1 0 0 1 1 右移一位，得P1补,1 1 0 1 0 1,+ 1 1 0 1 0 1 YnYn+1 10，加-X补,XY=0.10001111,补码一位比较乘法流程图,01,10,00 或11,i=0, P0补 =0,Pi补+-X补,Pi补 + 0,Pi补+X补,Pi补,Y补右移一位 i
11、+1i,开始,YnYn+1=,in+1?,Y,N,结束,10,阵列乘法器,高速的并行乘法运算,The engineering implementation of binary multiplication consists of taking a very simple mathematical process and complicating it a lot, in order to do fewer additions; a modern processor can multiply two 64-bit numbers with 16 additions (rather than 64
12、), and can do several steps in parallel.,11, 3. 4 二进制除法运算,Binary (Fixed-Point) Division Arithmetic,原码除法,补码除法,Tows complement Division,Unsigned Binary Division,12,计算机的除法运算对除数和被除数的大小有限制。,首先，除数不能为零。其次，定点除法运算可能会发生溢出。,对于定点小数，若被除数大于或等于除数，则商将大于或等于1，发生溢出。 所以，小数除法要求 0|被除数|除数|。,对于定点整数，商也应是整数。要求 0|除数|被除数|。,计算机
13、在做除法之前，必须先检查除数和被除数是否为零。若除数为零，则转出错处理。若被除数为零，则直接得出商为零。,若除数和被除数都不为零，则判断是否可能发生溢出。,若除数是n位，则得到n位的商Quotient和n位的余数Remainder。,整数除法若被除数Dividend只有n位，是不会发生溢出的。但是，若被除数为2n位，则被除数的高n位的绝对值必须小于除数Divisor的绝对值，否则，将发生溢出。,小数除法，只要满足 |被除数|除数| 就不会溢出。,13,手工计算二进制除法的方法,0.1011 被除数,除数 0.1101,商0.,先判断被除数与除数的大小,若被除数小，则上商0，并把被除数的下一位（
14、若存在）移下来；或在余数最低位补0，再用余数与右移一位的除数比较，若够除则上商1，否则上商0。,然后继续重复以上步骤，直至除尽（余数为0）或求得的商的位数满足要求为止。,01101,部分余数 010010,01101,Partial Remainder 0010100,01101,001110,01101,1,1,0,1,1,14,计算机实现除法时，要把除数右移改为被除数/余数左移。,要求计算机把求得的商直接写进商寄存器的每个对应位也是不可取的，通常是把商上到商寄存器的最低位，并把部分商左移一位。,运算过程中，存放被除数/余数和商的寄存器一同移位。计算完成后，商寄存器中是商的尾数，原来存放被除
15、数的寄存器中是余数。,做减法时，对于n位的除数，也不要求2n位的加法器，只需用n位的加法器即可。,15,原码除法运算,原码除法，商的符号位是除数和被除数的符号位的异或值，商的值是用被除数的绝对值除以除数的绝对值得出的。,计算机不能象人那样用观察的方法决定是上商0还是上商1。,1. 比较法,用汇编语言编写除法运算程序，可以用比较指令比较除数和被除数(余数)的大小，以决定是上商0还是上商1，这就是比较法。,计算机的比较指令实质上也是做减法，但摒弃减法的结果，不改变被减数，只影响状态标志寄存器的Cy（进位/借位），S（符号），Z（零）等标志位的状态。,若Cy1，表明有借位，被除数小于除数，应当上商0
16、，不做被除数/余数减除数，只把被除数/余数左移一位。反之，上商1，做被除数/余数减除数，并把余数左移一位。,比较法要多做一次比较，降低了速度。,Unsigned Binary Division,16,2. 恢复余数法,直接从被除数/余数中减去除数，若够减，余数为正，上商1；若不够减，余数为负，上商0。此时，必须将除数加回去，恢复成原来的余数，以便继续计算，因此称为恢复余数法。,恢复余数法在不够减时要恢复余数，多做一次加法操作，运算速度因而受到影响，控制线路复杂，运算不规则，运算时间与数据有关。,在计算机中实际采用的是不恢复余数法Non-restoring division 。,Restorin
17、g division,17,3. 加减交替法（不恢复余数法Non-restoring division ）,不恢复余数法的思想是当某一次减法的差为负时，不是把它恢复成原来的值，而是设法直接用这个负的差值求下一位商。,设上次余数为Ri。,当Ri 0时，,然后将余数左移一位（成为2 Ri2Y），,当Ri 0时，,显然，若不恢复余数，而将余数Ri左移一位成为2 Ri，再加除数，结果与恢复余数法一样。但却把加Y、左移、减Y三个步骤简化成左移、加Y两个步骤。,商上1，,继续求下次余数；,将余数左移一位得2 Ri ，,再减除数，,即 2 RiYRi1。,商上0。,此时若恢复余数，,应做RiY，,即2 Ri
18、2YY ,再减除数，,2 RiYRi1,18,最后一次余数若为负值，还应加上除数以得到正确的余数。,运算中总共左移n次，相当于乘2n，最后的余数应为Rn*2 -n。余数的符号与被除数一致。,由于不恢复余数法要根据余数Ri的情况分别做加法或减法，所以又称为加减交替法。,Non-restoring division,Unsigned Binary Division,无符号数不恢复余数除法算法流程图,Y,计数器i=0 XY R,商1,商上0, Ri左移一位, 2 RiYRi+1,商上1, Ri左移一位, 2 RiYRi+1,i+1i,商0 Rn +Y,开始,Ri 0?,Y,Y,N,i=n?,N,Rn
19、 0?,结束,N,除数、被除数符合规定 允许进行除法运算。 符号位单独运算。图中的X和Y实际是|X|和|Y|。,第一位商是小数点左边的0,总共求出N+1位商,20,例1 X= -0.1001 ，Y=+0.1011，用原码不恢复余数法计算XY,解：,X原1.1001,|X|0.1001,商的符号位,Y原0.1011,|Y|0.1011,|Y|补=,1.0101,被除数/余数 0. 1 0 0 1,商 0 . 0 0 0 0,|XY|=0.1101,XY原=1.1101,XY=0.1101,余数 |R| =0.000124， R=0.00000001,减Y用加|Y|的补码实现,减|Y| ） 1.
20、0 1 0 1,余数为负，商上0,1. 1 1 1 0,左移,余数为正，商上1,0. 0 0 0 1,加|Y| ） 0. 1 0 1 1,左移,1. 0 1 1 0,余数为负，商上0,1. 1 0 1 1,减|Y| ） 1. 0 1 0 1,左移,0. 0 1 1 0,余数为正，商上1,0. 0 0 1 1,0 0 0 1 1,0 1 1 0 1,0 0 1 1 0,减|Y| ） 1. 0 1 0 1,左移,0. 1 1 1 0,0 0 0 1,0 0 1 1,0 1 1 0,0 0 0 0 1,余数为正，商上1,0. 0 1 1 1,加|Y| ） 0. 1 0 1 1,0 0 0 0,1.
21、1 1 0 0,0 0 0 0 0,|Y|0.1011,|Y|补= 1.0101,22, 3.4.2 提高除法运算速度的方法,Named for its creators (Sweeney, Robertson, and Tocher), SRT division is a popular method for division in many microprocessor implementations.,SRT division is similar to non-restoring division, but it uses a lookup table based on the div
22、idend and the divisor to determine each quotient digit.,The Intel Pentium processors infamous divider bug was caused by an incorrectly coded lookup table. Five entries that were believed to be theoretically unreachable had been omitted from the more than one thousand table entries.,1. 跳0跳1除法,2. 除法运算
23、通过乘法操作来实现,23,105 总线结构,主机和外部设备的连接方式有辐射型连接和总线型连接等。,连接线多，不规整，设计 复杂，扩展难，维修难,24,总线的基本概念,定义： 总线（BUS）是由多个设备共享的传送信息的一簇公共的信号线及相关逻辑。,In computer architecture, a bus is a subsystem that transfers data between computer components inside a computer or between computers. Unlike a point-to-point connection, a bus
24、can logically connect several peripherals over the same set of wires.,现代计算机的各个组成部分是通过总线（Bus）相互连接的。,25,总线可分为：处理机内部总线，系统总线，通信总线。,系统总线用于连接一个计算机系统内各主要功能部件（处理机，主存，I/O接口）。,通信总线用于计算机系统之间或主机与I/O设备之间的通信。,Most computers have both internal and external buses. An external bus connects external peripherals to th
25、e motherboard.,An internal bus connects all the internal components of a computer to the motherboard (and thus, the CPU and internal memory). These types of buses are also referred to as a local bus, because they are intended to connect to local devices, not to those in other machines or external to
26、 the computer.,总线的分类,26,总线的分类,按总线的数据传输方式可分为：并行总线，串行总线。,系统总线通常是并行总线。由一组地址线、一组数据线和一组控制线构成。分别称为：地址总线，数据总线，控制总线。,数据线用于传送数据、命令或地址。数据总线的宽度决定了每次能同时传输的信息的位数。,地址线用于传送要访问的主存单元或I/O端口的地址。地址总线的位数决定了可寻址的地址空间的大小。,控制线用于传送控制信号和状态信号。,Buses can be parallel buses, which carry data words in parallel on multiple wires, o
27、r serial buses, which carry data in bit-serial form.,27,10.5.1 总线类型,1单总线结构,单总线结构的计算机系统是指一个计算机系统的所有部件都挂在一个系统总线上。,单总线结构计算机的框图：,These simple bus systems had a serious drawback when used for general-purpose computers. All the equipment on the bus has to talk at the same speed, as it shares a single cloc
28、k.,2双总线结构,面向存储器的双总线结构,面向输入输出的双总线结构,29,3多总线结构,单处理器的多总线结构,An increasing number of external devices started employing their own bus systems as well. But through the 1980s and 1990s, new systems like SCSI and IDE were introduced to serve this need, leaving most slots in modern systems empty.,30,多处理机的多总线
29、结构,31,The digital computer is a digital system that performs various computational tasks.,The word digital implies that the information in the computer is represented by variables that take a limited number of discrete values.,These values are processed internally by components that can maintain a limited number of discrete states.,An ALU must process numbers using the same format as the rest of the digital circuit. For modern processors, that almost always is the twos complement binary number representation.,Homework,3 - 18， 19，30，,