26. Vector Processing, Saturating Arithmetic, and Hardware Multiplier Architectures

Vector Processing and SIMD Architectures

• Definition of Vector Processing:

  • Vector processing operates on entire arrays or vectors of data simultaneously on a component-by-component basis, rather than executing independent sequential scalar instructions.

  • For two vectors $\mathbf{a}$ and $\mathbf{b}$ of dimension $k$, vector addition evaluates each element pair in parallel:     $\mathbf{c} = \mathbf{a} + \mathbf{b} \implies \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_k \end{pmatrix} = \begin{pmatrix} a_1 + b_1 \\ a_2 + b_2 \\ \vdots \\ a_k + b_k \end{pmatrix}$

• Sub-Word Parallelism in Standard Adders:

  • Modern $64\text{-bit}$ processors can partition a $64\text{-bit}$ adder to function as a vector adder rather than executing a single $64\text{-bit}$ addition.

  • Operating on four $16\text{-bit}$ elements simultaneously:

  • Vector $\mathbf{a}$ contains four $16\text{-bit}$ elements: $a_1, a_2, a_3, a_4$.

  • Vector $\mathbf{b}$ contains four $16\text{-bit}$ elements: $b_1, b_2, b_3, b_4$.

  • The adder computes $c_1 = a_1 + b_1$, $c_2 = a_2 + b_2$, $c_3 = a_3 + b_3$, and $c_4 = a_4 + b_4$ concurrently in a single clock cycle.

  • The four $16\text{-bit}$ results are packed together to form the unified $64\text{-bit}$ output vector $\mathbf{c}$.

  • Sub-word configurations for a $64\text{-bit}$ register include:

  • Eight $8\text{-bit}$ integer elements.

  • Four $16\text{-bit}$ integer elements.

• Architectural Classification and Domains:

  • This paradigm is classified under Flynn's taxonomy as SIMD (Single Instruction, Multiple Data), where a single instruction stream controls multiple execution datapaths.

  • Graphics Processing Units (GPUs): Heavily rely on SIMD and vector processing pipelines to handle massively parallel graphic geometry and pixel shading calculations.

  • Programming and Development Frameworks: Languages and frameworks such as CUDA leverage this architecture for compute shaders and general-purpose GPU computing.

  • Game Development: Modern gaming engines and media rendering engines perform vector math continuously for physics, lighting, and transformations.

• Supported Operations in Multimedia Extensions:

  • Unsigned addition and subtraction across eight $8\text{-bit}$ or four $16\text{-bit}$ elements.

  • Saturating addition and subtraction across eight $8\text{-bit}$ or four $16\text{-bit}$ elements.

  • Maximum and minimum evaluations across packed sub-word elements.

Saturating Arithmetic in Media and Audio Applications

• Comparison with Modulo Wrap-Around Arithmetic:

  • In standard computer arithmetic, integer overflow results in modulo truncation (wrap-around):

  • For an unsigned $w\text{-bit}$ integer, addition is computed modulo $2^w$.

  • In an $8\text{-bit}$ representation with a range of $[0, 255]$, computing $250 + 251 = 501$ yields:       $501 \pmod{256} = 245$

  • In graphics or audio, wrap-around causes catastrophic visual artifacts (e.g., an extremely bright pixel wrapping to a darker color) or severe acoustic distortion.

• Saturating Arithmetic Mechanics:

  • If an arithmetic operation produces a value exceeding the maximum representable limit of the finite bit format, the hardware clamps the result to the maximum allowable representable value:     $\text{Result} = \min(a + b, 2^w - 1)$

  • Clamping prevents arithmetic overflow from rolling over to zero or low values.

• Visual / Pixel Processing Example:

  • Given two $8\text{-bit}$ pixel intensities evaluated during image blending or lighting: $250$ and $250$.

  • Normal arithmetic sum: $250 + 250 = 500$.

  • Since $500 > 255$, the saturating operation clamps the result:     $\text{Saturated Output} = 255$

  • The pixel remains at peak brightness (white/maximum saturation) rather than wrapping around to $500 - 256 = 244$.

