COMPUTER ORGANIZATION AND DESIGNEdition

ARM

The Hardware/Software Interface

ARITHMETIC FOR
COMPUTERS
“There are 10 types of people in the
world, the ones who understand binary
and the ones who don’t.”
- Whatsapp Forward
 §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

Chapter 3 — Arithmetic for Computers — 2

 §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
Chapter 3 — Arithmetic for Computers — 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

Chapter 3 — Arithmetic for Computers — 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
• c.f. 2s-complement modulo arithmetic
• E.g., clipping in audio, saturation in video

Chapter 3 — Arithmetic for Computers — 5

How do we multiply?
•

Chapter 3 — Arithmetic for Computers — 6

 §3.3 Multiplication
Multiplication
• Start with long-multiplication approach

multiplicand
1000
multiplier
× 1001
1000
0000
0000
1000
product 1001000

Length of the
product is the sum of
operand lengths

Chapter 3 — Arithmetic for Computers — 7

Multiplication

Chapter 3 — Arithmetic for Computers — 8

Multiplication Hardware

Initially 0

Chapter 3 — Arithmetic for Computers — 9

 Optimized Multiplier
• Perform steps in parallel: add/shift

64

 One cycle per partial-product addition

 That’s ok, if frequency of multiplications is low
Chapter 3 — Arithmetic for Computers — 10
Faster Multiplier
(Thanks to Moore’s Law)
• Uses multiple adders
• Cost/performance tradeof

 Can be pipelined
 Several multiplication performed in parallel
Chapter 3 — Arithmetic for Computers — 11
LEGv8 Multiplication
• Three multiply instructions:
• MUL: multiply
• Gives the lower 64 bits of the product

• SMULH: signed multiply high

• Gives the higher 64 bits of the product, assuming the operands
are signed

• UMULH: unsigned multiply high

• Gives the higher 64 bits of the product, assuming the operands
are unsigned
Chapter 3 — Arithmetic for Computers — 12
 §3.4 Division
Division

1000 1001010

Chapter 3 — Arithmetic for Computers — 13

 §3.4 Division
Division • Check for 0 divisor
• Long division approach
quotient • If divisor ≤ dividend bits
dividend • 1 bit in quotient, subtract
1001 • Otherwise
1000 1001010 • 0 bit in quotient, bring down next dividend bit
-1000 • Restoring division
divisor
10
• Do the subtract, and if remainder goes < 0,
101
add divisor back
1010
-1000 • Signed division
remainder 10 • Divide using absolute values
• Adjust sign of quotient and remainder as
n-bit operands yield n-bit required
quotient and remainder

Chapter 3 — Arithmetic for Computers — 14

Division
Division Hardware
Initially divisor
in left half

Initially dividend
Chapter 3 — Arithmetic for Computers — 16
 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 — 17

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 — 18

LEGv8 Division
•Two instructions:
• SDIV (signed)
• UDIV (unsigned)

•Both instructions ignore overflow and

division-by-zero

Chapter 3 — Arithmetic for Computers — 19

 §3.5 Floating Point
Floating Point
•Representation for non-integral numbers
• Including very small and very large numbers

•Like scientific notation

• –2.34 × 1056
• +0.002 × 10–4
• +987.02 × 109

•In binary
• ±1.xxxxxxx2 × 2yyyy

•Types float and double in C

Chapter 3 — Arithmetic for Computers — 20

Floating Point Standard
•Defined by IEEE Std 754-1985
•Developed in response to divergence of
representations
• Portability issues for scientific code

•Now almost universally adopted

•Two representations
• Single precision (32-bit)
• Double precision (64-bit)

Chapter 3 — Arithmetic for Computers — 21

IEEE Floating-Point Format
single: 8 bits single: 23 bits
double: 11 bits double: 52 bits
S Exponent Fraction

x  ( 1)S  (1 Fraction)  2(ExponentBias)

