In lecture, we discussed the idea of a processor being connected to memory and I/O devices via common bus. Suppose we are executing the instruction movq (%rbx), %rax in this model. The processor will send messages over the bus in order to ___. Select all that apply.

Consider the following C snippet:

c = str[x+2];

where c is declared as a char, str is declared as a char * (pointer to char; and based on the context of the snippet a pointer to the beginning of an array of char), and x is declared as a long.

Suppose str is stored in the register %rax, x in %rdi, c in the register %bl, and %r8 through %r15 can be used for temporary values. Which (if any) of the following are correct translations to assembly? Select all that apply.

Consider the following C snippet:

unsigned long x;
unsigned long *p;
...
*p = x * 2;

If:

• x is stored in %rax,
• p is stored in %r8, and
• %r9 is a register available to store temporary values

then which of the following x86-64 assembly snippets are equivalent to the C statement above? Select all that apply.

Consider the expression

(((x & 0xFF0F) >> 2) & 0xFF0) == (((x & 0xFF0) >> 2) & 0xFF0F)

where x is a 32-bit unsigned integer. The set of values x for which the above expression is true is the same as the set of values for which the expression (x & Y) == 0 is true for some constant Y. What is the value of Y? Write your answer as a hexadecimal number.

Suppose we start with the mov-to-register CPU we described in lecture which implements the Y86 instructions irmovq, mrmovq, and rrmovq. This processor design had MUXes (represented in HCLRS by case expressions) that chose between several inputs based primarily on what the current instruction was. When adding a new instruction, for some of these MUXes, we can use an existing input and modify when it is selected to include the new instruction. For others, we may need to add a new input to this MUX for the new instruction (or some other logic that achieves this effect). In a few cases, we may even need to add a new a MUX (or other logic that achieves the same effect).

Suppose we added the addq instruction to the mov-to-register CPU. For which of the following parts of the circuit would we need to add a new MUX or a new MUX input (or equivalent logic) rather than modifying the conditions for selecting existing MUX inputs? Select all that apply.

In Y86, the popq instruction is encoded using 2 bytes. Suppose we made a variant of Y86 that instead encoded popq in one byte, where the high-order four bits of the first byte would be 0xB (like popq is in normal Y86) and the low-order four bits of the first byte would be the register index corresponding to the operand to popq.

Supporting this new encoding would likely ____. Select all that apply.

Suppose we added the instruction

immovq CONSTANT, DISPLACEMENT(rA)

to the single-cycle Y86-64 processor design we discussed in lecture. This instruction would store the 64-bit value CONSTANT in memory at an address computed by adding the value of the register rA to the 64-bit constant DISPLACEMENT.

While this instruction is executing, the value input to the data memory (called mem_input in HCLRS) will be equal to ______.

Suppose a single-cycle processor design has a cycle time of 3000 ps. If this design is modified into an 8-stage pipelined processor (using the same storage components and adding pipeline registers) and this results in a performance improvement, then the new cycle time would be greater than _____ ps and less than _____ ps. Choose the tightest bounds you can infer from the information in the question. Write your answer as two numbers of picoseconds seperated by a comma. (For example, if you think the answer is "greater than 100 ps and less than 200 ps" write "100,200".)

Suppose we construct a pipelined processor by modifying the single-cycle processor design we saw in lecture and that our pipeline processor has two stages:

• Fetch and Decode; and
• Execute and Memory and Writeback

With these stages, the pipeline registers should contain (at least when certain instructions are being run) ____. Select all that apply.

Suppose we modified the four-stage pipelined addq processor we discussed in lecture to have three stages:

• Fetch;
• Decode and Execute; and
• Writeback

With these three stages, suppose we run the following assembly and resolve data hazards with stalling:

addq %r8, %r9  
addq %r10, %r9   
addq %r8, %r10      
addq %r8, %r9    

Suppose the first instruction is fetched during cycle 1 (and so performs its decode during cycle 2 and its writeback during cycle 3). During what cycle would the last add instruction run its writeback stage?

Consider the following assembly code:

addq %r8, %r9
mrmovq 16(%r8), %r9
subq %r9, %r10
xorq %r9, %r11
rrmovq %r9, %r12

When the above instruction is executed on a five-stage pipelined processor which uses forwarding to resolve hazards in a way that minimizes stalling like we discussed in lecture, which of the following forwarding operations must occur? Select all that apply

Consider the five-stage pipelined processor design discussed in lecture but with a different branch prediction strategy: instead of predicting conditional jumps as always taken, predict them as taken if they target an address that is less than the jump instruction's and as not taken if they target an address than is greater than the jump instruction's. (This strategy is called "forward not-taken, backwards taken").

In this processor, incorrectly predicted branches require 2 extra cycles, instructions that use a value computed in memory by the previous instruction in the ALU require 1 extra cycle, and returns require 3 extra cycles. (And no other cases require extra cycles due to hazards.)

Suppose the instructions run in a program are:

• 10% conditional jumps, of which
  • 40% are taken and jump to an address that is less than the jump instruction's
  • 20% are taken and jump to an address that is greater than the jump instruction's
  • 10% are not taken and jump to an address that is less than the jump instruction's
  • 30% are not taken and jump to an address that is greater than the jump instruction's
• 10% instructions that use (for an ALU operation) a value loaded from memory by the previous instruction; and
• no ret instructions

About how many average cycles per instruction would the program experience on the processor described above?

Suppose the contents of a two-entry direct-mapped cache is as follows:

