Associative cache

COMPUTER ORGANISATION & ARCHITECTURE

Two-way set associative cache

Number of lines in set, k = 2

Main memory = 64M byte = 226

Address length = 26bits

Number of lines in cache = 8k/16 = 500 lines

Number of sets = 500lines / k = 500/2

= 250 = 28

Line size = 16 bytes = 24 = 2w, w = 4 bits

Tag = 26-8-4 = 14

Main memory address: tag=14 set=8 word=4

4.3a) Main memory address:

Tag=8

Line=14

Word=2

$111111: tag=$11 line=$0444 word=$1

$666666: tag=$66 line=$1999 word=$2

$BBBBBB: tag=$BB line=$2EEE word=$3

b) Main memory address:

Tag=22

Word=2

$111111: tag=$044444 word=$1

$666666: tag=$199999 word=$2

$BBBBBB: tag=$2EEEEE word=$3

c) Main memory address:

Tag=9

Set=13

Word=2

$111111: tag=$022 set=$0444 word=$1

$666666: tag=$0CC set=$1999 word=$2

$BBBBBB: tag=$177 set=$0EEE word=$

4.4a) Address length = 24 bits (16M bytes = 224)

Number of addressable units = 224 = 16Mbytes

Block size = 4 bytes

Number of blocks in main memory = 222 = 4M blocks

Number of lines in cache, r = 14 (2r=16k)

Size of tag = 8 bits

b) Address length = 24 bits

Number of addressable units = 224

Block size = 4 bytes

Number of blocks in main memory = 222

Number of lines in cache = undetermined

Size of tag = 22 bits

c) Address length = 24 bits

Number of addressable units = 224

Block size = 4 bytes

Number of blocks in main memory = 222=4M blocks

Number of lines in set = 2 lines

Number of sets, d = 13 (213=2d)

Number of lines in cache = 214=16k lines

Size of tag = 9 bits

Block frame size=16 bytes=4 doublewords

Number of block frames in cache=16k bytes/16 bytes=1024

Number of sets=number of block frames/associativity=1024/4=256sets

4.8

a) Memory address length = 16 bits (216 bytes)

Word length = 3 bits (block size = 8 = 23)

Line length = 5 bits (cache size of 32 lines = 25)

Tag length = 16-3-5 = 8 bits

b) i) cache line=$03 ii) cache line=$06 iii) cache line=$03 iv) cache line=$15

c) other main memory address with the same cache line and tat that will stored along with address 0001 1010 0001 1010 are:

tag

line

Word

0001 1010

00011

000

0001 1010

00011

001

0001 1010

00011

011

0001 1010

00011

100

0001 1010

00011

101

0001 1010

00011

110

0001 1010

00011

111

d) 256 bytes

e) The use of tag is to check if the correct block is in the cache (by comparing the tag in the cache word and the tag in main memory) after the specific line is determined.

4.11

a) Address format:

Tag = 20 bits

Line = 6 bits

Word = 6 bits

Number of addressable units = 2s+w

=232 bytes

Number of blocks in main memory = 2s

= 226

Number of lines in cache = 2r

= 26

= 64

Size of tag = 20 bits

b) Address format:

Tag = 26 bits

Word = 6 bits

Number of addressable units = 2s+w

=232 bytes

Number of blocks in main memory = 2s

= 226

Number of lines in cache = undetermined

Size of tag = 26 bits

c) Address format:

Tag = 9 bits

Set = 17 bits

Word = 6 bits

Number of addressable units = 2s+w

=232 bytes

Number of blocks in main memory = 2s

= 226

Number of lines in set = k = 4

Number of sets in cache = 2d=217

Number of lines in cache = k*2d

= 219

Size of tag = 9 bits

4.12

a) The block is 16bytes, the word size is 1 byte, so there are 16 words per block. We need 4 bits to indicate which word we want out of a block. Each cache line/slot matches a memory block. That means each cache slot contains 16bytes. If the cache is 64kbytes then 64kbytes/16 = 4096 cache slots. To address these 4096 cache slots, we need 12 bits (212=4096).

Direct mapping,

Main memory address:

Tag=4

Line=12

Word=4

i) F0010

Tag= F line=001 word offset=0

ii) 01234

Tag=0 cache line address=123 word offsets=4

iii) CABBE

TAG=C cache line address=ABB word offsets=E

b) We need to pick any address where the slot is the same, but the tag (and optically, the word offset) is different. Examples where the slot is 1111 1111 1111.

Address 1:

Word offset=1111

Slot=1111 1111 1111

Tag=0000

Address=0FFFF

Address2:

Word offset=0001

Tag=0011

Slot=1111 1111 1111

Address=3FFF1

c) With a fully associative cache, the cache is split up into a tag and word offset field. We no longer need to identify which slot is a memory block might map to, because a block can be in any slot and we will search each cache slot in parallel. The word offset must be 4 bits to address each individual word in the 16-word block. This leaves 16bits left over for the tag.

i) F0010

Tag=F001 word offset=0

ii) CABBE

Tag=CABB word offset=E

d) As computed in part a), we have 4096 cache slots, if we implement a two-way set associative cache, it means that we put two cache slots into one set. Our cache now holds 4096/2=2048sets where each set has 2 slots. To address these 2048 sets, we need 11bits (211=2048). Once we address a set, we will simultaneously search both cache slots to see if one has a tag that matches the target.

Main memory address:

Tag=5

Set=11

Word=4

i) F0010=1111 0000 0000 0001 0000

Tag=1E

Cache set=001

Word offset=0

ii) CABBE=1100 1010 1011 1011 1110

Tag=19

Cache set=2BB

Word offset=E

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!