For the following questions, consider the following AT&T syntax x86-64 assembly instruction:

movq (%rax, %rbx, 4), %rcx

And assume that, just before this instruction executes, registers have values as follows:

For each of the following assembly snippets, identify which are possible values of the ZF and SF condition codes.

    cmpq $0, %rax
    jl skip
    imulq $-1, %rax
skip:
    testq %rax, %rax

    movq $0, %rax
    cmpq %rax, %rax
    leaq 0x12345678(,%rax,4), %rax

For the following questions, consider static linking using object files as discussed in lecture.

Suppose one converts the following two assembly files into an executable (where ... represents some code that is not shown, and .asciz is an assembly directive to generate a nul-terminated ASCII string, and .global LABEL is a directive that causes the assembler to ensure that a specified label LABEL can be referenced from other files):

Assembly file main.s:

.text
.global main
main:
    mov $0, %r11
    mov $10, %r10
loop:
    mov $percent_d, %rdi
    mov %r11, %rsi
    call printf
    incq %r11
    decq %r10
    jge loop
    mov $0, %rax
    ret

.data
.global percent_d
percent_d:
    .asciz "%d"

Assembly file printf.s:

.text
.global printf
printf:
    movb (%rdi), %al
    ...
    ...
    ret

.data
...

Consider the single-cycle processor design we discussed in lecture (built using the components we discussed in lecture that executes every instruction in one cycle) executing the instruction:

mrmovq 10(%rax), %rbx

Consider the single-cycle processor design we discussed in lecture (built using the components we discussed in lecture).

Suppose one wanted to add support for a new push2q REG1, REG2 instruction which would be equivalent to pushq REG1 and pushq REG2 but be completed by one instruction (and in one cycle).

Consider a seven-stage pipelined processor with a 100 ps cycle time. Suppose this processor is executing instructions A, B, C, D, E, ... in order. (Assume no pipeline stalls, etc. are involved.)

Consider building a pipeline processor similar to our textbook's design Suppose the times required for components are as follows:

• pipeline registers (including PC) -- 10 ps (the "register delay")
• instruction memory read -- 175 ps
• PC increment computation -- 20 ps
• register file read -- 125 ps
• register file write -- 150 ps
• ALU -- 120 ps
• data memory read or write -- 175 ps

For the following questions, consider a four-stage pipelined processor built using the design we discussed in lecture but with the following stages:

• fetch
• decode
• execute
• memory and writeback

(That is, the memory and writeback stages are combined.)

Suppose this processor uses forwarding to resolve data hazards. If forwarding alone is insufficient, the processor combines forwarding with a minimum amount of stalling.

subq %rcx, %rax
addq %rdx, %rax

mrmovq (%rcx), %rax
subq %rcx, %rax

addq %r8, %r9
subq %r9, %r10
irmovq $42, %r9
rmmovq %r9, 0(%r10)
rmmovq %r8, 8(%r10)

For the following questions, consider the following assembly snippet:

        pushq %rax 
        addq %rcx, %rdx   
        jle foo          
        xorq %rdx, %rdx                  
        andq %r9, %r10       
        subq %r11, %r12
        nop
foo:    rrmovq %rdx, %r8        
        irmovq $10, %r13        
        rmmovq %r14, 0(%r15)    

For the questions below, consider a six-stage processor, similar in design to the one discussed in lecture, with the following stages:

• fetch
• decode
• execute part 1
• execute part 2
• memory
• writeback

In this processor, the result of arithmetic (such as performed by the addq or xorq instructions) or of evaluating the condition codes to determine if a conditional jump is taken is not available until near the end of the execute part 2 stage. In particular, a conditional jump that was not predicted correctly will not be able to fetch the instruction that follows the jump instruction until the jump instruction is in the memory stage.

Assume the processor uses forwarding and, where necessary, stalling to resolve data hazards. Control hazards are resolved as described in each question below.

Suppose a five-stage processor was executing during cycle N:

• instruction E in the fetch stage,
• instruction D in the decode stage,
• instruction C in the execute stage,
• instruction B in the memory stage
• instruction A in the writeback stage

and that the processor wants to stall instruction C and squash instructions B and A, so during the following cycle N+1:

• instruction E in the fetch stage,
• instruction D in the decode stage,
• instruction C in the execute stage,
• instruction B is running a nop (a pipeline "bubble") *[edit after quiz: should have written "the memory stage is running a nop"]
• instruction A is running a nop (a pipeline "bubble") *[edit after quiz: should have written "the writeback stage is running a nop"; also to squash instruction A, we need to something in addition to adjusting the pipeline registers]

Suppose we have a four-stage pipelined processor with the following stages:

• fetch
• decode
• execute and memory
• writeback

Suppose, unlike the processor we've discussed in lecture, this processor uses branch prediction which predicts are conditional jumps as not taken. When a conditional jump is mispredicted, the processor detects the misprediction during the corresponding jump instruction's execute stage, and retrieves the correct instruction in the following cycle.

Suppose the processor is executing the following assembly snippet:

        xorq %rax, %rax
        jle foo
        andq %rcx, %rdx
        pushq %rdx
foo:    addq %r8, %r9
        subq %r9, %r10
        xorq %r10, %r11

When the above assembly is run, the pushq instruction is fetched as a result of the misprediction.

