Hit and Miss Examples

Example 1: Simple Direct addressing mode.

Layout:

Main Memory: 16-words

Cache Memory: 4-words

Format address main (CPU): 24 = 16  4 bit

Cache = 22 = 4  2 bit (line/slot)

Format address main = 4 bit ;

2 2
MSB (tag) (line/slot) LSB

Line/slot = Line address + word

If in cache memory, each line address just contain 1 word, then line/slot = line address only.

Main Memory

Hex Dec Address Cont (Hex)

F 15 1111 11
E 14 1110 10
D 13 1101 01
C 12 1100 A1
Cache Memory B 11 1011 F5
A 10 1010 F4
9 9 1001 F3
Dec/Hex Address Tag Content 8 8 1000 F1
(line/slot) (2 bit) (word)
3 11 xx xx 7 7 0111 FF
2 10 xx xx 6 6 0110 91
1 01 xx xx 5 5 0101 10
0 00 xx xx 4 4 0100 19
3 3 0011 13
2 2 0010 02
1 1 0001 01
0 0 0000 EE

1
Example 2: Hit/Miss Operation (Read)

Main = 32-word
Cache = 8-word

Format address main (CPU): 25 = 32  5 bit

Cache = 23 = 8  3 bit (line/slot)
Format address main = 5 bit =
2 3
MSB (tag) (line/slot) LSB

Memory Map: Main Memory

Hex Dec Address Cont (Hex)
1F 31 11111 11
1E 30 11110 10
1D 29 11101 01
1C 28 11100 A1
Cache Memory 1B 27 11011 F5
1A 26 11010 F4
19 25 11001 F3
Dec Address Tag Content 18 24 11000 F1
(line/slot) (2 bit) (word)
7 111 xx xx 17 23 10111 FF
6 110 xx xx 16 22 10110 91
5 101 xx xx 15 21 10101 10
4 100 xx xx 14 20 10100 19
3 011 xx xx 13 19 10011 13
2 010 xx xx 12 18 10010 02
1 001 xx xx 11 17 10001 01
0 000 xx xx 10 16 10000 EE
F 15 01111 DD
E 14 01110 CC
D 13 01101 BB
C 12 01100 AA
B 11 01011 FF
A 10 01010 C1
9 9 01001 C2
8 8 01000 5F
7 7 00111 13
6 6 00110 23
5 5 00101 B1
4 4 00100 B0
3 3 00011 A3
2 2 00010 A1
1 1 00001 AB
0 0 00000 01

2
Hit/Miss: (Read Process)

CPU Generate Main Memory:

Generated Address Format Address Read Operation Cache

Address Tag Line/Slot Hit Miss Update Read
Cache
(Dec) (Bin) Content
22 10110 91 10 110 √ √ √
26 11010 F4 11 010 √ √ √
22 10110 91 10 110 √ √
26 11010 F4 11 010 √ √
16 10000 EE 10 000 √ √ √
3 00011 A3 00 011 √ √ √
16 10000 EE 10 000 √ √
18 10010 02 10 010 √ √ √

Cache Content (uninitialized)

Dec Address Tag Content Dec Address Tag Content

(line/slot) (2 bit) (word) (line/slot) (2 bit) (word)
7 111 xx xx 7 111 xx xx
6 110 xx xx 6 110 10 91
5 101 xx xx 5 101 xx xx
4 100 xx xx 4 100 xx xx
3 011 xx xx 3 011 00 A3
2 010 xx xx 2 010 11 10 F4 02
1 001 xx xx 1 001 xx xx
0 000 xx xx 0 000 10 EE

BEFORE AFTER (UPDATING)

3
 Cache Memory Examples

Example 6: Block Direct Mapping Example

Given a memory system as follows:

(a). Main memory capacity = 16MByte = 16 * 1MByte = 24 * 220 = 224

Therefore the number of bits for the main memory address = 24 bits

(b). Given a cache memory of the size 16 K line = 16 * K line = 24 * 210 = 214 lines
Therefore the number of bits for the cache lines/slots/blocks = 14 bits

(c). Each line stores a block of words.

Block size = 4 words = 22 words
Therefore 2 bits for block of words

(d). Memory address format consists of tag, line/slot/block and word field.
Tag bits + lines/slots/blocks bits + words bits = 24 bits
Tag bits + 14 + 2 = 24 bits
Therefore tag bits = 24 – 16 = 8 bits

Draw the format of main memory address

Tag Line/Slot/Block Word
8 bits 14 bits 2 bits

