💯 CSC3060 Quiz Q&A

April 7, 2026

⚠️ 两次 quiz 卷面满分都是 120，但只要拿 ≥ 100 分都属于实际满分。

CSC3060 2026Spring Quiz1

Section I (30 points): Select the best answer. The answer is shown after each question.

What is computer architecture?

a) It is the hardware implementation of a computer

b) It is the interface between the software and the hardware (Answer)

c) It is the rules and conventions that a programmer must follow

d) It is the components of a computer, including I/O, CPU, and memory
Which of the following is not a system program?

a) ChatGPT (Answer)

b) Compiler

c) OS

d) Linker
In the memory there is a sequence of 128 bits of zero. Which of the following is not a possible representation?

a) It may be two long integer zeros.

b) It may be four single‑precision floating point +0.0

c) It may be a character string “0000000000000000” (Answer)

d) It may be one quadruple‑precision floating‑point value +0.0
What illusion does a memory hierarchy give you?

a) The memory space is all yours.

b) A memory that is fast, large and inexpensive (Answer)

c) A memory that is small, large and expensive

d) A memory that is fast, small and inexpensive
Which of the following phases is not part of the “gcc” command?

a) Preprocessing b) Linking

c) Compiling

d) Loading (Answer)
Which of the following architectures has only sixteen general‑purpose registers?

a) RV32MI

b) RV32EM (Answer)

c) RV64IM

d) RV32ME
Which of the following descriptions of the RV32I ISA is not true?

a) It is for 32‑bit processor implementations; the address range is limited to 4 GB.

b) Its memory is byte‑addressable.

c) It requires an on‑chip cache hierarchy implemented (Answer)

d) It supports 32 general‑purpose registers X0–X31.
When a program is interrupted, what information must be saved so the program can resume after the interrupt is handled?

a) The memory

b) All the files used by this application program

c) The architectural state (registers, PC, etc.) (Answer)

d) The cache contents
How do you set up a 32‑bit constant 0xAABBCCDD in register X2?

a) li x2, 0xAABBCCDD

b) addi x2, x0, 0xAABBCCDD

c) lui x2, 0xAABBC; addi x2, x2, 0xCDD (Answer)

d) lw x2, 0xAABBCCDD(x0)
Why do RISC machines often require data to be naturally aligned?

a) Address generation would be easier

b) To make the data memory more compact

c) To support the C and E extension

d) To avoid data items crossing cache lines or page boundaries (Answer)
What range can an indirect jump (JALR) instruction in RV32I reach?

a) 512 KB

b) 1 MB

c) 4 MB

d) The full 4 GB address space (Answer)
When implementing the add(a,b) function in Project 1, what does the expression (a & b) « 1 represent?

a) The bitwise sum without any carries.

b) The values of the carry bits that need to be added in the next iteration (Answer)

c) The absolute difference between the two numbers.

d) A logical shift to check for overflow.
In the subtract(a,b) function, how is the subtraction operation typically transformed to use the add() function?

a) By calculating add(a, ~b) directly.

b) By performing a bitwise XOR and then a right shift.

c) By transforming it into add(a, add(~b, 1)) using two‑’s complement logic (Answer)

d) By using a loop to count the difference between a and b.
On a RV64I/FD processor, for the following struct:
```
struct S {
     int   white;
     long  count;
     char  c;
     long  red;
     int   green;
     char  d;
     int   blue;
   } A[1000];
```
Assume the starting address of A is stored in register X1. What instruction should be used for A[10].blue = 0?

a) sw x0, 322(x1)

b) sw x0, ‑520(x1)

c) sw x0, 340(x1)

d) sw x0, 4840(x1)

e) sw x0, 520(x1) (Answer)
Which of the following decimal numbers have exact representations in IEEE‑754 floating‑point format?

a) 1.625 (Answer)

b) 1.405

c) 1.35

d) 1.245

e) 1.11

Section II (40 points): Multiple choice (one or more correct answers). Put all correct letters; the answers are shown in parentheses.

Which of the following is the correct representation of 2050₁₀ in 16 bits?

a) 0b0000100000000010 (Answer)

b) 0x0813

