The Array Multiplier

In the last article we wrote down the equation for multiplication. In this one we build the most direct hardware for it. The array multiplier does exactly what long multiplication says: generate every partial product at once with AND gates, then add them up through a cascade of adder rows. It is regular enough to sketch on graph paper. It is not fast, but it shows clearly how the structure of an algorithm becomes the structure of a circuit, and once you see that, every faster multiplier is just a rearrangement of the same additions.

From the equation to an array of gates

$$A \times B = \sum_{i=0}^{N-1} B_i \cdot (A \ll i)$$

Each term is the multiplicand gated by one multiplier bit. The AND gate at row $i$, column $j$ computes

$$PP_{i,j} = A_j \cdot B_i$$

For a 4×4 multiplier that is 16 AND gates in a grid (Figure 1). All sixteen partial product bits are ready one gate delay after the inputs.

Row $i$ has to be added shifted left by $i$ positions. The shift costs nothing; it is just where the wires go.

Adding the rows

Four partial products have to be summed into an 8-bit result. The simplest arrangement is a cascade: add row 0 and row 1, add row 2 to that, add row 3 to that (Figure 2).

The lowest product bit, $P_0$, is just $PP0[0] = A_0 B_0$ and needs no adder. The top bits come out of the carry chain of the last row.

Tracing 0110 × 0101

$A = 0110$, $B = 0101$, expecting 30.

PP0 = A x 1 = 0110   aligned 00000110
PP1 = A x 0 = 0000   aligned 00000000
PP2 = A x 1 = 0110   aligned 00011000
PP3 = A x 0 = 0000   aligned 00000000

Row 1: $00000110 + 00000000 = 00000110$. Row 2: $00000110 + 00011000 = 00011110$. Row 3: $00011110 + 00000000 = 00011110 = 30$.

Timing

Each adder row waits for the row above it. If the rows are ripple-carry adders, the delay is one gate for the AND array plus $N - 1$ rows each of roughly $2N$ gate delays, so about $2N^2$: quadratic in the width, which becomes painful quickly.

The usual improvement is to let each row pass its carries diagonally down to the next row instead of rippling them along, so that only the final row has a full carry chain. The rows then cost about two gate delays each and the total is roughly $2N + 2N$, linear in $N$:

A 32-bit array multiplier at 80 gate delays is far too slow for a processor datapath, and that is the problem the Wallace tree solves in the next article.

Area

Doubling the width quadruples the gate count, and with it the area and power.

What the array does well

The array multiplier’s strength is regularity. Every cell is the same, the AND array is a grid, the adder rows repeat. Place-and-route tools handle it as a rectangular block, timing is predictable with no surprise paths, and a single full-adder cell designed and characterised once tiles the whole thing.

For that reason it is still used for small widths, 4 or 8 bits, where the quadratic growth does not hurt and a Wallace tree’s overhead is not worth it; in area-constrained designs; and as the reference implementation when you first write a multiplier in HDL, because it matches the algorithm line for line.

On an FPGA, do not build a multiplier from LUTs at all if you can avoid it. Every current FPGA has hardened DSP blocks, Xilinx’s DSP48 and Intel’s equivalents, that multiply 18×18 or 27×27 in one cycle. Write A * B and check the report to see that a DSP block was used.

Practice Exercise

Problem 1. How many AND gates does a 3×3 multiplier need, and what does each compute?

Problem 2. Compute $1101 \times 1010$ ($13 \times 10 = 130$) with the array method, showing each adder row.

PP0 = 1101 x 0 = 0000   aligned 00000000
PP1 = 1101 x 1 = 1101   aligned 00011010   (shift 1)
PP2 = 1101 x 0 = 0000   aligned 00000000
PP3 = 1101 x 1 = 1101   aligned 01101000   (shift 3)

The array’s weakness is that each adder row waits for the one above. The next article shows how to add all the partial products at once, in a number of levels that grows with the logarithm of the width rather than the width itself.