Microsoft PowerPoint - chap3.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - chap3.ppt"

另雷
5 years ago
Views:

1 微算機系統第三章 Arithmetic for Computers 陳伯寧教授電信工程學系國立交通大學 chap3-1 Arithmetic Where we've been: Abstractions: Instruction Set Architecture Assembly Language and Machine Language What's up ahead: Implementing the Architecture operation a b ALU 32 result chap3-2

2 Numbers Bits are just bits (no inherent meaning) conventions define relationship between bits and numbers Binary numbers (base 2) decimal: n 1 chap3-3 Numbers Of course it gets more complicated in real computers: numbers are finite (can possibly overflow) fractions and real numbers negative numbers e.g., no subi instruction in MIPS; it can be done by using addi since addi can add a negative number. How do we represent negative numbers in computer system? chap3-4

3 Possible representations Provide +0 and 0 Sign Magnitude: 1's Complement 2's Complement 000 = = = = = = = = = = = = = = = = = = = = = = = = 1 Sign bit How 2 s complement gets its name? (+x) 2 s complement +(-x) 2 s complement =2 n chap3-5 Possible representations Issues: Balance: 2 s complement only provides 4 but no 4. Number of zeros: Sign decision: Ease of hardware implementation: chap3-6

4 MIPS 32 bit signed numbers in 2 s complement representation: maxint minint two = 0 ten two = + 1 ten two = + 2 ten two = + 2,147,483,646 ten two = + 2,147,483,647 ten two = 2,147,483,648 ten two = 2,147,483,647 ten two = 2,147,483,646 ten two = 3 ten two = 2 ten two = 1 ten chap3-7 Two s complement operation shortcuts Negation shortcut Negating a two's complement number: invert all bits and add 1 Remember: negate and invert are quite different! Sign extension shortcut Sign extension of 2 s complement numbers Converting n-bit numbers into numbers with more than n bits: copy the most significant bit (the sign bit) into the other bits > > > > -6 chap3-8

5 lb versus lbu lb = load byte as a signed number treats the byte as a signed number, and hence sign-extend to fill the 24 left-most bits of the register lbu = load byte as an unsigned number hence, sign extension is not performed chap3-9 Bounds check shortcut Bounds check shortcut Use to check whether index-out-of-bound occurs or not sltu $t0, $a1, $t2; $t0=1 if 0<=$a1<$t2 beq $t0, $zero, Error; if bad, goto Error. chap3-10

6 Addition & subtraction of 2 s complements Two's complement operations make it easy Subtraction using addition of negative numbers chap3-11 Addition & subtraction of 2 s complements Overflow (result too large for finite computer word): e.g., adding two n-bit numbers does not yield an n-bit number chap3-12

7 How to detect overflow? No overflow when adding a positive and a negative number No overflow when signs are the same for subtraction Overflow occurs when the value affects the sign: Overflow when adding two positives yields a negative or, adding two negatives gives a positive or, subtract a negative from a positive and get a negative or, subtract a positive from a negative and get a positive chap3-13 How to detect overflow? (+) + (+) -> (-) (+) + (-) -> (no overflow) (-) + (+) -> (no overflow) (-) + (-) -> (+) (+) - (+) -> (no overflow) (+) - (-) -> (-) (-) - (+) -> (+) (-) - (-) -> (no overflow) chap3-14

8 Effects of overflow MIPS detects overflow with an exception (sometimes, called interrupt in other instruction set design). Control jumps to predefined address for exception Interrupted address is saved for possible resumption MIPS includes a register called the exception program counter (EPC) to contain the address of the instruction that caused the exception. The instruction mfc0 (move from system control) is used to copy EPC into a general-purpose register so that MIPS software has the option of returning to the offending instruction via a jump register instruction. mfc0 $k0, $epc; $k0=$epc chap3-15 Signed and unsigned operations Other sign and unsigned operations are: slt, slti, add, addi sltu, sltiu, addu, addiu (no overflow detection for the last two instructions) Notably, addiu also sign-extends its 16-bit immediate to 32- bit, when performing addition with a 32-bit register. This is because in its design, the immediate can be negative! So addiu is only an addi counterpart that ignores overflow detection. chap3-16

9 Multiplication More complicated than addition Accomplished via shifting and addition More time and more area Let's look at 3 versions based on grade school algorithm 0010 (multiplicand) 1011 (multiplier) Negative numbers: Convert and multiply There are better techniques. We however won t look at them. chap3-17 Sequential version of multiplication hardware Multiplicand Shift left 64 bits 64-bit ALU Multiplier Shift right 32 bits Product 64 bits Write Control test chap3-18

