nullCSE 575
Computer Arithmetic
Spring 2005
Mary Jane Irwin (www.cse.psu.edu/~mji)CSE 575
Computer Arithmetic
Spring 2005
Mary Jane Irwin (www.cse.psu.edu/~mji)AdministriviaAdministriviaMary Jane Irwin
348C IST Bldg
Office hours: by appointment
mji@cse.psu.edu; www.cse.psu.edu/~mji
Optional: Digital Arithmetic, Ercogovac & Lang, Morgan Kaufmann, 2004
Prerequisite: CSE 477 and CSE 431
Lectures are scheduled from 2:30 to 4:30 (but will often be over by 4:00, especially if a colloquium is scheduled)Course GradingCourse GradingHomeworks (2 in total) 150 pts
Course project 350 pts
TOTAL 500 ptsRemaining Lecture ScheduleRemaining Lecture ScheduleComputer ArithmeticComputer Arithmetic“ is a subfield of digital computer organization … deals with the hardware realization of arithmetic functions … a major thrust is the design of hardware algorithms and circuits to enhance the speed of numeric operations.”Parhami“ encompasses the study of number representation, algorithms for operations on numbers, implementations of arithmetic units in hardware, and their use …”Ercegovac & LangWhat Is Computer Arithmetic?What Is Computer Arithmetic?Hardware – Design of efficient circuits for arithmetic operations (+, -, x, /, sqrt, log, sine, …)
Software – Numerical methods for solving systems of equations (CSE 45x and 55x)Issues
Algorithm
Accuracy
Speed/power/area/ reliability trade-offs
Test/verificationIssues
Algorithm
Error analysis
Computational complexity
Test/verificationApplicationsApplications
Special purpose systems
Signal and image processing
Real-time 3D graphics
HDTV, image compression
Network processors (data compression, encryption/decryption)
…General purpose systems
Fast primitive operations for processor datapathsDesign AxesDesign AxesArchitectural innovations
Systolic arrays, wave pipelining, MMX, razor pipelines
Technological advancements
3D, multivalued gates, nanotechnology, …
Representation (encoding) systems
Redundant, residue, …
Arithmetic algorithms
SD arithmetic, serial arithmetic (lsb and msb first), saturating arithmetic, MACs, parallel multipliers, …interrelatedRepresenting NumbersRepresenting Numbersinfinite
(real numbers)finite
(machine representation)Number RepresentationsNumber Representations“Understanding different ways of representing numbers, including their relative cost-performance benefits and conversions between various representations, is an important prerequisite for designing efficient arithmetic algorithms or circuits.”ParhamiMachine Representation CharacteristicsMachine Representation CharacteristicsPositional - value of each symbol depends on its relative position (1492 1942)
Fixed radix, r - unit of each position is a constant multiple of the radix (base); usually a positive integer
Consecutive symbol (or digit) set, d, with at least r symbols, e.g., d [0, 1, 2, …, 8, 9]1 4 9 2Machine Repr. Characteristics, con’tMachine Repr. Characteristics, con’tScale factor, s - implied radix point (integer, fraction, or mixed number)
Precision, n = k + l - granularity of representation (k: # integer digits, l: # of fractional digits), ulp = r0 = 1 for integers, ulp = r-n for fractions
Range – number of distinct values from largest to smallest; depends on n, s, & r1 4 9 2Aside: Some NotationAside: Some NotationX - (capital letters) full precision operand consisting of multiple bits (base 2) or digits (base 2 and higher)
X = xiri = (xk-1 xk-2 … x1 x0. x-1 x-2 … x-l+1 x-l )rxi - (small letters) single bit or digit values (i negative then a fractional bit/digit, i positive then an integer bit/digit)Xi - (capital letters) full precision result from the ith iteration of a computationBinary Encoding ExamplesBinary Encoding ExamplesDigit vector of length n = k + l
( xk-1 xk-2 … x1 x0. x-1 x-2 … x-l+1 x-l )r= xirin = 4
Unsigned integer
Sign magnitude
integer
2+2 floating point
Sx2E, S (0,1,2,3)
E (-2,-1,0,1)Fixed-radix Positional # SystemsFixed-radix Positional # SystemsBinary: r=2, d[0,1]
Balanced ternary: r=3, d[-1,0,1]
Negabinary: r=-2, d[0,1]
Redundant (signed digit): r=2, d[-1,0,1]
Fractional radix: r=1/2, d[0,1]
Irrational radix: r=sqrt(2), d[0,1]
Complex-radix: r=2j, d[0,1,2,3]0 1 1 0Decimal Equilavent?Fixed-radix Positional # SystemsFixed-radix Positional # SystemsBinary: r=2, d[0,1]
Balanced ternary: r=3, d[-1,0,1]
Negabinary: r=-2, d[0,1]
Redundant (signed digit): r=2, d[-1,0,1]
Fractional radix: r=1/2, d[0,1]
Irrational radix: r=sqrt(2), d[0,1]
Complex-radix: r=2j, d[0,1,2,3]0 1 1 0Decimal Equilavent?61226¾2 + √2Real Number RepresentationsReal Number RepresentationsFloating point (approximation)
Slash (rational) representations
Keep numbers as num/denom pairs
Exact arithmetic (e.g., 2/3)
Division is multiplication
Logarithmic representation
Keep numbers as log2 |A|
Easy multiply and divide
Large dynamic range, but low precisionNumber Radix ConversionNumber Radix ConversionAssume that you are familiar with techniques for
converting to/from radix 2, 4, 8, 10, 16, …
doing arithmetic in the old radix
doing arithmetic in the new radix
using Horner’s rule shortcut to convert between radicesChoosing a “Best” RadixChoosing a “Best” RadixConversion
I/O is in decimal, so r=10 (BCD) would require no conversion, but wastes storage space and arithetic unit area and delay
Compatibility
CMOS circuitry supports two states (on, off) only, so r=2 (or some power of 2)
Reliability
circuitry supports binary logic only (as opposed to multivalued logic)Choosing a “Best” Radix con’tChoosing a “Best” Radix con’tEfficiency
The # of different representations is
M = r n
Assuming the component cost for repr is proportional to r (with binary logic it’s really prop. to log2r for r a power of 2), then the cost of the repr is
$ = K1 n r
$ = K1 (ln M)/(ln r) r = K2 r/(ln r)
To minimize $, take derivative at zero wrt r
d$/dr = (K2 (ln r -1))/ (ln r2) 0
So, ln r = 1 (r = e = 2.71828…) is the most efficient radix! Cost of r=2 and r=4 are about equal.Binary Full Adder (FA) ReviewBinary Full Adder (FA) Reviewxiyisicici+1FAaddendaugendcarry-incarry-outsum si = xi yi ci (odd parity function)
ci+1 = xi&yi | xi&ci | yi&ci (majority function)Ripple Carry Adder (RCA)Ripple Carry Adder (RCA)x0y0s0c0=cinFAx1y1s1FAx2y2s2FAcout=c4Can we use it to do both addition and subtraction?
How about negation?
How do we determine overflow, zero result, …?
How do we make it fast, power efficient, reliable, …?mod(2k) adderRepresenting Signed NumbersRepresenting Signed NumbersSigned magnitude
Complement
Two’s complement
One’s complement
Biased (excess)
Choice depends on area, delay, power, reliability of arithmetic hardware (adder) implementationsign indicated by
most significant
digitSign Magnitude (SM)Sign Magnitude (SM)most significant digit is the sign indicator, remaining digits are the magnitude X = xk-1 xk-2 … x1 x0Characteristics of Binary SMCharacteristics of Binary SMk-bit symmetric range of [-2k-1+ulp, 2k-1-ulp]
two representations for zero
simple negation (complement sign bit)
addition of unlike sign numbers must be handled differently than addition of like sign numbers (SM not a modular system)
symmetric shift – left: shift in zeros; right: shift zeros into magnitude - while maintaining sign bit
extend - left (sign): pad with zeros; right: pad with zeros – while maintaining sign bitSM Adder/SubtractorSM Adder/SubtractorSelective
complementSelective
complementControlBinary
addersign of Ssign of Xsign of Yadd/subcompl Scompl XXYS =signcoutcinXcomplX ± YComplement RepresentationsComplement Representationsnegation constant, M, so that negative representation of Y is M-YAddition RulesAddition Ruleswith a selection negation unit available all the operations are the same!Complement Rep OptionsComplement Rep OptionsTwo auxiliary operations required
negation (computing M-Y)
computation of residues mod M
Select M so these two operations are simple
Radix complement M= rk
negation –
mod M –
Diminished radix complement M = rk – ulp
negation –
mod M - Two’s Complement (2’sc)Two’s Complement (2’sc)M = 2k (for k=4, l=0, M = 24 =16)a mod(2k) systemCharacteristics of 2’scCharacteristics of 2’scasymmetric range of [-2k-1, 2k-1 - ulp]
so negation can lead to overflow!
one representation for zero (all zeros)
negation – complement all the bits and add 1
2s’c(Y) = 2k – Y = ((2k – ulp) – Y) + ulp = Ycompl + ulpmod - simply drop the high order carry-out
RCA with negation logic can handle both add and subtract
asymmetric shift – left: shift in zeros; right: shift in sign
extend - left (sign): replicate sign bit; right: pad with zeros2’sc Negation Example2’sc Negation ExampleRC(Y) = rk – Y
rK =
-Y = - yk-1 yk-2 . . . y1 y02’sc Negation Example2’sc Negation ExampleRC(Y) = rk – Y
rK =
-Y = - yk-1 yk-2 . . . y1 y01 0 0 . . . 0 00 r-1 r-1 . . . r-1 r-yk-1 -yk-2 . . . -y1 -y02s’c Adder/Subtractor2s’c Adder/Subtractormitigates disadvantage of negation
removes disadvantage of asymmetric range
if operand to be negated is -2k-1, it is represented in two parts: Ycompl (which is 2k-1 -1) and cinSelective
complementBinary
adderXYcout = ckcinadd/sub
0 for addition
1 for subtractionY or YcomplX ± Yoverflow: ck-1 ckOverflowOverflowLooking at the just the sign bit resultsoverflow = ck-1 ckno overflow here ever!One’s Complement (1’sc)One’s Complement (1’sc)M = 2k – 1 (for k=4, l=0, M = 24 – 1 = 15)a mod(2k-1) systemCharacteristics of 1’scCharacteristics of 1’scsymmetric range of [-2k-1 + ulp, 2k-1 - ulp]
two representations for zero
negation – complement all the bits
1s’c(Y) = 2k – 1 - Y = (2k – ulp) – Y = Ycompl
mod - end around carry
reduces magnitude by 2k - ulp if cout = 1
RCA with negation logic and end around carry can handle both add and subtract
symmetric shift – left: shift in sign; right: shift in sign
extend - left (sign): replicate sign bit; right: replicate sign bitEnd Around CarryEnd Around CarryWhen adding two 1’sc [mod(2k – ulp)] numbers that results in a high order carry out, result will be off by 2k - ulp
End-around carry
Drop a high order carry-out of 1 and simultaneously insert a carry-in of 1 into position l
Since the dropped carry is worth 2k units and the inserted carry is worth ulp, the combined effect is to reduce the magnitude of the result by 2k – ulp
Overflow – ? for you to consider1s’c Adder/Subtractor1s’c Adder/SubtractorDoes the end around carry terminate?
Assuming so, how long do we have to wait?
Selective
complementBinary
adderXYcout = ckcinadd/sub
0 for addition
1 for subtractionY or YcomplX ± Yoverflow: ck-1 ckComplement Rep Options RevisitedComplement Rep Options RevisitedTwo auxiliary operations required
negation (computing M-Y)
computation of residues mod M
Select M so these two operations are simple
Radix complement M= rk
negation – replace each digit by its radix complement [(r-1) - xi] and add a unit in the ls digit
mod M – ignore the high order carry out
Diminished radix complement M = rk – ulp
negation – replace each nonzero digit by its radix complement
mod M - do end around carryBiased (Excess)Biased (Excess)most significant digit is the sign indicator, remaining digits are the magnitudea mod(2k) systemCharacteristics of BiasedCharacteristics of Biasedsimilar to 2s’c with sign bit inverted (0 -> negative; 1 -> positive)
bias is always in the sign position
addition requires subtraction of bias
X + Y + bias = (X + bias) + (Y + bias) - bias
with a bias of 2k-1 just complement the msb
used to represent the exponent in floating point notation
simplifies comparison of floating point numbers (with leading excess exponent, integer comparison logic suffices)Indirect Signed ArithmeticIndirect Signed ArithmeticWhen hardware uses unsigned operands
some multiplication and division schemes
floating point mantissa unitsOther examples of pre/post operand processing
dealing with unacceptable or inconvenient operands
infinity, NAN
sin(2 + X) = sin( - X) = sin X
more efficient division when divisor can be scaled (along with the dividend) to be in a certain rangeKey ReferencesKey ReferencesBiannual Proc. Of the Computer Arithmetic Symposia, 1975 – 2003.
Cavanagh, Digital Computer Arithmetic Design and Implementation, McGraw Hill, 1984.
Ercegovac & Lang, Digital Arithmetic, Morgan Kaufmann, 2004.
Flynn & Oberman, Advanced Computer Arithmetic Design, Wiley, 2001.
Gosling, Design of Arithmetic Units for Digital Computers, Macmillan, 1980.
Koren, Computer Arithmetic Algorithms, Prentice-Hall, 1993.
Omondi, Computer Arithmetic Systems: Algorithms, Architectures, and Implementation, Prentice-Hall, 1994.
Parhami, Computer Arithmetic, Oxford Press, 1999.
Scott, Computer Number Systems and Arithmetic, Prentice-Hall, 1985.
Spaniol, Computer Arithmetic Logic and Design, Wiley, 1981.
Swartzlander, Ed., Computer Arithmetic, Dowden, 1980.
Swartzlander, Ed., Computer Arithmetic II, IEEE Press, 1990.
Waser & Flynn, Introduction to Arithmetic for Digital Systems Designers, Holt, 1982.
本文档为【computer arithmetic】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483