Module 04: Unsigned Multiplication (Array & Sequential Multipliers)

Tags: #◇Computer Science #◇CSARCH2 #◇Computer Architecture #◇Hardware Modeling #◇Unsigned Multiplication (Array & Sequential Multipliers)

◇Overview

Binary multiplication forms the mathematical core of scientific computing, graphics rasterization, signal processing, and memory address indexing. This module examines the hardware realization of unsigned binary integer multiplication. We analyze pure combinational Array Multipliers constructed from AND gate arrays and adder reduction matrices, evaluating their critical path delays and silicon area complexity. Furthermore, we formalize the microarchitectural mechanics of Sequential Multipliers, detailing register datapath configurations ($A, Q, M, C$), control state machines, and cycle-by-cycle execution traces.

◇Key Definitions

• Multiplicand ($M$): The number being multiplied ($n$ bits).
• Multiplier ($Q$): The number by which the multiplicand is multiplied ($n$ bits).
• Partial Product: The intermediate result generated by multiplying the entire multiplicand $M$ by a single bit of the multiplier $Q_i$, shifted left by $i$ bit positions.
• Bit Product: The boolean AND combination of two individual bits ($p_{ij} = M_j \cdot Q_i$).
• Array Multiplier: A purely combinational circuit consisting of a grid of AND gates producing partial product bits, reduced through a two-dimensional matrix of Half Adders and Full Adders.
• Sequential Multiplier: A sequential synchronous hardware datapath that computes the $2n$-bit product over $n$ consecutive clock cycles using a single $n$-bit adder, shift registers, and a down-counter.
• Carry Flip-Flop ($C$): A 1-bit register that captures the carry-out generated during the addition of the multiplicand to the accumulator ($A \leftarrow A + M$).
• Logical Shift Right ($LSR$): A shift operation where all bits shift right by one position, the carry bit $C$ shifts into the MSb of the accumulator ($A_{n-1}$), the LSb of $A$ ($A_0$) shifts into the MSb of $Q$ ($Q_{n-1}$), and a 0 enters $C$.

◇Theoretical Framework / Core Concepts

1. Mathematical Formulation of Unsigned Multiplication

Let $M = \sum_{j=0}^{n-1} M_j 2^j$ and $Q = \sum_{i=0}^{n-1} Q_i 2^i$ be two $n$-bit unsigned integers. Their product $P$ is a $2n$-bit unsigned integer:

$P = M \times Q = M \times \left( \sum_{i=0}^{n-1} Q_i 2^i \right) = \sum_{i=0}^{n-1} (M \cdot Q_i) 2^i$

Paper-and-Pencil Multiplication (4-bit Example):
              M3   M2   M1   M0    (Multiplicand M)
       x      Q3   Q2   Q1   Q0    (Multiplier Q)
       ------------------------
            M3Q0 M2Q0 M1Q0 M0Q0    (Partial Product 0)
       M3Q1 M2Q1 M1Q1 M0Q1   0     (Partial Product 1 << 1)
  M3Q2 M2Q2 M1Q2 M0Q2   0    0     (Partial Product 2 << 2)
+ M3Q3 M2Q3 M1Q3 M0Q3   0    0    0(Partial Product 3 << 3)
------------------------------------------------------------
  P7   P6   P5   P4   P3   P2   P1   P0  (8-bit Product)

Each single-bit product $M_j Q_i$ is computed with a single 2-input AND gate because:
$M_j \cdot Q_i = \begin{cases} M_j & \text{if } Q_i = 1 \\ 0 & \text{if } Q_i = 0 \end{cases}$

2. Combinational Array Multiplier Architecture

An $n \times n$ array multiplier uses an $n \times n$ grid of AND gates to generate all $n^2$ bit products in parallel, feeding into a matrix of adders:

4x4 Array Multiplier Topology:
         M3       M2       M1       M0
          |        |        |        |
Q0 -------+--------+--------+--------+---> [Row 0: 4 AND Gates] ---------> P0
          |        |        |        |
Q1 -------+--------+--------+--------+---> [Row 1: 4 AND Gates + 4 Adders] -> P1
          |        |        |        |
Q2 -------+--------+--------+--------+---> [Row 2: 4 AND Gates + 4 Adders] -> P2
          |        |        |        |
Q3 -------+--------+--------+--------+---> [Row 3: 4 AND Gates + 4 Adders] -> P3
                                                    |
                                                    v
                                          [P7, P6, P5, P4]

Hardware & Complexity Analysis:

• AND Gate Count: Exactly $n^2$ gates.
• Adder Count: $n(n - 1)$ Full/Half Adders ($n$ Half Adders in the first stage, $n(n-2)$ Full Adders in subsequent stages).
• Silicon Area: Scales quadratically as $O(n^2)$.
• Critical Path Latency:
  $t_{\text{critical}} = t_{\text{AND}} + (n - 1) t_{\text{carry}} + (n - 1) t_{\text{sum}} \approx O(n)$

Trade-off: High speed (computes result in 1 combinational clock cycle), but prohibitive silicon area cost for large word sizes (e.g., 64-bit multiplier requires 4,096 AND gates and over 4,000 adders).

3. Sequential Circuit Multiplier Architecture

To conserve hardware area, the sequential multiplier uses a single $n$-bit parallel adder and reuses registers over $n$ clock cycles:

