1 of 22

Arithmetic for computers�(integer)

Lars Ailo Bongo <larsab@cs.uit.no>

inf-2200, fall 2022

12.09.22

2 of 22

Arithmetic for Computers

  • Operations on integers
    • Addition and subtraction
    • Multiplication and division
    • Dealing with overflow
  • Floating-point real numbers
    • Later lecture

Chapter 3 — Arithmetic for Computers — 2

§3.1 Introduction

3 of 22

Our approach

  1. Barneskole algorithm…in binary
  2. Algorithm
  3. Overflow/ underflow issues
  4. Hardware implementation
  5. Optimizations

4 of 22

Integer Addition

  • Example: 7 + 6

Chapter 3 — Arithmetic for Computers — 4

§3.2 Addition and Subtraction

  • Overflow if result out of range
    • Adding +ve and –ve operands, no overflow
    • Adding two +ve operands
      • Overflow if result sign is 1
    • Adding two –ve operands
      • Overflow if result sign is 0

5 of 22

Integer Subtraction

  • Add negation of second operand
  • Example: 7 – 6 = 7 + (–6)

+7: 0000 0000 … 0000 0111�–6: 1111 1111 … 1111 1010�+1: 0000 0000 … 0000 0001

  • Overflow if result out of range
    • Subtracting two +ve or two –ve operands, no overflow
    • Subtracting +ve from –ve operand
      • Overflow if result sign is 0
    • Subtracting –ve from +ve operand
      • Overflow if result sign is 1

Chapter 3 — Arithmetic for Computers — 5

6 of 22

Overflow

How to deal with it?

  • in c?
  • in Python?

7 of 22

Dealing with Overflow

  • Some languages (e.g., C) ignore overflow
    • Use MIPS addu, addui, subu instructions
  • Other languages (e.g., Ada, Fortran) require raising an exception
    • Use MIPS add, addi, sub instructions
    • On overflow, invoke exception handler
      • Save PC in exception program counter (EPC) register
      • Jump to predefined handler address
      • mfc0 (move from coprocessor reg) instruction can retrieve EPC value, to return after corrective action

Chapter 3 — Arithmetic for Computers — 7

8 of 22

ALU

9 of 22

Optimization

10 of 22

Arithmetic for Multimedia

  • Graphics and media processing operates on vectors of 8-bit and 16-bit data
    • Use 64-bit adder, with partitioned carry chain
      • Operate on 8×8-bit, 4×16-bit, or 2×32-bit vectors
    • SIMD (single-instruction, multiple-data)
  • Saturating operations
    • On overflow, result is largest representable value
      • c.f. 2s-complement modulo arithmetic
    • E.g., clipping in audio, saturation in video

Chapter 3 — Arithmetic for Computers — 10

11 of 22

Multiplication

  • Start with long-multiplication approach

Chapter 3 — Arithmetic for Computers — 11

1000

× 1001

1000

0000

0000

1000

1001000

Length of product is the sum of operand lengths

multiplicand

multiplier

product

§3.3 Multiplication

12 of 22

Multiplication Hardware

Chapter 3 — Arithmetic for Computers — 12

Initially 0

13 of 22

Optimized Multiplier

  • Perform steps in parallel: add/shift

Chapter 3 — Arithmetic for Computers — 13

  • One cycle per partial-product addition
    • That’s ok, if frequency of multiplications is low

14 of 22

Faster Multiplier

  • Uses multiple adders
    • Cost/performance tradeoff

Chapter 3 — Arithmetic for Computers — 14

  • Can be pipelined
    • Several multiplication performed in parallel

15 of 22

MIPS Multiplication

  • Two 32-bit registers for product
    • HI: most-significant 32 bits
    • LO: least-significant 32-bits
  • Instructions
    • mult rs, rt / multu rs, rt
      • 64-bit product in HI/LO
    • mfhi rd / mflo rd
      • Move from HI/LO to rd
      • Can test HI value to see if product overflows 32 bits
    • mul rd, rs, rt
      • Least-significant 32 bits of product –> rd

Chapter 3 — Arithmetic for Computers — 15

16 of 22

Division

  • Check for 0 divisor
  • Long division approach
    • If divisor ≤ dividend bits
      • 1 bit in quotient, subtract
    • Otherwise
      • 0 bit in quotient, bring down next dividend bit
  • Restoring division
    • Do the subtract, and if remainder goes < 0, add divisor back
  • Signed division
    • Divide using absolute values
    • Adjust sign of quotient and remainder as required

Chapter 3 — Arithmetic for Computers — 16

§3.4 Division

17 of 22

Division Hardware

Initially dividend

Initially divisor in left half

18 of 22

Optimized Divider

  • One cycle per partial-remainder subtraction
  • Looks a lot like a multiplier!
    • Same hardware can be used for both

Chapter 3 — Arithmetic for Computers — 18

19 of 22

Faster Division

  • Can’t use parallel hardware as in multiplier
    • Subtraction is conditional on sign of remainder
  • Faster dividers (e.g. SRT devision) generate multiple quotient bits per step
    • Still require multiple steps

Chapter 3 — Arithmetic for Computers — 19

20 of 22

MIPS Division

  • Use HI/LO registers for result
    • HI: 32-bit remainder
    • LO: 32-bit quotient
  • Instructions
    • div rs, rt / divu rs, rt
    • No overflow or divide-by-0 checking
      • Software must perform checks if required
    • Use mfhi, mflo to access result

Chapter 3 — Arithmetic for Computers — 20

21 of 22

Concluding Remarks

  • Bits have no inherent meaning
    • Interpretation depends on the instructions applied
  • Computer representations of numbers
    • Finite range and precision
    • Need to account for this in programs

Chapter 3 — Arithmetic for Computers — 21

§3.10 Concluding Remarks

22 of 22

Concluding Remarks

  • ISAs support arithmetic
    • Signed and unsigned integers
    • Floating-point approximation to reals
  • Bounded range and precision
    • Operations can overflow and underflow
  • MIPS ISA
    • Core instructions: 54 most frequently used
      • 100% of SPECINT, 97% of SPECFP
    • Other instructions: less frequent

Chapter 3 — Arithmetic for Computers — 22