Transcript Today’s Topics - University of Cincinnati

Click
to
edit
Master
title
style
Click to editToday’s
Master
title style
Topics
•Click to edit Master text styles
level text styles
•Click –Second
to edit Master
•Third level
–Second
levellevel
• –Fourth
Introduction
to computing
•Third level
»Fifth level
–Fourth level
»Fifth level
• Universal computational devices
• Levels of transformation
1
1
Click
to
edit
Master
title
style
to Computers
ClickOur
toApproach
edit Master
title style
•Click to edit Master text styles
level text
GOAL:
construct
the styles
foundation, layer by
•Click• –Second
to
edit Master
level
layer,
needed to learn to program in C
–Second•Third
level
–Fourth level
•Third level
»Fifth level
–Fourth •level
A computer
»Fifth level
directs the processing of
information (selects next task to be
performed) and performs the processing
• We mean CPU, not peripherals that form a
computer system
2
2
Click
to
edit
Master
title
style
Will Study
Click toWhat
editWeMaster
title style
•Click to edit Master text styles
level text styles
•Click –Second
to edit Master
• •Third
How
information is encoded
level
–Second
level
–Fourth level
•Third •level
Transistors
»Fifth
level
–Fourth level
»Fifth level
• Von Neumann machine
• LC-2 (little computer)
• Machine language
• Assembly language
3
3
Click
to
edit
Master
title
style
The Hardware
Click to edit
Master title style
to editare
Master
text styles
• •Click
Computers
a systematically
level text
•Click –Second
to
edit Master
styles of simple parts
interconnected
collection
level
–Second•Third
level
–Fourth level
•
Deterministic
system
•Third level
»Fifth level
–Fourth •level
Parts are connected by wires, which can
»Fifth level
be at high or low voltage
– presence of voltage: 1
– absence of voltage: 0
• All information is encoded using
0’s and 1’s
4
4
Click
to
edit
Master
title
style
Important
Ideas
Click toTwo
edit
Master
title style
•Click to edit Master text styles
level text
•Click• –Second
to
Alledit
computers
Master
are capable
styles of
level
–Second•Third
level
computing
the same thing (given
–Fourth
level
•Third level
»Fifth
level time and memory)
enough
–Fourth level
»Fifth level
• A sequence of activities is necessary to
translate solutions in English to
activities carried out by electrons
5
5
Universal
Computational
Devices
Click
to
edit
Master
title
style
Click to edit Master title style
• •Click
“Universal”
to editmeans
Masterthat
textanything
styles that can
be computed
is possible to compute on
–Second
level
•Click to edit Master text styles
the device
•Third
level (as opposed to “specific”)
–Second–Fourth
levellevel
•Third level
»Fifth level
–Fourth level
»Fifth level
• Alan Turing proposed a formal,
mathematical definition of computation
in 1937
• Turing’s Thesis: every computation can
be performed by some Turing Machine
6
6
Computing a Function
Simple
Turing
Click
to
edit
Master
title
style
Click toa edit Master
title
style
Machines: +, *
a+b
+
•Click edit Master text styles
level text styles
•Click –Second
to edit Master
b
to
level
–Second•Third
level
Composing
Functions
–Fourth
level
•Third level
»Fifth level
a
–Fourth level
b
»Fifth level
*
+
c
?
Duplicating Input Values
a
+
?
7
7
Click
to
edit
Master
title
style
Machines
ClickUniversal
to editTuring
Master
title style
•Click to edit Master text styles
level
•Click• –Second
to
Universal
edit Master
Turing
textMachine:
styles can simulate
level
–Second•Third
level
any Turing
Machine (takes an encoded
–Fourth
level
•Third level
»Fifth
level
machine
description and its input)
–Fourth level
»Fifth level
• Since a UTM is programmable, it can
compute anything a computer can
compute!
8
8
Click
to
edit
Master
title
style
Contribution
ClickTuring’s
to editOther
Master
title style
to edit
Masterproblems
text styles
• •Click
There are
intractable
that are very
level but
slow
to Master
solve,
they
are solvable (but not
•Click –Second
to
edit
text
styles
level
feasible)
–Second•Third
level
–Fourth level
•Third level
»Fifth level
–Fourth •level
Besides
»Fifth level
defining computation, Turing showed
that there are functions that cannot be computed
… not by ANY computer EVER.
• e.g., The Halting Problem Solver: it is
impossible to write a program that will detect
whether any other program will halt.
9
9
Click
to
edit
Master
title
style
of Transformation
ClickLevels
to edit
Master title style
•Click to edit Master text styles
level text styles
•Click –Second
problems
to edit Master
level
–Second•Third
level
algorithms
–Fourth
level
•Third level
»Fifth level
–Fourth level
language
»Fifth level
ISA (machine architecture)
microarchitecture
circuits
devices
10
10
Click
to
edit
Master
title
style
Set Architecture
ClickInstruction
to edit Master
title style
to edit Master
text of
styles
• •Click
ISA: complete
specification
the interface
level
between
programs
and
the hardware that carries
•Click –Second
to
edit Master
text
styles
level
out
the
work of the programs
–Second•Third
level
–Fourth level
•Third level
»Fifth level
–Fourth level
• Set
»Fifth level
of instructions: operations and operands
• Memory: unique locations and their size
• C++ compiled to assembly language then
assembled to ISA
11
11
Click
to
edit
Master
title
style
Click to Microarchitecture
edit Master title style
•Click to edit Master text styles
level text implements
•Click• –Second
to
Microarchitecture
edit Master
styles
the ISA
level
–Second•Third
level
(“what’s
–Fourth
level under the hood of the car.”)
•Third level
»Fifth level
–Fourth level
»Fifth level
• e.g., DEC Alpha has 3 microarchitectures
that vary in cost and performance
12
12
Click
to
edit
Master
title
style
Click to editCircuits
Master title style
•Click to edit Master text styles
level text styles
•Click –Second
to edit Master
•Third level
–Second
levellevel
• –Fourth
Each
element of the microarchitecture is
•Third level
»Fifth level
implemented out of simple logic circuits
–Fourth level
»Fifth leveland there are cost/performance choices
13
13
Click
to
edit
Master
title
style
Click to editDevices
Master title style
•Click to edit Master text styles
• Each logic circuit is implemented in a particular
level text styles
•Click –Second
to
edit
Master
device technology (e.g., CMOS, NMOS,
level
–Second•Third
level
gallium
–Fourth
levelarsenide.)
•Third level
»Fifth level
–Fourth level
»Fifth level
• Electrons do the work at the device level: wires
carry electrons and to components that can
detect and manipulate high and low voltage …
they do the work of storing and processing
encoded values and instructions
14
14