+--------------------------------------------------------------------------+
|                     SEQUENTIAL MULTIPLIER DATAPATH                       |
|                                                                          |
|       +------------------------------------+                             |
|       |     Multiplicand Register (M)      | (n bits)                    |
|       +------------------------------------+                             |
|                          |                                               |
|                          v                                               |
|               +----------------------+                                   |
|               |   n-bit CLA Adder    |                                   |
|               +----------------------+                                   |
|                          ^                                               |
|                          |                                               |
|                          v                                               |
|  +---+      +-------------------------+      +-------------------------+ |
|  | C | ---> | Accumulator Register (A)| ---> | Multiplier Register (Q) | |
|  |1b |      | (n bits, init to 0)     |      | (n bits, holds Q)       | |
|  +---+      +-------------------------+      +-------------------------+ |
|    ^                     |                                |       |      |
|    |                     +------- Logical Shift Right <---+       |      |
|    |                                (LSR)                         |      |
|    |                                                              v      |
|    +-------------------- Control Logic <---------------------- [ Q0 ]    |
|                          (Counter = n)                                   |
+--------------------------------------------------------------------------+

Algorithm Execution Flow (Per Clock Cycle):

1. Test LSB of Multiplier ($Q_0$):
   • If $Q_0 = 1$: Add multiplicand to accumulator:
     $[C, A] \leftarrow A + M$
   • If $Q_0 = 0$: No addition occurs ($A$ remains unchanged, $C \leftarrow 0$).
2. Logical Shift Right ($LSR$):
   • Shift the combined composite register $[C, A, Q]$ right by 1 bit:
     $Q_i \leftarrow Q_{i+1}, \quad Q_{n-1} \leftarrow A_0, \quad A_i \leftarrow A_{i+1}, \quad A_{n-1} \leftarrow C, \quad C \leftarrow 0$
3. Loop Control:
   • Decrement the cycle counter: $\text{Count} \leftarrow \text{Count} - 1$.
   • If $\text{Count} \neq 0$, repeat from Step 1.
   • When $\text{Count} = 0$, the $2n$-bit product resides across registers $[A, Q]$ (where $A$ contains the upper $n$ bits and $Q$ contains the lower $n$ bits).

◇Worked Examples / Calculations / Hardware Traces

Example 1: 4-Bit Sequential Multiplier Execution Trace

Problem: Multiply unsigned 4-bit integers $M = 1011_2\ (11_{10})$ and $Q = 1101_2\ (13_{10})$ using the sequential shift-and-add hardware multiplier. Show the complete cycle-by-cycle register trace table.

Solution:

• Multiplicand $M = 1011_2$
• Initial state: $C = 0$, $A = 0000_2$, $Q = 1101_2$, $\text{Count} = 4$.
• Expected final product: $11 \times 13 = 143_{10} = (10001111)_2$.

Execution Trace Table:

• Final Register Contents:
  • $A = 1000_2$ (High 4 bits)
  • $Q = 1111_2$ (Low 4 bits)
  • Combined Product $[A, Q] = 10001111_2$
• Decimal Verification:
  $10001111_2 = 128 + 8 + 4 + 2 + 1 = 143_{10}$
  $11 \times 13 = 143_{10} \quad \checkmark$

Example 2: Critical Path Delay Comparison (Array vs Sequential)

Problem: An engineering team evaluates building a 32-bit unsigned multiplier:

• Option A: Combinational Array Multiplier where $t_{\text{AND}} = 0.2\text{ ns}$, $t_{\text{carry}} = 0.3\text{ ns}$, $t_{\text{sum}} = 0.4\text{ ns}$.
• Option B: Sequential Multiplier running at $1.5\text{ GHz}$ ($T_{\text{clk}} = 0.667\text{ ns}$), taking 32 clock cycles.

Calculate the total multiplication latency for both implementations.

Solution:

• Option A (Array Multiplier):
  $t_{\text{Array}} = t_{\text{AND}} + (n - 1) t_{\text{carry}} + (n - 1) t_{\text{sum}}$
  $t_{\text{Array}} = 0.2\text{ ns} + (31 \times 0.3\text{ ns}) + (31 \times 0.4\text{ ns}) = 0.2 + 9.3 + 12.4 = 21.9\text{ ns}$

• Option B (Sequential Multiplier):
  $t_{\text{Sequential}} = 32 \times T_{\text{clk}} = 32 \times 0.667\text{ ns} = 21.34\text{ ns}$

Analysis: While both yield similar total latencies ($\approx 21.5\text{ ns}$), Option B requires less than $5\%$ of the silicon area, freeing up die area for on-chip caches.

◇Complexity Analysis / Common Pitfalls

• Applying Unsigned Multipliers to Signed Negative Numbers: A critical error is attempting to multiply negative 2's complement numbers using this unsigned shift-and-add algorithm. Because negative numbers have leading 1s (due to sign weight $-2^{n-1}$), treating them as unsigned leads to grossly incorrect positive results. Signed multiplication requires Booth's algorithm or sign-correction logic.
• Forgetting to Capture Carry in Flip-Flop $C$: In sequential multiplier hardware, when $A + M \ge 2^n$, the generated carry bit $C$ must be shifted into the MSB of $A$ during the subsequent LSR. Discarding $C$ results in truncation errors.
• Logical vs. Arithmetic Shift Right: Sequential unsigned multiplication strictly requires a Logical Shift Right (inserting 0 into $C$), whereas signed multiplication requires an Arithmetic Shift Right (retaining the sign bit).

◇References & Navigation

• Previous Topic: ◇Binary Addition, Subtraction & Carry Lookahead Adders
• Next Topic: ◇Signed Multiplication (Booth's & Extended Booth's Algorithm)
• Related Notes: ◇Binary Division (Restoring & Non-Restoring Division Algorithms), ◇Processing Unit Organization & Single-Bus Datapath