CPSC313 Midterm Sample

1a) The classic RISC pipeline consists of 5 stages, what are they?

1b) Fetch is responsible for which actions? Check all that apply.

1c) Which of the following is a decode action?

1d) Which of the following is an execute stage action?

1e) Which of the following is a memory stage action?

1f) Which of the following is a write back stage action?

2a) Why is the memory stage after the execute stage? Include a Y86 instruction that could not be implemented if you reversed the order.

2b) Why is the execute stage after the decode stage? Include a Y86 instruction that could not be implemented if you reversed the order.

2c) Why is the write-back stage after the memory stage? Include a Y86 instruction that could not be implemented if you reversed the order.

3a) RISC instruction sets do not allow ALU operations to read from memory. Explain how the structure of the pipeline leads this restriction.

3b) Describe how the pipeline could be modified to lift this restriction. You may not change the number of pipeline stages or their basic function. Your revised pipeline does not need to be able to implement every Y86 instruction (in fact it would not be able to) but it must be able to execute instructions like: addl (%eax), %ebx # r[ebx] = r[ebx] + m[r[eax]]

3c) This revised pipeline must place some restrictions on the revised ISA that it implements. One of the impacts is on mrmovl and rmmovl. Describe the problem and modify the instructions so that they will work with the new pipeline. Note that the revised versions need not be as powerful as the original ones, but they must still load and store between memory and a register.

Consider the following five-stage pipeline with stage delays (including overheads) of 34 ps, 42 ps, 75 ps, 50 ps and 18 ps. What is the maximum clock rate (i.e., fastest) acceptable for this pipeline? [blank_start]1 cycle / 75ps = 1000/75 Ghz[blank_end]

Consider the following five-stage pipeline with stage delays (including overheads) of 34 ps, 42 ps, 75 ps, 50 ps and 18 ps. What is the maximum throughput of this pipeline? [blank_start]1/75 instructions per picosecond[blank_end]

4c) Consider the following five-stage pipeline with stage delays (including overheads) of 34 ps, 42 ps, 75 ps, 50 ps and 18 ps. What, if anything, might cause the actual throughput of programs to be lower than this maximum?

Consider the following five-stage pipeline with stage delays (including overheads) of 34 ps, 42 ps, 75 ps, 50 ps and 18 ps. What is the minimum instructions latency of this pipeline? [blank_start]75ps + 75ps + 75ps + 75ps + 75ps[blank_end]

5a) Consider the following piece of Y86 assembly code: [0] addl %eax, %ebx [1] irmovl $1, %eax [2] mrmovl %(ebx), %ebx [3] addl %ebx, %eax List all of the output dependencies present in this code.

5a) Consider the following piece of Y86 assembly code: [0] addl %eax, %ebx [1] irmovl $1, %eax [2] mrmovl %(ebx), %ebx [3] addl %ebx, %eax List all of the anti dependencies present in this code.

5a) Consider the following piece of Y86 assembly code: [0] addl %eax, %ebx [1] irmovl $1, %eax [2] mrmovl %(ebx), %ebx [3] addl %ebx, %eax List all of the causal dependencies present in this code.

5b) Consider the following piece of Y86 assembly code: [0] addl %eax, %ebx [1] irmovl $1, %eax [2] mrmovl %(ebx), %ebx [3] addl %ebx, %eax List all of the data hazards present in this code for the Y86, five stage pipeline

5c) Consider the following piece of Y86 assembly code: [0] addl %eax, %ebx [1] irmovl $1, %eax [2] mrmovl %(ebx), %ebx [3] addl %ebx, %eax For each hazard, indicate the total number of bubbles added by the Pipe-Minus implementation

5d) Consider the following piece of Y86 assembly code: [0] addl %eax, %ebx [1] irmovl $1, %eax [2] mrmovl %(ebx), %ebx [3] addl %ebx, %eax For each hazard, indicate the total number of bubbles added by the Pipe implementation

