Chapter 3

Size: px

Start display at page:

Download "Chapter 3"

歹孙
5 years ago
Views:

1 Chapter 3 Arithmetic for Computers 陳瑞奇 (J.C. Chen) 亞洲大學資訊工程學系 Adapted from class notes by Prof. C.T. King, NTHU, Prof. M.J. Irwin, PSU and Prof. D. Patterson, UCB 3.2 Addition & Subtraction p.67 ( 頁 69) Subtraction Addition 3. Fig. 3. 7

... Review: A Full Adder A B carry_in -bit Full Adder carry_out S A B carry_in carry_out S S = A B carry_in (odd parity function) carry_out = A&B A&carry_in B&carry_in How can we use it to build a

2 ... Review: A Full Adder A B carry_in -bit Full Adder carry_out S A B carry_in carry_out S S = A B carry_in (odd parity function) carry_out = A&B A&carry_in B&carry_in How can we use it to build a 32-bit adder? How can we modify it easily to build an adder/subtractor? 9 A 32-bit Ripple Carry Adder/Subtractor Remember 2 s complement is just complement all the bits control (=add,=sub) B if control = B,!B if control = add a in the least significant bit A B - + add/sub B B B 2 B 3 A A A 2 A 3 c =carry_in -bit FA S c -bit FA S c 2 -bit FA S 2 c 3 = A - B c 3 -bit FA S 3 c 32 =carry_out

Overflow Detection Overflow: the result is too large to represent in 32 bits http://images.digopaul.com/wpcontent/uploads/related_images/25/9/8/overflow_.

3 Overflow Detection Overflow: the result is too large to represent in 32 bits Overflow occurs when adding two positives yields a negative or, adding two negatives gives a positive or, subtract a negative from a positive gives a negative or, subtract a positive from a negative gives a positive Overflow Detection (cont.) Overflow: the result is too large to represent in 32 bits No overflow when adding a positive and a negative number No overflow when signs are the same for subtraction On your own: Prove you can detect overflow by: Carry into MSB xor Carry out of MSB, ex for 4 bit signed numbers

4 Overflow Detection (cont.) 3 Overflow Conditions p.68 ( 頁 7) 3.2 Overflow occurs when adding two positives yields a negative or, adding two negatives gives a positive or, subtract a negative from a positive gives a negative or, subtract a positive from a negative gives a positive 4

5 3.3 Multiplication p.7 ( 頁 73) Unsigned multiply example : () 2 x () 2 : x Multiplicand Multiplier Example. () 2 x () 2 : x Binary multiplication is just a bunch of left shifts and adds 2 7 Multiplication (cont.) Binary multiplication is just a bunch of left shifts and adds n multiplicand multiplier n 2n partial product array can be formed in parallel and added in parallel for faster multiplication double precision product 2

6 Multiplication (cont.) More complicated than addition accomplished via shifting and addition More time and more area Let's look at 3 versions based on a gradeschool algorithm (multiplicand) x_ (multiplier) Negative numbers: convert and multiply there are better techniques, we won t look at them 22 Multiplication: Implementation p ( 頁 75-76) x Multiplicand 64 bits Control (Fig. 3.4) Shift left Multiplier = a. Add multiplicand to product and place the result in Product register Datapath (Fig. 3.3) Start. Test Multiplier Multiplier = 2. Shift the Multiplicand register left bit 3. Shift the Multiplier register right bit First version 64-bit ALU Multiplier Shift right 32 bits 32nd repetition? No: < 32 repetitions Product 64 bits Write X Control test Done! Done Yes: 32 repetitions 23

MIPS Multiply Instruction Multiply produces a double precision product mult $t, $t2 # hi lo=$t * $t2 move from register Lo 26 MIPS Multiply Instruction (cont.

7 MIPS Multiply Instruction Multiply produces a double precision product mult $t, $t2 # hi lo=$t * $t2 move from register Lo 26 MIPS Multiply Instruction (cont.) Multiply produces a double precision product mult $s, $s # hi lo = $s * $s op rs rt rd shamt funct p.8( 頁 78) Low-order word of the product is left in processor register lo and the high-order word is left in register hi Instructions mfhi rd and mflo rd are provided to move the product to (user accessible) registers in the register file Multiplies are done by fast, dedicated hardware and are much more complex (and slower) than adders Hardware dividers are even more complex and even slower 27

8 3.4 Division Division is just a bunch of quotient digit guesses and right shifts and subtracts Dividend = Quotient X Divisor + Remainder (n + ) n n quotient divisor dividend (2n ) (2n) partial remainder array n remainder 28 Division: First version Fig. 3.8 p.78 ( 頁 8) p. 86( 頁 83) Subtract Add 33 repetitions =#dividend - #divisor + =

MIPS Divide Instruction Divide generates the reminder in hi and the quotient in lo Quotient div $s, $s # lo = $s / $s # hi = $s mod $s Remainder op rs rt rd shamt funct Instructions mfhi rd and mflo

