Adders and speed

[john.r.strohm@xxxxxxx]

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.