c) 0x0802 (Answer)

d) 0b0000100000100011
What is ABI?

a) ABI stands for Application Binary Interface (Answer)

b) ABI is just like an API

c) ABI includes the OS system calls, the ISA and the calling convention (Answer)

d) ABI defines whether an application binary is compatible with a computer system (Answer)
Which of the following instructions belong only to RV64I instead of RV32I?

a) sra x1, x6, x7

b) ld x1, 0(x2) (Answer)

c) lwu x1, 0(x2) (Answer)

d) slli x5, x6, 35 (Answer)
The contents of three floating‑point registers are:
```
 F1 = 0x40800000,
 F2 = 0x3F800000,
 F3 = 0xC0800000.
```
Which of the following is correct?

a) (F3 + F1) == 0.0 (Answer)

b) F3 < F2 < F1 (Answer)

c) F2 = F1 / F3

d) F3 = ‑(F1 * F2) (Answer)
Which of the following statements about jump instructions are true?

a) Jump instructions (JAL and JALR) have 20‑bit and 12‑bit immediates (Answer)

b) Jump instructions are in UJ‑type only

c) Jump instructions can be used for function calls (Answer)

d) JALR has a larger jump range than JAL (Answer)
Which of the following number systems has both +0 and –0?

a) Signed‑magnitude integers (Answer)

b) Two’s‑complement integers

c) One’s‑complement integers (Answer)

d) IEEE‑754 floating‑point numbers (Answer)
Which of the following statements about the branch and the store is true?

a) Both instructions generate a 12‑bit (±2¹¹) byte offset

b) The immediate in the store instruction is an offset relative to rs1, and in a branch instruction it is relative to the PC (Answer)

c) Both instructions generate a 12‑bit offset relative to the base register rs1

d) Branch instructions lack the rd (destination) field (Answer)
Assume A, B, C are int and X, Y, Z are floating‑point variables. Which of the following expressions are always true?

a) A*A >= 0

b) (X + Y) + Z == X + (Y + Z)

c) if (A < 0) then ‑A > 0

d) A == (int)(double)A (Answer)
Assume variable A is an integer. Under what conditions would the results from a big‑endian machine be different from those of a little‑endian machine?

a) Store A as an int but read it as a sequence of char (Answer)

b) Store A as a long and read it as a long

c) Store A as an int and read it as an int

d) Store A as a sequence of char but read it as an int (Answer)
What does “32” mean in RV32I?

a) The ISA has 32 general‑purpose registers

b) The ISA can address up to 2³² bytes

c) The instructions are 32 bits long

d) The general‑purpose registers are 32 bits wide (Answer)

e) The ISA contains 32 instructions

Section III (50 points): Short and brief answers. Provide concise explanations.

The RISC‑V F/D extension added a fused multiply‑add (FMA) instruction that uses a special R4 type to compute A = B × C + D.

a) How could you redesign this instruction using only three operands so that no new R4 type is needed? (3 points)

Answer: Make the addend operand implicit by reusing the destination register: define an instruction like fmadd rd, rs1, rs2 that computes rd = rd + (rs1 × rs2). By using the destination register both as the addend and the destination, only three register operands are needed and the standard R‑type format can be reused.

b) What regularity of the RV ISA does the design in (a) disrupt? (2 points)

Answer: RISC‑V instructions normally treat the destination register separately from the source registers; changing the meaning of rd to also hold one of the input operands breaks the clean separation between sources and destination. It also destroys orthogonality—one cannot freely choose all three source operands, because one of them must be the same as the destination.

c) A floating‑point multiply typically takes about 5 cycles and an add takes about 4 cycles. Why is FMA still only a 5–6‑cycle operation rather than a 9‑cycle operation? (3 points)
Answer: In a fused multiply‑add, the multiplier and adder stages are overlapped in a single pipeline: the product and the addend are formed in parallel and only one rounding is performed at the end. By merging the two operations, intermediate rounding and normalisation are avoided, so the hardware can compute the multiply and add in almost the same time as a single multiply, thus 5–6 cycles instead of 9.

bfloat16 is a 16‑bit floating‑point format designed by Google for machine learning.

