Adders and speed
- To: MISC
- Subject: Adders and speed
- From: john.r.strohm@xxxxxxx
- Date: Fri, 22 Mar 96 11:14:44 EST
MuP21 and the rest of Chuck's current projects all use straight ripple
carry adders for arithmetic, with the known result that you have to insert
a NOP after an ADD, because the addition is still propagating.
I went to a Computer Arithmetic lecture last night, on adders. The guy
talking was the guy who basically wrote the book on adders. He first went
through ripple carry adders, in gate-level detail, then he jumped to the
far end of the spectrum and did full-up carry lookahead adders, then backed
out to 4-bit carry lookahead cascades, then he covered a few pieces in
between (Carry Select, Carry Skip).
The points he made were:
- Ripple carry is simple and cheap.
- Carry lookahead is the fastest you can get.
- You don't want to do n-bit full-up carry lookahead in one level,
because you
have to build n-input gates for the carry logic.
- Since 4-input gates are a reasonable upper limit, what is normally
done is
to build a set of 4-bit carry lookahead units, then cascade them in
groups of
4 units (to build 16-bit units), then cascade those in groups of 4 to
build
64-bit units.
- At 64 bits, carry lookahead is an order of magnitude faster than
ripple carry,
while only 30% more gates (or so).
- For CMOS technologies, on average, ripple carry and cascaded carry
lookahead
use about the same amount of power. (This surprised him when he and his
students tripped over it.)
- Carry Select is utterly baroque and a waste of real estate.
- Carry Skip is more complex than Ripple Carry, less so than Carry
Lookahead,
and uses more power than either.
- For MOST applications within processors, ripple carry is perfectly
reasonable,
because the adder is small and doesn't have to be fast.
So: what is the point for MISC?
Well, I went away with the impression that, for the actual arithmetic unit
adder, that adds user operands, once you decide a ripple carry adder isn't
quite enough, you really need a pretty good reason not to go to a full-up
carry lookahead cascade unit, and you NEVER have a reason to do Carry
Select.
An interesting evening, all in all.