4
(e) For data at main memory address of 111111h, the cache address is:
0001 0001 0001 0001 0001 00 01

Word address = 01
Line address = 0001 0001 0001 00 = 00 0100 0100 0100 = 0444h
Tag value = 0001 0001 = 11h

line/slot tag word 11 word 10 word 01 word 00

0444h 11h Data

(f). Line size (cache word/cache block size)

= tag bits + ( no words in cache X size )
= 8 + ( 4 x 8 bit )
= 8 + 32
= 40 bits

(g) For data at cache line address 0CE7, the main memory address is:
line/slot tag word 11 word 10 word 01 word 00
0CE7h 3Dh Data

Word address= 11
Line address = 0CE7h = 00 1100 1110 0111
Tag value = 3Dh = 0011 1101

Main memory address

tag lines/slots/block word
0011 1101 00 1100 1110 0111 11

001111010011001110011111

0011 1101 0011 0011 1001 1111

0011 1101 0011 0011 1001 1111

3 D 3 3 9 F

3D339Fh

5
Example 7: Associative Mapping Example

(a). Main memory capacity = 16 M Byte = 16 * 1 M Byte = 24 * 220 = 224

Therefore the number of bits for the main memory address = 24 bits

(b) Given a cache memory of the size 16 K line = 16 * K line = 24 * 210 = 214 locations (line number) –
not important

(c) Each line stores a block of words.

Block size = 4 words = 22 words
Therefore 2 bits for block of words

(d) Memory address format consists of tag and word field.

Tag bits + words bits = 24 bits
Tag bits + 2 = 24 bits
Therefore tag bits = 24 – 2 = 22 bits

Draw the format of main memory address

Tag Word
22 bits 2 bits

6
(e) For data at main memory address of 666666h, the cache address is:
0110 0110 0110 0110 0110 01 10

Word address = 10
Tag = 0110 0110 0110 0110 0110 01

01 1001 1001 1001 1001 1001

199999h

tag word 11 word 10 word 01 word 00

199999h data

(f). Line size (cache word/cache block size)

= tag bits + ( no words in cache X size )
= 22 + ( 4 x 8 bit )
= 22 + 32
= 54 bits

(g) For data in cache as follows, the main memory address is:
tag word 11 word 10 word 01 word 00
123456h Data

Word address = 00
Tag value = 123456h = 0001 0010 0011 0100 0101 0110

Main memory address is 0001 0010 0011 0100 0101 0110 00

00 0100 1000 1101 0001 0101 1000

00 0100 1000 1101 0001 0101 1000

4 8 D 1 5 8

48D158h

7
Example 8: 2-way Set Associative Mapping Example

(a) Main memory capacity = 16MByte = 16 * 1MByte = 24 * 220 = 224

Therefore the number of bits for the main memory address = 24 bits

(b) There are 2 modules in the cache – 2-line sets (2-way)

(c) Given a cache memory of the size 16 Kline = 16 * Kline

There are 2 modules in the cache – 2-line sets (2-way)

Therefore there is 16 K line / 2 = 8 K line = 8 * Kline = 23 * 210 = 213
Therefore the set number consist of 13 bits

(d) Each line stores a block of words.

Block size = 4 words = 22 words
Therefore 2 bits for block of words

(e) Memory address format consists of tag, set and word field.
Tag bits + set bits + words bits = 24 bits
Tag bits + 13 + 2 = 24 bits
Therefore tag bits = 24 – 15 = 9 bits

Draw the format of main memory address

Tag Set Word
9 bits 13 bits 2 bits

8
(f) For data at main memory address of BBBBBBh, the cache address is:

1011 1011 1 011 1011 1011 10 11

Word address = 11
Set Number = 011 1011 1011 10 = 0 1110 1110 1110 = 0EEEh
Tag value = 1011 1011 1 = 1 0111 0111 = 177h

Set Tag Word 11 Word 10 Word 01 Word 00

0EEEh 177h Data

(g) Line size (cache word/cache block size)

= tag bits + ( no words in cache X size )

= 9 + ( 4 x 8 bit )
= 9 + 32
= 41 bits

(h) For data in cache as follows, the main memory address is:
Set Tag word 11 word 10 word 01 word 00
1652h 0ACh Data

Word address = 01
Set no. = 1652h = 0001 0110 0101 0010
Tag value = 0ACh = 0000 1010 1100

tag set no. word

0 1010 1100 1 0110 0101 0010 10

0 1010 1100 1 0110 0101 0010 10

0 101 0110 0101 1001 0100 1010

56594Ah