# 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

## 3 Answers

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.

About decimal

x86 have some decimal parts, now obsoleted but still present. There are the AAA, AAS, AAD, AAM instructions, unavailable in 64bits mode, wich are helpers for BCD arithmetics. The FPU x87 instruction set has instructions to read/write decimal numbers from memory and convert on the fly to/from binary (internal registers are binary).

Some high end CPUs, notably IBM servers/mainframes, feature decimal FPUs specifically for financial operations with are officially based on decimal rounding and cannot be easily implemented exactly on binary FPUs.

• In fact, I asked about BCD because I wonder how computers manage decimal inputs/outputs. I wonder if there is a special instruction for converting decimal to binary or if the program which wants to write to or read from the standard I/O uses a routine, which is a set of common instructions. – Jean-Paul Jul 19 '16 at 10:29
• Conversion from a decimal text input to binary can be done with multiplications, additions, and subtraction. Conversion from binary to decimal with divisions, remainder... If you can read C, search "itoa source" and "strtol source" in your preferred search engine. Multiplications and additions are fast in nowadays CPUs, conversion from a decimal input to internal binary representations is fast and simple. For binary to decimal, There may be faster methods than divisions, I don't know, but this is still used a lot. – TEMLIB Jul 19 '16 at 19:30
• Yes, there is the double dabble algorithm, and the inverse algorithm is very similar. They are also very simple to make with combinational logic (db.tt/2ftrBLF4 where the small rectangles are db.tt/Ro1dFyGv), which was the reason of my question about hardware converter. – Jean-Paul Jul 21 '16 at 21:42

I thought a 7/3 adder was 18 gates and you'd need less than 1000 of those for a full 64x64 multiplier. No big deal. And about 4 n^2.

There is absolutely no demand for BCD converters in hardware. Nothing that can't be done quicker with a lookup table.