For each of the pairs below, select which one is expected to exhibit more temporal locality.

Suppose a direct-mapped cache with a write-allocate, write-back policy has the following contents:

Suppose a 2-way set-associativate cache with an LRU (least recently used) replacement policy and a write-no-allocate, write-through policy has the following contents:

Suppose a direct-mapped cache with a write-allocate, write-back policy has the following contents:

Consider a system with two-level cache hierarchy where:

• the first-level cache has a hit time of 2 cycles
• the shared second-level cache has a hit time of 10 cycles
• main memory has an access time of 200 cycles

Suppose a workload is measured to have

• a 80% first-level cache hit rate
• a 90% second-level cache hit rate

The following question ask about what data cache misses occur for a particular cache and a particular piece of C code. For those questions assume:

• that only accesses to array use the data cache specified
• that the data cache is initially empty (all invalid)
• the address array[0] is a multiple of 2 to the 20th power (so array[0] is at the beginning of a cache block and has set index 0 in almost any cache)
• accesses in the omitted code labelled ... are irrelevant to the question
• the compiler compiles the loops so that the accesses to array are not reordered and does not omit any accesses to array

unsigned char array[280];
...
for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 280; ++j) {
        array[j] += 1;
    }
}

unsigned char array[2500];
...
for (int i = 0; i < 2500; i += 1000) {
    array[i] += 1;
}
for (int i = 0; i < 2500; i += 990) {
    array[i] += 1;
}

For the following questions, consider the following C code:

int A[1024 * 1024], B[1024 * 1024], C[1024 * 1024];

void foo1() {
    for (int i = 0; i < 1024; ++i) {
        for (int j = 0; j < 1024; ++j) {
            A[i + j] = B[j * 4] * C[i * 1024 + j];
        }
    }
}

void foo2() {
    for (int i_outer = 0; i_outer < 1024; i_outer += 16) {
        for (int j = 0; j < 1024; ++j) {
            for (int i = i_outer; i < i_outer + 16; ++i) {
                A[i + j] = B[j * 4] * C[i * 1024 + j];
            }
        }
    }
}

For the following questions, consider the following assembly code:

        movq $100, %rax             /* 1 */
begin_loop:     
        movq (%r8, %rax, 8), %r10   /* 2 */
        movq (%r9, %rax, 8), %r11   /* 3 */
        subq %r11, %r10             /* 4 */
        jg not_negative             /* 5 */
        neg %r10                    /* 6 */
not_negatve:
        addq %r10, %r13             /* 7 */
        subq $1, %rax               /* 8 */
        jg begin_loop               /* 9 */

(The neg (negate) instruction is equivalent to multiplying a value by negative 1.)

Consider the following assembly snippet:

addq %r8, %r9
subq %r8, %r10
imulq %r9, %r10
andq %r9, %r8
xorq %r11, %r12

addq ___ (1), ___ (2) -> ___ (3)
subq ___ (4), ___ (5) -> ___ (6)
imulq ___ (7), ___ (8) -> ___ (9)
andq ___ (10), ___ (11) -> ___ (12)
xorq ___ (13), ___ (14) -> ___ (15)

For the following question, consider the following C code:

void foo(int N, int *A, int *B, int *C) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            C[i] += A[j*N+i] + B[i+j];
        }
    }
}

Consider a system with 12-bit virtual addresses, 11-bit physical addresses, and 256-byte pages. On this system, page offsets are therefore 8 bits, virtual page numbers are 4 bits and physical page numbers are 3 bits.

Suppose a process's page table is as follows:

Consider a system with 12-bit virtual addresses, 11-bit physical addresses, and 256-byte pages.

Suppose a process's page table is as follows:

Consider a system with:

• 32-bit virtual addresses
• 32-bit physical addresses
• 4096 byte pages
• page tables stored in memory as an array
• 4-byte page table entries, which, when interpreted as a 4-byte integer consist of:
  • a physical page number (stored in the 20 most significant bits)
  • 11 unused bits, and
  • a valid bit (stored in the least significant bit)
• a current value for the page table base register of 0x88000, which is a physical byte address

In lecture, we mentioned a scheme where the operating system can allocate memory on demand. The following questions are about how that scheme might be implemented.

Consider a system that uses a two-level page table structure with 8192-byte pages and 1024 page table entries per table (at each level), where each page table entry is 8 bytes.

Suppose the processor is running with a page table base pointer containing physical (byte) address 0x44440000. When looking up the physical address for virtual address 0x12345678, the processor determines that the relevant first-level page table entry (that is, the one in the table pointed to by the page table base pointer) was marked valid and contained the physical page number 0x1111, and the relevant second-level page table entry was marked valid and contained the physical page number 0x4321.

Suppose a system has:

• a two-level page table structure with 16384-byte pages (below the "first-level page table" is the page table in this structure which is located via the page table base pointer)
• 4096 page table entries per level
• 38 bit virtual addresses
• 4-byte page table entries
• 36 bit physical addresses
• a 32-entry 2-way set associative TLB

If on this system, the processor looks up virtual address 0x52345, and:

• reads a first-level page table entry at index 0x0 in the first-level page table located at physical address 0x800000; then
• reads a second-level page table entry at index 0x14 in the second-level page table located at physical address 0x50000
• determines (using the second-level page table entry) that the physical address corresponding this virtual address is 0x5a345