Chapter 3 — Arithmetic for Computers — 22

IEEE Floating-Point Format

•S: sign bit (0  non-negative, 1  negative)

•Normalize significand: 1.0 ≤ |significand| < 2.0
• Always has a leading pre-binary-point 1 bit, so no
need to represent it explicitly (hidden bit)
• Significand is Fraction with the “1.” restored
•Exponent: excess representation: actual
exponent + Bias
• Ensures exponent is unsigned
• Single: Bias = 127; Double: Bias = 1023

Chapter 3 — Arithmetic for Computers — 23

Single-Precision Range
• Exponents 00000000 and 11111111 reserved
• Smallest value
• Exponent: 00000001
 actual exponent = 1 – 127 = –126
• Fraction: 000…00  significand = 1.0
• ±1.0 × 2–126 ≈ ±1.2 × 10–38

• Largest value
• exponent: 11111110
 actual exponent = 254 – 127 = +127
• Fraction: 111…11  significand ≈ 2.0
• ±2.0 × 2+127 ≈ ±3.4 × 10+38

Chapter 3 — Arithmetic for Computers — 24

Double-Precision Range
• Exponents 0000…00 and 1111…11 reserved
• Smallest value
• Exponent: 00000000001
 actual exponent = 1 – 1023 = –1022
• Fraction: 000…00  significand = 1.0
• ±1.0 × 2–1022 ≈ ±2.2 × 10–308

• Largest value
• Exponent: 11111111110
 actual exponent = 2046 – 1023 = +1023
• Fraction: 111…11  significand ≈ 2.0
• ±2.0 × 2+1023 ≈ ±1.8 × 10+308

Chapter 3 — Arithmetic for Computers — 25

 Reserved Words
Single Precision Double Precision Represents

Exponent Fraction Exponent Fraction

0 0 0 0 0

0 Nonzero 0 Nonzero Denormalized

255 0 2047 0 Inf

255 Nonzero 2047 Nonzero NaN

Chapter 3 — Arithmetic for Computers — 26

Floating-Point Precision
•Relative precision
• all fraction bits are significant
• Single: approx 2–23
• Equivalent to 23 × log102 ≈ 23 × 0.3 ≈ 6 decimal digits
of precision
• Double: approx 2–52
• Equivalent to 52 × log102 ≈ 52 × 0.3 ≈ 16 decimal digits
of precision

Chapter 3 — Arithmetic for Computers — 27

Floating-Point Example
•Represent –0.75
• –0.75 = (–1)1 × 1.12 × 2–1
•S = 1
• Fraction = 1000…002
• Exponent = –1 + Bias
• Single: –1 + 127 = 126 = 011111102
• Double: –1 + 1023 = 1022 = 011111111102

•Single: 1011111101000…00
•Double: 1011111111101000…00

Chapter 3 — Arithmetic for Computers — 28

Floating-Point Example
• What number is represented by the single-
precision float
11000000101000…00
•S = 1
• Fraction = 01000…002
• Fxponent = 100000012 = 129

• x = (–1)1 × (1 + 012) × 2(129 – 127)

= (–1) × 1.25 × 22
= –5.0

Chapter 3 — Arithmetic for Computers — 29

Denormal Numbers

•Exponent = 000...0  hidden bit is 0

x  ( 1)S  (0  Fraction)  2 Bias

 Smaller than normal numbers
 allow for gradual underflow, with
diminishing precision
 Denormal with fraction = 000...0
x  ( 1)S  (0  0)  2Bias  0.0
Two representations
of 0.0!

Chapter 3 — Arithmetic for Computers — 30

Infinities and NaNs
•Exponent = 111...1, Fraction = 000...0
• ±Infinity
• Can be used in subsequent calculations,
avoiding need for overflow check
•Exponent = 111...1, Fraction ≠ 000...0
• Not-a-Number (NaN)
• Indicates illegal or undefined result
• e.g., 0.0 / 0.0
• Can be used in subsequent calculations

