Transcript From Algorithms to Architecture - Bilkent University Computer

From Algorithms
to Architecture
...a lightning introduction to computer architecture
David Davenport
Computer Eng. Dept.,
Bilkent University
Ankara - Turkey.
email: [email protected]
IMPORTANT…

Students…
This presentation is designed to be used in class as
part of a guided discovery sequence. It is not selfexplanatory! Please use it only for revision purposes
after having taken the class. Simply flicking through
the slides will teach you nothing. You must be actively
thinking, doing and questioning to learn!

Instructors…
You are free to use this presentation in your classes
and to make any modifications to it that you wish. All
I ask is an email saying where and when it is/was
used. I would also appreciate any suggestions you
may have for improving it.
thank you,
David.
Implementing Algorithms

Now have a methodology for
going from problem to program
(program syntax coming soon!)

First, develop a mental model of a
device that might actually execute
our algorithm, i.e. a computer!
Memory – Mental Model

Information




anything
a number, letter, word, a report, book,
picture, music, animation, a collection of books…
written/drawn on a paper
cannot be changed!
Store in Box




can hold only a single paper
can examine/copy paper at will
replacing paper destroys old
always a paper in box!
Some info
on a piece
of paper!
Computer Memory

Set of memory locations


To identify easily, number or name them
To minimise bugs, restrict type of content
age
salary
(int 0-150) (pos. real)
1
2
SPEEDOFLIGHT
(integer = 300)
today
username
(string)
(date)
3
4
TAXRATE
holidaypics
(string)
6
(set of images)
7
PI
(real = 3.142)
(real = 22.5)
5
address
Might also specify whether
information can be changed or not
i.e. are constant or variable
Memory requirements
 What memory locations are needed?
The circle computer algorithm…
1.
2.
3.
4.
5.
Print “Welcome to circle computer”
Ask for & get radius from user
Compute area as pi.radius.radius
Compute circumference as 2.pi.radius
Report area, circumference & radius
Information flowing from one step
to another must be stored & so
needs a place in memory
Algorithm Trace (2)

Envisage area/circumference algorithm
in terms of computer memory model
radius
area
(positive
integer)
(positive
real)
5
?
?
circumference
pi
(positive
real)
?
?
?
(constant
3.142)
3.142
2
(constant
2.0)
2
5
2. Ask for & get radius from user
Algorithm Trace (3)

Envisage area/circumference algorithm
in terms of computer memory model
radius
area
(positive
integer)
(positive
real)
?
5
?
3.142
5
78.55
5
*
circumference
pi
(positive
real)
?
?
?
(constant
3.142)
3.142
2
(constant
2.0)
2
78.55
3. Compute area as pi.radius.radius
Algorithm Trace (4)

Envisage area/circumference algorithm
in terms of computer memory model
radius
area
(positive
integer)
(positive
real)
?
5
?
2
3.142
78.55
5
*
circumference
pi
(positive
real)
?
31.42
?
?
(constant
3.142)
3.142
2
(constant
2.0)
2
31.42
4. Compute circumference
as 2.pi.radius
Algorithm Trace (5)

Envisage area/circumference algorithm
in terms of computer memory model
radius
area
(positive
integer)
circumference
(positive
real)
5
?
?
78.55
The area of a circle of radius
and its circumference is 31.42
pi
(positive
real)
?
31.42
5
?
(constant
3.142)
?
3.142
2
(constant
2.0)
2
is 78.55
5. Report area,
circumference & radius
COMPUTER ARCHITECTURE
Data flow

Only three sorts of instructions



input - from external world to memory
output - from memory to world
assignment - from memory to memory
memory
input
output
ALU
Arithmetic & Logic Unit
Control flow (1)

Control mechanism implements algorithm

sets up the data paths in appropriate sequence
First computing devices had
control mechanisms that
were hardwired (fixed) or at
best “pluggable” e.g ENIAC
Control
memory
input
output
ALU
Changing the function of the
machine required literally
changing its wiring!
How it works…

memory

4
1
5
input
6
2
output
Switches control
data flow into and
out of memory.
Sequence of switch
settings determines
function
7
8
3
9
1 2 3 4 5 6 7 8 9 10 11
10000000000
01000000000
ALU
10 11
00110010001
00000001000
How it works…

memory
2
input
1

5
3
output
6
Switches control
data flow into and
out of memory.
Sequence of switch
settings determines
function
8
4
123 4
7
5678
9 10 11 12 13
1100000000000
ALU
12
1010000000000
13
0000100000010
9
0001010010101
10 11
0000001100000
Control flow (2)

Recognising


instructions can be encoded in memory like data
allows general control mechanism to be implemented
Program
memory
Control
PC
Instructions & hence the
machine’s function can be
changed quickly & easily.
memory
input
output
Limitation: may be out of
program memory, yet have free
data memory or vice versa!
ALU
Control flow (3)

Finally

realise that program & data can share same memory
Instructions stored in
sequentially numbered
locations in memory.
Control
PC
Current position in
program held in program
counter.
memory
input
output
ALU
Memory now holds
both program & data
Fetch
Execute
cycle
Control fetches current
instruction, decodes &
executes it (by setting
data paths), increments
PC, then fetches next
instruction, and so on.
Spaghetti Code?

