ch02.14.htm
来自「介绍asci设计的一本书」· HTM 代码 · 共 409 行 · 第 1/3 页
HTM
409 行
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=165352"></A> CSKIP[<SPAN CLASS="EquationVariables">
i</SPAN> ]<SPAN CLASS="White"> </SPAN>= (G[<SPAN CLASS="EquationVariables">
i</SPAN> ]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[<SPAN CLASS="EquationVariables">
i</SPAN> ]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>C[<SPAN CLASS="EquationVariables">
i</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1])<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>SKIP'<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>C[<SPAN CLASS="EquationVariables">
i</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>SKIP.(2.55)</P>
<P><P CLASS="BodyAfterHead"><A NAME="pgfId=165350"></A>This is a <B>carry-skip
adder</B> [Keutzer, Malik, and Saldanha, 1991; Lehman, 1961]. Carry-bypass
and carry-skip adders may include redundant logic (since the carry is computed
in two different wayswe just take the first signal to arrive). We must be
careful that the redundant logic is not optimized away during logic synthesis.</P>
<P><P CLASS="Body"><A NAME="pgfId=165312"></A>If we evaluate Eq. 2.44
recursively for <SPAN CLASS="EquationVariables"> i</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="EquationVariables">
<SPAN CLASS="White"> </SPAN></SPAN> =<SPAN CLASS="White"> </SPAN>1,
we get the following:</P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=85752"></A> C[1]=<SPAN CLASS="White"> </SPAN>G[1]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[1]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>C[0]<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>G[1]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[1]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>(G[0]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[1]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>C[1])</P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=86900"></A><SPAN CLASS="White"> </SPAN> =<SPAN CLASS="White"> </SPAN>G[1]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[1]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>G[0].(2.56)</P>
<P><P CLASS="Body"><A NAME="pgfId=85691"></A>This result means that we can
"look ahead" by two stages and calculate the carry into the third
stage (bit 2), which is C[1], using only the first-stage inputs (to calculate
G[0]) and the second-stage inputs. This is a <B>carry-lookahead adder</B>
(<B> CLA</B> ) [MacSorley, 1961]. If we continue expanding Eq. 2.44,
we find:</P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=176856"></A> C[2]=<SPAN CLASS="White"> </SPAN>G[2]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[2]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>G[1]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[2]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>P[1]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>G[0],</P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=170860"></A> C[3]=<SPAN CLASS="White"> </SPAN>G[3]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[2]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>G[2]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[2]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>P[1]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>G[1]<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>P[3]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>P[2]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>P[1]<SPAN CLASS="White"> </SPAN>·<SPAN CLASS="White"> </SPAN>G[0].(2.57)</P>
<P><P CLASS="Body"><A NAME="pgfId=170855"></A>As we look ahead further these
equations become more complex, take longer to calculate, and the logic becomes
less regular when implemented using cells with a limited number of inputs.
Datapath layout must fit in a bit slice, so the physical and logical structure
of each bit must be similar. In a standard cell or gate array we are not
so concerned about a regular physical structure, but a regular logical structure
simplifies design. The BrentKung adder reduces the delay and increases the
regularity of the carry-lookahead scheme [Brent and Kung, 1982]. Figure 2.24(a)
shows a regular 4-bit CLA, using the carry-lookahead generator cell (CLG)
shown in Figure 2.24(b).</P>
<P><TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0">
<TR>
<TD><P CLASS="TableFigure"><A NAME="pgfId=176735"></A><IMG SRC="CH02-66.gif"
ALIGN="BASELINE" WIDTH="454" HEIGHT="402" NATURALSIZEFLAG="3"> </TD></TR>
<TR>
<TD><P CLASS="TableFigureTitle"><A NAME="pgfId=176738"></A>FIGURE 2.24 The
BrentKung carry-lookahead adder (CLA). (a) Carry generation in a 4-bit
CLA. (b) A cell to generate the lookahead terms, C[0]C[3]. (c) Cells
L1, L2, and L3 are rearranged into a tree that has less delay. Cell L4 is
added to calculate C[2] that is lost in the translation. (d) and (e) Simplified
representations of parts a and c. (f) The lookahead logic for an 8-bit
adder. The inputs, 07, are the propagate and carry terms formed from the
inputs to the adder. (g) An 8-bit BrentKung CLA. The outputs of the
lookahead logic are the carry bits that (together with the inputs) form
the sum. One advantage of this adder is that delays from the inputs to the
outputs are more nearly equal than in other adders. This tends to reduce
the number of unwanted and unnecessary switching events and thus reduces
power dissipation.</TD></TR>
</TABLE>
<P CLASS="Body"><A NAME="pgfId=165169"></A>In a <B>carry-select adder </B>we
duplicate two small adders (usually 4-bit or 8-bit addersoften CLAs) for
the cases CIN<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>'0'
and CIN<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>'1'
and then use a MUX to select the case that we needwasteful, but fast [Bedrij,
1962]. A carry-select adder is often used as the fast adder in a datapath
library because its layout is regular.</P>
<P><P CLASS="Body"><A NAME="pgfId=177413"></A>We can use the carry-select,
carry-bypass, and carry-skip architectures to split a 12-bit adder, for
example, into three blocks. The delay of the adder is then partly dependent
on the delays of the MUX between each block. Suppose the delay due to 1-bit
in an adder block (we shall call this a bit delay) is approximately equal
to the MUX delay. In this case may be faster to make the blocks 3, 4, and
5-bits long instead of being equal in size. Now the delays into the final
MUX are equal3 bit-delays plus 2 MUX delays for the carry signal from
bits 06 and 5 bit-delays for the carry from bits 711. Adjusting the block
size reduces the delay of large adders (more than 16 bits).</P>
<P><P CLASS="Body"><A NAME="pgfId=165654"></A>We can extend the idea behind
a carry-select adder as follows. Suppose we have an <SPAN CLASS="EquationVariables">
n</SPAN> -bit adder that generates two sums: One sum assumes a carry-in
condition of '0', the other sum assumes a carry-in condition of '1'. We
can split this <SPAN CLASS="EquationVariables"> n</SPAN> -bit adder into
an <SPAN CLASS="EquationVariables"> i</SPAN> -bit adder for the <SPAN CLASS="EquationVariables">
i</SPAN> LSBs and an (<SPAN CLASS="EquationVariables"> n</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN><SPAN CLASS="EquationVariables">
i</SPAN> )-bit adder for the <SPAN CLASS="EquationVariables"> n</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN><SPAN CLASS="EquationVariables">
i</SPAN> MSBs. Both of the smaller adders generate two conditional sums
as well as true and complement carry signals. The two (true and complement)
carry signals from the LSB adder are used to select between the two (<SPAN CLASS="EquationVariables">
n</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN><SPAN CLASS="EquationVariables">
i</SPAN> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1)-bit
conditional sums from the MSB adder using 2(<SPAN CLASS="EquationVariables">
n</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN><SPAN CLASS="EquationVariables">
i</SPAN> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1)
two-input MUXes. This is a <B>conditional-sum adder</B> (also often abbreviated
to CSA) [Sklansky, 1960]. We can recursively apply this technique. For example,
we can split a 16-bit adder using <SPAN CLASS="EquationVariables"> i</SPAN>
<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>8
and <SPAN CLASS="EquationVariables"> n</SPAN> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>8;
then we can split one or both 8bit adders againand so on.</P>
<P><P CLASS="Body"><A NAME="pgfId=196563"></A>Figure 2.25 shows the
simplest form of an <SPAN CLASS="EquationVariables"> n</SPAN> -bit conditional-sum
adder that uses <SPAN CLASS="EquationVariables"> n</SPAN> single-bit conditional
adders, H (each with four outputs: two conditional sums, true carry, and
complement carry), together with a tree of 2:1 MUXes (Qi_j). The conditional-sum
adder is usually the fastest of all the adders we have discussed (it is
the fastest when logic cell delay increases with the number of inputsthis
is true for all ASICs except FPGAs).</P>
<P><TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0">
<TR>
<TD><P><P CLASS="TableFigure"><A NAME="pgfId=196482"></A> </P>
<P><IMG SRC="CH02-67.gif" WIDTH="448" HEIGHT="338" NATURALSIZEFLAG="3"
ALIGN="BOTTOM"></TD></TR>
<TR>
<TD><P CLASS="TableFigureTitle"><A NAME="pgfId=196485"></A>FIGURE 2.25 The
conditional-sum adder. (a) A 1-bit conditional adder that calculates
the sum and carry out assuming the carry in is either '1' or '0'. (b) The
multiplexer that selects between sums and carries. (c) A 4-bit conditional-sum
adder with carry input, C[0].</TD></TR>
</TABLE>
<HR ALIGN=LEFT></P>
<P><A HREF="CH02.12.htm">Chapter start</A> <A
HREF="CH02.13.htm">Previous page</A> <A HREF="CH02.15.htm">Next page</A>
</BODY>
<!--#include file="Copyright.html"--><!--#include file="footer.html"-->
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?