The second test in CS 220 will be given in class on Wednesday, November 9. Topics include: the memory hierarchy and caching; the design of Larc-in-Logisim and relevant material on logic circuits; the x86-64 architecture; x86-64 assembly language programming; the Linux C calling convention; and basic functions from the Linux standard library. This includes material from labs 7 through 11. For textbook readings, you can consult the weekly entries on the course web page for the sixth through eleventh weeks. A detailed list of topics is given below.
For the memory hierarchy, there will be only general questions; you do not need to understand how caching is implemented. For Larc-in-Logisim, you should be familiar with the overall design, and you should remember enough about logic circuits to do the sorts of things that were used in the implementation. You will not need to memorize the commands for assembling and linking assembly language programs, and you will not need to memorize the details of register use or the Linux C calling convention beyond knowing which registers to use for the first four function arguments; if more information is needed, it will be provided to you. There will be no questions about: debugging or ddd; C programming or pointers in C; specific syscalls; or assembly language instructions that are not listed below.
The format of the test will be as usual. There will be four pages. The types of questions might include: definitions, short-answer and longer essay-type questions, basic coding questions using x86-64 assembly language, reading and explaining assembly language instructions, implementing control structures in assembly language, writing and using functions in assembly langauge, and designing basic circuits similar to ones used in Larc-in-Logisim.
Here are some terms and ideas that you should be familiar with:
Larc-in-Logisim
how a complicated logic circuit can store and execute computer programs
the overall structure (like how the register file connects to the ALU)
the role of the clock
the role of the PC
the structure of the register file
how different sources of input can be selected for the PC and register
how the opcode is used to control the computation
how to build a logic circuit to test the opcode
the memory hierarchy
registers, cache memory, RAM, hard disks and SSDs
how levels of the memory hierarchy compare in terms of speed, cost, and size
caches and why they are used
the x86-64 architecture (for integers only)
16 general purpose registers
how registers are used for 8-bit, 16-bit, 32-bit, and 64-bit values
flag register, including the carry flag, C, and other flags
a memory location holds one byte; an address is 64 bits
little-endian representation of integers
x86-64 assembly language
assembling an assembly language (.asm) file with yasm to get an object (.o) file
linking object files with ld to get an executable program
sections of a program: .data, .text
data sizes: byte, word, dword, qword
declaring initialized variables in the .data section: db, dw, dd, and dq
declaring strings and arrays in the .data section
using registers in assembly langauge
64-bit registers rax, rbx, rcx, rdx, r8 through 15
32-bit registers eax, epx, ecx, edx, r8d through r15d
accessing memory, with brackets []
using a data size in an assembly instruction, such as inc dword [A]
labels
global and extern
the _start label for marking the entry point of a program
basic assembly language commands (see list below)
comparing values and jumping
the stack and the rsp register; push and pop
calling and returning from functions
syscall and why it exists (but nothing about any specific syscall)
the difference between pointers (addresses) and values (in memory)
translating Java-style control structures into assembly language
accessing array elements with notations like [A + r12*8]
writing and using functions in assembly language
how the stack is used for functions
calling convention
the Linux C calling convention
in the C calling convention, arguments are passed in rdi, rsi, rdx, rcx
callee-saved and caller-saved registers in the C calling convention
writing functions that can be called from C
using functions from the C standard library
using printf for output of integers and strings
understanding C function prototypes well enough to call a function
x86-64 assembly instructions that you should know for the test:
add <dest>, <src> and <dest>, <src> jmp <label>
sub <dest>, <src> or <dest>, <src> je <label>
inc <dest> not <dest>, <src> jne <label>
dec <dest> jg <label>
imul <dest>, <src> call <label> jge <label>
div <dest>, <src> ret jl <label>
mov <dest>, <src> push <src> jle <label>
pop <dest> cmp <op1> <op2>
1. What memory is allocated by the following .data section in an x86-64 assembly language program?
section .data A: dq 100 B: dd 10, 2, 5, 3 C: db "fizzbuzz", 0
2. Using the declarations from the .data section in the previous problem, what value is placed into the eax register by the following assembly language instructions? Explain!
mov eax, [B] imul eax, [B+4] imul eax, [B+8] imul eax, [B+12]
3. Suppose that list is defined in a .data section to refer to an array of 64-bit integers. Write assembly instructions to use the standard printf function to output the first three items in the array. Use the following format string:
listfmt: db "The first three items are %ld, %ld, and %ld.", 10, 0
4. What value is placed into the rax register by the following code? Explain!
mov rax, 24 mov r12, 10 mov rdx, 0 div r12 imul rdx, 10 add rax, rdx
5. Assume that X, Y, and Z are defined in a .data section as labels that refer to 64-bit values. Translate the following if statement into x86-64 assembly language instructions:
if ( X > Y ) {
Z = 1;
}
else if (X == Y) {
Z = 2;
}
else {
Z = 3;
}
6. What is accomplished by the following assembly language instructions? What would A and B have to be? (Your answer might include a translation of the assembly code into pseudocode.)
mov r12, 0 mov r13, 0 startloop: cmp r12, 12 je done add r13, [A + r12*8] mov [B + r12*8], r13 inc r12 jmp startloop done:
7. Suppose that when building the Larc computer, there is a wire that you want to be on for opcodes 1001, 1100, and 1011. Draw a logic circuit whose input is the four-bit opcode and whose output is that wire.
8. When the Larc computer is executing a program, the next value of the PC can come from three different sources. What are two of those sources and under what circumstances is each source used for input to the PC?
9. Discuss some of the ways that an assembly language such as x86-64 assembly differs from a high-level language such as Java.
10. Explain how using a memory cache can allow a program to run faster than it would run without the cache.