“go to” programming…
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Default is next
instruction
Read first number
If first number > 10 then go to 4
go to 1
Read second number
If second number <= first number goto 8
Print “Well done”
go to 10
Print “sorry, no good!”
go to 4
Print “finished.”
Von Neumann Architecture


Stored-program computer architecture
Credited to John von Neumann, circa 1946
Control
CPU – Central Processing
Unit (note: ALU may be
considered part of it too.)
PC
memory
input
output
ALU
Today
99.99999%
of all computers
still work like this!
Practicalities…
THE MEMORY HIERARCHY
Practical Considerations


Memory crucial to system speed!
Memory technology
High-speed, volatile,
expensive, so limited.
Non-volatile, cheap, so
plentiful, but slow!
Speed
differential
>10,000x
Semiconductor
RAM, ROM
Optical & Magnetic
Disks, tapes & CDROMs
Memory Hierarchy

Result of today’s
technological
limitations only!
Boot ROM
Control
PC
Primary memory
input
Secondary
memory
(disks)
output
ALU
Primary memory also
called RAM – Random
Access Memory
Practicalities…
THE LANGUAGE HIERARCHY
From problem to execution


From requirements to algorithm
From algorithm to program
(something “understandable” to machine)

Ultimately need machine code
(1’s & 0’s representing switch patterns)
but how do we get it…?
• Directly write machine code
• Write assembly & translate
• Write high-level & translate
Translation is
a symbol
manipulation
task!
Language Hierarchy (1)

Machine code



Patterns of 1’s & 0’s ~ machine instruction
Usually restricted, e.g. no real numbers
Difficult & error-prone writing by hand!
10011000
11000011
01000000
01000110
11111000
10000110
00000011
11111100
:
Note: machine dependent, same operation may
require different pattern of 1’s & 0’s on different
machines. Computer designer/manufacturer
defines machine code.
Language Hierarchy (2)

Assembly language




Each machine instruction has mnemonic
Easier to remember & understand
so slightly less error-prone,
but still difficult to do even simple things!
One-to-one mapping
so translation to machine code is trivial
Use program to do translation (assembler)
MOV #5, R1
ADD R1, R2
STR @R0
:
Like machine code, assembly
language is machine dependent
and low-level
Language Hierarchy (3)

High-level language




Much more “natural”, e.g. has real numbers!
Much easier to understand & write
Language standards, so machine independent
Translation to machine code is complex,
use program to do it!
This program takes a
input A
Z = A * 3 + 1;
print( “Z=“ . Z);
:
“program” as input
(data) and outputs a
“program”!
Two approaches


Interpret
Compile
Interpreters

Translate & immediately execute
each instruction in turn
Source code
(stored in file)
10 rem Sum two numbers
20 input “enter first number”, $a
30 input “enter second number”, $b
40 $s = $a + $b
50 output “sum is “ . $s
interpreter
machine code
(generated
& executed,
never stored)
11100101001000100…
Compilers

Translate all instructions to machine code,
save & execute as needed
Source code
(stored in file)
10
20
30
40
50
rem Sum two numbers
input “enter first number”, $a
input “enter second number”, $b
$s = $a + $b
output “sum is “ . $s
compiler
machine code
(generated once
& stored in file)
0011000101010000100
11100101001000100…
Stored machine
code executed by
OS as many times
as required!
Java – compile & interpret
Compile & save to bytecode (machine independent)
Execute by interpreting bytecode


MyProg.java
// Program MyProg
// David, Oct 2002
import
Import
MyProg.class
java.io.*;
cs1.JRobo;
public class MyProg {
public static void mai
System.out.println(
JRobo robby = new J
robby.f(100);
robby.rect( 150, 50);
}
Java
compiler
(javac)
}
Source code
(stored in file)
bytecode
(stored in file)
1100011100
0100010000
0111100111
0001010101
0001…
Also known as
the Java Virtual
Machine (JVM)
Java
interpreter
(java)
machine code
(generated
& executed,
never stored)
11100101001000100…
Java language levels…
Programs across Internet

Java Applets – run anywhere safely!
Mypage.html
// Program MyApplet
// David, Oct 2002
import
Import
java.io.*;
cs1.JRobo;
<html>
<body>
<applet class=“MyApplet.class”>
</applet>
</body>
public class MyApplet
extends Applet {
public void paint(
JRobo robby = new J
robby.f(100);
robby.rect( 150, 50)
}
}
Source code
(stored in file)
Java
compiler
(javac)
My WebPage
INTERNET
html webpage
containing applet
(stored in file)
WebBrowser – Netscape
http://somewhere.com/mypage.html
bytecode
(stored in file)
1100011100
0100010000
0111100111
0001010101
0001…
MyApplet.java
Look at this applet…
Welcome to
MyApplet
Java
interpreter
(java)
MyApplet.class
JVM in
webbrowser
creates machine
code for client
11100101001000100…