% Created 2020-08-30 Sun 14:24
% Intended LaTeX compiler: xelatex
\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{svg}
\usepackage{listings}
\lstset{basicstyle=\ttfamily\footnotesize,breaklines=true}
\usepackage[innermargin=1.0in,outermargin=1.0in,vmargin=1.0in]{geometry}
\usepackage{amsthm}
\newtheorem{DEFINITION}{Definition}
\usepackage{booktabs}
\usepackage{tabulary}
\usepackage{fontspec}
\defaultfontfeatures{Scale=MatchLowercase,Mapping=tex-text}
\setmainfont{Gentium Book Basic}
\setmonofont{DejaVu Sans Mono}
\setcounter{tocdepth}{-1}
\usepackage{listings}
\lstset{language=lisp, showstringspaces=false, showlines=true, literate={-}{{\texttt{-}}}1{--}{{\texttt{-{}-}}}2{---}{{\texttt{-{}-{}-}}}3, numberstyle=\tiny, stepnumber=1, numbersep=2mm, }
\author{Brian C. Ladd}
\date{Spring 2023}
\title{CPU Simulator Lab\\\medskip
\large CIS 203 Computer Science II}
\hypersetup{
 pdfauthor={Brian C. Ladd},
 pdftitle={CPU Simulator Lab},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.0.50 (Org mode 9.3.7)},
 pdflang={English}}
\begin{document}

\maketitle

\section{Note to Students}
\label{sec:org9d851cb}
Several questions you must answer come before our explanation. This is
on purpose. For you to get the most out of the learning with this lab,
\emph{please} do your best to answer the question, in writing,
\textbf{before} reading past the checkpoint. Your check mark for
answering the question depends on your making an honest effort to
think about what is being asked; your mind will be primed to remember
our explanation after engaging with the question. You will be able to
link your thinking and our thinking for better understanding.

