Smith and Goodman found that for a small instruction cache, a cache using direct

Question

Smith and Goodman found that for a small instruction cache, a cache using direct mapping could consistently outperform one using fully associative with LRU replacement.

Explain why this would be possible;

If cache size = 32 Bytes, and block size = 8 bytes, try to construct an address trace to show that the above statement holds.

(2) One difference between a write-through cache and a write-back cache (both with write-allocate) can be in the time it takes to write. During the first cycle, we detect whether a hit will occur, and during the second (assuming a hit) cycle we actually write the data. Let’s assume that 50% of the blocks are dirty for a write-back cache. For the question, assume that the write buffer for write through will never stall the CPU (no penalty). Assume that a cache read hit takes 1 clock cycle, the cache miss penalty is 50 clock cycles, and a block write from the cache to main memory takes 50 clock cycles (hint: this means there is no write buffer in write-back cache). Assume that the CPI for all other instructions is 1 without misses. Finally, assume the instruction cache miss rate is 0.5% and the data cache miss rate is 1%.

Suppose that the average percentages of loads and stores are 25% and 9%, respectively. Estimate the performance of a write-through cache with a two-cycle write versus a write-back cache with a two-cycle write for each of the programs.

Do the same comparison, but this time assume the write-through cache pipelines the writes, so that a write hit takes just one clock cycle.

Explanation / Answer

1.A small direct-mapped cache can potentially outperform a fully associative cache if
the system is executing a loop that does not fit entirely in cache. To see how this
happens, consider a loop that accesses three unique addresses: A, B and C and then
repeats the sequence by looping back to A. To reference stream for such a program
would look like this: ABCABCABC…, where each letter corresponds to an address in
the reference stream. To simplify the discussion, we assume that our caches have
only two blocks of storage space with addresses A and C mapping into the first block
and address B mapping into the second lock. For a fully associative version of the 2-
block cache, our reference team always misses the cache if the replacement policy is
LRU. Such behaviour does not occur in a direct-mapped cache using LRU
replacement because each address maps into the specific location of the cache. In
the direct-mapped version, we only miss on an access to A or C but we always hit on
an access to B (ignoring initially compulsory misses).

2.A cache write is called write-through when information is passed both to the block in
the cache and to the block in the lower-level memory; when information is only
written to the block, it is called write-back. Write-back is the fastest of the two as it
occurs at the speed of the cache memory, while multiple writes within a block require
only one write to the lower-level memory.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.