integer A[1000]; for i = 1 to 1000 for j = 1 to 1000 A[i] = A[i] + 1When the above program is compiled with all compiler optimizations turned off and run on a processor with a 1K byte direct-mapped write-back data cache with 4-word cache blocks, what is the approximate data cache miss rate? (Assume integers are one word long and a word is 4 bytes.)
address: 1 4 5 20 9 19 4 5 6 9 line #: 1 4 5 4 1 3 4 5 6 1 tag: 0 0 0 2 1 2 0 0 0 1So, figure (E) represents the final tag bits of the cache.
15 tag bits 1 valid bit 1 dirty bit (since this is a write-back cache) 128 data bits (16 bytes/cache line) === 145 bits per cache lineTotal storage required = 8192*145 bits = 1,160K bits.
Model | Associativity | Total data size (bytes) | Write- |
---|---|---|---|
DEFINATELY | four-way | 216 | back |
CERTAINLY | direct-mapped | 216 | back |
HOPEFULLY | 4-way | 210 | through |
PERHAPS | 2-way | 210 | back |
DOUBTFULLY | direct-mapped | 210 | back |
access 100: miss; cache contains 100, ---, --- access 200: miss; cache contains 200, 100, --- access 104: miss; cache contains 104, 200, 100 access 204: miss; cache contains 204, 104, 200 access 200: hit; cache contains 200, 204, 104 access 100: miss; cache contains 100, 200, 204 access 200: hit; cache contains 200, 100, 204 access 104: miss; cache contains 104, 200, 100 access 204: miss; cache contains 204, 104, 200 access 200: hit; cache contains 200, 204, 104 ...So in the steady state, location 200 stays in the cache and all other locations get replaced. So the hit rate is 2/5 or 40%.