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.