Take the 2-minute tour ×

In different assembly languages MUL (x86)/MULT (mips) refer to multiplication. It is a black box for the programmer. I am interested in how actually a CPU accomplishes a multiplication regardless of the architecture. Lets say I have two 16-bit values in my registers and I am the cpu, so I have to implement MUL using the other bit-fiddling instructions I have (and,or,xor,not,shl,shr,etc). What shall I do?

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

http://en.wikipedia.org/wiki/Multiplication_ALU on Wikipedia lists different methods for doing multiplication in a digital circuit.

When I worked on a project to add SIMD instructions to an DEC Alpha-like processor in Verilog back in college, we implemented a Wallace tree multiplier, the primary reason being it ran in a fixed number of cycles and was easy to pipeline.

EDIT: You mentioned using the other bit fiddling instructions, on modern processors multiplication would not be microcoded like this; it'd be way to slow and the processor would get slaughtered in benchmarks.

share|improve this answer
I though cpus don't call their own instructions for efficiency reasons. I just had no other way to express myself, since the lowest level I have ever been so far is asm. Thanks for the help! –  George Mar 28 '09 at 3:08
Sometimes they do. x86 is a complicated ISA and has some very strange instructions. These instructions are translated into an internal micro-code program. Look at en.wikipedia.org/wiki/File:Intel_Nehalem_arch.svg, you'll see a complex decode unit and a micro-code sequencer, which does this –  Michael Mar 28 '09 at 3:14
It's even worse than that on modern CPUs - given out-of-order execution, branch prediction, hyperthreading, etc, along with microcode, it's almost fair to say that the x86 ISA runs in a virtual machine that's implemented in microcode and circuits. But it's almost never necessary to worry about it... –  Jeff Shannon Apr 3 '09 at 5:08
add comment

To add to Michael's answer, not every CPU has a MUL instruction and implementing multiplication on a CPU that doesn't support it is another interesting problem to tackle. Z80 would be one example.

share|improve this answer
The original MIPS architecture didn't provide MUL either. –  Michael Mar 28 '09 at 3:11
C=64's 6510 obviously. And the 6502 in the floppy drive. –  Marco van de Voort May 8 '09 at 8:39
add comment

This page shows the logic gates for a 4 * 4 combinational multipler. You can work up from there.

Here is somebody's lab where they describe building a 16 bit multiplier from 4 4 bit multipliers, each built with AND gates and full adders. Full design, chip layout, and simulation waveforms.

share|improve this answer
add comment

Your Answer