a) IEEE 754‑2008 also defines the half‑precision FP16 format. Why do GPUs employ such low‑precision floating‑point formats? (3 points)
Answer: Many deep‑learning workloads do not require full single‑precision accuracy; using 16‑bit formats cuts memory bandwidth and storage in half, increases the number of values that can be processed in parallel, and reduces power consumption. Lower‑precision arithmetic provides higher throughput for training and inference while keeping enough numerical fidelity for neural‑network computations.

b) Why is bfloat16 more popular than IEEE FP16? (3 points)
Answer: bfloat16 keeps the same 8‑bit exponent as single‑precision but only 7 bits of mantissa, giving it the same dynamic range as FP32. That makes it much easier to convert FP32 values to bfloat16 without overflow or underflow and preserves the scale of gradients during training. In contrast, IEEE FP16 has only a 5‑bit exponent and frequently overflows/underflows. Thus bfloat16 is more robust for training neural networks and simpler to support in hardware.

Assume your machine is RV32I and function arguments unsigned int a, int b, c are passed in registers a0–a2. For each of the following C expressions, suggest efficient RV32I instructions.

a) a * 4: Use a left shift by 2: slli a0, a0, 2.

b) b * 61: Compute using shifts and subtracts because RV32I has no multiply. For example:

   slli t0, a1, 6        # t0 = b << 6  (b * 64)
   slli t1, a1, 1        # t1 = b << 1  (b * 2)
   sub  t0, t0, t1       # t0 = b * 64 - b * 2 = b * 62
   sub  t0, t0, a1       # t0 = b * 62 - b = b * 61

The result in t0 is b*61.

c) a / 8: For unsigned division by a power of two, use a logical shift right: srli a0, a0, 3.

d) b >> 3: An arithmetic right shift for a signed integer: srai a1, a1, 3.

e) b / 8: Signed division by 8 is not the same as an arithmetic shift because C truncates toward zero. One way is:

   srai t0, a1, 3          # tentative quotient = b >> 3
   srai t1, a1, 31         # t1 = sign bit replicated (0 or –1)
   andi t1, t1, 7          # t1 = mask = (1<<3)–1 if b < 0 else 0
   add  a0, t0, t1         # a0 = corrected quotient

f) a % 128: Use a bit mask: andi a0, a0, 127.

g) pow(2, a): Start with 1 in a temporary register and shift left by a:

   li   t0, 1
   sll  t0, t0, a0

h) a = (b >= c): Compute the comparison and set a to 1 or 0:

   slt  t0, a1, a2     # t0 = 1 if b < c else 0
   xori t0, t0, 1      # invert to get b >= c
   mv   a0, t0         # result in a0

i) b * c: RV32I has no hardware multiply, so you would implement a shift‑add loop:

   mv   t0, a1         # multiplicand = b
   mv   t1, a2         # multiplier = c
   li   t2, 0          # accumulator = 0
loop:
   andi t3, t1, 1
   beq  t3, x0, skip
   add  t2, t2, t0     # add multiplicand if low bit of multiplier is 1
skip:
   slli t0, t0, 1      # multiplicand <<= 1
   srli t1, t1, 1      # multiplier >>= 1
   bnez t1, loop
   mv   a0, t2         # a0 holds b*c

The Intel Itanium architecture includes 128 general‑purpose registers. Should we add 128 registers to RV64I? Why or why not? (6 points)

Answer: Increasing the register file to 128 registers would lengthen the instruction encoding—each register specifier would need 7 bits instead of 5. To keep 32‑bit instruction words, RISC‑V would have to shrink immediate fields or restrict other encodings, harming code density. A larger register file also increases context‑switch overhead and pipeline complexity. RISC‑V already allows register‑rich implementations via register windows or the “Zmmul” extension without changing the ISA. Therefore, adding 128 architected registers would provide only marginal benefit while complicating the instruction encoding and hardware.

When we access an array element A[i] we need a base register for the address of A and an index register for i. Why isn’t there a load instruction like lw rd, (rs1 + rs2)? (5 points)
Answer: RISC‑V keeps the load/store addressing modes simple: a base register plus a small immediate offset. An address form rs1 + rs2 would require an extra adder in the memory stage and complicate hazard detection, increasing cycle time. Compilers can generate an ADD instruction to compute rs1 + rs2 into a temporary register and then use a standard load; this extra instruction is inexpensive and preserves pipeline simplicity and code density.