\section{Pre-Lab}
\label{sec:org1e2b77e}
Before the lab you will need to watch several short video clips about
the inner workings of a modern computer:
\begin{itemize}
\item \href{https://www.youtube.com/watch?v=UdHK35N-Kuo}{What's a CPU?}
\item \href{https://www.youtube.com/watch?v=OTDTdTYld2g}{Fetch, Decode, Execute}
\item \href{https://www.youtube.com/watch?v=e4g9avBPUv4}{Assembly Language}
\item \href{https://www.youtube.com/watch?v=jhVuyveJMgA}{Primitive Data Types}
\texttt{float} or \texttt{double} can be ignored.
\item \href{https://www.youtube.com/watch?v=9HwATLewX9I}{Unsigned (Positive) Binary Numbers}
\item \href{https://www.youtube.com/watch?v=wuhM3HhR\_2Q}{What is Abstraction?}
\item \href{https://www.youtube.com/watch?v=\_zCH3BJAUZg}{Why use Abstraction?}
\item \href{https://www.youtube.com/watch?v=POyWMM29Uo0}{Abstraction/Reality}
\item \href{https://www.youtube.com/watch?v=PtJjnA-MPW4}{Creating an Abstract Model}
\end{itemize}

Testing referred to in these videos is UK A Levels testing. You will
not be expected to write code in any assembly language. \emph{Abstraction}
is an underlying idea in all of computer science.

\section{Student Learning Outcomes (or What Should You Know?)}
\label{sec:org97dd6f0}
\begin{itemize}
\item Describe the architecture of a modern, stored-program computer and how it reflects the abstract properties of \textbf{digital}, \textbf{binary}, and \textbf{general-purpose}.
\item Describe the \textbf{fetch-decode-execute} cycle and relate it to the parts of a computer.
\item Relate the fetch-decode-execute cycle for machine instructions to the \textbf{running-time} of a program.
\item Explain the difference between \textbf{hardware} and \textbf{software} in relation to the computer being general-purpose.
\end{itemize}

\section{What is a computer?}
\label{sec:org4d0469d}

Before you proceed, write down, in you notes, your answer to that
question. Consider what \emph{every} computer has in common and distill the
definition down into no more than three sentences.

[ ] Checkpoint 1: Show us your answer to the question: What is a computer?

\subsection{What is a program?}
\label{sec:org2d2db3f}

Pretend you are sitting at your computer. It is on and you are not
running any application programs. You want to surf the Web. What do
you do? And what does the computer do in response?

Picture what you would do to start the Web browser of your
choice. After you command the computer to run it, what does the
computer do? Go right up to the point where the browser is ready for
you to enter an URL address.

[ ] Checkpoint 2: Show us your description of what happens when the
computer begins running an application program.

\subsection{A General-purpose Computer}
\label{sec:org7c2be4d}

Your computer is \textbf{general-purpose}. This means that the \textbf{hardware} is
not a video player or a word processor. Instead, the hardware is an
\textbf{emulator} that takes a detailed description of \textbf{special-purpose}
computer (the video player or word processor) and follows the
definition to emulate the special-purpose computer.

It its core, the hardware stores and interprets zeros and ones, binary
numbers. Those binary numbers can encode integers, audio and video,
and even \textbf{instructions} for the hardware to execute.

When you write a Java program, the compiler places the variables and
instructions into specific memory locations by the compiler.  The
compiler reads your Java program file and writes another file to the
hard drive with instructions and variables laid out so they can be
read directly into memory. So, how does Firefox start on a Linux
computer with XWindows?

\begin{description}
\item[{Double click on icon}] the operating system associates the icon
with a particular compiled program, \texttt{firefox}.
\item[{Load the program}] the operating system reads the contents of the
file into the computer's memory.
\item[{Run the program}] the hardware has its own variable (a
\emph{register}) where it keeps track of the address, in memory, of the
next instruction it should execute. So, to start the program, the
operating system just points this register, the \emph{program counter}
to the spot where the compiler put the first instruction of the
compiled program.
\end{description}

But how can just two symbols, \{0, 1\} \emph{encode} all of these things.

[ ] Checkpoint 3: Show us your answer to that question. [Give this your
best shot.]

\subsection{A Binary Computer}
\label{sec:org20400c5}

How can two symbols, \{0, 1\} \emph{encode} all of these things? Think about
the Western European alphabet. It can be used to encode the complete
works of William Shakespeare, \emph{The Three Musketeers}, and even the
Java programs you wrote for CS 1. In order for you to read any of
these documents, you must know \textbf{what} language they are in (English,
French, Java) and know (be able to \emph{decode}) that language.

Similarly, the computer stores numbers in memory. To use the values
correctly, it needs to know which locations hold instructions, \texttt{int}
values, \texttt{char} values, or \texttt{String} objects. You give your variables
types to tell the Java compiler how your program interprets the
contents of the memory where the variable is stored.


The \emph{alphabet analogy} above is one way to model
combining low-level elements in different orders and proportions to
get many different results. Can \emph{you} come up with a different one?

Think about \textbf{cooking} for a start. You could construct a
similar analogy between binary encoding and cooking with a limited
number of ingredients.

[ ] Checkpoint 4: Show us your analogy for binary data encoding.

\section{Fetch-decode-execute}
\label{sec:org32bb82b}
\subsection{Tracing Java Programs}
\label{sec:org38803d8}
\begin{lstlisting}[numbers=left]
  // Sequential Instructions
  public static void main(String [] args) {
    int x = 11;
    int y = 2 * x;
    int z = x + 7 * y;
    System.out.println(String.format("%d %d %d", x, y, z));
  }
\end{lstlisting}

How does the above Java program execute? You could have put your
finger on a line, figured out what it did, and then updated your model
of the value of the variables.\footnote{By using your \emph{finger} you are
simulating a \emph{digital} computer. Terrible professor joke. Sorry.} Then
you would advance to the next executable line and do it again. That
\emph{cycle} of behavior could be defined as:

\begin{description}
\item[{fetch}] read the Java instruction currently pointed to
\item[{decode}] figure out what the Java instruction says to do
\item[{execute}] perform the instruction
\end{description}

Now, stop using your finger. Instead use a pencil and a box labeled
\emph{Pointer at Code} (\texttt{PC}). You could then extend the \textbf{fetch} stage as
follows:

\begin{description}
\item[{fetch}] read the Java instruction currently in \texttt{PC} and add 1 to \texttt{PC}.
\end{description}

Using the line number labels, write down the values of \texttt{PC} as the
program executes. Also write down the output of the program.

What happens if the program is more complicated? What if there is
\emph{selection} (an \texttt{if} statement)?

\begin{lstlisting}[numbers=left]
  // Selection Instruction: selection.java
  public static void main(String [] args) {
    int x = Integer.parseInt(args[0]); // read first argument as int
    if ((x % 2) == 0)
      System.out.println("Even");
    else
      System.out.println("Odd");
    System.out.println("Bye!")
  }
\end{lstlisting}

Think about using \texttt{PC} to trace this program.\footnote{There is no error
  checking. If you ran it without any arguments, the program would
  crash.} The rules of our current fetch-decode-execute are not
sufficient: sometimes we need to load a new address into \texttt{PC} rather
than just increment the old value.

In this code either line 4 is followed by 5 and then the \texttt{PC} goes to 8
(\emph{past} the \lstinline{else} clause) \textbf{or} line 4 is
followed by line 7 and then the \texttt{PC} goes to 8; one path or the other is
chosen depending on whether \lstinline{x} is even or odd.

We can extend \lstinline{fetch-decode-execute} so that the instruction
can update \texttt{PC} (if necessary) in the \lstinline{execute} phase.

\begin{description}
\item[{fetch}] read the Java instruction currently in \texttt{PC} and add 1 to \texttt{PC}
\item[{decode}] figure out what the Java instruction says to do
\item[{execute}] perform the instruction; update \texttt{PC} if necessary
\end{description}

Trace the values of \texttt{PC} when \lstinline{java selection 2} is run. Also
note the output. Then trace the values of \texttt{PC}
when \lstinline{java selection 1} is run and note the output.

[ ] Checkpoint 5: Show us your traces and output for both runs of the
program.

\subsection{Tracing Machine Instructions}
\label{sec:org7d7f2fd}

Start up the \href{https://tools.withcode.uk/cpu/}{CPU Simulator} in a browser; you will have to have
JavaScript enabled.

The cyan box on the right of the page is the \emph{random-access memory}
(RAM) with 16 bytes of memory. The salmon box on the left is the
\emph{central processing unit} (CPU). Notice that the red arrows connecting
them: the \emph{Control Bus} permits the CPU to send commands to and read
status from the RAM; the \emph{Address Bus} connects a particular byte in
the RAM to the \emph{Data Bus} for the CPU to load (from the RAM to the
CPU) or store (from the CPU to the RAM).

In this simulation, input and output are pop-up boxes in the browser
for user input when the program is running or putting values in the
bytes if you click on RAM cells or registers.



Go to the \texttt{Settings} section of the Web page and find the \texttt{Import/Export}
button. Click it and paste the following into the text box, replacing
whatever was there before. This is our \texttt{Add two numbers} example (a
little more complicated than the one on the Webpage). Make sure there
are no spaces \emph{before} what you paste and then press the \texttt{Import} button.

\begin{lstlisting}
91 3f 91 3e 1f 92 00 00 00 00 00 00 00 00 00 00
\end{lstlisting}


Notice that the values stored in the first six locations in the RAM
have changed from all zeros to different \textbf{binary} numbers. For the
moment, leave it showing binary but in \texttt{Settings} you \emph{can} change the
number base (\texttt{Binary} is base 2, \texttt{Denary} is base 10, \texttt{Hex} is base
16).

Look \emph{inside} the CPU and you will find the \emph{registers}; a register is
a named, one-byte storage location.\footnote{The registers are like
\emph{variables} (each has a name and a value stored in it) and the RAM is
like an \emph{array} (there is one name, RAM, and individual values are
found with an index to the memory location.)}

\begin{itemize}
\item \texttt{ACC}:: \emph{Accumulator} where one operand comes from for each math
instruction and where the result is placed. For example, if you
\texttt{Add} with the address \texttt{1000}, \texttt{ACC} becomes \texttt{ACC} plus the
contents of \texttt{RAM[8]}.
\item \texttt{CIR}:: \emph{Current instruction register} where the fetched
instruction is stored to be available throughout the cycle.
\item \texttt{MAR}:: \emph{Memory address register} is the RAM index for fetching
a byte from RAM into \texttt{MDR} or writing the \texttt{MDR} to a location in
the RAM.
\item \texttt{MDR}:: \emph{Memory data register} is the value read from (on a fetch
or \texttt{Load} operation) or written to (on a \texttt{Store} operation) RAM.
\item \texttt{PC}:: \emph{Program counter} (almost \emph{place in code}) is the index in
RAM where the next instruction is to come from.
\end{itemize}

When the program is loaded, the \texttt{PC} is initialized to the location
where the \textbf{compiler}, \textbf{operating system}, and \textbf{hardware designer} have
agreed program code is to begin. In this machine, that location is
\texttt{00000000}.

Use the \texttt{Step} button in the lower right of the Webpage to step
through the program's first instruction. Read the status box at the
bottom of the screen and pay attention to the fetch-decode-execute
cycle presented there.

The \texttt{PC} is, initially, \texttt{00000000} in binary or 0 in
base 10\footnote{The UK seems to use \emph{denary} as the adjective
  for a base 10 number; in the US, \emph{decimal} is more
  typical.}. The \texttt{PC} is copied to the \texttt{MAR} at the
first step of the fetch phase.

On the next step, the \texttt{MAR} communicates the address to the RAM
through the Address Bus; this sets the RAM up to read or write
\texttt{RAM[0]} (depending on the control signals sent from the
CPU). The simulation highlights \texttt{RAM[0]} (where that 0 comes
from the \texttt{MAR}).

On the next step, the contents of \texttt{RAM[0]} is communicated to
the \texttt{MDR} through the Data Bus. The simulation highlights the
data register and copies the \texttt{10010001} value from the RAM to
the register across the Data Bus.

On the next step, the \texttt{MDR} is copied to the
\texttt{CIR}. The \texttt{CIR} holds the encoded machine instruction
for the duration of the decode and execute phases. It is a separate
register than the \texttt{MDR} because the execute phase of a load or
store instruction makes use of the \texttt{MDR} and the CPU would lose
the instruction before execution was finished.

The last step of the fetch phase follows, incrementing the
\texttt{PC}. All instructions in this example run \emph{sequentially}
(the execute phase never changes the \texttt{PC}) so the next
instruction is always fetched from the address one higher than where
the previous instruction was found.

The decoding phase begins at the next step by splitting the eight
bits\footnote{bit = \textbf{b*inary dig*it}}
in the \texttt{CIR} into two four bit values, the \emph{opcode} (the
leftmost four bits) and the \emph{operand} (the rightmost four
bits). The \emph{operand} is used to look up what instruction is to be
performed inside the \texttt{Decode Unit}.

The \texttt{CIR} value of \texttt{10010001} is split into the opcode
of \texttt{1001} and the operand of \texttt{0001}. The last two lines
in the decoder say this opcode encodes either \texttt{Input} or
\texttt{Output}.

On the next step, the operand of \texttt{0001} decodes as
\texttt{Input}. The input instruction pops up a dialog and you can
type in a \emph{decimal} number. This time around, type in "7". The
binary value for 7 is placed in the \texttt{ACC} as \texttt{00000111}.

On the last step for this instruction, the CPU checks if any other
part of the computer needs servicing. Since none does, the CPU begins
the fetch-decode-execute cycle again.

Use the step button to watch the instruction in \texttt{RAM[1]}
fetched into the \texttt{MDR} and then  copied into the
\texttt{CIR}. Do not step past the message ``\textbf{Fetch} the
\emph{Control Unit} increments the \emph{Program Counter}''. The
\texttt{PC} should read \texttt{00000010}.

Write down, in your notes, the name of the instruction that is about
to be decoded: look at the \texttt{CIR}, break it into halves, and figure out
what the \emph{opcode} means. Without worrying about what it means, write
down the \emph{operand} next to the name of the opcode in your notes.

[ ] Checkpoint 6: Show us the name of the opcode and the operand you
just wrote down. The operand is treated as an \emph{address}: to what
\emph{register} in the CPU must the operand be copied during the
execute phase?

Step through the instruction until the message is about checking for
interrupts (the end of the whole fetch-decode-execute loop).

During the execute phase just completed, at what index in the RAM was
the \texttt{ACC} stored?  You can find it by matching the value in the
\texttt{ACC} with the \texttt{Value} in the RAM cell and then look at
the \texttt{Address} next to it.\footnote{If you want the
  \emph{decimal} value of the address, try switching the simulator to
  \texttt{Denary} and see what the address becomes. You should also
  see the value in the \texttt{ACC} and RAM location switch to 7, the
  value you gave as input.}

Go ahead and push the \texttt{Run} button. Every two seconds, the simulation
will step through the phases and instructions. You can watch the \texttt{PC}
increment by 1 at the end of the fetch phase, look at the opcode as
each instruction is decoded, and then watch the values move around in
the registers and RAM as each executes.

If you want to run the same program again without reloading it from
the Web (important after you make changes to the program later), just
click on the \texttt{Reset CPU} button in the top row of buttons. \textbf{Beware}
that if you reset the RAM, all the values in memory (instructions and
variables) will be lost.

\subsection{Uncompiling}
\label{sec:orgb351b1b}
What did the higher-level program that produced this program look
like? We will use a Java-like syntax, simplifying things so we do not
need a \texttt{class} or a \texttt{public static void main} line. Our code will
become instructions starting at address 0 and variables stored in the
highest addresses.

The program looked something like this:
\begin{lstlisting}[numbers=left]
  int firstNumber; // assigned to RAM[15]
  int secondNumber; // assigned to RAM[14]
  firstNumber = Input();
  secondNumber = Input();
  Output(secondNumber + firstNumber);
\end{lstlisting}

The compiler read the declaration of the variable \texttt{firstNumber} and,
as noted in the comment, assigned it the location of \texttt{RAM[15]}. This
means that in the assembly and machine language, the address 15 will
"mean" \texttt{firstNumber}. Similarly, location \texttt{RAM[14]} is where
\texttt{secondNumber} is stored.

The code was compiled into the seven instructions in RAM locations
0-6. If we write names for opcodes and decimal operands, the assembly
language looks like this:

\begin{lstlisting}[numbers=left,firstnumber=0]
  Input
  Store 15
  Input
  Store 14
  Add 15
  Output
  End
\end{lstlisting}

Find the address where the \texttt{Add} instruction is stored. Write the
address down in your notes.

Click on the RAM cell containing the \texttt{Add} instruction so that
you can edit it. Using the \texttt{Decode Unit} as a guide, change the
instruction so that it \emph{subtracts} \texttt{firstNumber} from
\texttt{secondNumber} rather than adding; all arithmetic takes place
between the value in a RAM cell (the \emph{operand}) and the value in
\texttt{ACC}.  Remember that an instruction is a byte\footnote{a
  \emph{byte} is a collection of eight bits} that has four bits of
opcode and four bits of operand. You want to change the assembly
program to:

\begin{lstlisting}[numbers=left,firstnumber=0]
  Input
  Store 15
  Input
  Store 14
  Subtract 15
  Output
  End
\end{lstlisting}

Run the program, entering the value 15 for the first number and 31 for
the second. Make note of the result displayed in your notes.

Take a glance at the "Java" version of the program. Think about what
part of the program you changed by changing the \texttt{Add}.

 [ ] Checkpoint 7: Show us your modified program. Be ready to point out
the changed instruction. What was the result when you entered 15 and
31? Was it the value you expected? Can you use the "Java" listing
above to explain why the output is correct?

\section{Selection}
\label{sec:org2fd7a38}
Our \texttt{Add two numbers} example program and your modification of it
demonstrates that the simulated CPU can run a \emph{sequence} of instructions
in a row; interesting computations require CPU support for \emph{selection}
of different instructions, depending on the data being processed.

\subsection{Find the Biggest of Two Numbers}
\label{sec:orgad945cd}
Think about the "Java" version of our program. How could we modify it
to output the larger of the two values the user entered?

CS 1 to the rescue: use an \texttt{if} statement and output one of the two
variables, depending on which is larger. Excellent.

\begin{lstlisting}[numbers=left]
  int firstNumber = 31; // assigned to RAM[15]
  int secondNumber = 42; // assigned to RAM[14]
  firstNumber = Input();
  secondNumber = Input();
  if (secondNumber - firstNumber >= 0)
    Output(secondNumber);
  else
    Output(firstNumber);
\end{lstlisting}

That might not be exactly what you would have written, especially in
the Boolean expression in the \texttt{if} statement. You probably would have
put the two variables on either side of the comparison operator. That
will be addressed below.

\subsubsection{How can the CPU select one of two paths?}
\label{sec:orgae1a313}

Go to the \texttt{Settings} section of the Web page and find the \texttt{Import/Export}
button. Click it and paste the following into the text box, replacing
whatever was there before. This is our \texttt{Find the Biggest} example (a
little more complicated than the one on the Webpage).

\begin{lstlisting}
91 3f 91 3e 2f 89 5f 92 6b 5e 92 00 00 00 1f 2a
\end{lstlisting}

Looking at this as the more readable \emph{assembly language} with all
16 memory locations shown, the loaded program looks like

\begin{lstlisting}[numbers=left,firstnumber=0]
  Input                  ; input -> Acc
  Store           15     ; store Acc -> RAM[15] firstNumber
  Input                  ; input -> Acc
  Store           14     ; store Acc -> RAM[14] secondNumber
  Subtract        15     ; Acc - RAM[15] -> Acc (secondNumber - firstNumber)
  Branch ACC >= 0  9     ; goto 9 if Acc non-negative
  Load            15     ; RAM[15] -> Acc firstNumber
  Output                 ; Acc -> output
  Branch Always   11     ; goto 11 ALWAYS
  Load            14     ; RAM[14] -> Acc secondNumber
  Output                 ; Acc -> output
  End                    ; End instruction
  0                      ; Unused location
  0                      ; Unused location
  42                     ; secondNumber
  31                     ; firstNumber
\end{lstlisting}

All the numbers are given in decimal. Before moving on: write down in
your notes the values of \texttt{firstNumber} and
\texttt{secondNumber} \emph{before} execution begins. Remember that
the variable \emph{names} are gone but their specific RAM locations
contain their values.

In the simulator, you can enter a values into the registers, just as
you can into the RAM locations. Pretend that you are the processor and
you want to print the bigger of the two variable values. Put the
address of the "right" instruction in the \texttt{PC}.\footnote{Again, if typing
it in in decimal is easier, use the \texttt{Denary} button in \texttt{Settings}.}
Use \texttt{Step} or \texttt{Run} to watch the program execute from your chosen
location check the output is 42, not 31 (or anything else).

Once the program gives the right output, \texttt{Reset CPU} and put the correct
value in \texttt{PC} again.

[ ] Checkpoint 8: Show us your register values in the simulator (the
value in the \texttt{PC}) and then run it for us so we can see the output is
the larger number. Also show us where you noted the values of the two
variables.

\subsubsection{A quick detour}
\label{sec:org3c10fc2}
Did you notice that the instructions for the machine were different
than the "Java" statements. This is because the instructions the CPU
knows are very, very simple and a "Java" statement might have to
become more than one machine instruction. To get input for
\texttt{firstNumber} and store it in the right location requires two
instructions; displaying the value for \texttt{secondNumber} also
requires two instructions.

The simplicity of the instructions is even more pronounced when it
comes to selection. This machine has only three instructions to change
the sequential execution:

\begin{description}
\item[{\texttt{Branch Always}}] As used above, at the end of showing one value,
to skip over showing the second value, the instruction at 8 resets
the \texttt{PC} during the execute phase from 9 (= 8+1; the value set at
the end of the fetch phase) to 11. 11 is the address of the first
instruction \textbf{after} output of the other variable.
\item[{\texttt{Branch on Zero}}] Same as \texttt{Branch Always} \textbf{but} it only resets the \texttt{PC} if
the \texttt{Acc} register is equal to zero.
\item[{\texttt{Branch Non-negative}}] Same as \texttt{Branch Always} \textbf{but} it only resets the \texttt{PC} if
the \texttt{Acc} register is non-negative. We are not talking about the
representation of negative numbers, just realize that some \texttt{int}
values are negative.
\end{description}

What happens if the conditional branches do \textbf{not} replace the value in
the \texttt{PC}? Then the value set at the end of the fetch remains and the
program continues \emph{sequentially} without taking the branch.

\subsubsection{Comparison with Subtraction}
\label{sec:org227ccb4}
In the previous checkpoint you set the value of the \texttt{PC} to 6 to
output \texttt{firstNumber} and to 9 to output \texttt{secondNumber}. We need a
conditional branch in instruction 5 to have the CPU set the \texttt{PC}
depending on which number is bigger.

Pause and think about that for a second. Pretend that the \texttt{Acc} has a
\emph{negative} number if \texttt{firstNumber} is bigger.\footnote{Look back at the
"Java" program above for spoilers on how we will get such a value in
the accumulator.} Then a \texttt{Branch Non-negative} would set the
\texttt{PC} to its operand if \texttt{Acc} is zero or positive.

Take a moment and think about that. Write down in your notes the
\emph{operand} value the \texttt{Branch Non-negative} should have. Using the
\texttt{Decode Unit} and the \texttt{Binary} button in the settings, write down the
binary for the whole \textbf{instruction} \texttt{Branch Non-negative X} where \texttt{X}
is the operand value you determined above.

If no instruction in the computer stores a value to \texttt{RAM[12]}, what
happens to the value in that byte? Similarly, what happens to the
value \texttt{10010001=\_2 stored in =RAM[0]} if no instruction stores the
accumulator to \texttt{RAM[0]}?

Compare the instruction in \texttt{RAM[4]} to the subtraction in the
"Java" program. How do you know that the correct value is stored in
\texttt{Acc} even though \texttt{secondNumber} is \textbf{not} loaded
before \texttt{firstNumber} is subtracted from the \texttt{Acc}.

[ ] Checkpoint 9: Show us your translation the \texttt{Branch Non-negative}
instruction. Be prepared to explain what happens to the values in RAM addresses
between \texttt{Store} instructions that address them. Be prepared to explain
why \texttt{RAM[4]} calculates \texttt{secondNumber - firstNumber}, even without
loading \texttt{secondNumber} before the subtraction.


\section{Levels of Abstraction}
\label{sec:orga293a70}

\subsection{\textbf{Digital}, \textbf{Binary}, \textbf{General-purpose} Computers}
\label{sec:orge2d47f4}
A computer is complex. It can be argued that modern \emph{central
processing units} (CPUs) are among the most complicate artifacts ever
constructed by humankind; it can also be argued that large computer
\emph{programs} are at least as complicated. How can a human being
understand a chip with more than twenty \emph{billion} transistors?

Short answer: no human being can. Instead they either understand the
function of some subset of those transistors \textbf{at the transistor level}
or they elide some of the details and understand more of the chip with
less resolution.

The longer answer is \textbf{abstraction}. Abstraction is "the process of
leaving out of consideration one or more properties of a complex
object so as to attend to others." [Websters 1913] Computers can be
defined at multiple levels, each level leaving out (taking for
granted) all the levels below and only focusing on one set of
features.

When you learned to program in Java, for example, you could ignore how
the operating system interacts with the hardware, how the hard drive
works, or how data is stored inside the \emph{random-access memory}
(RAM). Instead you focused on defining Java classes, compiling and
running them, and figuring out where the semicolons go.

In this lab you have looked at a lower level of the comupter, much
closer to the silicon.\footnote{Also known as the \emph{raw iron} of a
computer.} You watched the \emph{bits} and \emph{bytes} move through the RAM and
CPU of a simple, simulated computer.

You saw how the values stored in the computer are \textbf{digital}: any one
of the eight bits in a byte can be \emph{on} or \emph{off}, never halfway
between; a byte can therefore hold 2\textsuperscript{8} or 256 different values.

The values in the memory (registers and RAM) are just numbers. You saw
that numbers can be expressed in different \emph{bases} such as \textbf{decimal}
and \textbf{binary} (and you used the \texttt{Settings} buttons to have the computer
do the conversion for you).

Take a moment and speculate in your notes about why computers use
\textbf{binary} to actually store the numbers, rather than a base of
3\footnote{There actually was a ternary computer built in Russia at the end
of the 1950's. It is weird.} or a base of 10.

Finally, you saw that a byte just holds a sequence of bits. If it
contains the sequence \texttt{00111111} and it is loaded into the
\texttt{Acc}, then it is interpreted as the number
\texttt{00111111$_2$ or 145$_{10}$}. If, instead, it is at the
location referred to by the \texttt{PC} and it is fetched and decoded,
then it is the instruction \texttt{Store} (see \texttt{Decode Unit}
for opcode \texttt{0011}) to location \texttt{1111}$_{2}$ or
\texttt{15}$_{10}$.

The ability to encode numbers and instructions in the same bytes makes
the computer \textbf{general-purpose}. If you put different instructions in
the RAM, the computer can interpret the data contents of the RAM as
numbers, strings, audio, or even 3-D terrain for a video game.

[ ] Checkpoint 10: Using the London Underground map/satellite image
example of \textbf{abstraction}, explain to us the abstraction between
\emph{machine language} and \emph{Java}. Also, show us your speculation on why
computers use \textbf{binary} rather than another base.
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
