10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The cycle time of high performance processors and their single cycle add latency certainly points to them not using ripple-carry (but this would allow carry-select). Even for Intel's 22nm process, rippling through 64 bits in less than 300ps might be improbable. $\endgroup$ – Paul A. Clayton Aug 25 '14 at 4:42
  • $\begingroup$ @PaulA.Clayton I get the impression from looking through a few datasheets that carry-select or decoder-like adders are used. $\endgroup$ – qwr Aug 29 '14 at 20:30
14
+50
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

Yes, many computers use carry-lookahead adders. I've reverse-engineered some old microprocessors and I can give some examples.

The ALU on the Intel 8008 (their first 8-bit processor) included a large carry-lookahead circuit implemented with dynamic logic. This circuit took up about as much die space as the ALU itself. Carry lookahead is shown on the 8008 datasheet, figure 3. I haven't seen any other 1970s processors with carry-lookahead for the ALU, so the 8008 is a bit unusual in this regard.

The 6502 uses primitive carry-lookahead for the program counter (PC) incrementer. It detects if there will be a carry from the lower byte of the PC and uses this to increment the upper byte. This reduces ripple carry from potentially 16 bits to 8 bits. The 6502's ALU uses ripple carry, although the carry logic is inverted for alternating bits, which cuts an inverter out of the path and makes it slightly faster.

The Z-80 has a 16-bit incrementer/decrementer used for PC updates, inc/dec instructions, and a loop counter. It uses a carry-skip structure so carries are computed for groups of two bits. In addition, it uses some carry-lookahead to generate the carry from bits 0-7, 7-11, and 12-14. Other carries are computed with ripple carry (details). The Z-80's ALU, surprisingly, is 4 bits, so each 8-bit operation does two passes through the ALU.

The 8085, on the other hand, uses ripple carry for its 16-bit incrementer/decrementer. But like the 6502, it gets a bit of speedup by inverting the carry logic in alternating bits.

The ARM-1 has a 32-bit ALU with no carry-lookahead, just ripple carry. It also uses the trick of inverting the carry in alternating bits.

In the minicomputer world, many processors were built from the well-known 74181 4-bit ALU chip, which had internal carry lookahead. Examples include the Data General Nova, the Xerox Alto, the VAX-11/780 and the TI-990. (See longer Wikipedia list.) Some of these used ripple carry between each 4-bit chip and some uses the 74182 carry lookahead chip for full lookahead.

To summarize, different microprocessors use a variety of carry techniques depending on their performance goals and what operations are on the critical path. The ALU can use full carry-lookahead (like the 8008) or can even be half-sized (like the Z-80). The incrementer can be a performance problem because it is typically 16 bits in an 8-bit processor, resulting in twice the ripple delay. The incrementer can have ripple carry (8085), one carry lookahead (6502) or several carry lookahead stages (Z-80).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.