Question

Caches are important to providing a high-performance memory hierarchy to processors. Below is a list of memory address references, given as word addresses (in decimal, the byte-offset bits have been excluded from addresses). 1, 4, 8, 5, 20, 17, 4, 56, 9, 10, 43, 5, 6, 9, 17 For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with two-word blocks (two words per block) and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty. Please list results in a table with 5 columns (decimal address, binary address, tag, assigned cache block index, offset, miss or hit).

Answer 1

Given,

Size of block = 2 words

Number of bits in cache offset = log ( block size ) = log 2 = 1 bit

Cache size = 8 words

Number of lines = Cache size / block size = 8 / 2 = 4

Number of bits in the index = log 4 = 2 bits

Let the address be expressed in terms of 8 bits

Then,

tag bits = Address bits - ( Offset bits + Index bits ) = 8 - ( 1 + 2 ) = 5 bits

1.

The first address in decimal is 1.

The binary address is 00000001.

Tag = 00000

Index = 00

Offset = 1

It is a miss as this address is accessed for the first time.

The cache is :

Index	Tag	Memory Address mapped
00	00000	M[1]
01
10
11

2.

The next address is 4.

The binary address is 00000100.

Tag = 00000

Index = 10

Offset = 0.

It is a miss as this address is accessed for the first time.

Index	Tag	Memory Address mapped
00	00000	M[1]
01
10	00000	M[4]
11

3.

The next address is 8.

The binary address is 00001000.

Tag = 00001

Index = 00

Offset = 0.

This is a conflict miss as the tag does not match with the tag at index 0.

Index	Tag	Memory Address mapped
00	00001	M[8]
01
10	00000	M[4]
11

4.

The next address is 5.

The binary address is 00000101.

Tag = 00000

Index = 10

Offset = 1.

This is a hit as the tag matches with the tag in index 10.

Index	Tag	Memory Address mapped
00	00001	M[8]
01
10	00000	M[5]
11

5.

The next address is 20.

The binary address is 00010100.

Tag = 00010

Index = 10

Offset = 0.

This is a miss as the tag does not match with the tag in index 10.

Index	Tag	Memory Address mapped
00	00001	M[8]
01
10	00010	M[20]
11

6.

The next address is 17.

The binary address is 00010001.

Tag = 00010

Index = 00

Offset = 1.

This is a conflict miss.

Index	Tag	Memory Address mapped
00	00010	M[17]
01
10	00010	M[20]
11

7.

The next address is 4.

The binary address is 00000100.

Tag = 00000

Index = 10

Offset = 0.

This is a miss as the tag does not match with the tag in index 10.

Index	Tag	Memory Address mapped
00	00010	M[17]
01
10	00000	M[4]
11

8.

The next address is 56.

The binary address is 00111000.

Tag = 00111

Index = 00

Offset = 0.

This is a miss as the tag does not match with the tag in index 00.

Index	Tag	Memory Address mapped
00	00111	M[56]
01
10	00000	M[4]
11

9.

The next address is 9.

The binary address is 00001001.

Tag = 00001

Index = 00

Offset = 1.

This is a miss as the tag does not match with the tag in index 00.

Index	Tag	Memory Address mapped
00	00001	M[9]
01
10	00000	M[4]
11

10.

The next address is 10.

The binary address is 00001010.

Tag = 00001

Index = 01

Offset = 0.

This is compulsory miss.

Index	Tag	Memory Address mapped
00	00001	M[9]
01	00001	M[10]
10	00000	M[4]
11

11.

The next address is 43.

The binary address is 00101011.

Tag = 00101

Index = 01

Offset = 1.

This is a miss as the tag does not match with the tag in index 01.

Index	Tag	Memory Address mapped
00	00001	M[9]
01	00101	M[43]
10	00000	M[4]
11

12.

The next address is 5.

The binary address is 00000101.

Tag = 00000

Index = 10

Offset = 1.

This is a hit as the tag matches with the tag in index 10.

Index	Tag	Memory Address mapped
00	00001	M[9]
01	00101	M[43]
10	00000	M[5]
11

13.

The next address is 6.

The binary address is 00000110.

Tag = 00000

Index = 11

Offset = 0.

This is a compulsory miss.

Index	Tag	Memory Address mapped
00	00001	M[9]
01	00101	M[43]
10	00000	M[5]
11	00000	M[6]

14.

The next address is 9.

The binary address is 00001001.

Tag = 00001

Index = 00

Offset = 1.

This is a hit as the tag matches with the tag in index 00.

Index	Tag	Memory Address mapped
00	00001	M[9]
01	00101	M[43]
10	00000	M[5]
11	00000	M[6]

15.

The next address is 17.

The binary address is 00010001.

Tag = 00010

Index = 00

Offset = 1.

This is a miss as the tag does not match with the tag in index 00.

Index	Tag	Memory Address mapped
00	00010	M[17]
01	00101	M[43]
10	00000	M[5]
11	00000	M[6]

Hence, the final table is :

Decimal address	Binary address	Tag	Index	Offset	Miss or Hit
1	00000001	00000	00	1	Miss
4	00000100	00000	10	0	Miss
8	00001000	00001	00	0	Miss
5	00000101	00000	10	1	Hit
20	00010100	00010	10	0	Miss
17	00010001	00010	00	1	Miss
4	00000100	00000	10	0	Miss
56	00111000	00111	00	0	Miss
9	00001001	00001	00	1	Miss
10	00001010	00001	01	0	Miss
43	00101011	00101	01	1	Miss
5	00000101	00000	10	1	Hit
6	00000110	00000	11	0	Miss
9	00001001	00001	00	1	Hit
17	00010001	00010	00	1	Miss