home .. forth .. misc mail list archive ..

Adders and speed


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.