Try   HackMD

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

  1. 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=24,所以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...000000110032
    0 3 M
    1
    0...000000010032
    0 1 M
    180
    0...101101000032
    11 4 M
    43
    0...010100110032
    2 11 M
    191
    0...101111110032
    11 15 M
    88
    0...010101100032
    5 8 M
    190
    0...101111100032
    11 14 M
    14
    0...000011100032
    0 14 M
    11
    0...000010110032
    0 11 M
    181
    0...101101010032
    11 5 M
    65
    0...010000010032
    4 1 M
    186
    0...101110100032
    11 10 M
    2
    0...000000100032
    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...000000110032
    0 0 M
    1
    0...000000010032
    0 0 H
    180
    0...101101000032
    5 5 M
    43
    0...001010110032
    1 2 M
    191
    0...101111110032
    5 7 M
    88
    0...010110000032
    2 6 M
    190
    0...101111100032
    5 7 H
    14
    0...000011100032
    0 3 M
    11
    0...000010110032
    0 2 M
    181
    0...101101010032
    5 5 H
    65
    0...010000010032
    2 0 M
    186
    0...101110100032
    5 6 M
    2
    0...000000100032
    0 0 M
  2. 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會是

    2m+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,所以

    26=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,

    2328個data bits(block size in words * word size in bytes * 8 bits/byte),總共是135個bits,其中data bits佔了128個
    所以ratio是
    135128=1.05

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

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

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

    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=16
    4/337=64/337 bytes/cycle
    (b)
    1+2016/2+16/2=169 cycles
    bandwidth=64/169 bytes/cycle
    ©
    1+20
    16/4+16=97 cycles
    bandwidth=64/97 bytes/cycle