Transcript 08 War of the Words

Slides for Chapter 8
Note to Instructors
This Keynote document contains the slides for “The War of the Words”, Chapter 8 of Explorations in
Computing: An Introduction to Computer Science.
The book invites students to explore ideas in computer science through interactive tutorials where
they type expressions in Ruby and immediately see the results, either in a terminal window or a 2D
graphics window.
Instructors are strongly encouraged to have a Ruby session running concurrently with Keynote
in order to give live demonstrations of the Ruby code shown on the slides.
License
The slides in this Keynote document are based on copyrighted material from Explorations in
Computing: An Introduction to Computer Science, by John S. Conery.
These slides are provided free of charge to instructors who are using the textbook for their courses.
Instructors may alter the slides for use in their own courses, including but not limited to: adding new
slides, altering the wording or images found on these slides, or deleting slides.
Instructors may distribute printed copies of the slides, either in hard copy or as electronic copies in
PDF form, provided the copyright notice below is reproduced on the first slide.
© 2012 John S. Conery
The War of the Words
An introduction to computer architecture
✦
Hello, MARS
✦
The Temperature on MARS
✦
Corewar
✦
Self-Referential Code
✦
Clones
Explorations in Computing
© 2012 John S. Conery
A Brief History of Computing Machines
✦
People have been using mechanical devices to help with computation for
thousands of years
❖
Sumerians
❖
Egyptians
❖
Persians
❖
Greeks and Romans
❖
Chinese, Japanese and Koreans
❖
Mayans and Incans
See “abacus” at Wikipedia
Automatic Calculators
✦
In the middle ages European scientists dreamed about building machines
to carry out calculations automatically
Astronomers surely will not have to continue to exercise the patience which is
required for computation.... It is unworthy of excellent men to lose hours like
slaves in the labor of calculation which could safely be relegated to anyone else if
machines were used.
Gottfried Leibniz (1646--1726)
I wish to God these calculations had been executed by steam!
Charles Babbage (1821)
The First Computers
✦
✦
The first fully automatic calculating
machine was the Harvard Mark I (1944)
❖
storage for 72 numbers
❖
addition: 1/3 second
❖
multiplication: 6 seconds
❖
sequence of operations read from
a paper tape
The Mark I was a mechanical
computer
❖
used electro-mechanical
switches called relays
The First Computers
✦
✦
The first electronic machine was
ENIAC (1946)
❖
no moving parts
❖
used vacuum tubes, which were
electronic switches
Approximately 1000 times faster
than the Mark I
❖
addition: .0002 sec
❖
multiplication: .0026 sec
❖
controlled by a “plug board”
Size: 8’ x 3’ x 80’
Weight: 27 tons
❖
programmers connected adders,
multipliers, so output of one unit
fed into another
Power: 150 kW (~1000 light bulbs)
Modern laptop: 150 W
Modern Computers
✦
Modern processors use
semiconductor technology
❖
transistors instead of vacuum
tubes
✦
Approximately 109 times faster
than the Mark I
✦
Reasons for increased performance
are not just improvements in
hardware technology
❖
a landmark result in mathematical
logic paved the way for modern
computer design
SGI Altix cluster at NASA (10K CPUs)
The Stored Program Computer
✦
The idea was first presented in a paper by a Hungarian-born American
mathematician named John von Neumann
✦
von Nuemann’s proposal:
❖
✦
store the instructions that control a processor
in the same memory that holds the data
This idea can be traced to important mathematical results from the 1930s
❖
mathematical functions can be encoded as numbers
❖
therefore binary representations of functions
(i.e. programs) can be stored in a memory along
with binary encoding of numbers (i.e. data)
EDVAC
✦
✦
The first computer based on the stored-program
idea was named EDVAC
❖
proposed in 1944
❖
von Neumann’s paper describing stored
program organization presented in 1945
❖
machine operational in 1951
The is some controversy over who should
get credit for the stored-program design
❖
von Neumann was a consultant on EDVAC
project
❖
engineers who built the machine also
deserve credit
❖
Alan Turing developed a similar design in 1945
but was forced to keep it secret
Technological Implications
✦
A practical consequence of storing
programs and data in the same memory:
❖
improved memory and processor technology
will also speed up program execution
✦
Mark I read instructions from paper tape
✦
It won’t matter if a CPU can add a
pair of numbers in under 10-9 seconds
if it takes 10-1 seconds to read each
instruction from cards or paper tape
✦
If instructions are encoded in binary
and stored in memory along with data
the CPU can access instructions
just as quickly
Programming Implications
✦
More far-reaching implications:
❖
one program can treat another program
as a piece of data
✦
ENIAC was programmed by re-wiring
the front panel
✦
The fact that programs are just another
form of data means we can
❖
use text editors to create programs
❖
use compilers to translate them into
internal binary representations
❖
use an operating system to load the
program into memory and run it
The ability to execute a general-purpose, stored program is the
difference between a computer and a calculator
Theoretical Implications
✦
✦
Turing’s most important contribution to
computer science was a paper written
in 1936
❖
a paper on mathematical logic
❖
contained the specification of what we
now call a universal Turing machine
❖
used to prove the halting problem
The proof is based on the idea
that a description of one machine can
be written on a “tape” and the tape
is then read as input by another machine
To Learn More
✦
Some recommended reading to learn more about the idea that functions
can be encoded as numbers:
A readable history of
math, and how Gödel’s
ideas had a profound
effect on math and CS
History of computing
machines, by one of the
co-authors of the EDVAC
report
Programs as Data in Ruby
✦
A block in Ruby is a set of expressions enclosed in braces
>> a.each { |x| puts x if x.length > 5 }
>> time { a.sort }
✦
Ruby treats blocks as pieces of data that can be passed as parameters to
methods like each and time
✦
One of the implications of the halting problem there are limits to what we
can do with blocks
def time(&f)
tstart = Time.now
def foo(&f, &g)
if f.call
f == g
return Time.now ...
end end
Programs as Data in Ruby
✦
Another example of passing a block as a parameter:
>> a = RandomArray.new(:cars, 10)
=> ["porsche", "kia", "ferrari", "tesla", "lancia", "jaguar", "mg",
"lotus", "oldsmobile", "lexus"]
>> a.sort
=> ["ferrari", "jaguar", "kia", ... "porsche", "tesla"]
>> a.sort { |x,y| greater(x,y) }
=> ["tesla", "porsche", "oldsmobile", ... "jaguar", "ferrari"]
>> a.sort { |x,y| shorter(x,y) }
=> ["mg", "kia", "tesla", "lotus", ... "porsche", "oldsmobile"]
Project
✦
The goal for this chapter: learn about the von Neumann (stored program)
architecture
✦
The project is based on a computer game called Core War
❖
✦
basically a computer-based version of Battleship
Emphasizes the notion that programs
and data both reside in the same memory
❖
load two programs into a single memory
❖
take turns executing instructions from
each program
❖
each program tries to write a “halt”
instruction over the code of the other
program
MARSLab
✦
Outline:
❖
overview of MARS (the computer used to play Core War)
❖
MARSLab, the RubyLabs implementation of MARS
❖
example MARS programs
❖
playing Core War with MARSLab
Live Demo
Architecture
✦
✦
The two main components in machines organized according to the
von Neumann architecture:
❖
the central processing unit (CPU)
❖
the memory unit
The processor is in control
❖
the CPU can read information from memory (aka fetch)
❖
it can also write information into memory (aka store)
Memory
✦
Think of memory as a large array
✦
Items are accessed by their address
❖
address : memory :: index : array
✦
When a processor wants to fetch an instruction
or a piece of data it sends an address to memory
✦
The memory responds by
sending the contents
of that cell
Words
✦
In MARS each memory cell holds a single instruction or a single piece of
data
❖
✦
the generic term: word
In real computers, each memory location refers a single byte
❖
1 byte = 8 bits
❖
1 word = 4 bytes (32-bit processor) or
8 bytes (64-bit processor)
Title for Ch. 8:
“The War of the Words”
Fetch-Decode-Execute
✦
✦
The central processing unit (CPU) in a stored-program computer
continually executes a very simple algorithm:
fetch
get the next instruction from memory
decode
figure out what the instruction is supposed to do
execute
carry out the operation defined by the instruction
Before we look at these steps in more detail let’s look at a simple “hello,
world” program
❖
this program just adds two numbers and halts
❖
but it illustrates the sorts of things that can be done by a single machine instruction, and
shows how data is stored with the program
Hello, MARS
✦
Here is the text of the “hello, world” program
✦
The programming language for Core War is called Redcode
✦
Redcode programs (like Ruby programs) are created with a text editor
application and stored in plain text files
✦
The most important thing to remember:
❖
each statement in the program is translated into one word in memory
There are 4 statements
in this program
Everything following ; is a comment
Hello, MARS
✦
A statement can have a label at the front of the line
✦
The opcode specifies what the CPU should do
❖
✦
typically a three-letter name shown in upper case
Following the opcode are one or two operands
❖
these tell the processor where to find information required by the opcode
The first 3 instructions have labels
This program has 3 DAT instructions
and 1 ADD instruction
operands
Hello, MARS
✦
The last line in a file has the word end instead of an opcode
❖
this tells MARS where to start executing the program
❖
this small program will be loaded into four words in memory
❖
when the program is run, MARS will start with the instruction labeled hello
Begin execution with the line
that has this label
DAT
✦
✦
A line that has the word DAT is a piece of data
❖
usually the operand is the # symbol followed by a number x
❖
the line means “this word contains the number x”
Important: DAT also serves as a halt instruction
❖
if the CPU ever tries to execute an instruction that has DAT as an opcode the MARS
program terminates
ADD
✦
An instruction that has the opcode ADD tells the CPU to add two numbers
❖
ADD has two operands
❖
in the example below, both operands are labels
❖
this instruction means “find the value in the word labeled x, and add it to the word labeled
y”
Tracing the Program
✦
To run this program the CPU does two complete fetch/decode/execute
cycles
❖
the first instruction adds the contents of memory cell x to the memory cell y
❖
memory cell y now contains the number 11
❖
the second instruction is the DAT that follows the ADD
❖
executing the DAT causes the program to halt
To write this program in Ruby:
y = y + x
Memory Traffic
✦
The CPU does four memory operations when it executes an ADD instruction
❖
the first access occurs when the CPU fetches the instruction
❖
the add instruction tells the CPU to do two more fetches, to get the contents of cells x and y
❖
after the CPU adds the two values, the result is written back out to memory and stored in cell y
Testing the Program
✦
The RubyLabs module we will use this week is MARSLab
❖
the module has methods that simulate the actions of a MARS CPU
❖
a program that simulates the actions of a processor and memory is known as a virtual
machine
>> include MARSLab
=> Object
✦
To make a small “test machine” to try
out a program:
>> m = make_test_machine(:test_hello)
=> #<MiniMARS mem =
[DAT #0 #7, ... ] pc = [ *2 ]>
MARS =
Memory Array
Redcode Simulator
Testing the Program
✦
Call a method named dump to look at the contents of the test machine
memory
>> m.dump
0000: DAT #0 #7
0001: DAT #0 #4
0002: ADD -2 -1
The Redcode program has been translated into
MARS machine language instructions
0003: DAT #0 #0
Live Demo
Testing the Program
✦
A method named step will execute the next instruction
>> m
=> #<MiniMARS mem = [DAT #0 #7...] pc = [ *2 ]>
>> m.step
=> ADD -2 -1
>> m.dump
0000: DAT #0 #7
0001: DAT #0 #11
0002: ADD -2 -1
0003: DAT #0 #0
Note how “DAT 4” has
changed to “DAT 11”
Add the word 2 locations
before this instruction to
the word 1 location back
The program counter
holds the address of the
next instruction
Aside: Binary Code
✦
In a real CPU the machine language programs are binary numbers
❖
✦
memory chips hold an electric charge (e.g. 0v or 3.2v)
To store an instruction or a piece of data in memory
❖
convert the item into binary
❖
store 0s using one voltage, 1s using the other
✦
For this lab we’ll just show instructions by using their opcodes (ADD, JMN,
etc)
✦
We’ll also refer to data as “instructions” because DAT is an opcode
❖
it’s the instruction that halts the machine
A Simple Machine
✦
MARS is a very simple computer
❖
there are only 11 different
instructions
❖
the only kind of data is an
integer
❖
one instruction (MOV) just copies
data
DAT x
data / halt
MOV x,y
copy x to y
ADD x,y
add x to y
SUB x,y
subtract x from y
JMP x
continue execution at x
JMZ x,y
continue at x if y is zero
JMN x,y
continue at x if y nonzero
❖
the only arithmetic is addition
or subtraction
DJN x,y
decrement y, jump to x if nonzero
❖
six instructions are “branch
instructions” used to implement
loops
CMP x,y
skip the next instruction if x = y
SLT x,y
skip the next instruction if x < y
SPL x
start a new thread at x
‣
aka “jump” instructions
Assembly Language
✦
Redcode is a type of language
called assembly language
❖
✦
an assembler is a program that
translates AL programs into
binary machine language
AL programs are specific to one
particular type of processor
❖
Intel, IBM, and other CPU
chips all have their own
assembly language
DAT x
data / halt
MOV x,y
copy x to y
ADD x,y
add x to y
SUB x,y
subtract x from y
JMP x
continue execution at x
JMZ x,y
continue at x if y is zero
JMN x,y
continue at x if y nonzero
DJN x,y
decrement y, jump to x if nonzero
CMP x,y
skip the next instruction if x = y
SLT x,y
skip the next instruction if x < y
SPL x
start a new thread at x
Real processors have similar
types of instructions
Another Example Program
✦
Here is the Fahrenheit to Celsius
algorithm from Chapter 2
fahr
DAT #80
Input temperature
cels
DAT #0
Result saved here
DAT x
data / halt
MOV x,y
copy x to y
ADD x,y
add x to y
SUB x,y
subtract x from y
JMP x
continue execution at x
JMZ x,y
continue at x if y is zero
JMN x,y
continue at x if y nonzero
DJN x,y
decrement y, jump to x if nonzero
CMP x,y
skip the next instruction if x = y
ftmp
DAT #0
start
MOV fahr, ftmp
SLT x,y
skip the next instruction if x < y
SUB #32, ftmp
SPL x
start a new thread at x
(continued on the next slide)
First step: subtract 32 from
fahr, save result in ftmp
Note: in Ruby the expression is cels = (fahr - 32) * 5 / 9
Another Example (cont’d)
✦
DAT x
data / halt
MOV x,y
copy x to y
ADD x,y
add x to y
SUB x,y
subtract x from y
ADD ftmp, acc
JMP x
continue execution at x
SUB #1, count
JMZ x,y
continue at x if y is zero
JMN mult, count
JMN x,y
continue at x if y nonzero
DJN x,y
decrement y, jump to x if nonzero
CMP x,y
skip the next instruction if x = y
SLT x,y
skip the next instruction if x < y
SPL x
start a new thread at x
Fahrenheit to Celsius (cont’d):
mult
div
SUB #9, acc
SLT #0, acc
DAT #0
ADD #1, cels
This loop adds ftmp to acc 5 times,
i.e. acc = 5 * ftmp
JMP div
acc
DAT #0
count
DAT #5
end start
This loop counts the number of
times 9 can be subtracted, i.e.
cels = acc / 9
Live Demo
Playing a Game of Core War
✦
✦
The MARS system we will use has 4K words
❖
1K = 210 = 1024
❖
4K = 4096
When a game is started, the system loads
two programs into random locations
To make it easier to see 4096 cells they are displayed as a matrix
Playing a Game of Core War (cont’d)
✦
✦
The CPU will alternate between programs
❖
fetch/decode/execute one instruction from A (red)
❖
fetch/decode/execute one instruction from B (blue)
Each program tries to cause the other to halt
❖
store a DAT instruction over the code of the other program
Dwarf
✦
The code for a very simple
“core warrior” is shown at right
✦
The first word in the program is
a “bomb”
✦
❖
to this program, it’s a piece of data
❖
to the other program, it’s a halt instruction
The Dwarf program stores the bomb
in every 4th memory location
❖
each time through the loop the address
where the bomb will be stored is
incremented by 4
(details on the next slide)
Live Demo
Indirect Addressing
✦
The MOV instruction is the one that
“throws the bomb”
✦
The instruction MOV X, Y means
“copy the contents of X to cell Y”
✦
The instruction MOV X, @Y is the
same, except Y is not the destination,
it is the address of the destination
✦
In this program, vache has the value
4, 8, 12, ...
❖
the bomb will be stored 4, 8, 12, ...
words past the end of the code
Live Demo
Running Out of Memory
✦
The MARS computer has a 4096-word
memory
✦
What happens when the destination
for the bomb reaches 4096?
✦
Answer: the memory addresses
“wrap around” from 4095 to 0
❖
✦
the simulator calculates the memory
location for address x with the formula
x % 4096
It doesn’t matter where a program is
loaded into memory, it will always be
able to access all 4096 words
Live Demo
Imp
✦
The code for another “core warrior”
is shown at right
✦
This program (called Imp) has just
one instruction
✦
What does it do?
❖
recall addresses are relative to the
instruction
❖
e.g. ADD -2, -1 means “add the
contents of memory 2 words before
this instruction to the cell 1 word
before this instruction”
❖
so MOV 0, 1 means:
copy this instruction to the memory
location right after this instruction
Live Demo
Imp
✦
What happens after the CPU
executes MOV 0, 1?
❖
according to the fetch/decode/
execute algorithm, the CPU
should continue with the next
instruction in memory
❖
what is now in memory at this
location?
❖
MOV 0, 1 .....
this tiny “program” just copies
itself over and over, and moves
relentlessly through memory
copy this instruction to the memory location
right after this instruction
Live Demo
Imp vs. Dwarf
✦
What will happen when these two
programs compete against each
other?
❖
can Dwarf ever win?
❖
can Imp ever win?
❖
what are the possible outcomes
when the Imp reaches the
code for the Dwarf?
Live Demo
Jumping Around
✦
✦
A program can copy itself from one location to another
❖
not fair in Battleship, but OK in Core War
❖
if a program has n instructions, write a
loop that iterates n times
❖
each time through, copy an instruction
to a new location
The program shown at right will copy
itself to a new location in memory
❖
✦
833 words past the place where it was
loaded
It then jumps to the copy, and the
cycle repeats...
Live Demo
Threads
✦
MARS has an instruction that starts a new thread
✦
The idea is to “split” a program
into two pieces
✦
❖
analogy: the old video game named
Centipede
❖
a worm is crawling down from the
top of the screen
❖
whenever it is hit its splits in two,
with each piece continuing on
independently
In MARS:
SPL
x
means “start a second program beginning at location x”
Cannon
✦
An example of how to use SPL is a program shown here
✦
The “imp cannon” splits itself into
two pieces
✦
❖
it starts with a loop that just counts
down to zero
❖
one piece jumps back to the start
of the program
❖
the second piece is an Imp that starts
crawling through memory
End result: a series of imps,
following each other through memory...
Live Demo
Clones
✦
A more complicated program that uses
this strategy is named Mice
❖
it combines the Flea and Cannon
strategies
❖
it makes a copy of the entire
program
❖
it then executes a SPL
❖
the original copy and the new copy
continue to execute in parallel
Live Demo
Summary
✦
One of the most important ideas in the development of computer science was
the von Neumann architecture
❖
programs and data in the same memory
faster execution of programs
compilers, operating systems, ...
Summary (cont’d)
✦
✦
Memory is basically a large array of words
❖
a processor can fetch a word by sending an address to memory
❖
the processor can also store data
The CPU operates according to a fetch/decode/execute cycle
fetch
get the next instruction from memory
decode
figure out what the instruction is supposed to do
execute
carry out the operation defined by the instruction
Summary (cont’d)
✦
To explore this idea we experimented with a game called Core War
❖
two programs are loaded into random locations
❖
the MARS CPU alternates executing one instruction from each program
❖
a program tries to halt the other program
❖
halt = DAT
Summary (cont’d)
✦
MARS programs are written in a language named Redcode
❖
an “assembly language”
✦
Each line in the program corresponds to one word in memory
✦
The parts of an instruction are the label, opcode, and operands
The first 3 instructions have labels
This program has 3 DAT instructions
and 1 ADD instruction
operands
DAT x
data / halt
MOV x,y
copy x to y
ADD x,y
add x to y
SUB x,y
subtract x from y
JMP x
continue execution at x
JMZ x,y
continue at x if y is zero
JMN x,y
continue at x if y nonzero
DJN x,y
decrement y, jump to x if nonzero
CMP x,y
skip the next instruction if x = y
SLT x,y
skip the next instruction if x < y
SPL x
start a new thread at x