Homework on Textbook Sections 4.7 to 4.11, 5.1 to 5.3

For Questions 1 to 5: In the following code sequence, we need to stall the RISC-V pipeline to resolve the load-use data hazard:

i1: ld   x8, 0(x$5)
i2: add  x9, x8, x10
i3: addi x9, x9, -1
i4: sd   x9, 0(x5)

Consider the cycle when i1 is in the EX stage, i2 is in the ID stage, and i3 is in the IF stage.

Question 1: What is the value of ID/EX.MemRead in this cycle?

Solution:

1

Question 2: What is the value of ID/EX.RegisterRd in this cycle?

Solution:

8

Question 3: What is the value of IF/ID.RegisterRs1 in this cycle?

Solution:

8

Question 4: What is the value of IF/ID.RegisterRs2 in this cycle?

Solution:

10

Question 5: Which instruction (i1, i2, i3, or i4) will be fetch by the IF stage in the next cycle?

Solution:

i3

Question 8: For the 2-bit branch predictor shown in Figure 4.61, label the states anti-clockwise from the bottom left as 0, 1, 2 and 3, as shown below.

Assume the initial state for a branch is state 0. A given branch has the following history (T = taken, N = not taken):

N, N, T, T, T, N, N

What is the state of the predictor after this history?

Solution:

1

For Questions 11 to 15: Consider a system using 28-bit addresses, with a direct-mapped cache of 32Kbytes and a block size of 64 bytes. The cache uses a write-through/no-allocate strategy without a write buffer.

Question 11: How many bits are required for the offset field of an address?

Solution:

6

Question 12: How many bits are required for the index field of an address?

Solution:

9

Question 13:

How many bits are required for the tag field of an address?

Solution:

13

Question 14: How many bits of storage are required for the cache, in addition to those for data storage?

Solution:

7,168

Quiz on Textbook Sections 4.7 to 4.11

Question 1: In the following RISC-V instruction sequence executed in the 5-stage pipeline, which instructions use forwarded data?

i1:  sub  x2, x1, x3    # Register x2 written by sub
i2:  and  x12, x2, x5   # 1st operand (x2) depends on sub
i3:  or   x13, x6, x2   # 2nd operand (x2) depends on sub
i4:  add  x14, x2, x2   # 1st (x2) and 2nd (x2) depend on sub
i5:  sd   x15, 100(x2)  # Base (x2) depends on sub

Solution:

i2 and i3

Question 2: In the case of a load-use data hazard, how does the pipeline stall the instruction using the loaded data?

Solution:

It prevents update of the PC and IF/ID pipeline registers, and sets the control values for EX, MEM and WB to 0 in the ID/EX pipeline register.

Question 3: If branch computation is moved from the EX stage to the ID stage, forwarding paths are required from the EX/MEM and MEM/WB pipeline registers to the branch comparison logic in the ID stage.

Solution:

True

Question 4: Match the following descriptions to the correct terms.

Solution:

Prediction of branches at runtime using runtime information.
dynamic branch prediction

A small memory that is indexed using the address of the branch instruction and that contains bits indicating whether the branch was recently taken or not.
branch prediction buffer

A structure that caches the destination PC or destination instruction for a branch.
branch target buffer

A branch predictor with multiple predictions for each branch and a selection mechanism that chooses which predictor to enable for a given branch.
tournament branch predictor

Question 5: Which of the following events would cause an exception or interrupt in a RISC-V computer system?

Solution:

A request from an I/O device
An undefined instruction
An operating system request from a user program

Question 6: In a static dual-issue processor with 5 pipeline stages, what is the maximum number of instructions that can be in progress at any time?

Solution:

10

Question 7: Loop unrolling is a technique to get more performance from loops that access arrays, in which multiple copies of the loop body are made and instructions from different iterations are scheduled together.

Solution:

True

Question 8: Match the following descriptions to the defined terms.

Solution:

Hardware support for reordering the order of instruction execution so as to avoid stalls.
dynamic scheduling

A situation in pipelined execution when an instruction blocked from executing does not cause the following instructions to wait.
out-of-order execution

