Consider the following AT&T syntax assembly:

addq %rbx, %rbx
addq %rax, %rbx
movq (%rbx), %rax

Which of the following assembly snippets will result in the same final value of %rax? (Ignore changes to the value of %rbx.) Select all that apply.

Suppose the assembly label array is defined to be a constant 5-byte array as follows:

array:
   .byte 3
   .byte 4
   .byte 5
   .byte 6
   .byte 7

and the linker chooses to locate this array at address 0x10000. (Each .byte directive specifies the value of one byte of memory.)

Then, if we run the assembly snippet:

    movq $1, %rax
    addq $array, %rax
    movb 1(%rax), %bl

What would the value of 8-bit register %bl be afterwards? You may assume memory around array is not modified before this snippet is run.

Write your answer as a hexadecimal number. If not enough information is given write "unknown".

Consider the following C function:

long foo(long a, long b) {
    return a + b;
}

Which of the following are correct translations (but perhaps unnecessairily complex) of this function to AT&T syntax assembly (using the Linux x86-64 calling convention)? Select all that apply.

If x and y are 32-bit signed ints with values between -1000000 and 1000000 on a system that uses two's complement, which of the following C expressions are always true? Select all that apply.

Which of the following C expressions will, given an unsigned integer x, return the least significant 4 bits of the integer with its bits reversed. For example, if x in binary was 11001000001101, the result would be (in binary) 1011 (the reverse of 1101). Select all that apply.

Which of the following are examples of properties of an instruction set architecture (ISA) as opposed to properties of a particular microarchitecture?

Which of the following are likely attributes of processors following the RISC (reduced instruction set computer) design philosophy when compared to processors following the CISC (complex instruction set computer) design philosophy? Select all that apply.

Which of the following are valid Y86-64 code? Select all that apply.

Consider the following Y86-64 machine code, written as a sequence of bytes in hexadecimal:

 50 76 74 00 00 00 00 00 00 80 60 12 61 84 00 00 00 00 00 00 00

If we translate this to assembly (assuming the first instruction starts at the first byte) then the first two instructions would be:

Consider the following Y86-64 machine code, written as a sequence of bytes in hexadecimal:

30 f1 78 56 34 12 00 00 00 00 10

Write Y86-64 assembly for the first instruction in this machine code.

Consider the following HCLRS code snippet where ... represents some omitted code:

register xY {
    foo : 64 = ...;
    bar : 64 = ...;
}
...
x_foo = Y_foo + Y_bar;
x_bar = Y_bar - Y_foo;

During cycle 10, Y_foo has the value 500 and Y_bar has the value 300. What is the value of Y_foo during cycle 12? (Write your answer as a base-10 number, like 123.)

Assume that cycles are seperated by a rising edge of the clock signal.

Using the kind of registers we described in lecture and in section 4.2.5 of our textbook, suppose a register's output is 42 and its value input is also 42 and the clock signal is high. Then the following happens in this order:

2. the clock signal falls (becoming low)
3. the register's value input changes to 44
4. the register's value input changes to 45
5. the clock signal rises (becoming high again)
6. the register's value input changes to 46
7. the clock signal falls (becoming low)
8. the register's value input changes to 47

What will the value of the register's output be after this occurs? If not enough information is given to answer write unknown and explain in the comment field.

Consider the following HCLRS code snippet:

wire x : 64;
wire y : 64;
x = [
    y == 4 : 4;
    (y & 1) == 0 : 3;
    y > 10 : 2;
    1 : 1;
];

If y is 100 what is the value of x?

Using the instruction memory design we discussed in lecture designed for use in implementing the Y86-64 instruction set, the size of the output of the instruction memory ____.

Consider the following HCLRS code snippet:

reg_srcA = 8;
reg_dstE = 0;
reg_inputE = reg_outputA;

If this were part of an HCLRS processor which does not have any other code using the register file inputs and outputs, then

In the single-cycle Y86-64 processor design we discussed in lecture, which of the following operations may overlap in time with the addition of registers' values for an add instruction? Select all that apply.

In lab to implement condition codes, we suggested declaring condition code registers using

register cC {
    SF:1 = 0;
    ZF:1 = 1;
}

and then using

stall_C = (icode != OPQ);

to keep the condition code registers from changing when the instruction was not an OPq instruction. We noted that, in HCLRS, "Register banks like cC have a special input stall_C which, if 1, causes the registers to ignore inputs and keep their current value." (Each register bank has its own stall signal, this one is stall_C, since the condition code registers were declared using register cC.)

