Arithmetic Algorithms: Multiplication and Division

• Module 3 covers arithmetic algorithms for multiplication and division, pipelining principles, classification of pipeline processors, instruction and arithmetic pipelines, hazard detection, and resolution.

Multiplication of Unsigned Numbers

• The product of two n-bit numbers is at most 2n bits.
• Unsigned multiplication involves adding shifted versions of the multiplicand.
• Partial products are generated for each digit in the multiplier and then summed.
• If the multiplier bit is 0, the partial product is 0; otherwise, the partial product is the multiplicand.
• Successive partial products are shifted one position to the left relative to the preceding one.

Array Multiplier

• Binary multiplication can be implemented using a combinational two-dimensional logic array called an array multiplier.
• The main component in each cell is a full adder (FA).
• An AND gate in each cell determines whether a multiplicand bit is added to the incoming partial product depending on the multiplier bit's value.
• Each row adds the appropriately shifted multiplicand to the incoming partial product to generate the outgoing partial product if the multiplier bit equals 1.
• If the multiplier bit is 0, the partial product is passed vertically downward unchanged.
• The multiplication shifts left one position per row via the diagonal signal path.

Array Multiplier Disadvantages

• An n-bit by n-bit array multiplier requires n² AND gates and n(n-2) full adders, along with n half adders.
• The longest input-to-output path goes through n adders in the top row, n-1 adders in the bottom row, and n-3 adders in the middle row; this is called the critical path.

Sequential Circuit Multiplier

• Multiplication is performed as a series of n conditional addition and shifts.
• If the multiplier bit is 0, only a shift occurs.
• If the multiplier bit is 1, the partial products are added and a shift occurs.
• Sequential circuits use a single n-bit adder, unlike combinational array multipliers which require a large number of logic gates.
• Registers A and Q (concatenated) hold the partial product, while the multiplier bit generates the Add/Noadd signal.
• The multiplexer (MUX) selects 0 when the multiplier bit is 0 or the multiplicand when the bit equals 1, which is then added to the partial product.
• The product is computed in n cycles with the partial product growing one bit per cycle.
• The carry-out from the adder is stored in a flip-flop C.

Multiplication Algorithm

• The multiplier and multiplicand are loaded into registers Q and M, respectively; registers A and C are cleared to 0.
• Each cycle performs two steps:
  • If the LSB of the multiplier (qᵢ) equals 1, the control sequencer generates an Add signal to add the multiplicand (M) to register A, storing the result in A.
  • If qᵢ = 0, a Noadd signal is generated to maintain the previous value in register A.
• Registers C, A, and Q are right-shifted by 1 bit.

Multiplication of Signed Numbers

• Multiplication of 2’s-complement operands generates a double-length product.
• A negative multiplicand added to a partial product requires sign-bit extension to the product's full length.
• A straightforward approach for a negative multiplier is to take the 2's complement of both the multiplier and the multiplicand.
• Complementing both operands does not change the product's value or sign.
• A positive sign bit of 0 denotes a positive number, whereas a negative sign bit of 1 denotes a negative number.

Booth Algorithm

• Used for signed number multiplication
• The multiplicand is placed in the BR register, and the multiplier is placed in the QR register.
• The accumulator register AC and Qₙ₊₁ are initialized to 0.
• The sequence counter SC is initialized to n (number of bits).
• The values of Qₙ and Qₙ₊₁ are compared, and the following operations are performed:
  • 01 -> AC = AC + BR
  • 10 -> AC = AC + BR’ + 1
  • 00 -> No arithmetic operation
  • 11 -> No arithmetic operation
• An Arithmetic Shift Right (ASHR) operation is performed on AC and QR.
• The sequence counter SC is decremented by 1.
• The final product is stored in AC and QR.

Features of the Booth Algorithm

• The Booth algorithm works well for both negative and positive multipliers.
• It handles signed multiplication and speeds up the multiplication process.

Booth Recording of a Multiplier

