[Solved]: Do computers actually use carry-lookahead adders?

Problem Detail: 

There are plenty of details about carry lookahead adders such as Kogge-Stone, Lander-Fischer, etc. in college CS courses. They are described as "common in the industry". However, I can't find any evidence (aside from maybe the Manchester carry chain) from recent times that they are actually used anywhere specifically. A Google search only returns pages of journals and academic research. At most, hypothetical implementations are given.

My question is, are there any specific places/implementations carry-lookahead adders are used? Or are they irrelevant to the real world?

Asked By : qwr

Answered By : Pseudonym

This is a straightforward question with a very complex answer.

First off, some background.

Real-world VLSI design is an extremely technical field which features a constantly-changing balance of tradeoffs. The time that a circuit takes to calculate an answer is rarely the only important factor. There's also power draw and physical area, plus a bunch of factors which reveal that the circuits you're designing are actually analogue (e.g. wire resistance, parasitic capacitance). All of these are important in a real circuit and may impact which design is chosen.

Secondly, you have to consider the entire life-cycle of a project. An adder which is appropriate for a VLSI realisation may not be appropriate for an FPGA realisation. If the design is going to go through a phase being tested on an FPGA... you get the picture.

Thirdly, not every adder is made equal. On a typical CPU, there are lots of adders hanging around which do different tasks; there are probably several integer ALUs, a floating point mantissa adder, an adder which does address calculation, an adder which calculates branch targets, and so on. That's not counting the carry-save adders that you find in modern multiplication units. Each has its own peculiarities and constraints.

Branch target calculation, for example, typically involves adding a small constant to a full word, which suggests a different adder design from one which adds two full words together. Similarly, floating point addition requires a post-addition rounding step which might take less than a cycle, so there's no reason why you couldn't steal the rest of the cycle to finish off the addition.

Lastly, and perhaps most importantly, the big players (e.g. Intel, AMD, NVIDIA) are fairly tight-lipped about low-level implementation details for obvious reasons, unless they think they can get a paper and/or patent out of it. Even then, you often can't be sure what they actually did without reverse-engineering.

Having said that, there are a few things we know.

The key thing you need to realise is that carry-lookahead methods are building blocks, and not necessarily methods in themselves. An analogy might be in order here.

If you think about algorithms classes, you probably learned a bunch of sorting algorithms such as quick sort, merge sort, insertion sort, and so on. In the real world, if sorting is a performance bottleneck, any decent engineer would think of these as primitive building blocks from which a "real" sort can be constructed.

The sort algorithm from the GNU C++ standard library, for example, uses quick sort, using insertion sort when the intervals get small enough. However, if after a few passes it looks like the quick sort partitioning has hit pathological behaviour, it falls back to heap sort. That's three different sort algorithms to make one industrial-strength sort.

The same is true of adder circuits. It is known, for example, that the Pentium 4 integer unit used a Han-Carlson adder, which is a mix of Kogge-Stone and Brent-Kung. (Han-Carlson is especially interesting, because it's a "sweet spot" in the tradeoff between propagation delay and die area which also being quite power-efficient.) It often pays to use a mix of several methods.

"Pure" carry-lookahead adders are still very much the norm in synthesised circuits (e.g. if you feed a Verilog "+" operator to Cadence or Synopsys), when it comes to hand design, modern high-end CPUs with their superscalar out-of-order execution engines seem to be moving towards a slightly different design for their integer units.

Speculative adders are circuits which have extremely low propagation delay, but only work correctly some of the time (95% of the time is typical), and it's possible to tell with very little logic whether the speculative adder returns the correct result or not. So the idea is to do a speculative addition and half of a carry-lookahead addition in parallel, in one cycle. If the speculative adder returned the correct answer, the instruction is done. Otherwise, stall the pipeline and do the other half of the accurate addition.

Because you know that the slow path will take two cycles, the designers could use a more space and power-efficient method even if it would be too slow for general use.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29368