Question 1. Cache Mapping and Access

Consider a 1 MB cache with 16-word cachelines. Each word is 4-Bytes. This cache uses write-back scheme, and the address is 32 bits wide.

A. Direct-Mapped Cache Fields

Assume the cache is direct-mapped. Fill in the table below to specify the size of each address field of the cache.

Field                      Size (bits)

Cacheline             Offset

Cacheline             Index

Tag

B. Fully-Associative Cache Fields

Assume the cache is fully-associative. Fill in the table below to specify the size of each address field of the cache.

Field                      Size (bits)

Cacheline             Offset

Cacheline             Index

Tag

C. 16-Way Set-Associative Cache Fields

Assume the cache is 16-way set-associative. Fill in the table below to specify the size of each address field.

Field                      Size (bits)

Cacheline             Offset

Cacheline             Index

Tag

Question 2. Average Memory Access Time

Assume the following processor configuration: a dedicated L1 cache for instructions (IL1) and a L1 cache for data (DL1), a shared L2 cache that serves as an intermediate level between each of the L1 caches and the main memory. The figure below shows the hierarchy:

Figure 1: Cache Hierarchy

Figure 2: Table containing the processor cache Specifications

Out of the total instructions executed in this processor, assume load/store instructions comprise of 25% of the total instructions. Answer the following questions.

A. Calculate AMAT

What is the average memory access time?

B. Processor with no caches

Assume CPI = 1 if the processor has no memory stalls. Without the caches, each memory access would take 52 cycles. What is the CPI of the processor without any caches?

C. Processor with two levels of caches (as in Figure 1)

Assume CPI = 1 if the processor has no memory stalls. What is the CPI of processor with the all the caches? Remember that it takes 50 cycles to access memory from L2.

Question 3. Two-Cycle Instruction Cache

In this problem, we will be examining the performance of the instruction cache on the MIPS assembly program shown on the next page. The first column shows the instruction address for each instruction. Note that these addresses are byte addresses. The value of r1 is initially 64, meaning that there are 64 iterations in the loop. In this problem, we will be considering the execution of this loop with a direct-mapped instruction cache microarchitecture with eight cache lines, and each cacheline is 16B. This means each cache line can hold four instructions and the bottom four bits of an instruction address are the block offset. Hint: The first instruction in the code segment (i.e., addiu r1, r1, -1), is in the middle of a cache line with starting address 0x100.

For this problem, the instruction cache hit time is two cycles, but it is fully pipelined. Tag check occurs in the first cycle, and if it is a hit, the instruction is read in the second cycle. Essentially, this creates a six-stage pipelined processor with the following stages: instruction cache tag check (F0), instruction cache data access (F1), decode (D), execute (X), memory (M), and write-back (W). This also implies the data cache hit time is one cycle.

Assume that jumps are resolved in the decode stage and that branches are re- solved in the execute stage. Assume the miss penalty is three cycles so on a cache miss the pipeline will stay in F0 for a total of three cycles, go into F1 for one cycle, and then continue as normal. You should assume that in every other way, the processor pipeline follows the classic fully-bypassed five-stage pipeline. Assume that the processor does not include a branch delay slot. Assume the processor speculatively predicts all jumps and branches are not taken.

A. Control Hazards

Draw a pipeline diagram illustrating the first iteration of the loop assuming there are no instruction cache misses. Remember that there are two fetch stages (F0 and F1). Show stalls by simply repeating the pipeline stage character (e.g., D) for multiple consecutive cycles.

Use a dash (-) to indicate pipeline bubbles caused by killing instructions (pipeline flushes). You should show all instructions in the first iteration of the loop and the first instruction of the second iteration that you can properly draw the control dependency for the backwards branch.

B. First Iteration of the Loop

Fill in the table above. In the appropriate column, write compulsory, conflict, or capacity next to each instruction which misses in the instruction cache to indicate the type of instruction cache misses that occur in the first iteration of the loop. Assume that the instruction cache is initially completely empty. Now draw a pipeline diagram illustrating the first iteration of the loop including instruction cache misses. Clearly indicate the number of cycles it takes to execute the first iteration.

C. Second Iteration of the Loop and overall CPI

Continue to fill in the table above. Write compulsory, conflict, or capacity next to each instruction which misses in the instruction cache to indicate the type of instruction caches misses that occur in the second iteration of the loop. Now draw a pipeline diagram illustrating the second iteration of the loop. Clearly indicate the number of cycles it takes to execute the second iteration. Calculate the CPI for this processor executing all 64 iteration of the loop (Note: The CPI calculation should not include instructions that are fetched but then later squashed).