# Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?

Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?

An asynchronous multiplier is much bigger than an adder. It's about 18*n^2 NOR gates where n is the number of bits. An adder is about 15*n NOR gates. But for a 32-bits multiplication, a multiplier with successive additions will need 32 clock cycles, while an asynchronous mutliplier only 1. I think it's a big performance gain.

The same is for BCD to binary converter.

• – D.W. Jul 14 '16 at 19:01
• Desktop CPUs have had dedicated multipliers (~3 cycles) for over a decade. (See Agner Fog's document.) Doing shift-and-add for multiplication is much less common than it was in the 8-bit era. – Nayuki Jul 15 '16 at 15:08
• Thanks to Moore's Law, the number of gates (i.e. number of transistors, which is what Moore's Law predicts) hasn't been the limiting factor in CPU design for a while now. If it's a choice between using more transistors or increasing the length of a cycle or the number of cycles of some operation, CPU designers will generally use more transistors. You don't see a lot of asynchronous circuits in CPUs, though. – Pseudonym Jul 17 '16 at 14:08

Last time I checked (more than 15 years ago), Wallace trees (and variants such as Dadda trees) were still the state of the art ($O(N^2)$ number of gates, but $O(\log N)$ latency; if you are naive in the way you do the additions, the latency may be $O(N)$).

Note that multipliers may be pipelined so you can still achieve a throughput of one multiplication per cycle but with a latency of more than one cycle if the latency of the multiplier is too big for your target clock rate.

• And what's about the BCD to binary converter ? I thought about this because of the conversion that is needed when the user give a number in a decimal form to the computer. – Jean-Paul Jul 14 '16 at 20:13
• I'm not familiar with the implementation aspect of CPU having BCD to binary conversion on ship (I'd look papers about IBM CPU as I'm not aware of other CPU having such kind of thing for larger data size than a byte). – AProgrammer Jul 15 '16 at 13:00

Of course, it depends on the type of CPU. Primitive 8 bits CPUs had no multiplier (until the MC6809 which had a 8bits x 8bits multiplier :-).

Modern CPUs have both fast integer and floating point multipliers. The FP multipliers are replicated for "multimedia" SIMD instructions and there are also plenty of fast multipliers in the GPU.

Depending on the transistor budget, one may make a pipelined 1 cycle throughput double precision (53x53 bits) multiplier, or make only single precision 1 cycle and 2 or 3 cycles for double precision. Some GPUs still have this sorts of limitations.

In a modern FPU, the multiplier is often coupled with an adder and the mul/add operation can be done in 3/4 cycles, pipelined (so that a result can be obtained every cycle, as long as there is no data dependency). The core multiplication part lasts 1 cycle, while the other cycles are used for data algnment, conversion, rounding... There are many tricks for implementing multipliers using fewer gates than cascaded adders. Look for Booth encoding, Wallace trees... but it is more about EE than CS.