10 Sequential implementation Multiplier0 = Bit 0 of Multiplier Register Multiplier0=1 Start 1. Test Multiplier0 Multiplier0=0 1a. Add multiplicand to product and Place the result in Product register 2. Shift the Multiplicand register left 1 bit 3. Shift the Multiplier register right 1 bit Question: Is implementation of 64-bit adder (ALU) necessary? 32nd repetition No: < 32 repetitions Yes: 32 repetitions Done chap3-19 Refined implementation Multiplicand 32 bits 32-bit ALU Multiplier Shift right 32 bits Shift right Product Write Control test 64 bits chap3-20

11 Refined implementation Multiplier0=1 Start 1. Test Multiplier0 Multiplier0=0 1a. Add multiplicand to the left half of the product and place the result in the left half of the Product register Question: Since the right 32-bit of the Product register is unused, can we place the multiplier in the space to save some implementation cost? 2. Shift the Product register right 1 bit 3. Shift the Multiplier register right 1 bit 32nd repetition? No: < 32 repetitions Yes: 32 repetitions Done chap3-21 Further improvement Multiplicand 32 bits 32-bit ALU Shift right Product Write 64 bits Multiplier Control test chap3-22

12 Further improvement Product0 = 1 Start 1. Test Product0 Product0 = 0 1a. Add multiplicand to the left half of the product and place the result in the left half of the Product register 2. Shift the Product register right 1 bit 32nd repetition? N0: < 32 repetitions Yes: 32 repetitions Done chap3-23 Fast multiplication hardware Can we unroll the 32 additions in the implementation of multiplication hardware? Notably, it required 32 clocks to finish a multiplication for sequential multiplier. chap3-24

13 Signed multiplication The previous multiplication hardware only deals with multiplication of positive numbers. To run the previous hardware 31 iterations, leaving the signs out of the calculation. Then, negate the product only if the original signs disagree. chap3-25 MIPS instructions for multiplication mult (multiply) and multu (multiply unsigned) MIPS provides a separate pair of 32-bit registers to contain the 64-bit product, called Hi and Lo. The programmer can use mflo (move from lo) and mfhi (move from hi) to place the product into normal 32-bit registers. chap3-26

14 Division Divisor Quotient Dividend Remainder chap3-27 chap4-27 Division chap3-28

Hence, we have the revised implementation in the next slide.

15 Division Initial values This step is redundant, because Rem < 0 always. Again, shift the divisor right = shift the remainder left. Hence, we have the revised implementation in the next slide. chap3-29 Division: Revised implementation Again, we can combine the Quotient and Remainder into one register. chap3-30

16 Division: Further enhanced implementation See the next slide. chap3-31 Division: Further enhanced implementation chap3-32

17 Signed division Rule: The dividend and the remainder must coincide in their signs. ( + 7) ( + 2) = ( + 3)...( + 1) ( + 7) = ( + 2)( + 3) + ( + 1) ( 7) ( + 2) = ( 3)...( 1) ( 7) = ( + 2)( 3) + ( 1) ( + 7) ( 2) = ( 3)...( + 1) ( + 7) = ( 2)( 3) + ( + 1) ( 7) ( 2) = ( + 3)...( 1) ( 7) = ( 2)( + 3) + ( 1) So we only need to implement the first and third divisions,and use negation to obtain the results of the second and fourth divisions. chap3-33 Final note on multiplication and division We can use the same hardware structure to implement multiplication and subtraction, as long as the 32-ALU can do both addition and subtraction. The case of Divide by zero shall also be considered. div (divide) and divu (divide unsigned) (rs rt = lo hi) chap3-34

18 Floating point We need a way to represent numbers with fractions, e.g., very small numbers, e.g., very large numbers, e.g., x 10 9 Representation: sign, exponent, significand: ( 1) sign x significand x 2 exponent more bits for significand gives more accuracy more bits for exponent increases range chap3-35 Floating point IEEE 754 floating point standard: sign-and-magnitude representation single precision: 8 bit exponent, 23 bit significand double precision: 11 bit exponent, 52 bit significand Leading 1 bit of significand is implicit Exponent is biased to make sorting easier all 0s is smallest exponent all 1s is largest bias of 127 for single precision and 1023 for double precision summary: ( 1) sign x (1+significand) x 2exponent bias chap3-36

19 Single Precision Real Number Floating-point number (real number) short (4-byte) form : single precision 31 ~ ~ ~ 8 7 ~ 0 S bit (biased) exponent 23-bit mantissa/significand e.g., (12) 10 = (1100) 2 = ( ) S(ign) = 0B biased exponent = (127) 10 (bias) + (3) 10 = (130) 10 = 82H mantissa = , , B Hidden one bit chap3-37 Double Precision Real Number Floating-point number (real number) 63 ~ ~ ~ ~ 32 S bit exponent long (8-byte) form : double precision 31 ~ ~ ~ 8 7 ~ 0 52-bit mantissa/significand e.g., (12) 10 = (1100) 2 = ( ) S(ign) = 0B biased exponent = (1023) 10 (bias) + (3) 10 = (1026) 10 = 402H mantissa = , , ,..., B chap3-38

