Lab 10

There is no checkoff for lab this week. This is primarily review for the midterm, this will cover only a subset of the material in scope and is not a representation of what will appear on the exam.

Objectives

  • TSW gain insight on how to approach various topics that may be present for the midterm.

Exercise 1: Datapath Implementation (Structure/Control)

Recall that the critical path is the longest path(delay) from register to register, whether it be the same or different register. Setup time is the amount of time before the clock rise that the input signal must remain constant. Clk-to-Q time is the amount of time after the clock rise that the output signal takes to reflect the saved value. Hold time is the amount of time after the clock rise that the input signal must remain constant.

Some general formulas to note:

  • critical path = clk-to-q + LONGEST CL + setup
  • hold <= clk-to-q + SHORTEST CL

Make sure you know the different control signals, what they do, and how they affect our datapath!

  • PCSel - Selects between PC + 4 and ALU to update PC
  • RegWEn - Determines whether we allow the modification of registers in our register file
  • ImmSel - Selects which immediate type to generate (I, S, SB, U, UJ)
  • BrUn - Determines if we do unsigned or signed comparison
  • BrEq - On if rs1 == rs2
  • BrLt - On if rs1 < rs2 based off of BrUn
  • BSel - Selects between the rs2 and the immediate
  • ASel - Selects between rs1 and PC
  • ALUSel - Selects the ALU operation to perform on the inputs
  • MemRW - Selects if we want to be able to write to memory
  • WBSel - Selects if we want to send either PC+4, ALU, or memory output to be written into the register file

Exercise 2: Pipelining

Recall that pipelining involves adding registers in between operations to create checkpoints in our datapath.

Latency is defined as how long it takes for one instruction to finish to completion. Bandwidth is defined as how many instructions you can complete in a specified amount of time.

When we pipeline a circuit, does latency generally go up or down? What about bandwidth?

Exercise 3: Caches

Cache questions can be particularly tricky to those who don’t know how to approach them, so we’ll break down the approach!

Given the following scenario:

2 KiB Direct-mapped cache, with 128 B blocks and 4 MiB address space, what are the values for the following:

  • Size of address (bits)
  • Size of offset (bits)
  • Size of index (bits)
  • Size of tag (bits)

(Hint: # addr = # tag + # index + # offset)

Now, given the following chunk of code, answer the following (you may assume that integers are 4 bytes):

int arr[1024]; 2^10 Integers
for (int i = 0; i < 1024; i += 4) {
	arr[i] = 0; // Line 1
}
for (in i = 1023; i >= 0; i -= 8) {
	arr[i] += i; // Line 2
}
  • What is the hit rate of the first line? The second line?
  • What is the overall hit rate for the entire program?
  • Would increasing associativity increase our hit rate?

You should note the following:

  • How large is the cache in comparison to the array? In this case, the cache is 2^11 bytes and the array is 2^12 bytes, meaning we have half the array at once.
  • How many steps do we have per block? In this case for Line 1, we have a step size of 4 ints = 16 bytes. Block size is 2^7 bytes, meaning 2^7 (bytes/block) / 2^4 (bytes/step) = 2^3 steps/block.
  • How many accesses per step do we have? For Line 1, we have one write, meaning 1 access per step.
  • How many accesses per block? We have 1 access/step * 8 steps/block = 8 access/block.

For multi-access patterns such as this, where Line 2 operates after Line 1, we know that Line 2 doesn’t operate on a cold cache, so we need to see if the contents of the cache at the beginning of the loop affect Line 2. Hopefully you understand why the second half of the array is in the cache when we start Line 2, and that Line 2 starts with the second half of the array. Thus, ask yourself what the hit rate of Line 2 must be for the first half of the iterations!

Next, try to answer the rest using our tactics described to answer the original questions.

Checkpoint

  • Do you understand how to calculate Tag:Index:Offset?
  • Can you analyze hit rate from a cold(empty) cache?
  • Can you analyze hit rate from a cache that isn’t empty and correctly determine if the contents are relevant?

No Checkoff