Arithmetic Operations for Computers

undefined
 
Arithmetic for Computers
 
Chapter 3
 
1
 
Arithmetic for Computers
 
Operations on integers
Addition and subtraction
Multiplication and division
Dealing with overflow
Floating-point real numbers
Representation and operations
§3.1 Introduction
 
2
 
Integer Addition
 
Example: 7 + 6
§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
 
3
 
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
 
4
 
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 (positive or negative)
c.f. 2s-complement modulo arithmetic
E.g., clipping in audio, saturation in video
 
5
 
Multiplication
 
Start with long-multiplication approach
Length of product is
the sum of operand
lengths
multiplicand
multiplier
product
§3.3 Multiplication
 
6
 
Multiplication Hardware
Initially 0
 
7
 
Optimized Multiplier
 
Algorithm and hardware refined to take one clock cycle per step
Perform steps in parallel: add/shift
 
One cycle per partial-product addition
That’s ok, if frequency of multiplications is low
The hardware is usually further optimized to halve the width of the adder
and registers by noticing where there are unused portions of registers and
adders
 
8
 
Using 4-bit numbers to save space, multiply 2
ten
 × 3
ten
, or
0010
two
 × 0011
two
 
Multiplication - example
 
9
 
Faster Multiplier
 
Uses multiple adders
Cost/performance tradeoff
 
Can be pipelined
Several multiplication performed in parallel
 
10
 
LEGv8 Multiplication
 
Three multiply instructions:
MUL:  multiply
Gives the lower 64 bits of the product
 
SMULH:  signed multiply high
Gives the upper 64 bits of the product, assuming the operands are signed
 
UMULH:  unsigned multiply high
Gives the lower 64 bits of the product, assuming the operands are unsigned
 
11
 
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
 
        1001
1000 1001010
    -1000
        10
        101
        1010
       -1000
          10
 
n
-bit operands yield 
n
-bit
quotient and remainder
quotient
dividend
remainder
divisor
§3.4 Division
 
12
 
Division Hardware
Initially dividend
Initially divisor
in left half
 
13
 
Using a 4-bit version of the algorithm, divide 7
ten
 by 2
ten
, or 0000
0111
two
 by 0010
two
.
 
Divide - example
 
14
 
Optimized Divider
 
One cycle per partial-remainder subtraction
The speed-up comes from shifting the operands and the quotient
simultaneously with the subtraction.
This refinement halves the width of the adder and registers
Looks a lot like a multiplier!
Same hardware can be used for both
 
15
 
Remember the signs of the divisor and dividend and then
negate the quotient if the signs disagree
         -7 
 +2: quotient = -3
Remainder = (dividend – quotient x divisor) = -7 – (-3 x +2) = -1
        -7 
 +2: quotient = -3, remainder = -1
       +7 
 -2: quotient = -3, remainder = +1
       -7 
 -2: quotient = +3, remainder = -1
The correctly signed division algorithm negates the quotient if
the signs of the operands are opposite and makes the sign of
the nonzero remainder match the dividend
 
 
 
 
 
Signed Division
 
16
 
Faster Division
 
Can’t use parallel hardware as in multiplier
Subtraction is conditional on sign of remainder
Faster dividers (e.g. SRT division) generate multiple quotient
bits per step 
using a table lookup based on the upper bits of the
dividend and remainder
Still require multiple steps
The accuracy of this fast method depends on having proper values in
the lookup table
 
17
 
LEGv8 Division
 
Two instructions:
SDIV (signed)
UDIV (unsigned)
 
Both instructions ignore overflow and division-by-zero
LEGv8 software must check the divisor to discover division by 0
as well as overflow.
 
18
Slide Note
Embed
Share

The chapter delves into the fundamentals of arithmetic for computers, covering operations on integers, dealing with overflow, handling floating-point real numbers, and more. It explores addition, subtraction, multiplication, and division in detail, showcasing examples and techniques for efficient computation. Additionally, it discusses multimedia arithmetic operations on vectors and the process of multiplication, including hardware optimization strategies for efficient processing.

  • Arithmetic Operations
  • Computers
  • Integer Operations
  • Overflow Handling
  • Multimedia Arithmetic

Uploaded on Aug 14, 2024 | 4 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Chapter 3 Arithmetic for Computers 1

  2. 3.1 Introduction Arithmetic for Computers Operations on integers Addition and subtraction Multiplication and division Dealing with overflow Floating-point real numbers Representation and operations 2

  3. 3.2 Addition and Subtraction Integer Addition Example: 7 + 6 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 3

  4. 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 4

  5. 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 (positive or negative) c.f. 2s-complement modulo arithmetic E.g., clipping in audio, saturation in video 5

  6. 3.3 Multiplication Multiplication Start with long-multiplication approach multiplicand 1000 multiplier 1001 1000 0000 0000 1000 1001000 product Length of product is the sum of operand lengths 6

  7. Multiplication Hardware Initially 0 7

  8. Optimized Multiplier Algorithm and hardware refined to take one clock cycle per step Perform steps in parallel: add/shift One cycle per partial-product addition That s ok, if frequency of multiplications is low The hardware is usually further optimized to halve the width of the adder and registers by noticing where there are unused portions of registers and adders 8

  9. Multiplication - example Using 4-bit numbers to save space, multiply 2ten 3ten, or 0010two 0011two 9

  10. Faster Multiplier Uses multiple adders Cost/performance tradeoff Can be pipelined Several multiplication performed in parallel 10

  11. LEGv8 Multiplication Three multiply instructions: MUL: multiply Gives the lower 64 bits of the product SMULH: signed multiply high Gives the upper 64 bits of the product, assuming the operands are signed UMULH: unsigned multiply high Gives the lower 64 bits of the product, assuming the operands are unsigned 11

  12. 3.4 Division 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 quotient dividend 1001 1000 1001010 -1000 10 101 1010 -1000 10 remainder divisor n-bit operands yield n-bit quotient and remainder 12

  13. Division Hardware Initially divisor in left half Initially dividend 13

  14. Divide - example Using a 4-bit version of the algorithm, divide 7ten by 2ten, or 0000 0111two by 0010two. 14

  15. Optimized Divider One cycle per partial-remainder subtraction The speed-up comes from shifting the operands and the quotient simultaneously with the subtraction. This refinement halves the width of the adder and registers Looks a lot like a multiplier! Same hardware can be used for both 15

  16. Signed Division Remember the signs of the divisor and dividend and then negate the quotient if the signs disagree -7 +2: quotient = -3 Remainder = (dividend quotient x divisor) = -7 (-3 x +2) = -1 -7 +2: quotient = -3, remainder = -1 +7 -2: quotient = -3, remainder = +1 -7 -2: quotient = +3, remainder = -1 The correctly signed division algorithm negates the quotient if the signs of the operands are opposite and makes the sign of the nonzero remainder match the dividend 16

  17. Faster Division Can t use parallel hardware as in multiplier Subtraction is conditional on sign of remainder Faster dividers (e.g. SRT division) generate multiple quotient bits per step using a table lookup based on the upper bits of the dividend and remainder Still require multiple steps The accuracy of this fast method depends on having proper values in the lookup table 17

  18. LEGv8 Division Two instructions: SDIV (signed) UDIV (unsigned) Both instructions ignore overflow and division-by-zero LEGv8 software must check the divisor to discover division by 0 as well as overflow. 18

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#