MULT in a RISC - should instructions take the same amount of time in a RISC system

Question

I am studying computing as part of my A level course, and my understanding is that all instructions in a RISC architecture should execute in roughtly the same, small number of clock cycles (ideally one).

This leads me to ask how multiplying two (possible very large) numbers takes (roughly) the same time as all the other commands, such as LOAD, STORE, ADD, etc. I believe the most common way a computer multiplies numbers is using a Binary Multiplier, which requires multiple addition executions, meaning that a multiplication, or PROD command (from an example from Stanford University) will execute with many cycles per second and not be consistent with the speed/cycles of other commands from a reduced instruction set.

Answer 1

RISC processors are pipelined, and have been since the beginning. That is, at a single time there are several instructions which are in different phase of execution. That mean that there is two different numbers that you can give for the execution time. One, the latency, which measures the time between the start of an instruction and its end. The other, the throughput, which measures how many instructions can be executed in a given time.

When someone says that RISC have single clock instructions, they are thinking about throughput, that is that RISC processors are able to execute one instruction per clock, and not latency, that is that it take one clock to execute any given instruction.

Early RISCs did not have multiplication instructions. That was more a consequence of manufacturing process limitation of the time, which would not have allowed to put a multiplier on the chip along with the rest of the processor, than a fundamental characteristic of RISC. With increased integration density, RISC acquired such instructions.

Note that it is possible to achieve bigger throughput than one instruction per cycle. For that, you need to be able to decode several instructions per cycle, and have several execution unit. That is something called super-scalar and high-end processors are super-scalar since the early 90's.

Note also that the possibility to achieve the theoretical throughput in practice depend on the program (you need to have instructions which are independent to be able to execute them in parallel, you need to have the data available, and thus have pattern of memory accesses and a memory sub-system which together allow to provide the data rapidly enough).

Answer 2

Early RISC CPUs had no "real" multiply instructions because multiplication is a complex operation, usually multicycle or deeply pipelined, needing lots of gates, which breaks the simplicity of the pipeline where calculations are only performed in the EXECUTE stage, and are of moderate complexity (add/sub, logical operation...).

As a band-aid, some RISCs had primitive partial-multiply instructions which needed to be executed many times for a complete multiplication. A good example is the SPARC v7 MULScc "multiply step" instruction.

Nowadays, with transistors aplenty, most CPUs can afford a fast multiplier.
Division was also unavailable in early RISC CPUs. Integer division is less important than multiplication, though, and there is no reasonable method for making dividers as fast as multipliers.

Having a genuine multiply instruction is better than nothing, even if it is slow in first versions/low end variants, because it can be more easily enhanced than series of additions and shift instructions, or relying on dynamic patching of code depending on CPU versions (replacing the multiply subroutine call by a call to a single a multiply instruction, which was done sometimes).

Answer 3

Integer multiplication is actually something that can be done very fast (not much slower than an addition). If you throw enough hardware at it, which is usually done, you can perform a multiplication in about twice the time of an addition. And while an addition is usually done in one cycle, there is usually plenty of time to spare, and an integer multiplication does indeed fit into one cycle. You'll need a couple of thousand full adders for a 64x64 bit multiplication, but there are far more than one billion transistors in a modern smartphone, so that's no big deal.

See for example https://en.wikipedia.org/wiki/Wallace_tree . And that was apparently invented in 1964 - just at that time it was very, very expensive. Today it's cheap.

Memory on the other hand is slooooooooow. 50 cycles is not unusual for random access. Sequential access is substantially faster, and caches are used to reduce the number of memory accesses.

Overall: It's not multiplications that are slow (today), it's memory access. Division and square root are also multiple cycles and usually implemented in hardware.