9 MIPS Divide Instruction Divide generates the reminder in hi and the quotient in lo Quotient div $s, $s # lo = $s / $s # hi = $s mod $s Remainder op rs rt rd shamt funct Instructions mfhi rd and mflo rd are provided to move the quotient and reminder to (user accessible) registers in the register file As with multiply, divide ignores overflow so software must determine if the quotient is too large. Software must also check the divisor to avoid division by. 32 MIPS Multiply/Divide Summary Move To register Lo 33

10 MIPS Multiply/Divide Summary (cont.) p.83 ( 頁 87) Fig Floating Point (a brief look) We need a way to represent numbers with fractions, e.g., 3.46 very small numbers, e.g.,. very large numbers, e.g., Representation: sign, exponent, significand: ( ) sign significand 2 exponent more bits for significand gives more accuracy more bits for exponent increases range IEEE 754 floating point standard: single precision: 8 bit exponent, 23 bit significand double precision: bit exponent, 52 bit significand 35

11 Representing Big (and Small) Numbers What if we want to encode the approx. age of the earth? 4,6,, or 4.6 x 9 or the weight in kg of one a.m.u. (atomic mass unit).66 or.6 x -27 There is no way we can encode either of the above in a 32-bit integer. Floating point representation (-) sign x F x 2 E Still have to fit everything in 32 bits (single precision) s E (exponent) F (fraction) bit 8 bits 23 bits The base (2, not ) is hardwired in the design of the FPALU More bits in the fraction (F) or the exponent (E) is a trade-off between precision (accuracy of the number) and range (size of the number) 36 IEEE 754 FP Standard 錙銖必較 Sign and magnitude representation s hidden bit (-) * (+Significand) * 2 Single precision Double precision S Exponent -bit -bit S Exponent Significand -bit 8-bit 23-bit Significand 52-bit 64 bits E 32 bits eg.,.=.x2 - =.x2-2 Overflow( 溢位 )/Underflow( 短值 ) 是由於指數太大 / 太小而無法在指數欄位上表示出來 23 37

12 IEEE 754 FP Standard (cont.) IEEE 754 的偏差值 (Bias) 在單精度方面為 27, 在倍精度方面為 23 S E (-) * (+Significand) * 2 Exponent = E + bias E = Exponent - bias S Exponent Significand -bit 8-bit 23-bit E Bias 27 Exponent 大小比較大小大加減運算指數遞增減正規化 39

13 IEEE 754 FP Standard (cont.) p.89 ( 頁 93) 範例以 IEEE 754 二進位表示法, 說明十進位 2.75 的單精度及倍精度的格式» 解答 = (.) 2 = (.) 2 * 2 4 單精度 : hidden bit = (3) (7 s ) 2 連除 2 可以得到二進位整數部分.75 連乘 2 可以得到二進位小數部分 4 IEEE 754 FP Standard (cont.) p.89 ( 頁 93) 範例以 IEEE 754 二進位表示法, 說明十進位 -.75 的單精度及倍精度的格式» 解答 = -(.) 2 = -(.) 2 * 2 - 單精度 : hidden bit (26) (22 s ) = ( ) 27 = - 倍精度 : (22) ( ) 23 =

14 Fig. B.. $f $f $f3 MIPS R2 CPU and FPU 47 MIPS Floating Point Instructions MIPS has a separate Floating Point Register File ($f, $f,, $f3) (whose registers are used in pairs for double precision values) with special instructions to load to and store from them lwcl $f,54($s2) #$f = Memory[$s2+54] swcl $f,58($s4) #Memory[$s4+58] = $f From/To coprocessor And supports IEEE 754 single add.s $f2,$f4,$f6 #$f2 = $f4 + $f6 and double precision operations add.d $f2,$f4,$f6 #$f2 $f3 = $f4 $f5 + $f6 $f7 similarly for sub.s, sub.d, mul.s, mul.d, div.s, div.d 48

15 p.2( 頁 26) Fig. 3.7 單精準度 (Single precision) 倍精準度 (Double precision) #$f2 $f3 =$f4 $f5 + $f6 $f7 5 Chapter 3 Exercises: 3.3 將 5ED4 轉換為二進制表示的數字是什麼理由使得十六進制成為表示計算機中數值的常用數字系統? 3.22 若位元樣式 xc 是浮點數, 則代表的十進制數字是什麼? 假設使用的表示法是 IEEE 754 標準 3.23 寫出十進制的二進制 IEEE 754 單精確度格式表示法 3.4 以 IEEE 754 哪些種浮點格式寫出可代表 -/4 的位元樣式你可以完全準確地表示 -/4 嗎? 3.43 假設浮點格式的分數部分是以二進數字表示, 寫出 /3 的分數值的位元樣式假設分數部分有 24 個位元, 且結果不需做正規化這個結果完全準確嗎? 63

16 練習 3( 第 3 章 ) 不用交作業, 純練習, 可能有包含期中考類似題 64

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