• In the Booth algorithm, multiplying by -1 involves a shift of the multiplicand and is selected when moving from 0 to 1.
• Multiplying by +1 involves a shift of the multiplicand and is selected when moving from 1 to 0, as the multiplier is scanned from right to left.
• The least significant bit (LSB) of the multiplier is handled by assuming that an implied 0 lies to its right.
• Having a worst-case multiplier means that numbers of addition and subtraction operations are large.
• In an ordinary multiplier, 0 indicates no operation, but addition and subtraction operations still occur.
• A good multiplier consists of a block/sequence of 1s.
• The best case involves a long string of 1s (skipping over 1s).
• The worst case involves alternating 0s and 1s.
• The transformation 011....110 to 100....0-10 is called skipping over 1s.

Integer Division

• Binary division is similar to calculation, with the quotient bits being 0 and 1.
• A circuit implements division, positioning the divisor appropriately and performing subtraction.
• If the remainder is zero or positive, the quotient bit is 1, and the remainder is extended with another bit of the dividend.
• The divisor is repositioned, and another subtraction is performed.
• If the remainder is negative, the quotient bit is 0, the dividend is restored by adding back the divisor, and the divisor is repositioned for another subtraction; this is the restoring division algorithm.
• An n-bit positive divisor and dividend are loaded into registers M and Q, respectively, with register A initially set to 0.
• After division, the n-bit quotient is in register Q and the remainder in register A.

Restoring Division Algorithm

• An n-bit positive divisor is loaded into register M, and an n-bit positive dividend is loaded into register Q; register A is set to 0.
• After division, the n-bit quotient is in register Q, and the remainder is in register A.
• The following steps are performed n times:
  • Shift A and Q left one bit position.
  • Subtract M from A (A-M) and place the answer back in A.
  • If the sign of A is 1, set q₀ to 0 and add M back to A (restore A); otherwise, set q₀ to 1.

Pipelining

• Pipelining decomposes a sequential process into sub-operations, each executed in a dedicated segment concurrently with others.
• A pipeline is visualized as a collection of processing segments for binary information flow.
• Each segment performs partial processing based on task partitioning, transferring results to the next segment.
• The final result is obtained after data passes through all segments.
• A pipeline processor can execute each instruction in 4 steps:
  • Fetch: Read the instruction from the memory.
  • Decode: Decode the instruction and fetch the source operands.
  • Execute: Perform the operation specified by the instruction.
  • Write: Store the result in the destination location.
• Four distinct hardware units are needed to allow four instructions to progress at any given time.
• Units must perform tasks simultaneously without interference, passing information via storage buffers.
• As an instruction progresses through the pipeline, needed information is passed by stages downstream.

Pipeline Organization

• Each segment consists of an input register followed by a combinational circuit.
• The register stores data, and the combinational circuit performs the sub-operation.
• The combinational circuit's output is applied to the next segment's input register.
• A clock is applied to registers after enough time has passed for all segment activity.
• Data flows through the pipeline one step at a time.
• Registers receive new data with every clock pulse.

Four Segment Pipeline

• Operands pass through all four segments in a fixed sequence.
• Each segment contains a combinational circuit that performs a sub-operation on the data stream.
• Registers separate segments, holding intermediate results between stages.
• Information flows between adjacent stages under a common clock control applied to all registers simultaneously.

Space-Time Diagram

• Illustrates pipeline behavior, showing segment utilization over time.
• The horizontal axis represents time in clock cycles, and the vertical axis represents the segment number.
• It takes three clock pulses to fill the pipe and retrieve the first output.

Pipeline Performance

• For a k-segment pipeline executing n tasks with a clock cycle time tp, the first task requires ktp to complete.
• The remaining n-1 tasks emerge at a rate of one task per clock cycle and are completed after (n-1)tp.
• Completing n tasks using a k-segment pipeline requires k + (n - 1) clock cycles.

Speedup

• S = nt n/(k+n-1)*tp, where t n is the time to complete each task with a non-pipelined unit
• As n increases, the speedup ratio approaches S = t n/t p.
• Assuming processing time is the same in pipeline and non-pipeline circuits (t n = kt p), the speedup reduces to S = k.