If register banks did not provide this stall signal, we could have implemented the functionality using a case expression (MUX) when setting c_SF and c_ZF. What would the corresponding code for setting c_ZF look like?

Consider a three-stage pipelined processor The operations of the stages of this processor, including register delays for any required pipeline registers, take:

• 200 ps (first stage)
• 250 ps (second stage)
• 300 ps (third stage)

What is the best possible cycle time of this processor? Write your answer as a base-10 number of picoseconds.

Consider a three-stage pipelined processor has a cycle time of 500 picoseconds. Suppose this processor runs 5 instructions in the following order: A (completes first), B, C, D, and E (completes last). What is the time between when the instruction A starts its first stage and when instruction E starts its third stage? If multiple amounts of time are possible, write the minimum time. Write your answer as a base-10 number of picoseconds.

Suppose a processor designer took a three-stage pipelined processor design with a cycle time of 800 ps and turned it into a six-stage processor pipelined design that implemented the same ISA. Both the three-stage and six-stage processors were designed to achieve about the best cycle times possible (despite the constraints that lead to diminishing returns as one tries to add pipeline stages to a processor). Which of the following would be the most likely cycle time for the six-stage processor design?

Suppose we have a six-stage pipelined processor with 500 ps cycle time.

Running a particular benchmark program which executes 1 billion (10 to the 9th power) instructions in a simulator, we determine that 5% of its instructions require exactly one cycle of stalling and 10% require exactly two cycles of stalling and no instructions would require more than two cycles of stalling.

(For the purposes of this question, a cycle of stalling means one bubble (hardware-generated nop) inserted in the pipeline rather than advancing an instruction. Assume we attribute each stall to exactly one instruction.)

Assume these stalls are the only reasons why the processor would not complete one program instruction every cycle.

To the nearest millisecond, how long (in milliseconds) will the benchmark program take to run? Write your answer as a base-10 number of milliseconds.

Consider the following assembly snippet: (where ... represents irrelevant instructions):

    addq %rax, %rcx
    subq %rcx, %rdx
    je foo
    xorq %rcx, %rdx
    ...
    ...
    ...
foo:
    irmovq $10, %rax /* A */
    irmovq $20, %rbx /* B */
    ...

where the je is not taken.

Suppose that we are executing the assembly snippet on a five-stage pipelined processor based on the design in lecture that:

