網路上的解答都要錢 太小氣了 這裡提供一些題目的解法還有較為完整的思路
Temporal Locality
if an item is referenced, it'll tend to be referenced again soon
Spatial Locality
if an item is referenced, items whose addresses are close by will ten to be referenced soon
As a cache plays an important role to provide high-performance memory hierarchy to processors. The sequence of 32-bit memory address references is given as following. Note that all reference addresses are word addresses.
3, 1 ,180, 43, 191, 88, 190, 14, 11, 181, 65, 186, 2
2.1 Given a direct-mapped cache containing 16 one-word-size blocks. For each of these references, identify the binary address, the tag, and the index. Also list if each reference is a hit or a miss, assuming the cache is initially empty.
Answer:
we need to know the block address of each items
since they're giving their word addresses and our cache is an one word size block, so their block address is also their word address
Tag = floor(block address/num of blocks)
Index = block address % num of blocks
由於有16個block在cache裡,所以index bits有4bits,因為one word size block,所以offset bits是2bits,所以Tag bits=32-4-2=26
Word Address | binary address | Tag | Index | H/M |
---|---|---|---|---|
3 | 0 | 3 | M | |
1 | 0 | 1 | M | |
180 | 11 | 4 | M | |
43 | 2 | 11 | M | |
191 | 11 | 15 | M | |
88 | 5 | 8 | M | |
190 | 11 | 14 | M | |
14 | 0 | 14 | M | |
11 | 0 | 11 | M | |
181 | 11 | 5 | M | |
65 | 4 | 1 | M | |
186 | 11 | 10 | M | |
2 | 0 | 2 | M |
2.2 Suppose that the direct-mapped cache setting is changed to 8 four-word-size blocks. For each of these references, ˇidentify the binary address, the tag, and the index given a direct-mapped cache. Also list if each reference is a hit or a miss, assuming the cache is initially empty
Answer:
four-word-size blocks,所以offset bits變成4bits,8個blocks,所以index bits是3bits
Word Address | binary address | Tag | Index | H/M |
---|---|---|---|---|
3 | 0 | 0 | M | |
1 | 0 | 0 | H | |
180 | 5 | 5 | M | |
43 | 1 | 2 | M | |
191 | 5 | 7 | M | |
88 | 2 | 6 | M | |
190 | 5 | 7 | H | |
14 | 0 | 3 | M | |
11 | 0 | 2 | M | |
181 | 5 | 5 | H | |
65 | 2 | 0 | M | |
186 | 5 | 6 | M | |
2 | 0 | 0 | M |
For a direct-mapped cache design with a 16-bit address, the following bits of the address are used to access the cache.
Tag | Index |Offset
15–10 | 9–4 |3–0
3.1 What is the cache block size (in words)?
Answer:
16bit address,代表一個word是2 bytes,offset bit會是
block size會決定Offset bits,總共4bits,所以m=3,block size是8 words
3.2 How many entries does the cache have?
Answer:
index bits是被cache entries的數目決定的
總共6bits,所以,總共64個entries
3.3 What is the ratio between total bits required for such a cache implementation over the data storage bits?
Answer:
在cache中每個entry,有1個valid bit,6個tag bits,個data bits(block size in words * word size in bytes * 8 bits/byte),總共是135個bits,其中data bits佔了128個
所以ratio是
By referring to Question 3, please answer the following sub-questions. All cache settings are the same with that of Question 3. The following references are recorded in byte address.
Reference (Byte Address)
0 | 4 | 16 | 32 | 132 | 208 | 68 | 720 | 500 | 180 | 30
4.1 How many blocks are replaced?
Answer:
每個block有8words,所以是16bytes,以此來計算每個reference的block address,block address=floor(byte address/block size in bytes)。
算完後可以發現0 blocks are replaced
6.2 What is the hit ratio?
1/11=0.18
8.3 List the final state of the cache, with each valid entry represented as a record of <index, tag, data>.
Answer:
Assume that a main memory device needs to take 20 cycles to get one requested word data by the given of a specific row address. Please calculate the total latency and the bandwidth of the following architectures if we need to access 16-word-size data to these architectures. Please note that the requested data are evenly distributed to each bank.
Answer:
assume
1 clock cycles to send the starting address
1 clock cycles to send a word of data
從題目可以知道20 cycles for each DRAM access
我們需要16-word-size data
(a)
total latency=1+2016+16=337 cycles
bandwidth=164/337=64/337 bytes/cycle
(b)
1+2016/2+16/2=169 cycles
bandwidth=64/169 bytes/cycle
©
1+2016/4+16=97 cycles
bandwidth=64/97 bytes/cycle