• Audio Signal Processing Example:

  • Given two $8\text{-bit}$ audio samples: $250$ and $252$.

  • Normal arithmetic sum: $250 + 252 = 502$.

  • Saturating arithmetic clamps the output to $255$.

  • Digital audio hardware and players utilize saturating amplifiers/limiters (clipping) as a physical and acoustic safety mechanism:

  • When an audio level is raised to maximum, signal sums that exceed system bounds are clamped at the maximum peak threshold.

  • This design prevents dangerously high acoustic output spikes through headphones or earplugs, shielding human hearing from sudden overpressures.

Principles of Binary Multiplication and Partial Products

• Fundamental Terminology and Properties:

  • In multiplication, the two operands are the multiplicand (the base value being scaled) and the multiplier (the factor indicating how many times the multiplicand is added).

  • Multiplication is commutative ($a \times b = b \times a$); hence, $5 \times 2 = 2 \times 5$, allowing the roles of multiplicand and multiplier to be interchanged without affecting the mathematical result.

• Long Multiplication by Partial Products:

  • Multi-digit multiplication is executed by generating shifted partial products for each digit of the multiplier, followed by summation.

  • Decimal Arithmetic Analog:

  • Multiplying $54$ (multiplicand) by $22$ (multiplier):

    • Step 1 (Units place, $10^0$, shift $0$): $54 \times 2 = 108$.

    • Step 2 (Tens place, $10^1$, shift $1$ place left): $54 \times 20 = 1080$.

    • Summing partial products: $108 + 1080 = 1188$.

  • Multiplying $54$ by a three-digit multiplier $222$:

    • Partial product 1 (shift $0$): $108$.

    • Partial product 2 (shift $1$): $1080$.

    • Partial product 3 (Hundreds place, $10^2$, shift $2$): $54 \times 200 = 10800$.

    • Summing all three shifted partial products yields the total product.

• Simplification in Binary Multiplication:

  • Decimal digits range from $0$ to $9$, requiring multi-valued scalar multiplications at each position.

  • Binary digits (bits) are strictly restricted to the domain $\{0, 1\}$:

  • When the multiplier bit is $1$, the partial product is simply the multiplicand itself, shifted left by the bit's positional index ($2^k$).

  • When the multiplier bit is $0$, the partial product is identically zero ($0$).

• Product Word Length Rule:

  • Multiplying two $n\text{-bit}$ integers produces a product whose maximum length is $2n\text{ bits}$:

  • Two $32\text{-bit}$ inputs produce a product of up to $64\text{ bits}$.

  • Two $2\text{-digit}$ base-10 numbers produce a product of up to $4\text{ digits}$.

Sequential Shift-and-Add Hardware Multipliers

• Fundamental Relationship of Arithmetic Units:

  • The adder is the baseline primitive building block for all arithmetic logic units (ALUs):

  • Subtraction is implemented as addition with the second operand sign-inverted ($A - B = A + (-B)$).

  • Multiplication is implemented as repeated shifted addition.

• Accumulator / Running Sum Multiplier Algorithm:

  • Rather than generating all $n$ partial products simultaneously and summing them at the end, a sequential hardware multiplier maintains a single running sum in a product register.

  • Step-by-Step Procedure:

  1. Inspect the least significant bit (LSB) of the multiplier, denoted as $\text{Multiplier}[0]$.

  2. If $\text{Multiplier}[0] = 1$, add the current shifted multiplicand into the running product register.

  3. If $\text{Multiplier}[0] = 0$, bypass addition (add zero) and leave the product register unchanged.

  4. Shift the multiplier register one bit to the right ($\gg 1$) to position the next bit at LSB.

  5. Shift the multiplicand register one bit to the left ($\ll 1$) to align with the next power-of-two position.

  6. Repeat the cycle for each bit across the full word width $n$.