Describe the implementation of the following new instruction for Y86 Seq as you did in Homework 2. This instruction is similar to mrmovl except that it adds 4 to rB and does not have a static-displacement operand. It would be useful, for example, for iterating over an array of integers. Syntax: mrmovincl (rB), rA Semantics: r[rA] <= m[r[rB]] r[rB] <= r[rB] + 4 Memory Layout: | 5 | F | rA | rB | Describe each stage using a relaxed syntax similar as shown below. The Fetch and PC Update stages are complete. List only the code that would be added for this instruction. Fetch: f.iCd = m[F.pc] >> 4 f.iFn = m[F.pc] & 0xf f.rA = m[F.pc+1] >> 4 f.rB = m[F.pc+1] & 0xf f.valP = F.pc + 2 Decode: d.srcA = [blank_start]R_NONE[blank_end] d.srcB = [blank_start]D.rB[blank_end] d.dstE = D.rB d.dstM = [blank_start]D.rA[blank_end] d.valB = [blank_start]r[d.srcB][blank_end] Execute: e.aluA = 4 e.aluB = [blank_start]E.valB[blank_end] e.aluFun = [blank_start]A_ADD[blank_end] e.valE = [blank_start]4 + E.valB[blank_end] Memory: m.valM = [blank_start]m4[M.valB][blank_end] Write Back: r[W.dstE] = [blank_start]W.valE[blank_end] r[W.dstM] = [blank_start]W.valM[blank_end] PC Update (pseudo stage): w.pc = W.valP

Write Y86 assembly code that computes the sum of an array of integers where the address of the array is stored in %ebx and the length of the array is in %ecx. Place the sum in %eax. irmovl $0, [blank_start]%eax[blank_end] #SET SUM TO 0 irmovl $[blank_start]1[blank_end], %edi #HOW MUCH WILL THE LENGTH DECREMENT BY AS YOU ITERATE? irmovl $[blank_start]4[blank_end], %esi #AN ARRAY OF INTEGERS HAS ELEMENTS WITH A SIZE OF? [blank_start]andl[blank_end] %ecx, %ecx #IS THE LENGTH OF THE ARRAY 0? jle L1 L0: [blank_start]mrmovl[blank_end] [blank_start](%ebx)[blank_end], %edx #STORE ADDRESS OF ARRAY INTO %edx addl [blank_start]%edx[blank_end], %eax #ADD VALUE OF ELEMENT IN THE ARRAY TO SUM addl [blank_start]%esi[blank_end], %ebx #INCREMENT THE ARRAY POINTER subl [blank_start]%edi[blank_end], %ecx #DECREMENT THE LENGTH OF THE ARRAY [blank_start]jg[blank_end] L0 #CHECK IF LENGTH IS STILL GREATER THAN ZERO L1:

8a) What is spatial locality and why is it important?

8b) What is temporal locality and why is it important?

8c) What is instruction-level parallelism and why is it important?

8d) What is thread-level parallelism and why is it important?

Polymorphic dispatch common to object-oriented languages like Java is implemented using a double-indirect call instruction that reads an address from memory and then jumps to it. Explain why it is challenging to implement such an instruction without stalling in a pipelined processor.

Consider the following instruction-execution frequencies for a program running on the standard Y86 Pipe processor. The table shows, for example, that 7% of all instructions executed read the value of a register immediately after the preceding instruction modified that register by writing into it a value that came from memory. 7% read register immediately after an instruction writes into that register a value it reads from memory 6% read register immediately after an instruction writes into that register a value computed in Execute 12% conditional jump that is taken 8% conditional jump that is not taken 5% call 5% ret 57% the remaining introduce no bubbles What is the average cycles per instruction for this execution?

Consider the following instruction-execution frequencies for a program running on the standard Y86 Pipe processor. The table shows, for example, that 7% of all instructions executed read the value of a register immediately after the preceding instruction modified that register by writing into it a value that came from memory. 7% read register immediately after an instruction writes into that register a value it reads from memory 6% read register immediately after an instruction writes into that register a value computed in Execute 12% conditional jump that is taken 8% conditional jump that is not taken 5% call 5% ret 57% the remaining introduce no bubbles What is the throughput of this execution on a 3-Ghz processor (ie 3*10^9 cycles per second)? (You may go back one question to see what you chose for the answer.