Transcript Letcture 1

CSE 246: Computer Arithmetic
Algorithms and Hardware Design
Winter 2004
Lecture 1
Instructor:
Prof. Chung-Kuan Cheng
Agenda
 Administrative
 Motivation
 Lecture 1: Numbers
CSE 246
2
Administrative
 Textbook: Digital Arithmetic
Milos D. Ercegovac
Tomas Lang
 In addition: set of papers to
read
CSE 246
3
Administrative
 Grading:
 Homework – 20%
 Midterm – 35%
 Project
 Report – 25%
 Presentation – 20%
 Midterm: Feb. 10th
 Homework 1: 1.2, 1.3, 1.16, 1.17, 1.25
 Due: 1/20/04
CSE 246
4
Administrative
 Potential project samples:




CSE 246
Use FPGA for add/sub
Design reconfigurable blocks
Design Low power adder, multiplier
Invent Low power/reliable number systems
5
Administrative
 There is no class on the following days:
 January 27th
 January 29th
 February 5th
 To make up for these lectures, some
lectures will be extended
 The first extended lecture will be January 8th
CSE 246
6
Agenda
 Administrative
 Motivation
 Lecture 1: Numbers
CSE 246
7
Motivation
Why do we care about arithmetic algorithms
and hardware design?
 Classic problems – well defined
 Advancements will have a huge impact
 Solutions will be widely used
 New paradigm




CSE 246
Interconnect dominated
Power driven
Reliability centric
FPGAs
8
Motivation
 Should a new business focus on building
market or new technology?
 New technology: a market will be built
around new technology
CSE 246
9
Motivation
 What if we had a 10GHz chip that was
2 cm x 2 cm?
 It takes 2 clock cycles (time of flight) to get
from one end of the chip to the other
 How would the clock be distributed?
 What if the electrical input is 1 Volt/100 Watts?
How do we get 100 Amps through the chip?
CSE 246
10
Topics
 Numbers
 Binary numbers, negative numbers,
redundant numbers, residual numbers
 Addition/Subtraction
 Prefix adders (zero deficiency)




Multiplication/Division
Floating point operations
Functions: (sqrt),log, exp, CORDIC
Optimization, analysis, fault tolerance
CSE 246
11
Other Topics
 Potential focus on the following topics:
 Power reduction
 Interconnect
 FPGAs
CSE 246
12
Goals/Background
 Why do you want to take this class?
What would you like to learn?






CSE 246
Fulfill course requirement
Hardware
Software
Work
Research
Curiosity
13
Agenda
 Administrative
 Motivation
 Lecture 1: Numbers
CSE 246
14
Numbers
 Special Symbols
 Symbols used to represent a value
 Roman Numerals
1=I
100 = C
5=V
500 = D
10 = X
1000 = M
50 = L
For example: 2004 = MMIV
CSE 246
15
Numbers
 Position Symbols
 The value depends on the position of the
number
 For example:
125 = 100 + 20 + 5
One 100, Two 10s, and Five 1s
Another example:
1 hour, 3 minutes
 Positional systems includes radixes:
2, -2, 2, 2j (imaginary)
CSE 246
16
Numbers
 Summation of positional numbers
 Given:  x , x ,..., x 
n 1
n2
0
n 1
 Value is: val  i0 xi y i (where y is the base)
 For example:

 Consider x {0,1} , y  2
CSE 246
4 -2
1
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
1
0
1
-2
-1
4
5
2
3
 111  1 22   1 21   1 20   3
 Note that position systems
provide a complete range of
numbers (e.g. –2 to 5)
17
Signed Numbers
 Biased numbers
 Signed Bit
 Complementary representation
 Positive number:
x (mod p)
 Negative number:
(M-x) (mod p)
(Note: mod p is added implicitly)
 One’s complement
0
0
0
1
0
1
1
1
0
1
-1
-0
Two’s complement
M  2n1
0
0
0
1
0
1
Flip each bit
1
1
0
1
-2
-1
M  2n
Flip each bit + 1
 Two’s complement can be used for subtraction
CSE 246
18
Signed Numbers
 Two’s complement subtraction:
 (M-x+M-y) mod M = M-(x+y)
 Two’s complement conversion:
 Positive number: 0,0,0, x , x ,..., x 
 To negative:
CSE 246
1, 1, 1, x
k 1
k 1
19
k 2
0
, xk 2 ,..., x0   0,0,0,...,0,1
Signed Numbers
 Two’s complement
n 2
 xn1 , xn2 ,..., x0    xn1 2n1   xi 2i
i 0
Example:
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
2
3
-4
-3
-2
-1
Proof as follows:
if xn1  1 then
n 1
 xi 2
i 0
 M  y where M  2n
n 1
 M   xi 2i   y
i 0
2
n 1

n2
 xi 2
i 0
i
  y (note : decrease of n)
Which leads to:
 xn1 2
CSE 246
i
n 1

n2
 xi 2
i 0
20
i
Next time
 Talk about redundant numbers
CSE 246
21