Estimate the latencies (in clock cycles) of the following operations on a typical RV32I/F core. (5 points)

Operation	Estimated latency (cycles)
Integer multiply (via shift/add)	≈3 cycles
Integer divide (via software)	≈10 cycles
SP FP add	≈4 cycles
SP FP multiply	≈5 cycles
FP to int conversion	≈5 cycles

CSC3060 2026Spring Quiz2

Section I (30 points): Select the best answer. The answer is shown after each question.

Branch prediction should be performed at which of the pipelined stages?

a) IF (Answer)

b) ID

c) EXE

d) MEM

e) WB
Which branch/jump instruction generated from the following C statements is most difficult to predict?

a) if

b) for

c) switch (Answer)

d) while

e) function call
Which of the following microarchitectures may have a CPI lower than 1?

a) Superscalar implementation (Answer)

b) Single‑cycle data path implementation

c) Multi‑cycle data path implementation

d) Pipelined implementation
In the RISC‑V calling convention, which of the following registers is a callee‑save register?

a) x0

b) ra (return address)

c) t1

d) s1 (Answer)

e) a1
Which of the following implementations would have the highest instruction execution throughput?

a) Single‑cycle data path

b) Multi‑cycle data path

c) Pipelined data path

d) Superscalar and pipelined data path (Answer)
The ARM Cortex‑A57 is a processor with 16 pipeline stages. The decision for a branch instruction is made quite late, near the end of the pipeline. Assume 20% of the instructions executed are branches and the average CPI is 1. Without branch prediction, what would be the performance penalty caused by branches in an A57?

a) 90%

b) 75% (Answer)

c) 50%

d) 20%
Why do some RV pipelined data‑path designs utilize a comparison unit to execute compare‑and‑branch instructions instead of using the standard ALU?

a) To avoid structural hazards

b) To avoid setting the wrong branch condition due to subtraction overflow

c) Because the comparison unit does not trap

d) The ALU is reserved to compute PC + immediate (Answer)
Which of the following control signals is most difficult to generate?

a) ALUsrc (ALU source)

b) PCsrc (PC source) (Answer)

c) Wren (write enable)

d) ALUctr (ALU control)

e) MemRd (memory read)
Which pipelined register stores the least amount of information?

a) IF/ID

b) ID/EX

c) EX/MEM

d) MEM/WB (Answer)
Which DRAM is used in Nvidia’s high‑end GPU global memory?

a) Traditional DRAM

b) HBM (Answer)

c) SDRAM

d) RDRAM

e) DDR5 DRAM
How do we index to a branch history table in the correlated branch prediction (two‑level adaptive branch prediction)?

a) The current PC ⊕ the global history shift register value (Answer)

b) The PC address of the current branch instruction

c) The current PC + the value of the global history shift register

d) The current PC ⊕ the branch address
Which dependency type is the “true dependence” in code scheduling?

a) WAW (Write After Write)

b) RAW (Read After Write) (Answer)

c) WAR (Write After Read)

d) RAR (Read After Read)
In your Project #2, which of the following commands prints only the content of register a0 in decimal?

a) print a0 (Answer)

b) info registers

c) x/d a0

d) print/x a0
Regarding Project #2 – Bomb Lab, which of the following statements is correct?

a) The only way to solve Bomb Lab is by brute‑force guessing.

b) The bomb is an executable file that can run on any RISC‑V platform.

c) The goal of Bomb Lab is to determine the correct inputs for each phase without causing the bomb to explode. (Answer)

d) In RV321, argument registers such as aO and al will stay unchanged throughout the entire function lifetime.
RISC‑V would be a fixed‑length ISA if it did not have which extension?

a) A

b) B

c) C (Answer)

d) D

e) F

Section II (40 points): Multiple Choice (one or more correct answers). Put all correct letters; the answers are shown in parentheses.

Which of the following codes’ performance is limited by operation latency rather than bandwidth?