(In the table above, data bytes are listed with the lowest address's value first (left-most).)

The byte of memory at address 0x11 (binary: 10001) is stored in this cache and has the value 0x3F.

Bytes from which of the following memory addresses are also stored in the cache shown above? (Note that addresses may be written without all leading 0s.) Select all that apply.

Suppose a program accesses a cache in the following pattern:

• it reads a 4 byte array A, one byte at a time, from beginning to end; then
• it overwrites the same array A, one byte at a time, from end to beginning; then
• it repeats the above steps 9 more times; then
• it reads a different 4-byte array B, one byte at a time, from beginning to end

Assume the above accesses use a cache that is not also used for other accesses and that the cache is initially empty.

If the cache used for the accesses above is a 4-byte, direct-mapped cache with a write-through, write-no-allocate policy and 2 byte blocks, how many accesses (reads or writes) to the next level of cache (or main memory if there is not next level) will be performed when the above cache accesses happen?

Consider a system with the following caches and performance results on a benchmark:

• a L1 cache with a 3 cycle access time (hit or miss) and a 99% hit rate
• a L2 cache with a 10 cycle access time (hit or miss) and a 80% hit rate
• a L3 cache with a 50 cycle access time (hit or miss) and a 95% hit rate

and main memory has a 200 cycle access time.

Assume that accesses to the next level of cache are not started until the access time on the current level completes.

What is the average memory access time (in cycles) on this system?

Many caches store tags, valid bits, and other metadata separately from the data. One result of this design is that misses can be detected more quickly, after completing an access to likely faster "tag store".

Suppose a cache using this design:

• experiences a 90% hit rate on a benchmark
• has a 5 cycle hit time,
• takes 2 cycles to detect a hit or miss,
• once a miss is detected, starts an access with the next level of the memory hierarchy, which will take 100 cycles

Without the optimization to detect hits or misses early, this cache would have an average memory access time of 5 + 10% * 100 = 15 cycles. What would the average memory access time with this optimization be?

Suppose we have a 2-way, 2-set data cache with 8 byte blocks and an LRU replacement policy and run the following C code:

int array[12];
... /* code omitted */
int sum = 0;
for (int j = 0; j < 2; j += 1) {
    for (int i = 0; i < 4; i += 1) {
        if (sum > array[i * 3 + j]) {
            sum += array[i * 3 + j];
        }
    }
}

Assume that:

• the compiler does not reorder operations in the loop;
• only accesses to array in the loops use the data cache;
• the data cache is initially empty when the loop starts;
• the address of array[0] is a multiple of 1024

How many data cache misses will occur when the loops above run?

[Note that unlike some of the examples in lecture, the number of misses for each of the two sets of the cache may be different.]

Consider the following C code:

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

Consider the following attempts at optimizing the above C code:

/* version A */
for (int ii = 0; ii < N; ii += 2) {
    for (int i = 0; i < ii + 2 && i < N; i += 1) {
        for (int jj = 0; jj < N; jj += 2) {
            for (int j = 0; j < jj + 2 && j < i; j += 1) {
                A[i] += B[i * N + j] * C[j * N + i];
            }
        }
    }
}

/* version B */
for (int ii = 0; ii < N; ii += 2) {
    for (int jj = 0; jj < ii + 2; jj += 2) {
        for (int i = 0; i < ii + 2 && i < N; i += 1) {
            for (int j = 0; j < jj + 2 && j < i; j += 1) {
                A[i] += B[i * N + j] * C[j * N + i];
            }
        }
    }
}

/* version C */
for (int i = 0; i < N; i += 1) {
    int j = 0;
    for (; j + 1 < i; j += 2) {
        A[i] += B[i * N + j] * C[j * N + i];
        A[i] += B[i * N + j+1] * C[(j+1) * N + i];
    }
    if (j < i)
        A[i] += B[i * N + j] * C[j * N + i];
}

/* version D */
for (int j = 0; j < N - 1; j += 1) {
    int i;
    for (i = 0; i + 1 <= j ; i += 2) {
        A[i] += B[i * N + j] * C[j * N + i];
        A[i] += B[(i+1) * N + j] * C[j * N + i+1];
    }
    if (i <= j)
        A[i] += B[i * N + j] * C[j * N + i];
}

Assuming N is very large (relative to the cache size), which of the above attempts at such optimizations are most likely to be successful at reducing the number of data cache misses?

Consider the folowing assembly code:

xorq %rbx, %r8
andq %rbx, %r9
subq %r8, %rbx
addq %rbx, %r9

after register renaming, the physical register that andq reads to obtain the value of %rbx will be the same as ____. Select all that apply.

Consider the following assembly function 'satSum':

satSum:
    movq %rdi, %rax
    addq %rsi, %rax
    cmpq %rsi, %rax
    jb retMax
    cmpq %rdi, %rax
    jb retMax
    ret
retMax:
    movq $-1, %rax
    ret

Inlining this function would most likely allow an optimizing compiler to avoid including an instruction very similar to ___. Select all that apply.

The vector instructions we discussed in lectures supported loading a vector of values from (or storing a vector of values to) a single location in memory. In addition to these types of vector load and store instructions, some vector instruction sets include support for an instruction that takes a vector of memory locations and fills a vector by loading an element from each of those memory locations (or stores a vector by storing an element to each of those locations). These more featureful vector load and store instructions are typically substantially slower than those that load from (or store to) a single location.

When vectorizing which of the following snippets would these special vector load and store instructions be useful? Select all that apply.

Consider a single-core system with an operating system that uses time multiplexing (with context switching) to share the processor between multiple processes.

Initially, process A is running the following assembly snippet:

movq $100, %rax
movq $200, %rcx
addq %rcx, %rax

After the second movq and before the addq instruction can complete, the operating system switches to process B. After process B starts running, ____. Select all that apply.