Classification of Pipeline Processors

• Arithmetic pipelining: Arithmetic logic units are segmented for pipeline operations across various data formats.
• Instruction pipelining: The execution of a stream of instructions is pipelined by overlapping execution, fetch, and decode; this is known as instruction lookahead.
• Processor pipelining: A cascade of processors processes the same data stream, each performing a specific task, with data stored and accessible by subsequent processors.

Arithmetic Pipelines

• Break down arithmetic operations into sub-operations for execution in pipeline segments.
• They are commonly found in high-speed computers.
• They are used to implement floating-point operations, multiplication of fixed-point numbers, and similar computations for scientific problems.

Pipeline Unit for Floating-Point Addition and Subtraction

• Inputs are two normalized floating-point binary numbers: X = A * 2ª and Y = B * 2b
• Floating-point addition and subtraction are performed in four segments:
  • Compare the exponents.
  • Align the mantissa.
  • Add or subtract the mantissas.
  • Normalize the result.
• The exponents are compared by subtracting to determine their difference with the larger exponent of the chosen result.
• The exponent difference determines how many times the mantissa associated with the smaller exponent must be shifted to the right to align the mantissas.
• The two mantissas are added or subtracted in segment 3, and the result is normalized in segment 4.
• Overflow: When the result is larger in magnitude than the largest floating-point number that can be stored.
• Underflow: When the result is smaller in magnitude than the smallest floating-point number that can be stored.

Instruction Pipeline

• Operates on a stream of instructions by overlapping the instruction cycle's phases (fetch, decode, execute).
• An instruction pipeline reads consecutive instructions while previous ones are executed, enabling simultaneous operations.
• A computer is designed with instruction fetch and execute units to provide a two-segment pipeline implemented using a FIFO buffer.
• While execution is not using memory, consecutive instructions are read via an incremented program counter and placed in the FIFO buffer for execution on a first-in, first-out basis.

Four-Segment Instruction Pipeline

• Fetch the instruction (FI)
• Decode the instruction (DA) and calculate the effective address.
• Fetch the operands from memory (FO).
• Execute the instruction (EX).
• The clock is divided into steps of equal duration
• FI is the segment that fetches the instruction
• DA is the segment that decodes the instruction and calculates the effective address
• FO is the segment that fetches the operand
• EX is the segment that executes the instruction

Pipeline Conflicts

• Resource Conflicts: Caused by memory access by two segments simultaneously; resolved by using separate instruction and data memories.
• Data Dependency: Occurs when an instruction relies on a previous instruction's result but the result is unavailable.
• Branch Difference: Results from branch instructions that change the program counter's value.

Pipeline Hazards

• Caused by resource usage conflicts among instructions.
• Triggered by inter-instruction dependencies when successive instructions overlap fetch, decode, and execution.
• Inter-instruction dependencies prevent sequential data flow in the pipeline.
• Hazards can lead to the pipeline inter-locking.
• Three classes of data-dependent hazards exist:
  • Write After Read (WAR) hazards occur.
  • Read After Write (RAW) hazards occur.
  • Write After Write (WAW) hazards occur.
• Read After Read does not pose a problem.

Resources, Objects, and Hazards

• Resource object: Refers to working registers, memory locations, and special flags whose contents are called data objects.
• Instruction: A mapping from a set of data objects to another set.
• The domain D(I) of instruction I is a set of resource objects whose data objects may affect I's execution.
• The range R(I) is the set of resource objects whose data objects may be modified by the execution of I.
• Hazard Types and Resolution
  • RAW hazard: Instruction J attempts to read a data object modified by instruction I.
  • WAR hazard: Instruction J attempts to modify a data object read by instruction I.
  • WAW hazard: Both instructions I and J attempt to modify the same data object.
• A short-circuiting approach gives the instruction waiting to read a copy of the data object to be written.
• Data forwarding forwards multiple data copies to waiting instructions.