a) A single query checking your account balance (Answer)

b) Large matrix multiplication

c) Chasing a linked list to locate the end of the list (Answer)

d) Traversing a binary tree to find a data item (Answer)
In which situations should caller‑saved registers be considered for allocation?

a) Leaf routines (Answer)

b) A temporary value used across multiple calls

c) Temporaries in expression evaluation (Answer)

d) Array variables

e) Local scalar variables
What hazards might commonly occur when performing a binary tree search on a pipelined data path?

a) Tree hazards

b) Structure hazards

c) Data hazards (Answer)

d) Control hazards (Answer)
In the RV32I processor data path, what are the possible selections for the address of the next instruction to be fetched?

a) PC

b) PC + 4 (Answer)

c) PC + immediate (Answer)

d) RS1 + immediate (Answer)

e) (RS1 + immediate) (memory indirection)
Most modern microprocessors have split I/D caches. Why?

a) To avoid structural hazards in the pipeline (Answer)

b) To get a higher overall cache hit rate

c) To increase processor reliability

d) To increase the cache access bandwidth (Answer)
Under what circumstances might a longer/deeper pipeline be less desirable?

a) When there are frequent branch mispredictions (Answer)

b) When there are intensive data dependencies among instructions (Answer)

c) When there are frequent memory operations

d) When there are lots of instruction cache misses (Answer)

e) When there are frequent procedure calls (Answer)
A scheduler gives the following schedule for the dependency graph on the right. Which of them are valid scheduling (i.e., produce the same result as the unscheduled code block)?

a) 0 1 2 5 3 9 4 7 6 8 10 (Answer)

b) 0 2 1 5 3 8 4 7 9 6 10 (Answer)

c) 0 2 4 1 3 7 9 6 5 8 10

d) 0 1 2 3 5 4 7 8 6 9 10 (Answer)

e) 0 1 2 3 4 5 6 7 8 9 10 (Answer)
Which of the following are techniques used to reduce the penalty caused by control hazards?

a) Pipelined stalls
b) BTB (branch target buffer) (Answer)

c) untagged BHT (branch history table) (Answer)

d) Always predict backward branches taken (Answer)

e) Data forwarding
What locality is exhibited by the following C loop?
```
while (A != NULL) A = A->next;
```
a) Data temporal locality

b) Data spatial locality

c) Structural locality

d) Instruction temporal locality (Answer)

e) Instruction spatial locality
What information is stored in each cache block (line)?

a) Byte offset

b) Cache block data (Answer)

c) Cache block tag (Answer)

d) A valid bit (Answer)

e) A set number

Section III (50 points): Short and brief answers. Provide concise explanations.

Data Hazards (13 points)

We are given the following RV32I code sequence:

1. LW  S1, 8(S0)
2. LW  S2, 16(S0)
3. SUB T4, S2, S1
4. AND T5, T4, T3
5. SUB S4, T4, T3 
6. ADD T6, S4, T4
7. SW  T6, 4(S7)
8. LW  S3, 24(S7)
9. LW  S1, 8(S7)
10. LW  S5, 32(S0)
11. ADD T7, S3, S1
12. LW  S6, 64(S0)

a) In a 5‑stage pipeline without data forwarding, many data hazards will be detected. How many bubbles will be generated during the execution?

Answer: I1 → I3：s1, I2 → I3：s2, I3 → I4：t4, I3 → I5：t4, I3 → I6：t4, I5 → I6：s4, I6 → I7：t6, I8 → I11：s3, I9 → I11：s1. In total there’re 9 RAW dependencies, so 9 bubble stalls.

b) With data forwarding, how do you detect the data‑forwarding conditions in the pipeline?
Answer: The forwarding unit compares destination register fields in the EX/MEM and MEM/WB pipeline registers against the source register fields in the ID/EX register. For example:

  * If `(EX/MEM.RegWrite) && (EX/MEM.Rd ≠ 0) && (EX/MEM.Rd == ID/EX.Rs1)` then forward the EX/MEM result to the first ALU input (set `ForwardA = 10`).  
  * If `(EX/MEM.RegWrite) && (EX/MEM.Rd ≠ 0) && (EX/MEM.Rd == ID/EX.Rs2)` then forward the EX/MEM result to the second ALU input (`ForwardB = 10`).  
  * If `(MEM/WB.RegWrite) && (MEM/WB.Rd ≠ 0) && !(EX/MEM.RegWrite && EX/MEM.Rd == ID/EX.Rs1) && (MEM/WB.Rd == ID/EX.Rs1)` then forward the MEM/WB result to the first ALU input (`ForwardA = 01`).

