Computer Arithmetic ECE 645
Popular in Course
Popular in ELECTRICAL AND COMPUTER ENGINEERING
This 15 page Class Notes was uploaded by Antonina Wuckert on Monday September 28, 2015. The Class Notes belongs to ECE 645 at George Mason University taught by Staff in Fall. Since its upload, it has received 34 views. For similar materials see /class/215036/ece-645-george-mason-university in ELECTRICAL AND COMPUTER ENGINEERING at George Mason University.
Reviews for Computer Arithmetic
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
Lecture 1 1 Floating Point Operations MultiPrecision Arithmetic in Software Floating Point Operations No finite number system can represent all real numbers Various systems can be used for a subset of real numbers Fixedpoint w f low precision andor range Rational p q difficult arithmetic Floatingpoint is x be most common scheme Logarithmic logbx limiting case of floatingpoint Fixedpoint numbers x y 0000 0000 0000 1001two 1001 0000 0000 0000two Small number Large number Floating point numbers xsgtltbe or significand x baseexponent Two signs are involved in a floating point number 1 The significand or number sign usually represented by a separate sign bit 2 The exponent sign usually embedded in the biased exponent when the bias is a power of 2 the exponent sign is the complement of its MSB S K Sign inpon L39llI ig39 ml integer l ul39lcn i39cln cscnlul 1 1L unxigncd nluc in with u liiux Rnngc ilh 1 hih iihiil Zhiiiiii R Fig 171 Sigliil icuiid RL III39CNL illCd ux u l39ictiil3illl numlici islluib norinnlicd b sliii39ling m llml ihc MSB litmines lioncm in i39zuli I he I39iid lcntling I can liC mum ml In an unu hit this hit is knnnn l quothiddrn 1quot Typical floating point number format 7 nm FLPA min 0 min FLP mux gt 4 f Spm39ser Denser Delmar SWINE Neguti VL Positive vm lnw umbcrs lintlcr nw m39ml l lquot Over ow Region Regions chmn Fig 172 Subranges and special values in floatingpoint number representations Fig 173 The ANSIIEEE standard floatingpoint number representation formats Shim 324mg fcrmat 139 a bits 39 3923 bits tar fracnrenal pan bias 1275 plus hladen I In Intagerpan K 426 m 1quot i i i K Signl Exponent 1 Signi cand a aquot I t quot I 5K K r 5quot bits lor treat anal part H5 I 39 plus hidden 1 mintegerpart I Long 64bit format Sign Biased exponent Significde s if the l is hidden i I e bias I f I 32bit 8 bits bins 127 23l bits sillgleeprecisinn or short fm39mat 647bit ll bits bi219023 52l bits inubleprecisinn m39 long format Fig 173 The ANSIIEEE standard floatingpoint number representation formats Table 171 Some features of the ANSIIEEE standard floatingpoint number representation formats Feature Singler Short DoubleLong Word width bits 32 64 Significant bits 23 1 hidden 52 1 hidden Signi cend range 1 2 7 2231 1 2 e 252 Exponent bits 8 11 Exponent bias 127 1023 ZeroriO ebr as0f0 ebias0f0 Denorlnal 39 0 f D e 0 f 0 represents iOf 2 126 represents 0f 21022 Infinity 34 e bias 255 f 0 e bias 2047 f O Not avnurnber NaN 5 bias 255 f 0 e bias 2047 f 0 Ordinary number 6 bias 6 1 254 e bias E 1 2046 eE 71 6127 at 7102210231 represents 1f lt 29 represents 11 29 min 2126 a 12 y 1033 21022 2 22 10308 max 2728 34 1035 21024 16x10305 Exceptions divide by zero overflow underflow inexact result rounded value not same as original invalid operation examples include addition 00 00 multiplication O x 00 division 00 or so 00 square root operand lt O Operations on special operands Ordinary number 00 00 x Ordinary number NaN Ordinary number H H O H H 8 II 2 9 Z Fig 174 Denormals in the IEEE singleprecision format The IEEE floating point standard also defines The four basic arithmetic operations x and v must match the results that would be obtained if intermediate computations were infiniteprecision Extended formats for greater internal precision Single extended 211 bits for exponent 2 32 bits for significand bias unspecified but exp range 3 1022 1023 Doubleextended 2 15 bits for exponent 2 64 bits for significand exp range 3 1 6 382 16 383 ANSIIEEE standard includes four rounding modes Round to nearest even default mode Round toward zero inward Round toward 00 upward Round toward 00 downward nnerjx R lx l ai 4i 9quot 3 2 1 1 d 2 1 2 3 a 1 Fig 178 Rounding to the nearest even number Fig 173 R rounding or rounding to the nearest odd number We may need computation errors to be in a known direction Example in computing upper bounds larger results are acceptable but results that are smaller than correct values could invalidate the upper bound This leads to the definition of upwarddirected rounding round toward 00 and downwarddirected rounding round toward oo optional features of the IEEE floatingpoint standard Ltplx Multiplication S1xbe1 gtlt182be2 1 81 x82 x be1ez Postshifting for normalization exponent adjustment Overflowunderflow during multiplication or normalization Fig 185 Block diagram of a floatingpoint multiplier Fluulngpulm psi and I I eJJ Division 51xbe1s2gtltb92 3132gtltbe1 e2 Fig 186 Block diagram of a floatingpoint divider i imiug wm mums Qunlsenl AdditionSubtraction Assume e1 e2 need alignment shift or preshift if e1 gt e2 51 xbeissz62 si xbe1s2be1 92x be1 S1182be1e1 x be1 bee Like signs 1 digit normalizing right shift may be needed Different signs shifting by many positions may be needed Overflowunderflow during addition or normalization Fig 181 Block diagram of a floatingpoint addersubtractor x Operands y Unpack Sigrs Exponents sgni canaa Salad we complemerrl and possible swap Narmalize Lind an solemne ca n plemenl Sign Exponent Significand s SumDifference Fig 182 One bitslice of a singlestage preshi er MN m 1 1M 1M Fig 183 Fourstage combinational shi erfor preshi ing an operand by 0 to 15 bits u 1 10 1 u m m n aghah a aa aaaa s O O I i I l Fig 184 Leading zerosones counting versus prediction Arithmetic Operations in Software LittleEndian vs BigEndian Representation A0 B1C2D3 E4 F5 67 896 MSB LSB BigiEndian Lit eiEndian address LittleEndian vs BigEndian Camps 0 LSB address MSB MAX I I BigiEndian th eiEndlan anmla 633m 680m Bi Endim anmla iner PC Hawlaszdmd Sun SuperSPARC Internet TCP ZP LittleEndian vs BigEndian Origin of the terms Jonathan Swi Gulliver s Travels A law requiring all citizens ofLilliput to break their so eggs at the little ends only A civil war breaking between the Little Endians and the BigEndians resulting in the Big Endians taking refuge on anearby island the kingdom ofBlefuscu Satire overholy wars between protestant church ofEngland and the Catholic church omence LittleEndian vs BigEndian Advanmges and Disadvantages BigEndian LittleEndian easier 39 39 of Cain 39 the number numbers easier to compare two numbers 39 easie 39 i i routines especially addition and easier to divide two numbers multiplication easier to print Pointers 1 BigrE ndian Lit erEndian 0 int iptr iptr 8967 iptr 6789 address lerH MAX Pointers 2 BigiE ndian Lit eiEndian 0 lph 8967F5EA 1erE4F56789 address 1 MAX SOFTWARE NIULTIPLICATION 1wordlbytes7 b1ts MCMCH Mcu cm ZN bytes Zn words PaperiandiPencil Algorithm of Multiplication 1 Wurd bytes A bus A x HEM m B Assemun Zwmds 2qu D Aan In AoB AxBn D 2AxBxAan 3m Dz DzmAzBmAnzBmAman sz AzBmAxan AMER 2m cmxcmx cmcnwcmc cmcmc PapersandsPencil Algorithm of Squaring l Word llsytes 2t bits A X m A Assemun Zwmds stula DEM In DiZAoAi D2 ZAoAi Ai swan Zwards Dz Dm3 pm A zwan Cmilcml cnl cn cnl c cl c c PapersandsPencil Algorithm of Multiplication paparandrpennl ltNgt11Mlt1 E lt14 lgtgt N e operand length in bytes tM ls word length in bytes tA 7 time ofa single word addition PapersandsPencil Algorithm of Squaring E lt t mlt 5le paperrzndrpmcll 1 l 7 time ofa single word multiplication tA time ofa single word addition Forlargen l SQszperrzndrpmcll N L tMUL paparandrpennl Karamuba Algorithm of Multiplication Basic Recursive Step 1 Ewes v has 2 AAway 1202an x nwmds N bytes A B CCCycncu2v C Karamuba Algorithm of Multiplication Basic Recursive Step 2 CABA12VA0B12VBU AlBl 22V A1AOB0B1 A0B0A1Bl 2V AOBU D D Du D Du Karamuba Algorithm of Multiplication Tree Recursive Calls 5 5 Karamuba Algorithm of Multiplication N lg 1 1c A ltNgtH noggmuo 8 7 T i tM s time ofa single word multiplication MU39L Karatsub a N e operand length in bytes tA s time ofa single word addition ls word length in bytes k s time ofstaek opemtions in every recunent call ofthe function Mm 9 NW Karatsuba SchiinhagesStrassen Algorithm of Multiplication F7 Discrete Fourier Transform in Finite Field GFp c A B F1FA O FB A00AM An B00BM Bn n71 n71 F on ZAk gn k F1 3 ZBk ahn39k lFU lFU FA0tniii tau FA zniv v u O 09m 32 i 0in 5Q FAFBZ FC an YQ can lFEI c c Vc SchiinhagesStrassen Algorithm of Multiplication Run Time Assuming Purely Sequential Execution of Instructions tMU39L 9 N lgz N Schunhagerstxassen Optimization for Squaring C A2 F391FA FA tSQR s chunhagerstxassen MU39L Schunhzgerstxassm
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'