Computer Organizations exercises (cache)

網路上的解答都要錢 太小氣了 這裡提供一些題目的解法還有較為完整的思路

1. In this exercise we look at memory locality properties of matrix computation. The following code is written in C, where elements within the same row are stored contiguously. Assume each word is a 32-bit integer.
   ​​​​for (I=0; I<8; I++)
   ​​​​    for (J=0; J<8000; J++)
   ​​​​        A[I][J]= A[J][I] + C[I][0];
   

   1.1 How many 32-bit integers can be stored in a 32-byte cache block?
   Answer:
   1 byte=8 bits，所以32 bytes=32 x 8 bits
   32 x 8 / 32 = 8
   8 integers can be stored.
   1.2 References to which variables exhibit temporal locality?
   Answer:
   C[I][0]、I、J
   1.3 References to which variables exhibit spatial locality?
   Answer:
   A[I][J]

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

2. 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裡

   $16=2^4$，所以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	$\underset{32}{\underbrace{0...0000001100}}$	0	3	M
   1	$\underset{32}{\underbrace{0...0000000100}}$	0	1	M
   180	$\underset{32}{\underbrace{0...1011010000}}$	11	4	M
   43	$\underset{32}{\underbrace{0...0101001100}}$	2	11	M
   191	$\underset{32}{\underbrace{0...1011111100}}$	11	15	M
   88	$\underset{32}{\underbrace{0...0101011000}}$	5	8	M
   190	$\underset{32}{\underbrace{0...1011111000}}$	11	14	M
   14	$\underset{32}{\underbrace{0...0000111000}}$	0	14	M
   11	$\underset{32}{\underbrace{0...0000101100}}$	0	11	M
   181	$\underset{32}{\underbrace{0...1011010100}}$	11	5	M
   65	$\underset{32}{\underbrace{0...0100000100}}$	4	1	M
   186	$\underset{32}{\underbrace{0...1011101000}}$	11	10	M
   2	$\underset{32}{\underbrace{0...0000001000}}$	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	$\underset{32}{\underbrace{0...0000001100}}$	0	0	M
   1	$\underset{32}{\underbrace{0...0000000100}}$	0	0	H
   180	$\underset{32}{\underbrace{0...1011010000}}$	5	5	M
   43	$\underset{32}{\underbrace{0...0010101100}}$	1	2	M
   191	$\underset{32}{\underbrace{0...1011111100}}$	5	7	M
   88	$\underset{32}{\underbrace{0...0101100000}}$	2	6	M
   190	$\underset{32}{\underbrace{0...1011111000}}$	5	7	H
   14	$\underset{32}{\underbrace{0...0000111000}}$	0	3	M
   11	$\underset{32}{\underbrace{0...0000101100}}$	0	2	M
   181	$\underset{32}{\underbrace{0...1011010100}}$	5	5	H
   65	$\underset{32}{\underbrace{0...0100000100}}$	2	0	M
   186	$\underset{32}{\underbrace{0...1011101000}}$	5	6	M
   2	$\underset{32}{\underbrace{0...0000001000}}$	0	0	M

3. 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會是

   $2^{m+1}$
   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，所以

   $2^6=64$，總共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，

   $2^3\ast 2\ast 8$個data bits(block size in words * word size in bytes * 8 bits/byte)，總共是135個bits，其中data bits佔了128個
   所以ratio是
   $\frac{135}{128}=1.05$

4. 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:

5. 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