Similarly, test (MEM/WB.Rd == ID/EX.Rs2) to set ForwardB = 01.

c) With data forwarding, how many bubbles remain?
Answer: One, since adjacent commands with RAW cannot be solved by bypassing (I2 → I3：s2).

d) Without data forwarding, we may still avoid bubbles by reordering the instructions. Provide one reordered code sequence that is free of data hazards.
Answer: Just Follow the DAG graph shown above, don’t arrange adjacent RAWs, and the answer will be correct. E.g.: 1, 2, 8, 9, 3, 10, 11, 5, 4, 6, 12, 7.

Register ports (4 points)

a) How many write ports and read ports must be provided for the RV32I integer register file?

Answer: The RV32I register file must support two simultaneous register reads and one register write each cycle to handle most instructions. Thus it needs two read ports and one write port.

b) For a two‑issue superscalar RV64IFD processor with FMA instructions, how many read and write ports must the floating‑point register file provide?

Answer: An FMA reads three source registers and writes one destination register. If the processor can issue two FMA instructions per cycle, the register file must supply at least 6 read ports (2 × 3) and 2 write ports (2 × 1) to support all operand fetches and writes in one cycle.

Memory Wall (8 points)

a) What is the “memory wall”?

Answer: The memory wall refers to the growing gap between processor speed and memory speed. As CPU cycles become faster and more instructions can be issued per cycle, memory latency and bandwidth do not scale proportionally, so memory accesses increasingly dominate execution time and limit performance.

b) The memory wall can be divided into the latency and the bandwidth walls. What could be done to mitigate the impact of each?

Answer: To mitigate the latency wall, architects use multi‑level cache hierarchies, hardware prefetching, and techniques like out‑of‑order execution and multithreading to hide memory latency. To mitigate the bandwidth wall, systems employ wider memory buses, multiple memory channels, high‑bandwidth memory (HBM), and data compression; software techniques such as blocking and tiling improve reuse and reduce bandwidth demand.

c) How is the memory hierarchy managed—by hardware, by software, or by a combination?
Answer: A modern memory hierarchy is managed by a combination of hardware and software. Hardware caches automatically fetch and replace data; the operating system manages page tables, virtual memory, and TLBs; and compilers and programmers can structure data and insert prefetches to improve locality. Coordinated hardware–software management yields the best performance.

Architecture/Micro‑architecture states (10 points)

In a processor we have many types of storage elements: general‑purpose registers, program counter (PC), vector registers, floating‑point registers, overflow/underflow flags, pipelined registers, BHT (branch history table), BTB (branch target buffer), L1 instruction cache, and L1 data cache.

a) Which of the above are architectural states for RV32I? (4)

Answer: Architectural state includes only elements that are defined by the ISA and visible to software. For RV32I these are the 32 general‑purpose registers (x0–x31) and the program counter (PC). RV32I has no floating‑point or vector registers and no condition flags.

b) Which are architectural states for RV64IF/V? (2)

Answer: In RV64IF/V the architectural state consists of the 64‑bit general‑purpose registers, the program counter, the floating‑point register file (F registers) and the vector register file (V registers). These are preserved across exceptions and context switches.

c) Why must instructions be retired in order? For example, even if an integer add instruction is issued later but completes sooner than a divide instruction, it must wait for the divide to finish and update the register. (3)

Answer: In‑order retirement ensures precise exceptions and a correct architectural state. Even if instructions execute out of order internally, committing them in program order guarantees that the architectural registers and memory reflect the sequential semantics of the program. If a later instruction completed earlier and wrote its result before an older instruction raised an exception, the processor would expose an inconsistent state to software. Therefore, results are written back in order.

