Addition is implemented in computers using a circuit of logic gates.
Do we know what is the lowest depth circuit possible for 64bits? And is it used in practice?
3
-
$\begingroup$ I don't know which particular architecture companies like Intel use to the adders, but given the importance of these devices, you can be sure that they strive to optimize them to the maximum that their technology allows, which might not match the theoretical optimum. $\endgroup$– Yves DaoustCommented Aug 31 at 19:28
-
$\begingroup$ Since most high-performance CPUs use out-of-order superscalar pipelines, it is no longer required that additions take a single cycle all the time. So research in the last decade has concerned itself with "speculative adders". The idea is to speculate the carry propagation, which is then fed into an adder. If the speculation was incorrect, addition may take a second cycle. $\endgroup$– Pseudonym ♦Commented Sep 1 at 2:33
-
$\begingroup$ In clocked circuitry, single cycle is as fast as it gets. $\endgroup$– greybeardCommented Sep 1 at 9:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Lookup carry-select adder. An n-bit carry-select adder produces two outputs x+y and x+y+1. For a 64 bit adder, you use two 32-bit carry select adders. The lower 32 bits of the output are either xlo+ylo or xlo+ylo+1. You take the carry of the result, then the higher 32 bits are xhi+yhi or xhi+yhi+1.
You do this recursively taking a depth of c*n levels. Other operations like subtraction, min, max, shift operations take equally long. Logical operations take a constant number of levels.
You can add three 64 bit numbers with cn + d levels instead of 2cn levels, for some small constant d.
Now a few more details: You must likely build all your logic using nand-gates. For example a two bit carry-select adder has four input bits and six output bits. If you try to implement this with NAND-gates, you may find that you can get the same result if one or two inputs arrive later. Or that you produce one or two outputs a bit later. If you are clever and/or lucky you can match these bits from different rounds and get the speed.
For the time taken, you don’t just count the depth of the circuit. Usually there are different implementations of the basic logic that take different time at different cost. So 13 levels with an expensive implementation may be just as fast as 12 levels with a cheaper implementation.
And in a clocked CPU (in practice every CPU) someone decides in the cycle time. Then any operation below the cycle time takes one cycle, anything above that must likely be split. Make the cycle time longer, and more different operations can run in one cycle. Make it shorter, and all single cycle operations are faster, but there are more operations that don’t work in a single cycle. Make it just a little bit shorter, and there will be more operations that can run in a single cycle with a more expensive implementation. Picking the optimal point is hard.
-
$\begingroup$ Is carry-select the preferred way of building adders these days? It has been a long time since I was involved with building hardware, and back then Ling adders (a form of carry-lookahead adder, AFAIK) were popular. My vague recollection is that a 64-bit barrel shifter has delay of about 15 FO4, so if that wants to be a single-cycle operation, a two-operand 64-bit adder with delay of 12 FO4 has room to spare, and one might as well tack on a CSA (carry-save adder) with a delay of 3 FO4 to implement a three-operand adder (e.g.
leainstruction in x86-64) with a delay of 15 FO4. $\endgroup$– njuffaCommented Sep 2 at 19:39