Computer Architecture Chapter 3: Arithmetic for Computers Dr. Phạm Quốc Cường Adapted from Computer Organization the Hardware/Software Interface – 5th Computer Engineering – CSE – HCMUT 1 Arithmetic for Computers • Operations on integers – Addition and subtraction – Multiplication and division – Dealing with overflow • Floating-point real numbers – Representation and operations Chapter 3: Computer Arithmetic - Dr. Cuong 2 Pham-Quoc 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: Computer Arithmetic - Dr. Cuong 3 Pham-Quoc 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: Computer Arithmetic - Dr.
Cuong 4 Pham-Quoc Dealing with Overflow • Some languages (e., C) ignore overflow – Use MIPS addu, addui, subu instructions • Other languages (e., 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: Computer Arithmetic - Dr. Cuong 5 Pham-Quoc 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. 2s-complement modulo arithmetic – E., clipping in audio, saturation in video Chapter 3: Computer Arithmetic - Dr. Cuong 6 Pham-Quoc Multiplication • Start with long-multiplication approach multiplicand 1000 multiplier × 1001 1000 0000 0000 1000 product 1001000 Length of product is the sum of operand lengths Chapter 3: Computer Arithmetic - Dr.
Cuong 7 Pham-Quoc Multiplication Hardware Initially 0 Chapter 3: Computer Arithmetic - Dr. Cuong 8 Pham-Quoc Example • Using 4-bit numbers, multiply 210x310 Chapter 3: Computer Arithmetic - Dr. Cuong 9 Pham-Quoc Optimized Multiplier • Perform steps in parallel: add/shift • One cycle per partial-product addition – That’s ok, if frequency of multiplications is low Chapter 3: Computer Arithmetic - Dr. Cuong 10 Pham-Quoc Faster Multiplier • Uses multiple adders – Cost/performance tradeoff • Can be pipelined – Several multiplication performed in parallel Chapter 3: Computer Arithmetic - Dr.
Cuong 11 Pham-Quoc 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: Computer Arithmetic - Dr. Cuong 12 Pham-Quoc Division • Check for 0 divisor quotient • Long division approach dividend – If divisor ≤ dividend bits 1001 • 1 bit in quotient, subtract 1000 1001010 – Otherwise -1000 • 0 bit in quotient, bring down divisor next dividend bit 10 101 • Restoring division 1010 – Do the subtract, and if remainder goes < 0, add -1000 divisor back remainder 10 • Signed division – Divide using absolute values n-bit operands yield n-bit – Adjust sign of quotient and quotient and remainder remainder as required Chapter 3: Computer Arithmetic - Dr. Cuong 13 Pham-Quoc Division Hardware Initially divisor in left half Initially dividend Chapter 3: Computer Arithmetic - Dr. Cuong 14 Pham-Quoc Example • Using 4-bit numbers, let’s try dividing 710 by 210 Chapter 3: Computer Arithmetic - Dr.
Cuong 15 Pham-Quoc Optimized Divider • One cycle per partial-remainder subtraction • Looks a lot like a multiplier! – Same hardware can be used for both Dividend (initially) Reminder (finally) Quotient (finally) Chapter 3: Computer Arithmetic - Dr. Cuong 16 Pham-Quoc Faster Division • Can’t use parallel hardware as in multiplier – Subtraction is conditional on sign of remainder • Faster dividers (e. SRT division, use a backup table instead of restoring) generate multiple quotient bits per step – Still require multiple steps Chapter 3: Computer Arithmetic - Dr. Cuong 17 Pham-Quoc 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: Computer Arithmetic - Dr.
Cuong 18 Pham-Quoc Floating Point • Representation for non-integral numbers – Including very small and very large numbers • Like scientific notation normalized – –2.xxxxxxx2 × 2yyyy • Types float and double in C Chapter 3: Computer Arithmetic - Dr. Cuong 19 Pham-Quoc 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: Computer Arithmetic - Dr. Cuong 20 Pham-Quoc IEEE Floating-Point Format • S: sign bit (0 non-negative, 1 negative) • Normalize significand: 1.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 = 1203 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: Computer Arithmetic - Dr. Cuong 21 Pham-Quoc Single-Precision Range • Exponents 00000000 and 11111111 reserved • Smallest value – Exponent: 00000001 actual exponent = 1 – 127 = –126 – Fraction: 000…00 significand = 1.2 × 10–38 • Largest value – exponent: 11111110 actual exponent = 254 – 127 = +127 – Fraction: 111…11 significand ≈ 2.4 × 10+38 Chapter 3: Computer Arithmetic - Dr.
Cuong 22 Pham-Quoc Double-Precision Range • Exponents 0000…00 and 1111…11 reserved • Smallest value – Exponent: 00000000001 actual exponent = 1 – 1023 = –1022 – Fraction: 000…00 significand = 1.2 × 10–308 • Largest value – Exponent: 11111111110 actual exponent = 2046 – 1023 = +1023 – Fraction: 111…11 significand ≈ 2.8 × 10+308 Chapter 3: Computer Arithmetic - Dr. Cuong 23 Pham-Quoc 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: Computer Arithmetic - Dr. Cuong 24 Pham-Quoc Real to IEEE 754 Conversion • Step 1: Decide S • Step 2: Decide Fraction – Convert the integer part to Binary – Convert the fractional part to Binary – Adjust the integer and fractional parts according the Significand format (1.xxx) • Step 3: Decide exponent Chapter 3: Computer Arithmetic - Dr. Cuong 25 Pham-Quoc Floating-Point Example • Represent –0.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: Computer Arithmetic - Dr.
Cuong 26 Pham-Quoc 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.0 Chapter 3: Computer Arithmetic - Dr. Cuong 27 Pham-Quoc Infinities and NaNs • Exponent = 111.0 – ±Infinity – Can be used in subsequent calculations, avoiding need for overflow check • Exponent = 111.0 – Not-a-Number (NaN) – Indicates illegal or undefined result • e.0 – Can be used in subsequent calculations Chapter 3: Computer Arithmetic - Dr. Cuong 29 Pham-Quoc Floating-Point Addition • Consider a 4-digit decimal example – 9. Align decimal points – Shift number with smaller exponent – 9.
Normalize result & check for over/underflow – 1. Round and renormalize if necessary – 1.002 × 102 Chapter 3: Computer Arithmetic - Dr. Cuong 30 Pham-Quoc Floating-Point Addition • Now consider a 4-digit binary example – 1. Align binary points – Shift number with smaller exponent – 1.
Normalize result & check for over/underflow – 1.0002 × 2–4, with no over/underflow • 4. Round and renormalize if necessary – 1.0625 Chapter 3: Computer Arithmetic - Dr. Cuong 31 Pham-Quoc 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: Computer Arithmetic - Dr. Cuong 32 Pham-Quoc FP Adder Hardware Step 1 Step 2 Step 3 Step 4 Chapter 3: Computer Arithmetic - Dr.
Cuong 33 Pham-Quoc Floating-Point Multiplication • Consider a 4-digit decimal example – 1. Add exponents – For biased exponents, subtract bias from sum – New exponent = 10 + –5 = 5 • 2. Normalize result & check for over/underflow – 1. Round and renormalize if necessary – 1.
Determine sign of result from signs of operands – +1.021 × 106 Chapter 3: Computer Arithmetic - Dr. Cuong 34 Pham-Quoc Floating-Point Multiplication • Now consider a 4-digit binary example – 1. Add exponents – Unbiased: –1 + –2 = –3 – Biased: (–1 + 127) + (–2 + 127) = –3 + 254 – 127 = –3 + 127 • 2. Normalize result & check for over/underflow – 1.1102 × 2–3 (no change) with no over/underflow • 4.
Round and renormalize if necessary – 1. Determine sign: +ve × –ve –ve – –1.21875 Chapter 3: Computer Arithmetic - Dr. Cuong 35 Pham-Quoc 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: Computer Arithmetic - Dr. Cuong 36 Pham-Quoc FP Instructions in MIPS • FP hardware is coprocessor 1 – Adjunct processor that extends the ISA • Separate FP registers – 32 single-precision: $f0, $f1, … $f31 – Paired for double-precision: $f0/$f1, $f2/$f3, … • Odd-number registers: right half of 64-bit floating-point numbers • Release 2 of MIPs ISA supports 32 × 64-bit FP reg’s • 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 – lwc1, ldc1, swc1, sdc1 • e., ldc1 $f8, 32($sp) Chapter 3: Computer Arithmetic - Dr.
Cuong 37 Pham-Quoc FP Instructions in MIPS • Single-precision arithmetic – add.s $f0, $f1, $f6 • Double-precision arithmetic – add.d $f4, $f4, $f6 • Single- and double-precision comparison – c.d (xx is eq, lt, le, …) – Sets or clears FP condition-code bit • e.s $f3, $f4 • Branch on FP condition code true or false – bc1t, bc1f • e., bc1t TargetLabel Chapter 3: Computer Arithmetic - Dr. Cuong 38 Pham-Quoc FP Example: °F to °C • C code: float f2c (float fahr) { return ((5.