A commit in which the results of pipelined execution are written to the programmer visible state in the same order that instructions are fetched.
in-order commit

The buffer that holds results in a dynamically scheduled processor until it is safe to store the results to memory or a register.
reorder buffer

Question 9: Which of the following correctly describes the ARM Cortex-A8 processor?

Solution:

Dynamic multiple-issue, static in-order pipeline scheduling

Question 10: Which of the following correctly describes the Intel Core i7 920 processor?

Solution:

Dynamic multiple-issue, dynamic out-of-order pipeline scheduling

Quiz on Textbook Sections 4.5 and 4.6

Question 2: Suppose a single-cycle datapath has 4 major function units each with a latency of 200ps. A pipelined version of this datapath has one stage for each of the function units, with the same latencies. What is the speed up of the pipelined version compared to the single-cycle datapath?

Solution:

4

Question 3: Match the following descriptions to the defined terms.

Solution:

When a planned instruction cannot execute in the proper clock cycle because the hardware does not support the combination of instructions that are set to execute.

structural hazard

When a planned instruction cannot execute in the proper clock cycle because data that is needed to execute the instruction is not yet available.

data hazard

When the proper instruction cannot execute in the proper pipeline clock cycle because the instruction that was fetched is not the one that is needed; that is, the flow of instruction addresses is not what the pipeline expected.

control hazard

Question 4: For the following RISC-V code sequence:
ld    x7, 0(x3)
addi  x8, x7, 1
the RISC-V pipeline can use forwarding to completely eliminate stall cycles.

Solution:

False

Question 5: How many stall cycles are required the following code sequence executing in the RISC-V pipeline, assuming all required forwarding paths are included?
slli  x6, x10, 3
add   x6, x6, x18
ld    x20, 0(x6)
addi  x28, x20, -1

Solution:

1

Question 6:  Branch prediction reduces the effect of branch hazards by assuming a given outcome for a branch and proceeding from that assumption, rather than waiting to ascertain the actual outcome.

Solution: 

True

Question 7: What is the latency, in clock cycles, for the following instruction in the RISC-V pipeline, assuming no stall cycles?
andi  x30, x8, 0x0ff

Solution:

5

Question 9: Consider execution of a sd instruction in the RISC-V pipeline, with the instruction word being fetched in cycle n, and no stalls. In which cycle is the value of the MemWrite control signal determined, and in which cycle is it used?

Solution:

Determined in cycle n + 1, used in cycle n + 3

Question 10: The pipeline registers in the RISC-V pipeline contain control signal values for use in subsequent pipeline stages.

Solution:

True

Homework on Textbook Sections 1.1 to 1.4, 1.6 to 1.9, 2.1 to 2.8

Q1: HTC’s VIVE VR headset, comprising two displays for stereo video, has the following specifications:

•     Resolution: 1080 × 1200 per eye

•     Refresh Rate: 90Hz

Assuming 24bit/pixel video, what data rate in Gbps (Gigabits/sec) is required on the HDMI cable for the device?

Solution: 5.5987

Q2: A processor, which has a clock frequency of 1.3GHz, take 10s to run a program of 6×10^9 instructions. What is the average number of cycles per instruction? 

Solution: 2.167

Q3: Suppose, for the program in Question 2, the instructions are composed as follows:

Instruction class	Instruction count	CPI
Arithmetic/logic	4×10^9	1
Load/store	1×10^9	6
Branch	1×10^9	3

We are trying to redesign the processor to increase performance by a factor of 1.25, but this would lead to an increase in the CPI for load/store instructions from 6 to 8. What clock frequency in GHz would be needed for the redesigned processor?
Solution: 1.875

Q4: Instead of trying to increase the performance of the single processor, we can consider using multiple processor cores in a computer. Suppose, for the program in Question 2, parallelizing the program to use p processor cores divides the number of arithmetic/logic instructions by 0.7p, the number of load/store instructions by 0.8p, and the number of branches by 0.9p. What is the minimum number of processor cores required to improve performance by a factor of 3? 
 Solution: 4

