CPU设计案例3

我们回过来看上两章的CPU，最主要的操作就是把一个数据从一个组件复制到另外一个组件。这些操作主要是对寄存器之间、寄存器与存储器之间进行的。例如：取指周期只有PC<—PC+1修改了数值，其他的微操作都是数据的转移。 然而，CPU如果只是进行数据移动则它也就没有了什么功能可言。所以一个CPU必须能够修改数据来达到所需的功能。所以用来执行算数操作的指令和微操作也是CPU极其重要的一部分。 本章我们将讲述算数操作算法和它们几种通用数格式的硬件实现。我们首先来看定点无符号数操作。接下来我们研究无符号的浮点数和有符号的浮点数以及其加减乘除的实现方法。 然后我们讲解了一些用来加快算数操作的特殊的硬件。例如：流水线、查找表和惩罚操作中的Wallace树等。 最后，本章讲解了浮点无符号数和它们的算数操作，从浮点数的特性、它们的加减乘除的实现还介绍了浮点数表示的定义IEEE754。 1 无符号数 本节说明无符号数的加减乘除等操作，给出其硬件实现。这些算法实现也可以作为由符号数、BCD码数和浮点数算法的基础。注意：无符号数只是说明它没有一个明确的位来表示符号，但是它也是可以表示正数或者负数的。 有两种常用的无符号数。第一种就是没有负数的无符号数，它把数字分为0和正数。一个n位的数可以是0到 中的任何一个。另一种把数字看作二进制的补码形式。这种方法可以表示正数或者负数。一个n位的这种数可以表示的范围是： 。负数以1开头，正数以0开头。正数的表示和前一种方法相同，负数的表示是前一种方法表示的正数按位取反末尾加1得到的。下表表示了8位的非负的无符号数表示和2进制补码的无符号数表示： Binary Representation Unsigned Non-Negative Unsigned Two’s Complent 00000000 0 0 00000001 1 1 … … … 01111111 127 127 10000000 128 -128 10000001 129 -127 … … … 11111111 255 -1 1.1加法和减法 对于非负的无符号数表示和2进制补码表示的数来说，加法和减法都是很直接的。加法就是一个二进制的加法如下图所示：执行操作ADD：X<—X+Y，只要结果在相应的数的表示范围之内它就能正常地工作。（X，Y均为8bit） 但是当结果超出了所能表示的表示范围的时候，就会出现溢出。例如255+1就需要9bit表示100000000。对于非负数表示的无符号数加法来说溢出就是Cout溢出标志位。 对于2进制补码表示的无符号数，溢出可能发生在这样几个地方： · 127+1，产生结果01111111+00000001=10000000，但是10000000表示的是-128不是应得的结果128。 · 同样-128+-1，10000000+11111111产生结果01111111，表示的是127而不是应得的结果-129。 这种2进制补码表示的无符号数其判断是否溢出的标准不仅仅是进位信号Cout，而是Cout和最高位的进位两位进行判断，如果Cout和最高位的进位信号相等那么就没有溢出，否则就是溢出。 对于减法来说，它能够转换成加法来执行。X-Y就是先把Y取2进制的补码变成-Y，然后作X+（-Y）的操作。如下图所示：图中Y取反，加一是用加法器的进位来实现的。 对于非负数表示的无符号数来说，这个结果永远不可能超出 ，但是结果可能是负数，例如1-2将会被这样计算：2（0000010）取反码11111101然后末尾加一得11111110，所以计算00000001-11111110=11111111其结果为255不是正确结果。对于这些数来说可能发生溢出，产生溢出时进位信号Cout应该是0，如果Cout=1则没有溢出。 对于2进制补码表示的无符号数减法和加法的溢出判断条件相同：Cout和最高位进位相同则没有溢出，否则就有溢出。 1.2乘法 乘法可以看成是很多的加法操作。乘以一个数字n也就是加上n-1个被乘数。这就给出了一种乘法器的设计思路： Z=0; FOR i=0 TO y DO {z=z+x} 这种做法由于其要做y次的加法，所以太慢一般不用。 考虑手工计算成法的方法： X= 27 Y= 253 ----------- 81 135 54 ------------------ 6831 首先做27*3=81然后做27*5=135，这个结果要左移1位与上一个权值的计算结果对位。然后作27*2=54，这个结果还要再左移对位。 由上面可以看出：乘法就可以转化成一系列的移位加法和乘法来做。每个部分积被左移然后相加。很明显，它比对27做253次的加法是要快的多。我们对它做一点硬件上的修改就得到了非负数表示的无符号数乘法操作。 首先我们作的修改是，把每个部分积一产生就进行求和，而不是流到最后一起求和。因为2输入的加法器是比较容易设计的，而3输入或者更多输入的加法器就相对复杂了。所以上面的计算过程就成了： X= 27 Y= 253 ----------- 81 135 ----------------- 1431 -----部分和 54 -----部分积 ------------------ 6831 然后我们来看这个计算过程，我们注意到每个部分积需要左移的位数不同，这样硬件实现时就需要很大的代价。如果我们能够让每个部分积移位次数相同，那就将很大程度的节省硬件资源。同时我们注意到很多的部分积最右边的位是空余的，并不需要的。所以我们可以来移动部分和而不是部分积达到同样的目的。而部分和的移动每次只需要固定向右移动1bit，这样就很大程度的减少了硬件设计的代价。计算公式如下： X= 27 Y= 253 ----------- 81 81 ----右移1bit 135 ----------------- 1431 1431 54 ------------------ 6831 6831 -----最后结果 用二进制而不是十进制来进行部分积乘法的计算，这是因为在十进制中每个部分积有10种可能的值，而在二进制中只有两种可能要不是被乘数X要不就是0。这样可以简化实现。 下面的算法实现两个n为的寄存器X、Y的移位加乘，并把结果存到两个n位的寄存器U和V中。U包含了结果的高nbit，V包含了结果的低nbit。C是一个1bit的寄存器用于保存加法的进位： U=0； FOR i=1 TO n DO {IF Y0=1 THEN CU=U+X； Liner shift right CUV Circular shift right Y} 现在我们考虑两个数13*11 也就是1101*1011的计算如下表： Function i C U V Y Comments U=0 0000 0000 1011 If(Y0=1) 1 0 1101 Y0=1,add Shr(CUV) 0 0110 1000 Cir(Y) 1101 If(Y0=1) 2 1 0011 Y0=1,add Shr(CUV) 0 1001 1100 Cir(Y) 1110 If(Y0=1) 3 Y0=0 Shr(CUV) 0 0100 1110 Cir(Y) 0111 If(Y0=1) 4 1 0001 Y0=1,add Shr(CUV) 0 1000 1111 Cir(Y) 1011 Original Value DONE 1000 1111 Result=143 接下来的任务就是用RTL代码来实现这个算法。X，Y，U，V都是nbit的值C是1bit的值。还需要开始位START，结束位FINISH计数状态i要能包含n个的状态。设计中可以使i从n减到0以便简化设计。下面给出实现的RTL代码：当i=0时z=1（z是0标志寄存器）； 1：U<—0，i<—n Y02：CU<—U+X 2：i<—i-1 3：shr（CUV），cir（Y） ！Z3：GOTO 2 Z3：FINISH<—1 下面表格表示了13*11的相应的RTL代码 Function Micro-Operation i C U V Y Z FINISH START x x xxxx xxxx 1011 0 1 U<—0，i<—4 4 0000 0 Y02，2 CU<—U+X， i<—i-1 3 0 1101 0 3，！Z3 Shr（CUV），cir（Y） GOTO 2 0 0110 1xxx 1101 Y02，2 CU<—U+X i<—i-1 2 1 0011 0 3，！Z3 Shr（CUV），cir（Y） GOTO 2 ０ 1001 11xx 1110 2 i<—i-1 1 0 3,!Z3 Shr(CUV),cir(Y) GOTO 2 0 0100 111x 0111 Y02,2 CU<—U+X 0 1 0001 1 3,Z3 Shr(CUV),cir(Y), FINISH<—1 0 1000 1111 1011 1 最后，根据RTL代码得出相应的硬件设计。这个设计与CPU的设计相似：一个部分是寄存器部分用来执行为操作，另外还有一个部分是控制单元用来生成所需要的控制信号。为了简化设计，我们用nbit的寄存器实现X用nbit的移位寄存器实现Y，U，V。i是一个模n的计数器，C和FINISH是两个1bit的寄存器。Z用来当i所有的位都为0时输出1。框图如下： 现在我们来看上图中的控制单元，分析RTL代码是如何实现的。当START有效时，Counter被清零，FINISH寄存器也被清零，从而触发译码器工作。现在译码器输出应该是1，所以U被清零，i被置数n。然后状态计数器Counter加一INC到01态，译码器输出2使i=i-1； 同时判断Y0，如果Y0=1，那么CU<—U+X，如果Y0=0，那就不改变C和U的值。然后Counter再加一，译码器输出3使得CU和V右移1位。由于C中移入一个0，所以可以用CLR信号实现。同时判断Z，如果Z=0，也就是i！=0，那么算法还没有结束。Counter载入01译码输出2（也就是实现了GOTO 2）；如果Z=1，也就是！=0算法结束，FINISH载入1使译码器不工作，也就没有控制信号输出，所以整个硬件实现停止操作。 如果着两个操作书都不需要保存的话，这个算法可以被优化以减少硬件需求。如果牺牲Y操作数，直接把他存到V中，那么部分积就变成了UV<—X*V。检查V的最低位，如果为1则进行加法。在进行移位时，这个最低位就会被丢掉。修改后的RTL代码如下： 1：U<—0,i<—n V02: CU<—U+X 2:i<—i-1 3:shr(CUV) !Z3:GOTO 2 Z3:FINISH<—1 这两个算法的不同在于：首先，CU<—U+X的控制条件现在是V02而不是Y02。第二，这个算法去掉了cir（Y）的操作。硬件实现和上一个图相似，所不同之处只是C和U的LD信号变成了V0和2的与。下表表示了用这个算法进行13*11的计算： Function Micro-Operation i C U V Z FINISH START x x xxxx xxxx 0 1 U<—0，i<—4 4 0000 0 V02，2 CU<—U+X， i<—i-1 3 0 1101 0 3，！Z3 Shr（CUV）， GOTO 2 0 0110 1xxx V02，2 CU<—U+X i<—i-1 2 1 0011 0 3，！Z3 Shr（CUV）， GOTO 2 ０ 1001 11xx 2 i<—i-1 1 0 3,!Z3 Shr(CUV), GOTO 2 0 0100 111x V02,2 CU<—U+X 0 1 0001 1 3,Z3 Shr(CUV), FINISH<—1 0 1000 1111 1 1.2.1BOOTH算法 以上算法对于二进制补码表示的无符号数来说并不时总能正常工作的。特别的如果当一个操作数是负数的时候它就不能正常地工作了。还看上面的例子，二进制补码的1101和1011分别表示-3和-5那么他们的乘积应该是15，然而结果实10001111也就是-113，出现错误。但是我们可以通过以下修改这个算法来使其正常工作： IF multiplicand < 0 THEN multiplicand<—-multiplicand; IF multiplier < 0 THEN multiplier<—-multiplier; Multiply using non-negative multiplication; Restore multiplicand and multiplier to original values; IF exactly one of multiplier and multiplicand is negative, AND the other is not zero, THEN result<—-result 另外一种不是这么讨厌的方法就是用Booth算法。这个算法直接对两个二进制补码表示的数进行乘法操作。像前面一种算法一样，它需要检查乘数的每一位，移位结果。但是它并不对每个乘数中的1执行加法操作，而是它只对一个1串开始的那个1执行一次减法操作，对一个1串末尾的那个1执行一次加法操作。这个算法的合理性是它把1个1串当作两个制来处理，例如对1011*0111来说，它执行的和1011*（1000-0001）结果应该相同。 这个算法完成UV<—X*Y的过程可以如下表示，其中Y-1是一个1bit的值，我们后面就会解释： U=0；Y-1=0； FOR i=1 TO n DO {IF start of a string of 1’s in Y THEＮ　Ｕ＝Ｕ－Ｘ（＝Ｕ＋！Ｘ＋１）; IF end of a string of 1’s in Y THEN U=U+X; Arightmetic shift right UV; Circular shift right Y AND copy Y0 to Y-1;} 这个算法的关键在于检测1串。如果Y的最低位是Y0和最后被移出的位Y-1是10，那么说明这个1是一串1的开始；如果是01，那么说明这个0时1串1的结束；如果是11，那说明是1串的中间，不需要做任何操作；如果是00说明在一串0的中间，也不需要作任何操作。为了进行这样的检查我们设立了寄存器Y-1并初始化为0以便能够检测出第一个Y0=1的情况。 下表列出了用这个算法执行X=-3(1101)和Y=-5（1011）的乘法操作。结果是00001111（15）。 Function i U V Y Y-1 Comments U=0,Y-1=0 0000 0000 1011 0 If start of string 1 0011 Start of string If end of string Ashr(UV) 0001 1000 Cir(Y),Y-1<—Y0 1101 1 If start of string 2 Still within string If end of string Ashr(UV) 0000 1100 Cir(Y),Y-1<—Y0 1110 1 If start of string 3 If end of string 1101 End of string Ashr(UV) 1110 1110 Cir(Y),Y-1<—Y0 0111 0 If start of string 4 0001 Start of string If end of string Ashr(UV) 0000 1111 Cir(Y),Y-1<—Y0 1011 1 Original value DONE 0000 1111 Result=15 注意：上表中最后一次运算，i=4。算法执行一串1开始的减法操作，因为最高位是1，所以它永远是减法，相当于一串1的开始。 这个算法可以转换到相应的RTL描述，以及相应的硬件实现。像前面所述的移位累加算法一样加上start信号和1bit的FINISH寄存器，我们可以实现booth算法的RTL代码如下： 1：U<—0，Y-1<—0，i<—n Y0（！Y-1） 2：U<—U+！X=1 （！Y0）Y-1 2：U<—U+X 2：i<—i+1 3:ashr(UV),cir(Y),Y-1=Y0 !Z3:GOTO 2 Z3:FINISH<—1 把加法和减法操作变成一个为操作会使这个算法更加的有效： 也就是上面两句变为： （Y0 xor Y-1）2：U<—U+（X xor Y0）+Y0 这里X xor Y0是说X的所有的位都要和Y0位进行异或操作，例如Y0=1，Y-1=0，那么U<—U+(X xor 1) +1,X每位和1异或也就是X按位取反，然后末尾加一，也就是作了操作U<—U+！X+1。同理，当Y0=0，Y1=1时，U<—U+（X xor 0）+0，因为X xor 0=X，所以也就是作了U<—U+X操作。 对应这段RTL代码的硬件实现如下图：和移位累加方法设计相似，它也是包括一个寄存器部分和一个控制逻辑部分。 下表列出了用这个算法进行-3*-5的计算的RTL代码 Conditions Micro_operatins i U V Y Y-1 Z FINISH START x xxxx xxxx 1011 X 0 1 U<—0，Y-1<—0, i<—4 4 0000 0 0 Y0(!Y-1)2,2 U<—U+!X+1, i<—i-1 3 0011 0 3,!Z3 Ashr(UV),cir(Y), Y-1<—Y0,GOTO 2 0001 1xxx 1101 1 2 i<—i-1 2 0 3!Z3 Ashr(UV),cir(Y), Y-1<—Y0,GOTO 2 0000 11xx 1110 1 (!Y0)Y-12,2 U<—U+X, i<—i-1 1 1101 0 3,!Z3 Ashr(UV),cir(Y), Y-1<—Y0,GOTO 2 1110 111x 0111 0 Y0(!Y-1)2,2 U<—U+!X+1 i<—i-1 0 0001 1 3,Z3 Ashr(UV),cir(Y), Y-1<—Y0, FINISH<—1 0000 1111 1011 1 同上面移位累加设计相似，我们也可以通过去掉寄存器Y来优化设计。优化后的RTL代码和硬件实现原理图留给读者自己练习。 1.3除法操作 同乘法能看作一系列的加法操作一样，除法也可以看作一系列的减法操作。例如：Z=x/y的计算可以由下面的算法来实现： Z=0； WHILE x〉=y DO { Z=Z+1,x=x-y} 同样这种算法的实现通常需要很长的时间。 像我们用部分积累加来实现乘法操作一样，我们也可以用移位减法来完成除法操作。我们考虑如下计算： 虽然没有明确的表示，但是第一个操作应该是比较被除数的最高两位（68）和除数（71），由于除数71比被除数的最高两位68大，所以在商的地方产生一个0的结果，这一部分也可以在计算机进行除法运算式用来做溢出判断。接下来被除数左移近一位变成682然后进行检查，它大于除数71，得到商9，并且有余数43。最后被除数的最低位被移入，进行检查437大于71，商6，余数是11。 这种算法与移位加法实现乘法的原理相同，所以也需要一个移位器。在这里是被除数进行左移，而不是乘法算法中的右移。随着除法的进行，最高位是不需要的可以直接移出。用这种算法实现除法的过程如下： 第一步，检查除数71和被除数的最高两位68，是一个溢出检测步骤，所以除法器不作任何操作。在典型的除法器硬件实现方法中，被除数是用一个2nbit的寄存器来实现的，而除数和商是用一个nbit的寄存器实现的，而余数是留在被除数寄存器中的。但是当被除数的前nbit大于或者等于除数，那么商就不可能用一个nbit的寄存器进行存储了。例如7827/71，那么商将是个3个数字位表示的数，不可能用象存储除数那样的2个数字位的寄存器表示。另外一种溢出的检测就是被除数为零的监测。 用二进制编码数据也可以简化这个算法的实现。除数只能去除被除数的0倍或者1倍，不再是一个0~9的倍数。如果如果被除数大于或者等于除数那么相应的商的位置就赋1，否则商的位置就赋0。 下面的算法实现了移位减法的二进制除法运算。初始化时被除数被存到UV中，U和V都是nbit的寄存器。除数被存到一个nbit的寄存器X中上被存到一个nbit的寄存器Y中。计算结果的余数存放在U中。C是一个1bit的寄存器用来存储U左移移出的最高位。 IF U>=X THEN exit with overflow; Y=0;C=0; FOR i=1 TO n DO {linear shift left CUV; Linear shift left Y; IF CU>=X THEN {Y0=1,U=CU-X} } 在我们看整个算法的操作之前，我们首先来考虑电路在那个状态下第一步算法会结束。对于例子112/7来说假设n=4bit，UV=01110000，X=0111由于U>=X，所以溢出，算法终止。反过来说，假设能够执行，那么正确的结果应该是16（10000），是不能够用一个4bit的寄存器来进行存储的。下表表示了算法执行147/13的执行过程，初始化U=1001，V=0011，X=1101，n=4。 Function i C U V Y Comments Initial 0 1001 0011 0000 If U>=X U=X 0101 0001 10010>=1101 Shl(CUV) 2 0 1010 1100 Shl(Y) 0010 If CU>=X CU=X 1000 0101 10101>=1101 Shl(CUV) 4 1 0111 0000 Shl(Y) 1010 If CU>=X 0100 1011 10001>=1101 下面给出这个算法的RTL代码，X，U，V, Y是nbit的寄存器，C，OVERFLOW,FINISH,G是1bit的寄存器，对这个算法来说如果U〉=X，则设G=1。1，2，3，4，是状态的顺序。 G1: FINISH<—1,OVERFLOW<—1 2: Y<—0,C<—0,OVERFLOW<—0,i<—n 3:shl(CUV),shl(Y),i<—i-1 (C+G)4:Y0<—1,U<—U=!X+1 !Z4: GOTO 3 Z4:FINISH<—1 上面算法中的绝大部分都可以直接实现，而(C+G)4:Y0<—1,U<—U=!X+1这条语句需要额外的解释如下：算法执行操作CU>=X，也就是用X去除CU时，如果U>=X,G=1,如果此时C=0，那么CU=U>=X。如果C=1，此时不管G是什么CU都一定大于X，所以语句的执行条件为C+G。 同样是上条语句中U<—U+！X+1并没有将最高位可能向外的进位信号送到C中，这是因为在下一个周期的3状态要进行左移，最高为向外的进位是无用的将被移出。 下表给出了用上面的RTL代码进行147/13的运算过程： Conditions Micro-operations i C U V Y Z FINISH START x x 1001 0011 xxxx 0 1 NONE 2 Y<—0,C<—0, OVERFLOW<—0, i<—4 4 0 0000 3 Shl(CUV),shl(Y), i<—i-1 3 1 0010 0110 0000 0 (C+G)4,!Z4 Y0<—1, U<—U+!X+1, GOTO 3 0101 0001 3 Shl(CUV),shl(Y) i<—i-1 2 0 1010 1100 0010 0 !Z4 GOTO 3 3 Shl(CUV),shl(Y) i<—i-1 1 1 0101 1000 0100 0 (C+G)4,!Z4 Y0<—1, U<—U+!X+1, GOTO 3 1000 0101 3 Shl(CUV),shl(Y) i<—i-1 0 1 0001 0000 1010 1 (C+G)4,Z4 Y0<—1, U<—U+!X+1, FINISH<—1 0100 1011 1 这个算法的硬件实现如下图：（实在是有点懒得画了，图的大体样子和乘法器的相似，至少各个模块都是一样的，有兴趣的朋友自己画一下吧）。 _1175426617.unknown _1175498227.unknown _1175498797.unknown _1175426492.unknown