[Robelle] [SmugBook] [Index] [Prev] [Next]

Multiply Without a Multiply Instruction

The PA-RISC computers do not have hardware to do integer multiply and divide directly because a complex multiply instruction would slow the basic cycle time of all instructions. Since these instructions are used less than 1 percent of the time, most computers do not have hardwired logic for them. CISC processors like the Classic 3000 use a complex microprogram that is hidden from the application programmer. The PA-RISC designers wanted to multiply with good performance, but without the microprogram or hardwired logic.

The PA-RISC designers attacked this problem in the same way that we often attack performance problems with database applications. They did a frequency analysis of actual multiplications in real user programs. They found that 91 percent of multiply tasks use a constant operand which is known at compile time, that the constants tend to be small, that non-constant operands also tend to be small, and that 32-bit results occur more frequently than 64-bit results. They set out to optimize the frequent cases, even at the expense of the less frequent cases.

Any multiply can be converted into a series of additions and smaller multiplies. For example, 10 times x is the same as (5 times x) times 2, or even (4 times x plus x) times 2. The only tricky step is the last.

   120 = 10 x 12
   120 = (5 x 12) + (5 x 12)
   120 = ((4 x 12) + 12) + ((4 x 12) + 12)

The Shift-and-Add machine instructions multiply any register by 2, 4 or 8 and add to any register in one cycle. To multiply register x by 10 uses just two instructions:

Text version.

SH2ADD x,x,x;shift x 2 bits (multiply by 4), add to x, store in x
ADD x,x,x;add register x to itself and store in x

The compilers can convert any multiplication by a constant into a series of specific Add and Shift-and-Add instructions. PA-RISC can do such a multiply in four or fewer instructions, often in only two. When neither of the operands is known at compile-time, you have multiply-by-variable. Again the PA-RISC designers did frequency analysis and came up with a subroutine that includes optimizations for those special cases that occur most frequently.


[Robelle] [SmugBook] [Index] [RISC] [Prev] [Next]