📄 4-5.htm
字号:
<p align=center style='text-align:center;mso-line-height-alt:9.0pt'><span
lang=EN-US style='font-size:13.5pt'>0</span></p>
</td>
<td width=143 style='width:107.25pt;padding:0cm 0cm 0cm 0cm;height:15.75pt'>
<p class=MsoNormal align=center style='text-align:center'><span lang=EN-US>1+1+0=10<sub>two</sub></span></p>
</td>
</tr>
<tr style='height:15.75pt'>
<td width=86 style='width:64.5pt;padding:0cm 0cm 0cm 0cm;height:15.75pt'>
<p class=MsoNormal align=center style='text-align:center;mso-line-height-alt:
5.25pt'><span lang=EN-US style='font-size:13.5pt'>1</span></p>
</td>
<td width=83 style='width:62.25pt;padding:0cm 0cm 0cm 0cm;height:15.75pt'>
<p align=center style='text-align:center;mso-line-height-alt:5.25pt'><span
lang=EN-US style='font-size:13.5pt'>1</span></p>
</td>
<td width=89 style='width:66.75pt;padding:0cm 0cm 0cm 0cm;height:15.75pt'>
<p align=center style='text-align:center;mso-line-height-alt:5.25pt'><span
lang=EN-US style='font-size:13.5pt'>1</span></p>
</td>
<td width=94 style='width:70.5pt;padding:0cm 0cm 0cm 0cm;height:15.75pt'>
<p align=center style='text-align:center;mso-line-height-alt:5.25pt'><span
lang=EN-US style='font-size:13.5pt'>1</span></p>
</td>
<td width=95 style='width:71.25pt;padding:0cm 0cm 0cm 0cm;height:15.75pt'>
<p align=center style='text-align:center;mso-line-height-alt:5.25pt'><span
lang=EN-US style='font-size:13.5pt'>1</span></p>
</td>
<td width=143 style='width:107.25pt;padding:0cm 0cm 0cm 0cm;height:15.75pt'>
<p class=MsoNormal><span lang=EN-US>1+1+1=11<sub>two</sub></span></p>
</td>
</tr>
</table>
</div>
<p><span lang=EN-US style='font-size:13.5pt'> 我们将真值表转化成一个代数式：<br>
<img border=0 width=450 height=73 id="_x0000_i1040" src="images\4-5-pic4.gif"></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 我们根据代数式用3个AND
gates 和1个OR gate 画出Adder hardware for the carry out signal：</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> <img border=0
width=264 height=155 id="_x0000_i1041" src="images\4-5-pic5.gif"><br>
同理我们也可以画出Adder hardware for the Sum signal,这让读者自己来做。<br>
接下来我们将几个硬件部分组合起来构建一位加法器，这个ALU可以有AND ,OR,和addition三种操作，<br>
其设计如下图：<br>
<img border=0 width=231 height=155 id="_x0000_i1042" src="images\4-5-pic6.gif"></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 上图的执行AND,OR,addition的一位ALU中，指令操作译码后决定operation为0，1，2。00对应AND，01对应OR，10对应a+b,a+(-b)。有时候设计者想让ALU有一些简单的其他功能，例如生成0，最简单的方式在选择器上加一个控制线，然后直接将0接到新的控制线上。</span></p>
<p><span style='font-size:13.5pt'>四：<a name=32位串行进位的ALU><span lang=EN-US>32位串行进位的ALU</span></a></span><span
style='mso-bookmark:32位串行进位的ALU'></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 我们已经完成了1-bit
ALU，32-bit ALU就是将1-bit ALU 邻接起来。我们用x<sub>i</sub>表示第i个x,就象一块石头扔在水面可以产生一系列波纹一样，a
single carry out of the least significant bit (Result0)能够一直传递下去，直到完成整个加法器的运算产生a
carry out of the most significant bit(Result31)。因此这种加法器叫做串行进位加法器。如下图：</span></p>
<p><span lang=EN-US style='font-size:13.5pt'>
<img border=0 width=638 height=109 id="_x0000_i1043"
src="images\4-5-pic7.gif"></span></p>
<p><span style='font-size:13.5pt'>五：<a name=求补的实现>求补的实现</a></span><span
style='mso-bookmark:求补的实现'></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 我们接下来要实现减法，只需将减数取补，然后同被减数相加即得结果。求补时必须首先给操作数取反，我们添加a
2:1 multiplexor 来在a和ã中选择。然后我们要给操作数加1，只需要将the least significant bit的CarryIn
signal 置为1就可以了。如：b+ã+1=b+(ã+1)=b+(-a)=b-a.</span></p>
<p><span style='font-size:13.5pt'>具体实现如下图：</span></p>
<p><span lang=EN-US style='font-size:13.5pt'>
<img border=0 width=343
height=155 id="_x0000_i1044" src="images\4-5-pic8.gif"> 当Binvert=1,b-a;当Binvert=0,b+a;</span></p>
<p><span style='font-size:13.5pt'>六：<a name=数字大小比较的实现>数字大小比较的实现</a></span><span
style='mso-bookmark:数字大小比较的实现'></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 在任何计算机的ALU中，都有add,subtract,AND,OR操作，但是这种ALU的设计是不完全的。我们在MIPS
instructions set中，我们还需要the set-on-less-than instruction。如果Rs<Rt,则结果置1；反之则置0。相应的，set
on less 将除the least significant bit都置为0，然后根据比较结果对the least significant bit置数。</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 因此我们需要为每个ALU增加一个选择线来传递比较的结果，如下图：</span></p>
<p><span lang=EN-US style='font-size:13.5pt'>
<img border=0 width=343 height=193 id="_x0000_i1045" src="images\4-5-pic9.gif"></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 接下来我们需要考虑如何进行比较并且进行the
least significant bit置数。</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 当我们用Rs减去Rt,如果结果是负值，则Rs<Rt,有(Rs-Rt)<0
==>((Rs-Rt)+Rt)<(0+Rt) ==>(0+Rs)<(0+Rt) ==>Rs<Rt。</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 因此 如果两数之差是负值，则the
least significant bit of set on less than 置1，反之置0。也就是1表示负数，0表示正数，我们只需要把最高位的adder
output连接到the least significant bit。但是第31位ALU的Result output并不是the output of the
adder，</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> the ALU output
for the less operation是输入值比较的结果， 因此我们需要为the most significant设计一个新的ALU，这个新的ALU除了有标准功能，还能使加法器的输出值有效。设计如下图
，同时我们增加了the overflow detection logic。</span></p>
<p><span lang=EN-US style='font-size:13.5pt'>
<img border=0 width=343 height=261 id="_x0000_i1046" src="images\4-5-pic10.gif"></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 注意到在每次ALU进行减法时，我们都将CarryIn
和Binvert置1，对于加法和逻辑运算则将两个信号线都置0.</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 由以上两种ALU可以设计出A
32-bit ALU,如下图：</span></p>
<p><span lang=EN-US style='font-size:13.5pt'>
<img border=0 width=725 height=154 id="_x0000_i1047" src="images\4-5-pic11.gif"></span></p>
<p><span style='font-size:13.5pt'>七：<a name=两数结果相等判断的实现>两数结果相等判断的实现</a></span><span
style='mso-bookmark:两数结果相等判断的实现'></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 接下来我们还得支持conditional
branch instructions，我们要求判断两个寄存器中的数字是否相等。最简单的方法就是将两数相减，看结果是否为0，即(a-b=0)==>a=b。因此我们需要加一个硬件来测试结果是否为0，只要将所有的outputs进行或（OR）操作，然后取反即得结果，如下：</span></p>
<p><span lang=EN-US style='font-size:13.5pt'><img border=0 width=725
height=232 id="_x0000_i1048" src="images\4-5-pic12.gif"></span></p>
<p><span style='font-size:13.5pt'>八：<a name=能完成5条指令操作的ALU>能完成<span lang=EN-US>5条指令操作的ALU</span></a></span><span
style='mso-bookmark:能完成5条指令操作的ALU'></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 现在我们已经搞懂了a
32-bit ALU 的内部结构,<br>
我们用如右图的符号表示一个完成的ALU:
<img border=0 width=169 height=128 id="_x0000_i1049" src="images\4-5-pic13.gif"></span></p>
<p><span lang=EN-US style='font-size:13.5pt'>The values of the three ALU
Control lines Bnegate and Operation and the corresponding ALU operations:</span><span
lang=EN-US><o:p></o:p></span></p>
<div align=center>
<table border=1 cellspacing=0 cellpadding=0 width="40%" style='width:40.0%;
mso-cellspacing:0cm;mso-padding-alt:0cm 0cm 0cm 0cm' bordercolordark="#CC9966"
bordercolorlight="#FFCC66">
<tr>
<td width="50%" style='width:50.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>ALU Control lines</span></p>
</td>
<td width="50%" style='width:50.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>Function</span></p>
</td>
</tr>
<tr>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>000</span></p>
</td>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>And</span></p>
</td>
</tr>
<tr>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>001</span></p>
</td>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>Or</span></p>
</td>
</tr>
<tr>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>010</span></p>
</td>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>Add</span></p>
</td>
</tr>
<tr>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>110</span></p>
</td>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>Subtract</span></p>
</td>
</tr>
<tr>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>111</span></p>
</td>
<td width="50%" style='width:50.0%;padding:0cm 0cm 0cm 0cm'>
<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'>Set-on-less-than</span></p>
</td>
</tr>
</table>
</div>
<p><span style='font-size:13.5pt'>九：<a name="先行进位Carry_lookahea">先行进位<span
lang=EN-US>Carry lookahea</span></a><span lang=EN-US>d</span></span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 接下来的问题是这个ALU进行加法的速度有多快呢？我们能够决定a和b的输入值，但是CarryIn
input依赖于相邻的1-bit adder。这就象一条链条一样一环扣一环，则和的最高位要等32 1-bit adders的一系列运算结果，其平均需要等待：</span></p>
<p><span lang=EN-US style='font-size:13.5pt'>
（32+0）/2=16 （注：设1-bit为1）</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 这在对时间要求很严格的情况下无疑是太慢了。结果是我们用先行进位来实现多位加法，即<b>进位先于和的产生</b>。</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 在两位加法器中，CarryIn
for bit2 of the adder 是CarryOut of bit1 of the adder,<br>
因此有公式CarryIn2=(b1*CarryIn1)+(a1*CarryIn1)+(a1*b1),同样，我们可以定义CarryIn1:<br>
<span
style="mso-spacerun: yes"> </span>CarryIn1=(b0*CarryIn0)+(a0*CarryIn0)+(a0*b0)<br>
这样可以得到c2=(a1*a0*b0)+(a1*a0*c0)+(a1*b0*c0)+(b1*a0*b0)+(b1*a0*c0)+(b1*b0*c0)+(a1*b1),<br>
这样一直可以推到最高位，但是同时在硬件上更加复杂了，花费也更高。</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 令gi=ai*bi(称本地进位);pi=ai+bi(称传送进位)。我们可以得到四位一组的组内并行递推公式：<br>
c1=g0+(p0*c0)<br>
c2=g1+(p1*g0)+(p1*p0*c0)<br>
c3=g2+(p2*g1)+(p2*p1*g0)+(p2*p1*p0*c0)<br>
c4=g3+(p3*g2)+(p3*p2*p1)+(p3*p2*p1*g0)+(p3*p2*p1*p0*c0)</span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 为了使高位运行更快，同时在硬件上更简单一些，我们可以进行组间并行进位。我们将组内的4-bits抽象的看成1bit，如下；<br>
P0=p3*p2*p1*p0<br>
P1=p7*p6*p5*p4<br>
P2=p11*p10*p9*p8<br>
P3=p15*p14*p13*p12</span></p>
<p><span lang=EN-US style='font-size:13.5pt'><br>
G0=g3+(p3*g2)+(p3*p2*g1)+(p3*p2*p1*g0)<br>
G1=g7+(p7*g6)+(p7*g6*g5)+(p7*p6*p5*g4)<br>
G2=g11+(p11*g10)+(p11*p10*g9)+(p11*p10*p9*g8)<br>
G3=g15+(p15*g14)+(p15*p14*g13)+(p15*p14*p13*g12)</span></p>
<p><span lang=EN-US style='font-size:13.5pt'>
然后我们可以得到最后的进位：<br>
C1=G0+(P0*c0)<br>
C2=G1+(P1*G0)+(P1*P0*c0)<br>
C3=G2+(P2*G1)+(P2*P1*G0)+(P2*P1*P0*c0)<br>
C4=G3+(P3*G2)+(P3*P2*G1(+(P3*P2*P1*G0)+(P3*P2*P1*P0*c0)<br>
<br>
十：<a name=本节小结>本节小结</a> </span></p>
<p><span lang=EN-US style='font-size:13.5pt'> 1：我们介绍了ALU的构成：通过一个多路选择器和一些门组合起来并复制32遍<br>
2：扩展功能：判断零电路，小于设置，检查溢出<br>
3：求和也可以用异或门:将a,b,Cin进行异或操作<br>
4：先行进位能分组实现并行进位，加快了运算速度<br>
本地进位gi=ai*bi<br>
传送进位pi=ai+bi<br>
可由此推导出递推公式：<br>
c1=g0+(p0*c0)<br>
c2=g1+(p1*g0)+(p1*p0*c0)<br>
c3=g2+(p2*g1)+(p2*p1*g0)+(p2*p1*p0*c0)<br>
c4=g3+(p3*g2)+(p3*p2*p1)+(p3*p2*p1*g0)+(p3*p2*p1*p0*c0)</span></p>
<p><span lang=EN-US style='font-size:13.5pt'><br>
</span></p>
<p> </p>
</div>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -