计算机组成原理第5讲定点除法.ppt

《计算机组成原理第5讲定点除法.ppt》由会员分享，可在线阅读，更多相关《计算机组成原理第5讲定点除法.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机组成原理Principles of Computer Organization广义双语教学课程青岛理工大学 校级精品课程1第第3章章 运算方法和运算部件运算方法和运算部件(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 produce one digit of the final quotient p

2、er 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 iteration.Newton-Raphson and Goldschmidt fall i

3、nto this category.2补码一位乘法补码一位乘法Tows complement MultiplicationBooths 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.比较法比较法（又称又称Booth法法）是实现补码一位乘法的一种方案是实现补码一位乘法的一种方案。M

4、odern 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.3补码一位乘法补码一位乘法设 X补=X0.X1X2Xn-1Xn ，Y补=Y0.Y1Y2Yn-1Yn 根据校正法 X

5、Y补=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页4P0补补 0 开始时，部分积为开始时，部分积为0，然

6、后在上一步的部分积上加然后在上一步的部分积上加 (Yi+1Yi)X补补（i=n,2,1,0），再右移一位，得到新的部），再右移一位，得到新的部分积。如此重复分积。如此重复n+1步，最后一次不移位，得到步，最后一次不移位，得到XY补补。从该递推公式可归纳出补码一位比较乘法的运算规则递推公式（递推公式（Booth公式）公式）:P1补补 P0补补+(Yn+1Yn)X补补21P2补补 P1补补+(YnYn1)X补补21Pi补补 Pi1补补+(Yni+2Yni+1)X补补21Pn补补 Pn1补补+(Y2Y1)X补补21Pn+1补补 Pn补补+(Y1Y0)X补补XY补=X补(Y1Y0)+(Y2Y1)2-1

7、+(Yn+1Yn)2-n=XY补补部分积的初值0位积+部分积然后右移1位5补码一位比较乘法的运算规则：补码一位比较乘法的运算规则：参加运算的数用补码表示，符号位一并参加运算。参加运算的数用补码表示，符号位一并参加运算。被乘数和部分积取双符号位，乘数取单符号位。被乘数和部分积取双符号位，乘数取单符号位。乘数末位增设附加位乘数末位增设附加位Yn+1，其初始值为，其初始值为0。乘数末位乘数末位Yn与附加位与附加位Yn+1构成各步运算的判断位：构成各步运算的判断位：按照上述算法进行按照上述算法进行n+1步操作，但第步操作，但第n+1步不再移位。步不再移位。右移必须按补码右移规则进行。右移必须按补码右移

8、规则进行。部分积累加时最高有效位产生的进位是有效数值，可以用第部分积累加时最高有效位产生的进位是有效数值，可以用第二符号位暂存起来，第一符号位表示正确的符号。二符号位暂存起来，第一符号位表示正确的符号。0 1 部分积加部分积加X补补后右移一位后右移一位 Y i+1-Y i=11 0 部分积加部分积加-X补补后右移一位后右移一位 Y i+1-Y i=-1Yn Y n+1 操操 作作 0 0 部分积加部分积加0后右移一位后右移一位 Y i+1-Y i=01 1 部分积加部分积加0后右移一位后右移一位 Y i+1-Y i=06【例【例3】X+0.1011B，Y0.1101B，用补码一位比较乘法计算用

9、补码一位比较乘法计算XY。解：解：X补补Y补补X补补00.10111.001111.0101 运算过程中每一个新的部分积都是在上一次部分积的基础上运算过程中每一个新的部分积都是在上一次部分积的基础上，根据根据(Yi+1Yi)来决定是加来决定是加X补补或是加或是加-X补补或加零或加零。机器不做机器不做减法减法，而是采用比较相邻两位的结果来决定上述操作的而是采用比较相邻两位的结果来决定上述操作的，故称比故称比较法较法。Tows complement MultiplicationBooths algorithm involves repeatedly adding one of two predet

10、ermined values A and S to a product P,then performing a rightward arithmetic shift on P.7部分积部分积 0 0.0 0 0 0部分积部分积/乘数乘数 附加位附加位 1.0 0 1 1 0说说 明明P0补补 0，Yn+10XY补补=11.011100011 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 Yn

11、Yn+1 00，加，加00 0 0 1 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，加，加01 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.100011118补码一位比较乘法流程图补码一位比较乘法流程图011000 或或11 i

12、=0,PP0 0 补补 =0=0PPi i 补补+-X+-X补补PPi i 补补 +0+0PPi i 补补+X+X补补PPi i 补补,Y,Y补补右移一位右移一位 i+1i开始开始YnYn+1=in+1?YN结束结束9阵列乘法器阵列乘法器高速的并行乘法运算高速的并行乘法运算The engineering implementation of binary multiplication consists of taking a very simple mathematical process and complicating it a lot,in order to do fewer additi

13、ons;a modern processor can multiply two 64-bit numbers with 16 additions(rather than 64),and can do several steps in parallel.10 3.4 二进制除法运算二进制除法运算Binary(Fixed-Point)Division Arithmetic 原码除法原码除法补码除法补码除法Tows complement DivisionUnsigned Binary Division11计算机的除法运算对除数和被除数的大小有限制。首先，除数不能为零。其次，定点除法运算可能会发生溢出

14、。对于定点小数，若被除数大于或等于除数，则商将大于或等于1，发生溢出。所以，小数除法要求小数除法要求 0|被除数被除数|除数除数|。对于定点整数，商也应是整数。要求 0|除数|被除数|。计算机在做除法之前，必须先检查除数和被除数是否为零。若除数为零，则转出错处理。若被除数为零，则直接得出商为零。若除数和被除数都不为零，则判断是否可能发生溢出。若除数是n位，则得到n位的商Quotient和n位的余数Remainder。整数除法若被除数Dividend只有n位，是不会发生溢出的。但是，若被除数为2n位，则被除数的高n位的绝对值必须小于除数Divisor的绝对值，否则，将发生溢出。小数除法，只要满足

15、小数除法，只要满足|被除数被除数|除数除数|就不会溢出。就不会溢出。12手工计算二进制除法的方法0.1011 被除数除数 0.1101商0.先判断被除数与除数的大小若被除数小，则上商0，并把被除数的下一位（若存在）移下来；或在余数最低位补0，再用余数与右移一位的除数比较，若够除则上商1，否则上商0。然后继续重复以上步骤，直至除尽（余数为0）或求得的商的位数满足要求为止。01101部分余数 01001001101Partial Remainder 0010100011010011100110111 0 1113计算机实现除法时，要把除数右移改为被除数要把除数右移改为被除数/余数左移余数左移。要求

16、计算机把求得的商直接写进商寄存器的每个对应位也是不可取的，通常是把商上到商寄存器的最低位，并把部分商左移通常是把商上到商寄存器的最低位，并把部分商左移一位一位。运算过程中，存放被除数/余数和商的寄存器一同移位。计计算完成后，商寄存器中是商的尾数，原来存放被除数的寄存器中算完成后，商寄存器中是商的尾数，原来存放被除数的寄存器中是余数是余数。做减法时，对于n位的除数，也不要求2n位的加法器，只需用n位的加法器即可。14原码除法运算原码除法运算原码除法，商的符号位是除数和被除数的符号位的异或值，原码除法，商的符号位是除数和被除数的符号位的异或值，商的值是用被除数的绝对值除以除数的绝对值得出的。商的值

17、是用被除数的绝对值除以除数的绝对值得出的。计算机不能象人那样用观察的方法决定是上商0还是上商1。1.比较法比较法 用汇编语言编写除法运算程序，可以用比较指令比较除数和被除数(余数)的大小，以决定是上商0还是上商1，这就是比较法。计算机的比较指令实质上也是做减法，但摒弃减法的结果，不改变被减数，只影响状态标志寄存器的Cy（进位/借位），S（符号），Z（零）等标志位的状态。若若Cy1，表明有借位，被除数小于除数，应当上商，表明有借位，被除数小于除数，应当上商0，不做，不做被除数被除数/余数减除数，只把被除数余数减除数，只把被除数/余数左移一位。反之，上商余数左移一位。反之，上商1，做被除数，做被除

18、数/余数减除数，并把余数左移一位。余数减除数，并把余数左移一位。比较法要多做一次比较，降低了速度。Unsigned Binary Division152.恢复余数法恢复余数法 直接从被除数/余数中减去除数，若够减够减，余数为正，上商上商1；若不够减不够减，余数为负，上商上商0。此时，必须将除数加回去，恢复成原来的余数，以便继续计算，因此称为恢复余数恢复余数法。恢复余数法在不够减时要恢复余数，多做一次加法操作，运算速度因而受到影响，控制线路复杂，运算不规则，运算时间与数据有关。在计算机中实际采用的是不恢复余数法Non-restoring division。Restoring division16

19、3.加减交替法（不恢复余数法加减交替法（不恢复余数法Non-restoring division）不恢复余数法的思想是当某一次减法的差为负时，不是把它恢复成原来的值，而是设法直接用这个负的差值求下一位商。设上次余数为设上次余数为Ri。当当Ri 0时，时，然后将余数左移一位（成为然后将余数左移一位（成为2 Ri2Y），），当当Ri 0时，时，显然显然，若不恢复余数若不恢复余数，而将余数而将余数Ri左移一位成为左移一位成为2 Ri，再加除数再加除数，结果与恢复余数法一样。但却把加结果与恢复余数法一样。但却把加Y、左移、减、左移、减Y三个步骤简化三个步骤简化成左移、加成左移、加Y两个步骤。两个步骤。

20、商上商上1，继续求下次余数；继续求下次余数；将余数左移一位得将余数左移一位得2 Ri，再减除数，再减除数，即即 2 RiYRi1。商上商上0。此时若恢复余数，此时若恢复余数，应做应做RiY，即即2 Ri2YY 再减除数，再减除数，2 RiYRi117最后一次余数若为负值，还应加上除数以得到正确的余数最后一次余数若为负值，还应加上除数以得到正确的余数。运算中总共左移运算中总共左移n次，相当于乘次，相当于乘2n，最后的余数应为，最后的余数应为Rn*2-n。余数的符号与被除数一致。余数的符号与被除数一致。由于不恢复余数法要根据余数Ri的情况分别做加法或减法，所以又称为加减交替法。Non-restor

21、ing divisionUnsigned Binary Division18无符号数不恢复余数除法算法流程图Y计数器i=0XY R商1商上0,Ri左移一位,2 RiYRi+1商上1,Ri左移一位,2 RiYRi+1i+1i商0Rn+Y开始Ri 0?YYNi=n?NRn 0?结束N除数、被除数符合规定允许进行除法运算。符号位单独运算。图中的X和Y实际是|X|和|Y|。第一位商是小数点左边的第一位商是小数点左边的0总共求出总共求出N+1位商位商19例1 X=-0.1001，Y=+0.1011，用原码不恢复余数法计算XY解：X原1.1001|X|0.1001商的符号位Y原0.1011|Y|0.101

22、1|Y|补=1.010120被除数/余数0.1 0 0 1 商0.0 0 0 0|XY|=0.1101XY原=1.1101XY=0.1101余数|R|=0.000124，R=0.00000001减Y用加|Y|的补码实现减|Y|）1.0 1 0 1余数为负，商上01.1 1 1 0左移余数为正，商上10.0 0 0 1加|Y|）0.1 0 1 1左移1.0 1 1 0余数为负，商上01.1 0 1 1减|Y|）1.0 1 0 1左移0.0 1 1 0余数为正，商上10.0 0 1 10 0 0 1 10 1 1 0 10 0 1 1 0减|Y|）1.0 1 0 1左移0.1 1 1 00 0 0

23、 10 0 1 10 1 1 00 0 0 0 1余数为正，商上10.0 1 1 1加|Y|）0.1 0 1 10 0 0 01.1 1 0 00 0 0 0 0|Y|0.1011|Y|补=1.010121 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

24、-restoring division,but it uses a lookup table based on the dividend 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 fro

25、m the more than one thousand table entries.1.跳跳0跳跳1除法除法2.除法运算通过乘法操作来实现除法运算通过乘法操作来实现22105 总线结构总线结构主机和外部设备的连接方式有辐射型连接和总线型连接等。主机MainMemoryALUControl UnitInputDevicesOutputDevicesControl SignalDataInstructionResultDataProgramAddressCPUMMBUSI/O接口I/O接口I/O设备I/O设备连接线多，不规整，设计复杂，扩展难，维修难23总线的基本概念 定义：总线（总线（BUS）

26、是由多个设备共享的传送信息的一簇公共的信是由多个设备共享的传送信息的一簇公共的信号线及相关逻辑号线及相关逻辑。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 can logically connect several peripherals over the same set of wires.现代

27、计算机的各个组成部分是通过总线（Bus）相互连接的。24总线可分为：处理机内部总线处理机内部总线，系统总线系统总线，通信总线通信总线。系统总线系统总线用于连接一个计算机系统内计算机系统内各主要功能部件主要功能部件（处理处理机机，主存主存，I/O接口接口）。通信总线通信总线用于计算机系统计算机系统之间或主机主机与I/O设备设备之间的通信。Most computers have both internal and external buses.An external bus connects external peripherals to the motherboard.An internal b

28、us 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 the computer.总线的分类25总线的分类按总线的数据传

29、输方式可分为：并行并行总线，串行串行总线。系统总线系统总线通常是并行总线并行总线。由一组地址线、一组数据线和一组控制线构成。分别称为：地址总线地址总线，数据总线数据总线，控制总线控制总线。数据线数据线用于传送数据、命令或地址传送数据、命令或地址。数据总线的宽度决定了每次能同时传输的信息的位数。地址线地址线用于传送要访问传送要访问的主存单元主存单元或I/O端口端口的地址地址。地址总线的位数决定了可寻址的地址空间可寻址的地址空间的大小。控制线控制线用于传送传送控制信号控制信号和状态信号状态信号。Buses can be parallel buses,which carry data words i

30、n parallel on multiple wires,or serial buses,which carry data in bit-serial form.2610.5.1 总线类型总线类型1单总线结构单总线结构 单总线结构的计算机系统是指一个计算机系统的所有部件都所有部件都挂在一个系统总线挂在一个系统总线上。单总线结构计算机的框图：CPUMMBUSI/O接口I/O接口I/O设备I/O设备These simple bus systems had a serious drawback when used for general-purpose computers.All the equip

31、ment on the bus has to talk at the same speed,as it shares a single clock.272双总线结构双总线结构CPUMMI/O接口I/O接口I/O设备I/O设备系统总线主存总线面向存储器的双总线结构CPUMMI/O接口I/O接口I/O设备I/O设备系统总线I/O总线IOP面向输入输出的双总线结构283多总线结构多总线结构高速总线处理器处理器SCSI扩展总线接口系统总线扩展总线Cache/桥主存储器P1394视频网络ModemFax串口单处理器的多总线结构An increasing number of external device

32、s 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.29扩展总线处理器CacheSCSI扩展总线桥系统总线PCI总线主存控制器处理器CacheDRAM主机桥主机桥PCI总线SCSI网络扩展总线桥PCIPCI桥PCI总线扩展总线多处理机的多总线结构30The digital

33、 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.Homework3-18，19，30，31