The first test in CS 220 will be given in class on Wednesday, September 28. It will cover almost everything that we have done through Friday, September 23, including labs. (Exceptions include the IEEE 754 representation of floating point numbers and our discussion of the memory hierarchy and caching. There will be no questions about using the Larcsim and Logisim programs.)
General topics include: Java's bitwise logical and shift operators, the Larc computer and its machine language and assembly language, and logic circuits, including combinational circuits and memory circuits. A detailed list of topics is given below.
The test will be made up of a variety of questions. There will be some short answer questions and longer essays, ranging from things as simple as the meaning of a single assembly language instruction to very general questions about computers and circuits. There can be some problems that ask you to write some Larc assembly language code, or to say what some given code does. You might be asked to convert between circuits and Boolean expressions, or determine what a given circuit does.
You do not have to memorize the Larc machine language or the Larc assembly language. You will be given a copy of the class handout containing the tables of instructions and hex digits.
Here are some terms and ideas that you should be familiar with:
CPU (Central Processing Unit)
RAM (memory, memory locations, and memory addresses)
ALU (Arithmetic/Logic Unit)
registers
PC (program counter)
how a computer executes a program that is stored in RAM (fetch-and-execute)
how the PC is used during program execution
the "clock" in a computer
ISA (Instruction Set Architecture)
binary numbers
counting in binary
hexadecimal numbers
binary arithmetic
adding, subtracting, and multiplying binary numbers (but not dividing)
signed and unsigned integers
twos-complement representation of negative numbers
bitwise logical operators in Java: &, |, ~
logical shift operators in Java: >>> and <<
arithmetic shift operator in Java: >>
using shift and bitwise logical operators to examine one or more bits from a number
Larc, a simple model computer
Larc registers -- 16 16-bit numbers, register 0 is always 0
Larc RAM -- 65536 memory locations, each holding a 16-bit number
Larc machine language
the simple assembly language used in Larcsim
format of Larc machine language instructions
LIMM, SIMM, and sign extension
immediate values for li and lui instructions
conditional branch instructions (beqz and bnez)
implementing loops in assembly language
accessing memory using load and store (lw and sw)
subroutines, return addresses, and the jalr instruction
how strings are represented in Larc
system traps and the syscall instruction
why system traps are necessary
kernel mode versus user mode
logic gates and how they correspond to logic operations &, |, and ~
logic circuits
combinational logic circuits
converting a Boolean expression to a combinational logic circuit
converting a combinational logic circuit to a Boolean expression
truth tables and how to build a circuit that computes a truth table
sequential circuits (output can depend on the history of inputs)
memory circuits
basic circuits (but not how to build them, except for really simple ones):
half-adder
one-bit adder
n-bit adder
ALU
multiplexer
decoder
S-R latch
D-latch
D-flip-flop
the clock in a computer; clock cycles
edge-triggered memory, such as the flip-flop
how edge-triggered memory is used to implement circuits that do computations
The following questions are meant as examples of questions that might be on the test. (This is not meant to be a complete survey of every kind of question that you might encounter on the test.)
1. Suppose that A, B, C, D, and E are int variables in Java, and that the following assignment statements are executed. What values are assigned to the variables C, D, and E? Write your answers in hexadecimal.
A = 0x12345678; B = 0xABCDEFAB; C = A | 0xFFFF0000; D = B >> 8; E = (0xFFFF0000 & A) | (0x0000FFFF & B);
2. Suppose that N is the 16-bit binary number 0b0011010010100110. Write the negation, -N, as a 16-bit binary number.
3. The Larc model computer has 16 registers. How is this number reflected in the format of Larc machine language instructions?
4. Translate each of the following 16-bit numbers into a Larc assembly language instruction, and state what the instructions does, including how registers and memory locations are affected:
a) 0x1442 b) 1001000100000001 c) 1101000100101111
5. Suppose that a, b, and c are in registers $1, $2, and $3 respectively. Translate the following assignment statement into Larc assembly language. You can use other registers as necessary.
a = (b - c) * (a + 7)
6. Suppose that a string is stored in memory, with a zero marking the end of the string, and that the address of the first character in the string is stored in register $1. Write Larc assembly code that will find the length of the string and leave the answer in register $2. (The length is the number of characters, not counting the zero at the end.)
7. What is the purpose of the following Larc assembly program segment? (Explain)
li $5 0 li $1 4 syscall add $5 $5 $1 bnez $1 -4
8. Discuss the beqz instruction. What does it do? What do its parameters mean? How is it implemented?
9. What is meant by a register?
10. Explain the role of the Program Counter in the Larc computer, and discuss how and why its value changes during the fetch-and-execute cycle.
11. Draw a combinational logic circuit that computes the Boolean expression
(A | B | C) & ~((A & B) | (A & C))
12. Find the Boolean expression computed by the following circuit:
13. What is a multiplexer? What role does it play in circuits.
14. Draw an S-R latch, and explain how it is used.