• Stationary Multiplicand Architecture (Right-Shift Design):

  • Shifting a large $64\text{-bit}$ multiplicand register to the left requires wide shifting hardware.

  • An alternative hardware optimization keeps the multiplicand register stationary (fixed in place without shifting):

  • The product and multiplier are unified in a single shifting register structure.

  • The multiplier is initially loaded into the lower $32\text{ bits}$ of the product register, while the upper $32\text{ bits}$ are initialized to zero.

  • During each clock cycle, if the LSB of the register is $1$, the fixed multiplicand is added to the upper half of the product register.

  • The combined product-multiplier register is then shifted to the right by one bit ($\gg 1$).

  • After $n$ cycles, the complete $2n\text{-bit}$ product resides across the combined register.

Parallel Tree Multipliers and Pipelining

• Parallel Tree Architecture:

  • All partial products are evaluated simultaneously at cycle zero using combinational AND gates.

  • The partial products are arranged in a hierarchical binary tree of adders to sum all products concurrently.

• Latency / Delay Analysis:

  • In a sequential shift-and-add multiplier:

  • Processing an $n\text{-bit}$ operand takes $O(n)$ clock cycles.

  • For $n = 32\text{ bits}$, the sequential algorithm requires $32\text{ clock cycles}$.

  • In a parallel tree multiplier:

  • The height (depth) of the reduction tree determines the clock cycles needed when each level corresponds to a cycle.

  • Latency scales logarithmically: $O(\log_2(n))$.

  • For $n = 32\text{ bits}$:       $\text{Tree Depth} = \log_2(32) = 5\text{ clock cycles}$

• Hardware Complexity vs. Latency Tradeoff:

  • Sequential Multiplier:

  • Hardware requirement: $1\text{ adder}$.

  • Time latency: $32\text{ clock cycles}$.

  • Parallel Tree Multiplier:

  • Hardware requirement: A tree reduction of $n$ inputs requires $n - 1$ adders.

  • For $n = 32\text{ bits}$, reducing $32$ partial products requires:       $16 + 8 + 4 + 2 + 1 = 31\text{ adders}$

  • Time latency: $5\text{ clock cycles}$.

  • The substantial speedup from $32$ cycles down to $5$ cycles incurs a hardware area penalty from $1$ adder to $31$ adders.

• Pipelined Tree Execution:

  • Due to the large hardware cost, parallel multipliers are structured as pipelined stages to maximize hardware utilization:

  • Operands $a_0$ and $b_0$ enter the first tree level and generate initial partial sums.

  • When these sums advance to tree level 2, tree level 1 immediately begins processing the next operands $a_1$ and $b_1$.

  • Once the pipeline is filled, the circuit outputs a completed $64\text{-bit}$ product on every single clock cycle.

Questions & Discussion

• Delay of Parallel Tree Multipliers:

  • Question: What is the delay involved in a parallel multiplier if each reduction level takes one clock cycle, compared to the sequential case?

  • Response: The number of levels is determined by the base-2 logarithm of the bit width $n$. For a $32\text{-bit}$ multiplication, because $\log_2(32) = 5$, the tree depth is $5$. Consequently, it requires $5\text{ clock cycles}$ ($O(\log_2(n))$), whereas the sequential shift-and-add multiplier requires $32\text{ clock cycles}$ ($O(n)$).

• Hardware Cost Tradeoff:

  • Question: What is the structural downside of moving from $n$ clock cycles to $\log_2(n)$ clock cycles?

  • Response: The architecture requires significantly more adders. Rather than utilizing a single adder sequentially, a parallel tree requires an order of $n - 1$ adders ($16 + 8 + 4 + 2 + 1 = 31\text{ adders}$ for $32\text{-bit}$ inputs).

• Pipelining Applicability:

  • Question: Is the hardware overhead justified if only multiplying two standalone numbers, and how is it optimized?

  • Response: For single isolated operations, dedicating $31\text{ adders}$ involves substantial hardware overhead. However, high-performance designs pipeline the adder stages. Successive operand pairs ($a_0, b_0$ followed by $a_1, b_1$) are fed continuously through the levels, ensuring full utilization across all stages.