Transcript www.cs.nccu.edu

1
Welcome Aboard – Chapter 1
COMP 2610
Dr. James Money
COMP 2610
2
How We Will Get There
Dr. James Money
COMP 2610
• Computer: electronic genius?
▫ NO! Electronic idiot!
▫ Does exactly what we tell it to, nothing more.
• Goal of the course:
▫ You will be able to write programs in C
and understand what’s going on underneath.
• Approach:
▫ Build understanding from the bottom up.
▫ Bits  Gates  Processor  Instructions  C
Programming
3
Two Recurring Themes
Dr. James Money
COMP 2610
• Abstraction
▫ Allows us to be more productive
 Can drive a car without knowing how the
internal combustion engine works.
▫ …until something goes wrong!
 Where’s the dipstick? What’s a spark plug?
Do you understand how a car works?
▫ Important to understand the components and how
they work together.
4
Two Recurring Themes
Dr. James Money
COMP 2610
• Hardware vs. Software
▫ Most people refer to themselves as one who
specializes in hardware or software, but not both
▫ You should take the opposite approach – it is good
to know both and sometimes essential
 Hardware engineers added MMX
instructions for video when this did not exist
yet
 Sorting can be dependent on the underlying
hardware
▫ You are seen as more versatile if you know both
5
Computer Systems
ca 1980
It took 10 of these boards to
make a Central Processing Unit
Dr. James Money
COMP 2610
ca 2000
You can see why they called
this CPU a microprocessor!
6
Computer Systems
Dr. James Money
COMP 2610
• When we mention computer systems,
most people do not only think of the
CPU.
• It usually includes the keyboard,
mouse, monitor, video card, hard
drive, and so on
• We focus on the CPU and how it does
what we want it to do
7
Two important concepts
Dr. James Money
COMP 2610
1. All computers, given enough time and memory,
are capable of computing exactly the same
things. They are Universal Computing Devices
=
=
PDA
Workstation
Supercomputer
8
Two important concepts
Dr. James Money
COMP 2610
2. Problem Transformation
▫ The ultimate objective is to
transform a problem expressed in
natural language into electrons
running around a circuit!
9
Computers as Universal Computing
Devices
Dr. James Money
COMP 2610
• Mathematical model of a device that can
perform
any computation – Alan Turing (1937)
▫ ability to read/write symbols on an infinite “tape”
▫ state transitions, based on current state and
symbol
• Every computation can be performed by some
Turing machine. (Turing’s thesis)
10
Turing Machines
a,b
Tadd
a+b
Turing machine that adds
For more info about Turing machines, see
http://www.wikipedia.org/wiki/Turing_machine/
Dr. James Money
COMP 2610
a,b
Tmul
ab
Turing machine that multiplies
For more about Alan Turing, see
http://www.turing.org.uk/turing/
11
Universal Turing Machine
Dr. James Money
COMP 2610
• Also known as a Universal Computational Device: a
theoretical device that accepts both input data and
instructions as to how to operate on the data
12
Computers as Universal Computing
Devices
Dr. James Money
COMP 2610
• U is programmable – just like a
computer!
• instructions are the input data
• a computer can emulate a Universal Turing
Machine
• A computer is a universal
computing device.
13
From Theory to Practice
Dr. James Money
COMP 2610
• In theory, computer can compute anything
that’s possible to compute given enough
memory and time
• In practice, solving problems involves
computing under constraints.
▫ time
 weather forecast, next frame of animation, etc
▫ cost
 cell phone, automotive engine controller, etc
▫ power
 cell phone, handheld video game, etc
14
Transformations between layers
Dr. James Money
COMP 2610
Problems
Algorithms
Language
Instruction Set Architecture
Microarchitecture
Circuits
Devices
15
Statement of Problem
Dr. James Money
COMP 2610
• We describe the problem initially in natural
language
• This is inefficient
▫ There are ambiguities in the description normally
▫ “Stir until soup is thick” has multiple meanings to
different people
• We cannot have this ambiguity in computer
programs
• We need precision
16
Algorithm
Dr. James Money
COMP 2610
• In order to make the problem precise, we turn it
into an algorithm
• This process is called software design
▫ We choose algorithms and data structures
• An algorithm is a step by step procedure that is
guaranteed to terminate such that each step is
precisely stated and can be carried out by a
computer.
• There are three terms for these properties.
17
Algorithm
Dr. James Money
COMP 2610
• Definiteness – each step is precisely
stated
• Effective Computability – each step
can be carried out by a computer. For
example, you cannot ask a computer
to find the largest prime number.
• Finiteness – the algorithm
terminates.
18
Algorithm
Dr. James Money
COMP 2610
• There are many algorithms for each
problems.
• There may be one with the fewest
steps
• Others may allow concurrent
computations
19
Program
Dr. James Money
COMP 2610
• We now using programming to convert the
algorithm to a program
• Programming languages are precise and
invented to specify a sequence of instructions to
the computer
• Over 1000 languages
• There are two types of languages:
▫ High level – C,C++,Pascal, Java
▫ Low Level – Assembly, one language for each
computer type
20
Instruction Set Architecture(ISA)
Dr. James Money
COMP 2610
• Next, by compiling, we convert the programming
language into the instruct set of the computer, called
the ISA
• The ISA specifies what instructions the computer
can perform, what values it needs, and it’s results
• We use the term operand to describe the values the
instruction needs
• The ISA specifies acceptable representations for
operands called data types
• The ISA also specifies where the operands are
located called the addressing modes
21
Microarchitecture
Dr. James Money
COMP 2610
• Processor design results in the
microarchitecture that runs the ISA
• The microarchitecture is the detailed particular
implementations of the ISA
• There are many microarchitectures for each ISA
▫ Intel, AMD for x86
▫ Different models of Intel chips
22
Logic Circuit
Dr. James Money
COMP 2610
• We now implement the microarchitecture using
simple logic circuits
• Here there is a cost tradeoff between cost and
performance
▫ NOT gates are cheaper than regular ones
• Many choices just for a simple case of addition
• This is called the logic circuit design phase
23
Devices
Dr. James Money
COMP 2610
• Finally, process engineering and
fabrication results in the devices used
to build the logic circuits
• There might be CMOS, NMOS, and
other types of circuits.
24
Putting it together
Dr. James Money
COMP 2610
Solve a system of equations
Red-black SOR
FORTRAN
PowerPC
Centrino
C
C++
Java
Intel x86
Atmel AVR
Pentium 4
Xeon
Ripple-carry adder
CMOS
Jacobi
iteration
Gaussian
elimination
Bipolar
Carry-lookahead adder
GaAs
Multigrid
Tradeoffs:
cost
performance
power
(etc.)
25
Course Outline
Dr. James Money
COMP 2610
• Bits and Bytes
▫ How do we represent information using electrical signals?
• Digital Logic
▫ How do we build circuits to process information?
• Processor and Instruction Set
▫ How do we build a processor out of logic elements?
▫ What operations (instructions) will we implement?
• Assembly Language Programming
▫ How do we use processor instructions to implement algorithms?
▫ How do we write modular, reusable code? (subroutines)
• I/O, Traps, and Interrupts
▫ How does processor communicate with outside world?
• C Programming
▫ How do we write programs in C?
▫ How do we implement high-level programming constructs?