Transcript 01-Introduction

ECE 8053 Introduction to
Computer Arithmetic
(Website: http://www.ece.msstate.edu/classes/ece8053/fall_2002/)
Course & Text Content:
Part 1: Number Representation
Part 2: Addition/Subtraction
Part 3: Multiplication
Part 4: Division
Part 5: Real Arithmetic (Floating-Point)
Part 6: Function Evaluation
Part 7: Implementation Topics
Course Learning Objectives
Computer Arithmetic students will be able to ...
1. explain the relative merits of number systems used by
arithmetic circuits including both fixed- and floating-point
number systems
2. demonstrate the use of key acceleration algorithms and
hardware for addition/subtraction, multiplication, and
division, plus certain functions
3. distinguish between the relative theoretical merits of the
different acceleration schemes
Course Learning Objectives
(Continued)
4. identify the implementation limitations constraining
the speed of acceleration schemes
5. evaluate, design, and optimize arithmetic circuits for
low-power
6. evaluate, design, and optimize arithmetic circuits for
precision
Course Learning Objectives
(Continued)
7. design, simulate, and evaluate an arithmetic circuit
using appropriate references including current journal
and conference literature
8. write a paper compatible with journal format standards
on an arithmetic design
9. make a professional presentation with strong technical
content and audience interaction
Importance of Computer Arithmetic
1.7GHz Pentium has a clock cycle of 0.59 ns
1 integer addition < 0.59 ns in execution stage of P/L
Assume a 4-bit adder – ripple carry, 0.2 ns gate delay
STEP 1
1101
1110
11011
-Note: added from right to left. Why?
Ripple-carry Structure
STEP 2 – Design a circuit
x3 y3
c4
z4
x2 y2
c3
z3
x1 y1
c3
z2
x0 y0
c3
z1
– Each box is a full-adder
– Implement it
c0=0
z0
Full Adder Implementation
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
cin
0
1
0
1
0
1
0
1
z
0
1
1
0
1
0
0
1
xy
cout
00
01
11
10
0 cin
0
0
0
1
0
1
0
1
1
1
0
1
0
0
1
z  cin x y  cin x y  cin x y  cin x y
1
 cin  x  y
1
xy
00
01
11
10
0
0
0
1
0
1
0
1
1
1
cin
cout  cin ( x  y )  xy
Adder Circuit Analysis
STEP 3 – Analysis
Critical Path is 3 gates
34=12
(12)(0.2ns)=2.4ns
2.4ns > 0.59ns
Must Use Faster Adder!!!!
Roman Numeral System
Symbolic Digits
symbol value
I
1
V
5
X
10
L
50
C
100
D
500
M
1000
RULES:
• If symbol is repeated or lies to
the right of another higher-valued
symbol, value is additive
XX=10+10=20
CXX=100+10+10=120
• If symbol is repeated or lies to the
left of a higher-valued symbol,
value is subtractive
XXC = - (10+10) + 100 = 80
XLVIII = -(10) + 50 + 5 + 3 = 48
Weighted Positional Number System
Example: Arabic Number System (first used by Chinese)
symbol
(digit)
0
1
2
3
4
5
6
7
8
9
value
(in 1’s position)
0
1
2
3
4
5
6
7
8
9
Addition Paradigms
• right to left serial
1
147865
+30921
178786
• right to left, parallel
147865
+30921
177786
001000
178786
•random 461325
147865
+30921
177786
001000
178786
Binary Number System
• n-ordered sequence:
xn1 xn2
x2 x1 x0
• each xi{0,1} is a BInary digiT (BIT)
• magnitude of n is important
• sequence is a short-hand notation
• more precise definition is:
xn 1 2n 1  xn 2 2n 2 
n 1
 x2 22  x1 21  x0 20   xi 2i
• This is a radix-polynomial form
i 0
Number System
• A Number System is defined if the following exist
1.
2.
3.
4.
A digit set
A radix or base value
An addition operation
A multiplication operation
•Example: The binary number system
1.
2.
3.
4.
xi  {0,1}
 2
Addition operator defined by addition table
Multiplication operator defined by multiplication table
+ 0 1
 0 1
0 0 1
0 0 0
1 1 10
1 0 1
Number System Observations
• Cardinality of digit set (2) is equal to radix value
• Addition operator XOR, Multiplication is AND
•How many integers exist?
Mathematically, there are an infinite number, 
In computer, finite due to register length
X min  smallest representable number
X max  largest representable number
[ X min , X max ]  range of representable numbers
[-inclusive; (-exclusive interval bounds
•When ALU produces a result >Xmax or <Xmin, incorrect
result occurs
•ALU should produce an error signal
Example
•Assume 4-bit registers, unsigned binary numbers
X min  00002  010
X max  11112  1510
[ X min , X max ]  [00002 ,11112 ]
X max  1  100002  1610
X max  1  [00002 ,11112 ]  X (mod 16)
X 1101 13
Y  0110 6
1 0011 19
19(mod 16)  3
Answer in register is 00112=310
Overflow
Machine Representations
• Most familiar number systems are:
1. nonredundant – every value is uniquely represented
by a radix polynomial
2. weighted – sequence of weights
wn1 , wn2 ,
, w2 , w1, w0
determines the value of the n-tuple formed from
the digit set
xn1 , xn2 ,
, x2 , x1, x0
n 1
X   xi wi
i 0
3. positional – wi depends only on position i
4. conventional number systems
wi   i
where ß is a constant. These are fixed-radix systems.
Example
X  7  84  6  83  2  81  4  80
Since octal is fixed-radix and positional,
we can rewrite this value using shorthand notation
X  760248
Note the importance of the use of 0 to serve as a
coefficient of the weight value w2=82
Fixed-Radix Systems
Register of length n can represent a number with a
fractional part and an integral part
k – number of integral digits
m – number of fractional digits
n=k+m
xk 1 xk 2
.
x1 x0 x1
x m
radix point
X  xk 1
 x1
k 1
1
 xk  2 

k 2
 x m 
 x1  x0 

m
1

0
k 1
x
i  m
i
i
A programmer can use an implied radix point in any position
Scaling Factors
Fixed point arithmetic can utilize scaling factors to
adjust radix point position
a – scaling factor
aX  aY  a ( X  Y )
aX  aY  a 2 XY
aX X

aY Y
no correction
must divide by a
must multiply by a
Scaling Factor Example
X  4.210
Y  2.110
aX  4210
a  10
aY  2110
aX  aY  63  a ( X  Y )
X  Y  6.3
aX  aY  42  21  21  a ( X  Y )
X  Y  2.1
aX  aY  42  21  882  a 2 X  Y
X  Y  8.82
aX 42

2
aY 21
X 4.2

2
Y 2.1
Unit in the Last Position (ulp)
• Given w0=r-m and n, the position of the radix point is determined
• Simpler to disregard position of the radix point in fixed
point by using ulp
ulp  r
m
Example
98.67510
1 ulp = 110-3=0.001
1 ulp is the smallest amount a fixed point number
may increase or decrease