d) Which of the above are microarchitectural states? (2)

Answer: Microarchitectural states are internal to the implementation and need not be preserved by the ISA. Examples include pipeline registers, branch history tables (BHT), branch target buffers (BTB), and cache contents (L1 instruction and data caches). These can be flushed and reconstructed from the architectural state when necessary.

e) Why, during an interrupt, are micro‑architecture states not saved? (2)

Answer: Interrupt handlers save and restore the architectural state (registers and PC) so that a program can resume correctly. Microarchitectural state is not visible to software and can be safely discarded or reinitialised; the pipeline can be flushed and predictors and caches will be repopulated automatically. Saving such state would be expensive and provides no benefit to correctness.

Data Structures and Data Hazards (5 points)

Many basic data structures (linked lists, trees, queues, stacks, hash tables with collision chains) naturally involve pointer chasing, which introduces memory dependencies that slow performance on pipelined processors due to data hazards. As a programmer, what steps can you take to reduce inefficiencies in applications that use such data structures?

Answer: To reduce the impact of pointer‑chasing data structures:

Improve spatial locality by storing nodes in contiguous arrays or using pool allocators rather than scattered heap allocations.
Reduce pointer following by flattening structures (e.g., using dynamic arrays or vectors instead of linked lists) and by grouping related fields together.
Use prefetching—software prefetch instructions can bring the next nodes into cache ahead of use.
Batch operations to amortise pointer traversal costs, and reorganise algorithms to traverse data in cache‑friendly order.
Consider cache‑aware data structures such as B‑trees and open‑addressing hash tables that reduce memory dependencies.

Control hazards (10 points)

In the pipelined data path, the branch target address (PC + immediate) is normally calculated in the EXE stage. However, this PC + immediate calculation could occur earlier at the ID stage, since both the PC value and the immediate are available there.

a) If PC + immediate is calculated at the ID stage, how can we take advantage of it? (2)

Answer: Computing the branch target in the decode stage allows the processor to begin fetching from the branch target one cycle earlier. When combined with branch prediction, the fetch unit can speculatively redirect the instruction fetch immediately after decode, reducing the number of wasted cycles if the prediction is correct.

b) Do you think this is a good design choice? Argue for or against it. (3)

Answer: Moving the PC + immediate adder to the ID stage shortens the branch resolution latency by one cycle, which reduces the branch penalty. However, it adds an adder to an already complex stage and may lengthen the critical path, increasing the clock period and offsetting the benefit. In simple in‑order cores with short pipelines, the benefit may outweigh the cost; in high‑performance out‑of‑order cores, branch prediction and speculative execution already mitigate branch penalties, so the extra hardware and timing cost may not justify the small improvement. Overall, it can be beneficial in shallow pipelines but less so in deeply pipelined, superscalar designs.

c) Modern microprocessors like Apple’s M4 can predict branch outcomes with 99% accuracy. Discuss potential directions for further improvements in branch prediction. (3)
Answer: To push accuracy beyond 99%, researchers explore larger and more sophisticated branch predictors, such as TAGE predictors with more history lengths, and hybrid predictors that combine multiple schemes. Path‑based and neural‑network predictors, including perceptron and recurrent neural networks, can learn longer‑range correlations. Compiler techniques such as profile‑guided optimisation and static branch hints can aid predictors. Finally, exploiting machine‑learning methods and hardware–software co‑design may further improve prediction accuracy.

d) The textbook’s Figure 4.59 suggests that a branch instruction would cause three pipelined bubbles, but in class we claim that a branch instruction may cause only two bubbles. Explain the one‑bubble discrepancy. (2)

Answer: The number of bubbles inserted depends on where the branch target address and condition are resolved in the pipeline. In the textbook’s example the branch target is computed in the EXE stage and the pipeline must flush the IF, ID and EX stages when a branch is taken—three bubbles. In class we assumed that PC + immediate is calculated one stage earlier, and/or that branch prediction supplies a speculative target in IF; in that design the branch outcome is known sooner, so only two bubbles are required to flush the incorrect instructions. The difference arises from placing the branch‑address calculation earlier in the pipeline.

CSC3060