Q5: What is the actual speedup achieved with the number of processor cores you identified in Question 4? 
 Solution: 3.14

Q6: What RISC-V instruction is encoded by the hex word 0x0051E933? 
Solution: or x18, x3, x5

Q7: What hex word encodes the RISC-V instruction ld x9, -24(x10)? 
Solution: 0xFE853483

Q8: If x9 initially contains the value 0xC445028461001003, what value (in hex) is placed in x18 by the following instruction?

srai x18, x9, 6?
Solution: 0xFF11140A11840040




Q9: Which of the following RISC-V instruction sequences extracts the 6-bit field from bits 4 to 9 of x10 and places it in the least-significant 6 bits of x7? 
 Solution: andi x7, x10, 0x3F0
srli x7, x7, 4
 
Q10: Write RISC-V instructions for the following C statements, assuming a is in x9 and b is in x18:

if (a == b)
  a = a + 1;
else
  a = a - 1;
 
Solution: bne x9, x18, L1
addi x9, x9, 1
beq x0, x0, L2
L1: addi x9, x9, -1
L2:

Q11: What C statements are encoded by the following, assuming x10 contains the signed int variable m?

      addi x5, x0, 20
      bgeu x10, x5, skip
      jal  x1, my_func
skip:
 
Solution: if (m >= 0 && m < 20) my_func(m);

Q12: Write RISC-V instructions for the following leaf function:

int min(int a, b) {
  return a < b ? a : b;
}
Solution: min: bge x10, x11, L1
           add x10, x0, x10
           jalr x0, 0(x1)
L1: add x10, x0, x11
        jalr x0, 0(x1)

Q13: Write RISC-V instructions for the following recursive function, without eliminating the recursion (i.e., without replacing it by a loop):

int sum(int n) {
  if (n == 0)
    return 0;
  else
    return n + sum(n – 1);
}
Solution: sum: addi sp, sp, -16
            sd x1, 8(sp)
            sd x8, 0(sp)
            beq x10, x0, ret
            add x8, x0, x10
            addi x10, x10, -1
             jal x1, sum
             add x10, x8, x10
ret: ld x8, 0(sp)
         ld x1, 8(sp)
         addi sp, sp, 16
         jalr x0, 0(x1)

Quiz on Textbook Sections 2.1 to 2.8

Q1: What C statement is represented by the following RISC-V assembly code?

add  x5, x8, x9
add  x6, x20, x11
sub  x8, x5, x6
Solution: a = (a + b) - (c + d);

Q2: Which of the following RISC-V instruction implements the C assignment

n = A[3];

assuming n is in x9, the base address of A is in x10, and A is an array of uint64_t?
Solution: ld  x9, 24(x10)

Q3: The statement that RISC-V is little-endian means that the least-significant byte of a doubleword in memory is at the lowest address and the most-significant byte the doubleword is at the highest address. 
Solution: True

Q4: What range of values can be used as the immediate operand in a RISC-V addi instruction? 
Solution:  −2048 to +2047
 
Q5: What RISC-V instruction is encode by the hexadecimal word 04533023? 
Solution:  sd  x5, 0x040(x6)

Q6: If the register x8 contains the value 0x804600B91200C00F, what value is placed in x5 by the instruction

srli x5, x8, 4
Solution: 0x0804600B91200C00


Q7: What C statement is implemented by the following RISC-V assembly code, assuming a is in x9 and b is in x18?

    blt  x18, x9, L1
    addi x9, x9, 1
L1:
Solution: if (a <= b) a = a + 1;


Q8: Which of the RISC-V code sequences correctly implements the C statements

i = 0;
while (A[i] != 0) i++;

assuming i is in x9 and the address of A is in x18
Solution:

    addi x9, x0, 0
L1: slli x5, x9, 3
    add  x5, x5, x18
    ld   x5, 0(x5)
    beq  x5, x0, L2
    addi x9, x9, 1
    j    L1
L2:

Q10: The RISC-V calling convention uses registers x10 to x17 for parameter passing. If a procedure has more than eight parameters, where are the additional parameters passed? 
 Solution:
They are pushed onto the stack by the caller.