Chapter 3 — Arithmetic for Computers — 31

Floating-Point Addition
• Consider a 4-digit decimal example
• 9.999 × 101 + 1.610 × 10–1

• 1. Align decimal points

• Shift number with smaller exponent
• 9.999 × 101 + 0.016 × 101

• 2. Add significands
• 9.999 × 101 + 0.016 × 101 = 10.015 × 101

• 3. Normalize result & check for over/underflow

• 1.0015 × 102

• 4. Round and renormalize if necessary

• 1.002 × 102

Chapter 3 — Arithmetic for Computers — 32

Floating-Point Addition
• Now consider a 4-digit binary example
• 1.0002 × 2–1 + –1.1102 × 2–2 (0.5 + –0.4375)

• 1. Align binary points

• Shift number with smaller exponent
• 1.0002 × 2–1 + –0.1112 × 2–1

• 2. Add significands
• 1.0002 × 2–1 + –0.1112 × 2–1 = 0.0012 × 2–1

• 3. Normalize result & check for over/underflow

• 1.0002 × 2–4, with no over/underflow

• 4. Round and renormalize if necessary

• 1.0002 × 2–4 (no change) = 0.0625
Chapter 3 — Arithmetic for Computers — 33
FP Adder Hardware
• Much more complex than integer adder

• Doing it in one clock cycle would take too long

• Much longer than integer operations
• Slower clock would penalize all instructions

• FP adder usually takes several cycles

• Can be pipelined

Chapter 3 — Arithmetic for Computers — 34

FP Adder Hardware

Step 1

Step 2

Step 3

Step 4

Chapter 3 — Arithmetic for Computers — 35

Floating-Point Multiplication
• Consider a 4-digit decimal example
• 1.110 × 1010 × 9.200 × 10–5

• 1. Add exponents
• For biased exponents, subtract bias from sum
• New exponent = 10 + –5 = 5

• 2. Multiply significands
• 1.110 × 9.200 = 10.212  10.212 × 105

• 3. Normalize result & check for over/underflow

• 1.0212 × 106

• 4. Round and renormalize if necessary

• 1.021 × 106

• 5. Determine sign of result from signs of operands

• +1.021 × 106

Chapter 3 — Arithmetic for Computers — 36

Floating-Point Multiplication
• Now consider a 4-digit binary example
• 1.0002 × 2–1 × –1.1102 × 2–2 (0.5 × –0.4375)

• 1. Add exponents
• Unbiased: –1 + –2 = –3
• Biased: (–1 + 127) + (–2 + 127) = –3 + 254 – 127 = –3 + 127

• 2. Multiply significands
• 1.0002 × 1.1102 = 1.110  1.1102 × 2–3
• 3. Normalize result & check for over/underflow
• 1.1102 × 2–3 (no change) with no over/underflow

• 4. Round and renormalize if necessary

• 1.1102 × 2–3 (no change)

• 5. Determine sign: +ve × –ve  –ve

• –1.1102 × 2–3 = –0.21875

Chapter 3 — Arithmetic for Computers — 37

FP Arithmetic Hardware
• FP multiplier is of similar complexity to FP adder
• But uses a multiplier for significands instead of an adder
• FP arithmetic hardware usually does
• Addition, subtraction, multiplication, division, reciprocal, square-root
• FP  integer conversion

• Operations usually takes several cycles

• Can be pipelined

Chapter 3 — Arithmetic for Computers — 38

Overflow/ Underflow
• Why do we need to care

• Sid Meier's Civilization

• Each Civilization given an aggression rating of 1-10.

• Reduced by 2 on researching democracy.

• India Starts with an initial rating of 1

• Underflow

Chapter 3 — Arithmetic for Computers — 39

FP Instructions in LEGv8
• Separate FP registers
• 32 single-precision: S0, …, S31
• 32 double-precision: DS0, …, D31
• Sn stored in the lower 32 bits of Dn

