Transcript HO-01 - people.vcu.edu

EGRE 426
Handout 1
8/25/09
1
Preliminary
• EGRE 365 is a prerequisite for this class.
• Class web page
http://www.people.vcu.edu/~jhtucker/f09egre426/index.html
• Syllabus Grades:
–
–
–
–
–
Quizzes (2)
Homework
Laboratory
Design Project
Final Exam
40%
10%
10%
15%
25%
• Text book Computer Organization and Design 3rd
edition, Designers Guide to VHDL.
2
Computer Organization and
Design
• This book and the slightly more advanced
Computer Architecture a Quantitative Approach
are the dominant computer architecture text books.
• Too big.
– Chapter 1 – Read
– Chapter 2-7 – will be covered in detail skipping some
material.
– Chapters 8-9 – Will depend on time.
– Supplement with additional material.
3
Introduction
• We will learn not just how computers work,
but gain an understanding into how and why
computers evolved into the current
generation.
• Computer have undergone rapid changes.
– Increasing performance
– Decreasing cost
4
History
• Computers did not really begin until World
War II.
• The widespread use of microprocessors
began about 35 years ago.
• Personal computers were not taken
seriously until the introduction of the IBM
PC in 1981.
5
Computers have resulted in the
information revolution.
• Agricultural revolution.
– Several Thousand years.
• Industrial revolution.
– Several Hundred years.
• Information revolution.
– A couple of decades.
6
My History
• I started at NASA in 1963 and worked in the
computer division.
– At that time computers were very expensive and very
large.
– Programs were written on punched cards (one line per
card) and fed into the computer.
– The state-of-the-art super computer that I worked with
was capable of executing one million instructions per
second, it cost several million dollars, and occupied the
major portion of a large building.
7
My History continued
• In the 60’s I did early work in interactive
computing techniques.
– Forerunner of what we do today, but not
practical when it required a dedicated super
computer connected to a display console.
• In 1974 I completed my PhD and started
working with microprocessors.
8
Moore’s Law
• One of the founders of Intel, Dr. Gordon Moore,
observed in 1965 that the number of transistors in
an IC was doubling every year. He predicted that
this would continue for a couple of decades and
then slow to doubling every 18 months.
• This prediction has proved remarkably accurate.
So much so that it has come to be expected, and
Moore’s prediction has become known as Moore’s
law.
– It is worth noting that since Moore made his prediction
the consensus at any time has been that it would last for
only about ten more years.
– Economics not technology may be what actually stops
Moore’s law.
9
10
11
12
13
14
Single instruction stream – single data stream
15
Multiple instruction stream – multiple data stream.
16
Single instruction stream – single data stream
17
18
Definitions
Efficiency is the measurement of how close we come to achieving ideal speed up.
T1
Ep 
p
Tp

Sp
p
1
19
20
Assumptions
• All operations take one unit of time.
• All instructions and data are available when
needed.
• i.e. We don’t have to wait for memory or
communication.
• This is naïve and completely unrealistic, but
can be used to teach some fundamental
truths.
21
Conventional uniprocessor (SISD)
T
A1*B1 A2*B2 A3*B3 A4*B4
…
An*Bn
1
2
3
4
5
6
22
Multiprocessor MIMD (unlimited processors)
SIMD – same results.
T
A1*B1 A2*B2 A3*B3 A4*B4
…
An*Bn
1
2
3
4
5
6
23
Multifunction computer (2 * units)
T
A1*B1 A2*B2 A3*B3 A4*B4
…
An*Bn
1
2
3
4
5
6
24
n
P   Ai  A1 A2 ... An
SISD – single processor
i 1
T
A1
A2
A3
A4
A5
An
1
2
3
4
5
6
25
MIMD or SIMD – with
unlimited processors
T
A1
A2
n
P   Ai  A1 A2 ... An
i 1
A3
A4
A5
An
1
2
3
4
5
6
26
Algorithm can effect speedup.
SISD
T
A (B C D + E)
A( BCD  E )  ABCD  AE
A B C D +A E
1
2
3
4
5
6
27
Algorithm can effect speedup.
MIMD
T
A (B C D + E)
A( BCD  E )  ABCD  AE
A B C D +A E
1
2
3
4
5
6
28
n
SISD
P   Ai X i  A0  A1 X  A2 XX  A3 XXX  A4 XXXX  ...
Method A
i 0
T
1
2
A0 + A1*X + A2*X*X + A3*X*X*X + A4*X*X*X*X
3
4
5
6
7
8
9
10
11
29
n
SISD
P   Ai X i  A0  A1 X  A2 XX  A3 XXX  A4 XXXX  ...
Method B
i 0
T
1
2
A0 + A1*X + A2*X*X + A3*X*X*X + A4*X*X*X*X
3
4
5
6
7
8
9
10
11
30
n
SISD
Method C
T
1
2
3
P   Ai X i  A0  A1 X  A2 XX  A3 XXX  A4 XXXX  ...
i 0
 A0  X ( A1  X ( A2  X ( A3  X ( A4  ...))))
A0 + X ( A1 +X ( A2 + X ( A3 + X ( A4 + …))))
4
5
6
7
8
9
31
n
MIMD
unlimited
processors
T
1
2
3
P   Ai X i  A0  A1 X  A2 XX  A3 XXX  A4 XXXX  ...
i 0
 A0  X ( A1  X ( A2  X ( A3  X ( A4  ...))))
A0 + X ( A1 +X ( A2 + X ( A3 + X ( A4 + …))))
4
5
6
7
8
9
32
MIMD
n
unlimited P   Ai X i  A0  A1 X  A2 XX  A3 XXX  A4 XXXX  ...
i 0
processors
T
1
2
3
A0 + A1*X + A2*X*X + A3*X*X*X + A4*X*X*X*X
4
5
6
7
8
9
33
SIMD
n
unlimited P   Ai X i  A0  A1 X  A2 XX  A3 XXX  A4 XXXX  ...
i 0
processors
T
1
2
3
A0 + A1*X + A2*X*X + A3*X*X*X + A4*X*X*X*X
4
5
6
7
8
9
34
Using an MIMD machine with unlimited processors, the time
to compute
n 1
i
2
3
n 1
A
X

A

A
X

A
X

A
X



A
X
 i
0
1
2
3
n 1
i 0
is given by

T (n )  log 2 (n )  log 2 K log 2 (n )  n  2
log2 ( n ) 1
Where,
K (0)  0, K (1)  1, K (2)  1
And,
K (i )  K (i  2)  2i  3 for i > 2
For example when N = 9,
log 2  9    4, K (4)  K (4  2)  243  K (2)  21  2  2  4
log 2  9  1
T (9)  log 2  9    log 2  4   9  2 

 4  3  7
  4   2  9  241 



For N = 3000
T(3000)=23
35

N
Compute F ( N )   Ai * Bi
i 1
using a SISD computer with a add-multiply arithmetic unit.
T(4) = 4
36
Pipeline examples
37
38
39
40
41
42
Using a four segment pipeline
with the restriction that the
pipeline must empty before a
new type (add, multiply, etc.) of
operation can begin.
T4(4) = 16 segment
times.
43
Using a four segment pipeline
which does not require that the
pipeline empty before a new
type of operation can begin.
T4(4)=15 segment times.
44