I have no idea how to do this, if someone can explain it or just do the problem
ID: 3731393 • Letter: I
Question
I have no idea how to do this, if someone can explain it or just do the problem with their setups so I can understand what I am supposed to be doing I would appreciate it.
Simulate a set of address-requests for various cache configurations.
For each configuration you are required to:
Draw the cache
Report the total number of hits/misses
For each cache line you must:
Show the intermediate addresses: which is a historical record of which address requests previously occupied the cache-line
Show the final tag
Show the final data values (for data: use the addresses of the bytes that reside in each entry)
Assume each cache is initially empty and that the replacement scheme is least recently used.
The cache configurations are:
A fully associative cache with sixteen 8-byte blocks.
A direct-mapped cache with four 16-byte blocks.
An 8-way set-associative cache with a total of sixteen 4-byte blocks (eight blocks per set).
The address requests to simulate for each configuration are (assume 8-bit addresses): 0, 4, 8, 18, 20, 64, 32, 0, 23, 96, 32, 36, 16, 24, 40, 68.
For example, assume a fully-associative cache with a 4-byte block size, and a request for the byte at address 33. The address 33 translates to 0x21, or 00100001. Since the block-size is 4-bytes, the bottom two-bits of the address correspond to the byte offset within the block (01), and the remaining bits comprise the tag(001000) The cache entry would be formatted as follows:
Valid
Intermediate
Final Tag
Data (Byte Offsets below)
00
01
10
11
1
4/8/33
001000
32
33
34
35
For the caching scenario above, note that Byte 33 is at byte offset 01 in the 4-byte cache block. A request for 33 implies that the other 3 bytes in 33’s block are also in the cache, thus bytes 32(offset:00), 34(offset:10), and 35(offset:11) appear in the same entry as 33. In this case, data would be 32, 33, 34, 35.
Valid
Intermediate
Final Tag
Data (Byte Offsets below)
00
01
10
11
1
4/8/33
001000
32
33
34
35
Explanation / Answer
in a fully associative cache, the element will go anywhere free entry available. there no any restriction.
16 blocks and 8-byte blocks(3-bit representation in offset representation).
first 0 binary representation: 0x000000( at starting cache is empty so miss)
Next 4: 4 is present in the cache so a cache hit.
next 8: not present in the cache so miss
next 18: 18 entry not present in the cache so cache miss
next 20 it is present in the cache so a cache hit.
next 64 binary representation (0x001000000)
next 32 : no entry in the cache so a cahce miss
32 binary representation (0x000100000)
next 0 block is present in the cache so a cache hit.
next 23 block is present so a cache hit.
next 96 not present so a cache miss
96 binary form(0x001100000)
next 32 present in the cache so a cache hit.
next 36 present in the cache so a cache hit.
16 -> cache hit
24 -> cache miss (0x000011000)
31
40 ->cache miss
31
68 a cache hit
misses(0,8,18,64,32,96,24,40) remaining are hits. we have 16 blocks present in the cache we used only 8 entries.
A direct-mapped cache with four 16-byte blocks.
16-byte blocks mean (for offset representation 4 bits are required)
only 4 entries so for line number 2 bits are required.(so entries 00, 01, 10, 11)( for line numbers see blod bits in below Final tag)
first 0 ---> (ox000000000)2
15
next 4 , 8 present so hits
next 18 0x0000010010 ( so here first 4 0010 offset bits , next 2 line number bits)
15
31
next 20 hit
64 (0x0001000000) (line bits 00 tags bits 0000)
79
31
next 32 miss (0x0000100000)(line bits 10 )
79
31
next 0 miss:(0x0000000000)2
15
31
next 23 hit
next 96 (0x0001100000)
15
31
next 32 again miss (0x0000100000)
15
31
next 36,16,24,40 hits
68 miss(0x00010000010)
80
31
misses(0,18,64,32,0,96,32,68) remaining are hits.
2-way set-associative cache with a total of sixteen 4-byte blocks
sixteen blocks means 8 sets each set contains 2 blocks 8 sets means (3 bits for line number)(000,001,010,011,100,101,110,111)
4 byte blocks mean( 2 bits for offset)
0 miss (0x000000000)
next 4 (ox00000100)
8 (0x00001000)
next 18 (0x00010010)
next 20( 0x00010100)
next 64 (0x01000000)
next 32(0x00100000) here we are using least recently used algorithm so we replacing the block which has 0 intermediate.
0 (0x000000) least recently used so replace with 64
next 23 hit. next 96 miss
like this we apply we can get the final table as
14 misses which are present in intermediate staze.
8-way set-associative cache with a total of sixteen 4-byte blocks
total no of blocks is equal to 16 and 8 way set associative so each set contains 8 blocks so no of sets is equal to 2 (2 bits required for sets representation 0,1)
4 byte blocks so 2 bit required(00,01,10,11)
0 miss( 0x000000)
next 4 (0x00000100)
next 8 (0x0001000)
next 18 (0x00010010)
20 miss(0x0010100)
like this entries will be filed so final cache will be
total no of misses are 11 which are present in the intermediate step.
valid intermediate Final Tag 000 001 010 011 100 101 110 111 1 0 000000 0 1 2 3 4 5 6 7