20 Exceptions to Real Number Note Having a separate sign bit facilitates the test of less than, greater than, or equal to zero. Placing the exponent before the significand, as well as biased exponent format, simplifies sorting of floatingpoint numbers. Zero all zeros format sigh bit can be either 1 or 0, which indicating 0 or +0. Infinity exponent = all ones mantissa = all zeros sign bit can be either 1 or 0, which indicating or +. chap3-39 Exceptions to Real Number Single precision Double precision Object represented Exponent Significand Exponent Significand ± Nonzero Anything Nonzero Anything 0 ± denormalized number ± floating-point number ± infinity 255 nonzero 2047 nonzero * denormalized = the leading bit in Significand is zero. NaN (Not a number) chap3-40

21 Floating-point operations Operations, such as additions, are somewhat more complicated In addition to overflow we can have underflow -Max -Min 0 Min Max - chap3-41 Floating-point complexity Accuracy can be a big problem IEEE 754 keeps two extra bits, guard and round four rounding modes always round up (toward + ) always round down (toward - ) truncate round to nearest even If the least significant bit retained in a halfway case would be odd, add one; if it s even, truncate. positive divided by zero yields infinity zero divide by zero yields not a number chap3-42

Example of Rounding with Guard Digits Assume three significant decimal digits. Add 2.34 10 0 and 2.51 10 2 2.3400 + 0.0251 2.

22 Example of Rounding with Guard Digits Assume three significant decimal digits. Add and (gr)=(0~49) round down, and (gr)=(51~99) round up, and (gr)=50 tie. Round to the nearest decimal number 2.37 round guard chap3-43 Floating-point addition chap3-44

23 Floating-point addition The two Signs should be sent to the Big ALU in case one of the operands is negative. (See Example on page 198) chap3-45 Floating-point multiplication chap3-46

24 More about IEEE 754 Implementing the standard can be tricky (complicated, e.g., both overflow and underflow need to be considered) Not using the standard can be even worse see text for description of 80x86 and Pentium bug! chap3-47 Floating-point instructions in MIPS Floating-point addition add.s $f2, $f4, $f6; single precision add.d $f2, $f4, $f6; double precision Note that $f0, $f1, $f2, are separate floating-point registers provided by MIPS, which can be load-and-stored by lwc1 and swc1. Floating-point subtraction, sub.s and sub.d Floating-point multiplication, mul.s and mul.d Floating-point division, div.s and div.d Floating-point comparison, c.x.s and c.x.d, where x = eq, neq, lt, le, gt and ge. Floating-point branch, bc1t (branch coprocessor true) and bc1f (branch coprocessor false) chap3-48

25 IA-32 stack structure The IA-32 floating-point architecture is different from all other computers in the world. Intel provided a stack architecture with its floating-point instructions Loads push numbers onto the stack Operations find operands in the two top elements of the stacks Stores can pop elements off the stack. As anticipated, floating-point performance of IA-32 family lagged far behind other computers. chap3-49 IA-32 stack structure In 2001, Intel adds 144 instructions with 8 SSE2 (Streaming SIMD Extension 2) registers that can be used for floating-point operands. AMD later expanded the register number to 16, as part of AMD64. Intel then re-labeled AMD64 as EM64T for its own use. In addition, EM64T can load or store 128-bit aligned data to the 128-bit SSE2 register (4 single-precisions or 2 double-precisions) in one instruction. This new architecture can then more than double performance over Intel s traditional stack architecture. chap3-50

26 Concluding remarks Computer arithmetic is constrained by limited precision So it is better to avoid adding a very big number to a very small number. ( ) = 1 but ( ) = 0; Bit patterns have no inherent meaning but standards do exist two s complement IEEE 754 floating point Computer instructions determine meaning of the bit patterns Performance and accuracy are important so there are many complexities in real machines (i.e., algorithms and implementation). chap3-51 Something to think about. Could the below statement be stopped by a divide-by-zero error? If (x == 0.0) y = 17.0 else y = z/x. Answer: Yes, because the examine of x == 0.0 and division of z/x are usually done separately from hardware aspect. Could overflow happen for y = z/x, if z is approximately equal to x? Answer: Yes, because some computers do y = z/x by y = z * (1/x); so if x is too small, 1/x can overflow. chap3-52

27 Suggestive exercises 3.1 ~ 3.12, 3.14, 3.27, 3.30 ~ 3.32, 3.34 ~ 3.40, 3.42 ~ 3.46 Should you have questions on exercises, you can ask the teaching assistants ( 助教 ). chap3-53

Microsoft PowerPoint - STU_EC_Ch02.ppt

Microsoft PowerPoint - STU_EC_Ch02.ppt 樹德科技大學資訊工程系 Chapter 2: Number Systems Operations and Codes Shi-Huang Chen Sept. 2010 1 Chapter Outline 2.1 Decimal Numbers 2.2 Binary Numbers 2.3 Decimal-to-Binary Conversion 2.4 Binary Arithmetic 2.5