BITS Pilani
Pilani Campus
The basic structure of a memory hierarchy
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
The Basics of Caches
Example: Library
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Important Terms
Hit time & hit rate
Miss Penality & miss rate
block (or line)
temporal locality
spatial locality
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Measuring and Improving Cache
Performance
cache miss: A request for data from the cache that cannot be
fulfilled because the data is not present in the cache
CPU time =
(CPU execution clock cycles + Memory-stall clock cycles) × Clock
cycle time
Assume the miss rate of an instruction cache is 3% and the miss rate of
the data cache is 5%. If a processor has a CPI of 3 without any memory
stalls and the miss penalty is 120 cycles for all misses,
Determine
how much faster a processor would run with a perfect cache that never
missed. Assume the frequency of all loads and stores is 40%.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Assume the miss rate of an instruction cache is 3% and the miss rate of
the data cache is 5%. If a processor has a CPI of 3 without any memory
stalls and the miss penalty is 120 cycles for all misses,
Determine
how much faster a processor would run with a perfect cache that never
missed. Assume the frequency of all loads and stores is 40%.
Total Miss penalty = Ic X(0.03X0.6X120+0.05 X 0.4 X 120) X 100=
(2.16+2.4)Ic=4.56Ic
For Perfect cache execution time= 3 X Ic = 3Ic
Total with imperfect= 3 X 0.92Ic + 4.56Ic = 2.76Ic + 4.56Ic = 7.32Ic
Speed up = 7.32/3= 2.44
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Direct Mapped cache
Cache always smaller
(Block address) modulo (Number of blocks in the cache)
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Example:
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
How many total bits are required for a directed mapped
cache with four byte blocks, if the cache contains 64 Kbytes of data and
the address length of the processor is 32 bits? Assume that byte
addressing is used.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
How many total bits are required for a directed mapped
cache with four byte blocks, if the cache contains 64 Kbytes of data and the address
length of the processor is 32 bits? Assume that byte addressing is used.
With four byte blocks, the 64 Kbyte cache contains a total of
64K/4 = 16K blocks. The cache has the following parameters
(a) Byte select size: 2 bits (since 22 = 4 bytes/block)
(b) Cache index size: 14 bits (since 214 = 16K blocks)
(c) Cache tag size: 16 bits (remaining bits from 32)
(d) Block size: 32 bits (4 bytes)
(e) Number of blocks: 16K blocks (cache size/block size)
Assuming that the cache has a valid bit, a cache tag, and
data for each block, the size of the cache is:
cache bits = number of blocks x (block size + tag size + 1)
= 214 x (32 + 16 + 1)
= 802,816 bits
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
How many bits are required if the block size is 32
bytes?
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
How many bits are required if the block size is 32 bytes?
With 32 byte blocks, the 64 Kbyte cache contains a total of
64K/32 = 2K blocks.
The cache has the following parameters
(a) Byte select size: 5 bits (since 25 = 32 bytes/block)
(b) Cache index size: 11 bits (since 211 = 2K blocks)
(c) Cache tag size: 16 bits (remaining bits from 32)
(d) Block size: 256 bits (32 bytes)
(e) Number of blocks: 2K blocks (cache size/block size)
cache bits = number of blocks x (block size + tag size + 1)
= 211 x (256 + 16 + 1)
= 559,104 bits
Note: Increasing the block size tends to decrease the
number of bits needed to implement the cache
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Miss rate versus block size
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Mapping an Address to a Multiword Cache Block
Consider a cache with 32 blocks and a block size of 8 bytes. To what
block number does byte address 600 map?
Explore?
Address of the block is
This block contains all addresses of 8 bytes
is the block address
This maps to (75 modulo 32) = 11
In fact this contains all address between 600 to 607
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Analyse Directly Mapped cache organization using different cache size and
block size : Explain what cache hit and miss rates are
Write a new program in the CPU simulator and name it as call it
Cache understanding1
MOV #0, R02
STB R02, @R02
CMP #63, R02
JEQ 28
INR R02
JMP 6
HLT
Question: Can you think of another instruction in place of INR R02?
It can be ADD #01, R02.
JEQ 28 instruction?
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Configure the cache
Block Size = 4
Cache Type = Direct Mapped
Cache Size = 16
Write Policy = Write-Back
Change Block size =2
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Change Block size =8
Insert Instruction LDB 9, R08
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