• uses forwarding to resolve data hazards to the extent possible without substantially increasing the cycle time, and
• speculates that all conditional jumps will be taken, like we described in lecture, so the instructions labeled A and B will be fetched in the two cycles after the je is fetched and then squashed (discarded)
• when a conditional jump is not taken like the processor guessed, fetches the corrected instruction during the memory stage of the conditional jump instruction (the cycle after determining what address to fetch in the conditional jump's execute stage)

Which of the following is true about what happens when the above assembly executes? Select all that apply.

Consider a direct-mapped cache which contains 256KB of data (1KB = 1024 bytes) and uses 256 byte blocks. When there is a cache miss for address 0x12345, this cache will copy an entire 256-byte block from memory into the cache. What is the lowest address of a byte in this block? (Write your answer in hexadecimal.)

Consider a 64KB direct-mapped cache with 32 byte blocks. (1KB = 1024 bytes)

In this cache, the byte at address 0x12345 would (if present in the cache) be stored in the same set as the byte at address ____ would be stored (if present in the cache). Select all that apply.

Consider a 8KB 2-way set associtiave cache with an LRU replacement policy and 64-byte blocks. (1KB = 1024 bytes.)

Suppose the cache is initially empty (all valid bits set to 0), then the program acceses 1 byte from each of the following addresses in the following order:

• 0x10005
• 0x40000
• 0x12400
• 0x10001
• 0x33320

Immediately after the accesses described above, give an example of an address which, if read using this cache, would cause something to be evicted from the cache:

Suppose we have a system with:

• a 2-set direct-mapped cache with 8 byte cache blocks
• 4-byte ints (so each cache block can store 2 ints)

and run the following code:

int array[9];
...
int count1 = 0, count2 = 0, count3 = 0;
count1 += array[0];
count1 += array[3];
count1 += array[6];
count2 += array[1];
count2 += array[4];
count2 += array[7];
count3 += array[2];
count3 += array[5];
count3 += array[8];

Assuming that:

• array[0] is assigned an address at the beginning of a cache block
• the assembly the compiler generates for the above code does not reorder or omit data cache accesses
• only accesses to array use the data cache, and
• the cache is initially empty

how many data cache misses should we expect?

(Note that unlike the examples in lecture, the 9 accesses here are not evenly distributed across cache sets.)

Consider the following assembly snippet:

addq %rax, %rbx
mrmovq 8(%rbx), %rax
subq %rbx, %rcx

In lecture, we discussed how an out-of-order processor may perform register renaming where it converts instructions from using architectural registers (the ones that appear in assembly) to physical registers (used internally in the processsor). When doing this, the processor ensures that each version of an architectural register's value uses a different physical register, which aids in resolving hazards.

After an out-of-order processor performs register renaming on the above instructions as discussed in lecture, which of the following statements about the physical registers used by the renamed versions of the above instructions will be true?

Suppose an out-of-order processor has two execution units (that matter for this questions):

• a 1-cycle adder (that can perform one add per cycle)
• a 3-cycle pipelined multiplier (that can start one multiply per cycle, but finishes it two cycle later)

Suppose on this processor the results of an addition or multiply can be used to start another addition or multiply in the cycle after the first addition or multiply completes.

Consider the following C snippet:

a = b + c;
d = e * f;
h = a + d;
i = a * d;

With the processor described above, what's the fastest time (in cycles) the above C snippet can execute? (Do not attempt to count for time doing instruction fetching, register renaming, etc. — just the time to finish the actual computation.)

In lecture, we discussed the use of multiple accumulators to improve performance in addition to simple loop unrolling. Consider the following pair of unrolled loops with and without use of multiple accumulators:

/* loop, without multiple accumulators transformation */
for (int i = 0; i < N; i += 4) {
    product = product * (a[i] * b[i]);
    product = product * (a[i+1] * b[i+1]);
    product = product * (a[i+2] * b[i+2]);
    product = product * (a[i+3] * b[i+3]);
}

/* loop, with multiple accumulators transformation */
for (int i = 0; i < N; i += 4) {
    product1 = product1 * (a[i] * b[i]);
    product2 = product2 * (a[i+1] * b[i+1]);
    product1 = product1 * (a[i+2] * b[i+2]);
    product2 = product2 * (a[i+3] * b[i+3]);
}
product = product1 * product2;

Whether this transformation would be helpful depends on the execution units the processor has.

Suppose the performance of the execution units that perform the multiplications (represented by a * operations in the C code above) is what determines the performance of the loop overall. To make it easier to reason about performance, assume the execution units that perform these multiplications are never involved in any of the address or index calculations needed by the loop above (so one only needs to consider how the multiplication instructions are dispatched and executed).

Given which configuration(s) of execution units to perform the multiplications could the loop's performance benefit from the multiple accumulators optimization shown above? Select all that apply.

Which of the following optimizations are likely to significantly decrease the number of times an instruction that accesses the data cache runs? Select all that apply.

Consider the following two C functions:

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

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

(The two functions differ in their loop orders.)

A compiler cannot generate identical for these two functions because in cases where A and result are pointers that refer to the same data (a problem we called "aliasing"), they can write different answers to the result array.

Which of the following are examples of calls to all_pairs_products1 which could result in different values in the array array than if the same call were made to all_pairs_products2 instead? Select all that apply.

In lecture we discussed vector instructions (also known as SIMD instructions) where a single instruction can perform an operation on every pair of values in two vectors, which are typically fixed-sized array stored in registers.

Using vector instructions similar to those used in the lab, which of the following code snippets is simplest to transform into a version that makes effective use of vector instructions?

/* loop A */
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        A[j*N + i] += A[i*N + j];
    }
}

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

/* loop C */
for (int i = 2; i < N; ++i) {
    A[i] *= (A[i-1] + A[i-2]);
}

(Assume A, B, and C are independent arrays.)

Suppose a program A makes a system call requesting to "sleep" for 2 seconds. During those 2 seconds the operating system runs a program B, then it switches back to program A.

When the operating system later switches back to program A, the first instruction it runs is most likely:

In lecture, we discussed the idea of an exception table, which is used as part of handling exceptions. Which of the following statements about the exception table are true?

Suppose a system has 15-bit virtual addresses, 13-bit physical addresses, and page tables with a total of 32 entries. What is the size of pages on this system (in bytes)?