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.1 to 4.4

Q2: Why are multiplexers required, as shown in Figure 4.2? 
Solution: We cannot wire data lines from multiple sources together. Instead, we require a logic circuit element to select between the sources.

Q3: Match the logic design terms to their corresponding definitions. 
Solution:
Combinational element: The outputs depend only on the current inputs
State element: The outputs depend on current inputs and internal stored values
Edge-triggered clocking: All state changes occur on a clock edge
Control signal: Directs operation of a functional unit or selection by a multiplexer
Data signal: Contains information that is operated on by a functional unit

Q4: The register file is a state element that consists of a set of registers that can be read and written by supplying a register number to be accessed. 
Solution: True

Q6: The single-cycle datapath conceptually described in Section 4.3 must have separate instruction and data memories, because 
 Solution: the processor operates in one cycle and cannot use a single-ported memory for two different accesses within that cycle.

Q8: How does the datapath in Figure 4.17 determine the outcome of a beq instruction? 
Solution: The ALU subtracts the operands and asserts the Zero output if the difference is zero. That, ANDed with the Branch decode signal, controls the multiplexer to select the next PC value.

Q10: The clock cycle time for the datapath described in Section 4.4 is determined by the longest chain of functional units used for any instruction. All instructions thus take that amount of time to execute. For this reason, single-cycle implementations are the main form of processor used today. 
Solution: False 

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)