• FP instructions operate only on FP registers

• Programs generally don’t do integer ops on FP data, or
vice versa
• More registers with minimal code-size impact

• FP load and store instructions

• LDURS, LDURD
• STURS, STURD
Chapter 3 — Arithmetic for Computers — 40
FP Instructions in LEGv8
• Single-precision arithmetic
• FADDS, FSUBS, FMULS, FDIVS
• e.g., FADDS S2, S4, S6
• Double-precision arithmetic
• FADDD, FSUBD, FMULD, FDIVD
• e.g., FADDD D2, D4, D6
• Single- and double-precision comparison
• FCMPS, FCMPD
• Sets or clears FP condition-code bits

• Branch on FP condition code true or false

• B.cond

Chapter 3 — Arithmetic for Computers — 41

FP Example: °F to °C
• C code:
float f2c (float fahr)
{
return ((5.0/9.0)*(fahr - 32.0));
}
• fahr in S12, result in S0, literals in global memory
space,
• Floating point 5.0,9.0, 32.0 stored in array with base
address in X27

Chapter 3 — Arithmetic for Computers — 42

FP Example
• Compiled LEGv8 code:
f2c:
LDURS S16, [X27,#0] // S16 = 5.0 (5.0 in memory)
LDURS S18, [X27,#8] // S18 = 9.0 (9.0 in memory)
FDIVS S16, S16, S18 // S16 = 5.0 / 9.0
LDURS S18, [X27,#16] // S18 = 32.0
FSUBS S18, S12, S18 // S18 = fahr – 32.0
FMULS S0, S16, S18 // S0 = (5/9)*(fahr – 32.0)
BR LR // return

Chapter 3 — Arithmetic for Computers — 43

FP Example: Array Multiplication
• C = C +A × B
• All 32 × 32 matrices, 64-bit double-precision elements
• Addresses of a, b, c in X0, X1, X2, and
i, j, k in X19, X20, X21

Chapter 3 — Arithmetic for Computers — 44

FP Example: Array Multiplication
void mm (double a[][],
double b[][], double c[][])
{
int i, j, k;
for (i = 0; i<32; i = i + 1)
for (j = 0; j<32; j = j + 1)
for (k = 0; k< 32; k = k + 1)
c[i][j] = c[i][j]
+ a[i][k] * b[k][j];
}

Chapter 3 — Arithmetic for Computers — 45

 FP Example: Array Multiplication
LDI X10, 32 // X10 = 32 (row size/loop end)
LDI X19, 0 // i = 0; initialize 1st for loop
L1: LDI X20, 0 // j = 0; restart 2nd for loop
L2: LDI X21, 0 // k = 0; restart 3rd for loop
LSL X11, X19, 5 // X11 = i * 2^5 (size of row of c)
ADD X11, X11, X20 // X11 = i * size(row) + j
LSL X11, X11, 3 // X11 = byte offset of [i][j]
ADD X11, X0, X11 // X11 = byte address of c[i][j]
LDURD D4, [X11,#0] // D4 = 8 bytes of c[i][j]

Chapter 3 — Arithmetic for Computers — 46

 FP Example: Array Multiplication
L3: LSL X9, X21, 5// X9 = k * 2^5 (size of row of b)
ADD X9, X9, X20 // X9 = k * size(row) + j
LSL X9, X9, 3 // X9 = byte offset of [k][j]
ADD X9, X2, X9 // X9 = byte address of b[k][j]
LDURD D16, [X9,#0] // D16 = 8 bytes of b[k][j]
LSL X9, X19, 5 // X9 = i * 2^5 (size of row of a)
ADD X9, X9, X21 // X9 = i * size(row) + k
LSL X9, X9, 3 // X9 = byte offset of [i][k]
ADD X9, X1, X9 // X9 = byte address of a[i][k]
LDURD D18, [X9,#0] // D18 = 8 bytes of a[i][k]
FMULD D16, D18, D16 // D16 = a[i][k] * b[k][j]
FADDD D4, D4, D16// f4 = c[i][j] + a[i][k] * b[k]
[j]
Chapter 3 — Arithmetic for Computers — 47
FP Example: Array Multiplication
ADDI X21, X21, 1 // $k = k + 1
CMP X21, X10 // test k vs. 32
B.LT L3 // if (k < 32) go to L3
STURD D4, [X11,0] // = D4
ADDI X20, X20, #1 // $j = j + 1
CMP X20, X10 // test j vs. 32
B.LT L2 // if (j < 32) go to L2
ADDI X19, X19, #1 // $i = i + 1
CMP X19, X10 // test i vs. 32
B.LT L1 // if (i < 32) go to L1

Chapter 3 — Arithmetic for Computers — 48

Accurate Arithmetic
• IEEE Std 754 specifies additional rounding
control
• Adjust higher bits wrt the lower bits
• Extra bits of precision (guard, round, sticky)
• Choice of rounding modes
• Allows programmer to fine-tune numerical behavior of
a computation
• Accuracy measured in terms of the number of bits in
error wrt the lsb.

Chapter 3 — Arithmetic for Computers — 49

Accurate Arithmetic
• Not all FP units implement all options
• Most programming languages and FP libraries just use
defaults
• Trade-of between hardware complexity,
performance, and market requirements

Chapter 3 — Arithmetic for Computers — 50

 §3.6 Parallelism and Computer Arithmetic: Subword Parallelism
Subword Parallellism
•Graphics and audio applications can take
advantage of performing simultaneous operations
on short vectors
• Example: 128-bit adder:
• Sixteen 8-bit adds
• Eight 16-bit adds
• Four 32-bit adds

•Also called data-level parallelism, vector

parallelism, or Single Instruction, Multiple Data
(SIMD)
•Carry Chains are split

Chapter 3 — Arithmetic for Computers — 51

ARMv8 SIMD
• 32 128-bit registers (V0, …, V31)

• Works with integer and FP

• Examples:
• 16 8-bit integer adds:
• ADD V1.16B, V2.16B, V3.16B

• 4 32-bit FP adds:
• FADD V1.4S, V2.4S, V3.4S

Chapter 3 — Arithmetic for Computers — 52

Other ARMv8 Features
• 245 SIMD instructions, including:
• Square root
• Fused multiply-add, multiply-subtract
• Convertion and scalar and vector round-to-integral
• Structured (strided) vector load/stores
• Saturating arithmetic

Chapter 3 — Arithmetic for Computers — 53

 §3.9 Fallacies and Pitfalls
Right Shift and Division
• Left shift by i places multiplies an integer by 2i
• Right shift divides by 2i?
• Only for unsigned integers

• For signed integers

• Arithmetic right shift: replicate the sign bit
• e.g., –5 / 4
• 111110112 >> 2 = 111111102 = –2
• Rounds toward –∞
• c.f. 111110112 >>> 2 = 001111102 = +62

Chapter 3 — Arithmetic for Computers — 54

Associativity
• Assumptions of associativity may fail

Chapter 3 — Arithmetic for Computers — 55

Who Cares About FP Accuracy?
•Important for scientific code
• But for everyday consumer use?
• “My bank balance is out by 0.0002¢!” 

•The Intel Pentium FDIV bug

• The market expects accuracy
• See Colwell, The Pentium Chronicles

Chapter 3 — Arithmetic for Computers — 56

 §3.9 Concluding Remarks
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 — 57

Concluding Remarks
•ISAs support arithmetic
• Signed and unsigned integers
• Floating-point approximation to reals

•Bounded range and precision

• Operations can overflow and underflow

Chapter 3 — Arithmetic for Computers — 58

Practice Problems
• 3.15, 16, 17, 20-29, 47

Chapter 3 — Arithmetic for Computers — 59