Direct Mapping from Cache to Main Memory

Direct Mapping Cache Organization

Associative Mapping from Cache to Main Memory
Fully Associative Cache Organization
Mapping From Main Memory to Cache:
k-way Associative
K-Way Set Associative Cache Organization
A write-through cache
with
write around
A write-back cache
with
write allocation
Cache Coherence Problem
• An additional control bit called “valid bit” is provided for each cache block.
• If the block contains valid data, then the bit is set to 1, else it is 0.
• Valid bits are set to 0, when the power is just turned on.
• When a block is loaded into the cache for the first time, the valid bit is set to 1.
• The DMA transfer between main memory and disk bypasses the cache.
• Whenever a main memory block is updated from disk using DMA and the data is
also resident in the cache, the valid bit is set to 0.
• Assume, DMA transfer is made from main memory to disk and the cache uses
write-back protocol. The changes made in the cached copy will not be reflected
in the main memory data.
• Thus, the copies of the data in the cache and the main memory will be different.
This is called the cache coherence problem.
• Solution: Prior to DMA transfer, forced update of main memory data from the
cached copy and flush the cache. The OS can do it without greatly affecting the
performance because such disc transfers occur seldom.
Virtual memories

• Recall that an important challenge in the design of

a computer system is to provide a large, fast
memory system at an affordable cost.
• Architectural solutions increase the effective speed
and size of the memory system.
◼ Cache bridges the speed gap between the processor and
main memory and is implemented in hardware.
◼ Virtual memory bridges the size and speed gaps
between main memory and secondary storage and is
usually implemented in part by software techniques.
Virtual memory organization
Process
or
•Memory management unit (MMU) translates
virtual addresses into physical addresses.
Virtual
address •If the desired data or instructions are in the
Dat MMU main memory they are fetched as described
a previously.
Physical •If the desired data or instructions are not in
address
the main memory, they must be transferred
Cach
e from secondary storage to the main memory.
Dat Physical •MMU causes the operating system to bring
a address
the data from the secondary storage into the
Main
memory main memory.
DMA transfer •Transfer of data between the disk and the
main memory is performed using DMA.
Disk
storage
Address translation (cont’d)
• Concepts of virtual memory are similar to the concepts of
cache memory.
• Cache memory:
• Introduced to bridge the speed gap between the processor and the main
memory.
• Implemented in hardware.
• Virtual memory:
• Introduced to bridge the size and speed gaps between the main memory
and secondary storage.
• Implemented in part by software.
Address translation (cont’d)
◼ High-order bits in each virtual or logical address
generated by a processor represents virtual page number
and low-order bits the offset that specifies the location of
a particular word within that page.
◼ Information about the main memory location of each page
is kept in the page table.
▪ Main memory address where the page is stored.
▪ Current status of the page.
◼ Area of the main memory that can hold a page is called as
page frame.
◼ Starting address of the page table is kept in a page table
base register.
 Address translation
PTBR holds Virtual address from
Page table base processor
the address of register
the page table. Page table Virtual page Offse
address number t
Virtual address is
interpreted as page
+ number and offset.
PAGE
PTBR + virtual TABLE
page number provide
the entry of the page This entry has the starting location
in the page table. of the page.

Page table holds information

about each page. This includes
the starting address of the page
in the main memory. Contro Page
l bit in
frame Page Offse
s memory frame t

Validity bit; dirty bit; permission

Physical address in main
bit memory
Address translation (cont’d)
◼ Where should the page table be located?
◼ Recall that the page table is used by the MMU for every
read and write access to the memory.
▪ Ideal location for the page table is within the MMU.
◼ Page table is quite large.
◼ MMU is implemented as part of the processor chip along
with cache.
◼ Impossible to include a complete page table on the chip.
◼ Page table is kept in the main memory.
◼ A copy of a small portion of the page table can be
accommodated within MMU.
▪ Portion consists of page table entries that correspond to the most recently
accessed pages.
Address translation (cont’d)
◼ For this purpose, a small cache called as Translation
Lookaside Buffer (TLB) is included in the MMU.
▪ TLB holds page table entries of the most recently accessed pages.
◼ Recall that cache memory holds most recently accessed
blocks from the main memory.
▪ Operation of the TLB and page table in the main memory is similar to the
operation of the cache and main memory.
◼ Page table entry for a page includes:
▪ Address of the page frame where the page resides in the main memory.
▪ Some control bits.
◼ In addition to the information that constitutes a page
table entry, TLB must hold the virtual address of the entry.
 Address translation (cont’d)
Virtual address from
processor

Virtual page number Offse

t
Associative-mapped TLB
High-order bits of the virtual address
generated by the processor contain the
TLB
virtual page number.
Virtual page Contro Page frame
number l bit in memory These bits are compared to the virtual
s
page numbers in the TLB.
If there is a match, a hit occurs and
the corresponding address of the page
N
frame is read.
=
o
? If there is no match, a miss occurs
Ye
s and the page table within the main
Mis
s memory must be consulted.
Hit Set-associative mapped TLBs are also
found in commercial processors.
Page Offse
frame t

Physical address in main

memory
Address translation (cont’d)
• How to keep the entries of the TLB coherent with the
contents of the page table in the main memory?
• Operating system may change the contents of the page
table in the main memory.
• Simultaneously it must also invalidate the corresponding entries in the TLB.
• A control bit is provided in the TLB for this purpose.
• If an entry is invalidated, the TLB gets the information for
that entry from the page table and the TLB is updated.
• Follows the same process, which it would follow in response to access
misses, if the entry is not found in the TLB.
Address translation (cont’d)
• What happens if a program generates an access request to
a page that is not in the main memory?
• In this case, a page fault is said to occur.
• Whole page must be brought into the main memory from the disk, before
access can proceed.
• Upon detecting a page fault by the MMU, following actions
occur:
• MMU asks the operating system to intervene by raising an interrupt.
• Processing of the active task that caused the page fault is interrupted.
• Control is transferred to the operating system.
• Operating system copies the requested page from secondary storage to
main memory.
• Once the page is copied, control is returned to the task that was
interrupted.
Pentium Pro multichip module with processor (left) and
256-KB cache (right)
DRAM Organization
 Asynchronous DRAMs
Row Address Strobe
• 16Mbit=16M× 1=4×4×K×K
RAS • DRAM chip configured as
4K×4K=4096×4096
Row
address Row 4096× (512× 8) • 212 = 4096; 29 = 512; 23 = 8
latch decoder cell array
• There are 4096 rows.
• Each row = 512 groups of 8.
• 12 bits to select a row, and 9
A20 - 9 ⁄ A 8 - 0 Sense / Write CS
circuits
bits to select a group in a row.
R/ W
• Total of 21 bits.
Multiplexed Column
• First apply the row address, RAS
to reduce the address Column signal latches the row address.
decoder
number of latch Then apply the column address,
pins needed CAS signal latches the address.
CAS D7 D0 • Timing of the memory unit is
controlled by a specialized unit
Column Address which generates RAS and CAS.
Strobe
• This is asynchronous DRAM
Fast Page Mode

◼ It is possible to access the other bytes in the same row without having to
reselect the row.
▪ Add a latch at the output of the sense circuits in each column.
▪ All the latches are loaded when the row is selected.
▪ Different column addresses can be applied to select and place different bytes on the data lines.
◼ Transfer the bytes in sequential order, by applying a consecutive sequence of
column addresses under the control of successive CAS signals.
▪ Allows a block of data to be transferred at a much faster rate than random accesses.
▪ Small group of bytes is usually referred as ‘block’ and larger group as ‘page’.
◼ This transfer capability is referred to as the
fast page mode feature.
Synchronous DRAMs
•Operation is directly synchronized
Refres
hcount with processor clock signal.
er •The outputs of the sense circuits are
connected to a latch.
Ro
•During a Read operation, the
R w
addre
w decod
o
Cell contents of the cells in a row are
sslatc array
Row/Colum h
er loaded onto the latches.
n addre •During a refresh operation, the
ss Colum contents of the cells are refreshed
C lum Read/Writ
naddre
count
ss
odecod
n circuits
e & without changing the contents of
er latches
er the latches.
•Data held in the latches correspond
Cloc
to the selected columns are transferred
kRA S to the output.
Mode
CA S register
an Data Data •For a burst mode of operation,
regist
input regist
output
R/ W timing
d successive columns are selected using
er er
control
CS column address counter and clock.
CAS signal need not be generated
externally. A new data is placed during
Dat
Supports several modes of rising edge of the clock
a
operation by writing control
info in mode register
 Asynchronous v Synchronous
DRAMs
Asynchronous Synchronous
•The timing of DRAM is governed ◼The DRAM moves data in and out under
asynchronously by a specialized memory control of the system clock.
controller circuit that provides RAS and CAS ◼The processor or other master issues the
signals.
instruction and address information, which
•After the delay in response, the DRAM is latched by the DRAM.
writes/reads the data. ◼The DRAM then responds after a set number
•During such access-time delay, the DRAM of clock cycles.
performs various internal functions (e.g. ◼Meanwhile, the master can safely do other
activating the high capacitance of the row tasks while the SDRAM is processing the
and column lines, sensing the data, and request.
routing the data out through the output
buffers).
•The processor waits through access-time
delay, reducing system performance.
Latency, Bandwidth, and Double
Data Rate (DDR) SDRAMs
• Memory latency is the time it takes to transfer a word of
data to or from memory
• Memory bandwidth is the number of bits or bytes that can
be transferred in one second.
• DDR SDRAMs
• Standard SDRAMs performs all actions, including data transfer, on
the rising clock edge
• DDR SDRAMS transfer data on both edges thus bandwidth is
essentially doubled
• To make it possible to access the data at double rate, cell array is
organized in two banks; each bank can be accessed separately
• Consecutive words of a block are stored in different banks
• Accessing both banks simultaneously, allows transfer of two words
on successive (rising & trailing) clock edges 33
Larger Memory Organization
21-bi
address
t 19-bit internal chip address Q. Implement a 2Mx32 memory unit,
A0 es
A1 i.e. 2M words of 32 bits each.
Use 512Kx8 static memory chips.
A1 A. 16x512Kx8=4x512Kx8x4=
A29
0 2x1024Kx32=2xKxKx32=2Mx32
Each column consists of 4 chips.
Each chip implements one byte
position.
A chip is selected by setting its
2-bi
decod
t chip select control line to 1 (high).
er
Selected chip places its data on the
data output line, outputs of other
chips are in high impedance state.
51 K × 8
memory
2 21 bits to address a 32-bit word.
D31-2 D23-1 D 15- D7-
chip
4 6 8 0 High order 2 bits are needed to
512×K×8=29×210×8=219×8=51 K × 8 memory
2 chip select the row, by activating the
Q. Design 8M×32 memory
unit using same chip.
four Chip Select signals.
19-bi 8-bit
Ans. 16 rows; addre
t input/outp
data 19 bits are used to access specific
A19-22 are connected to 4-bitss ut
byte locations inside the selected
decoder;
A0-18 connected to all chips chip. 34
Chip
select
 SIMM, DIMM, RIMM
• SIMM: the connectors are only present on the single side of the module
and are shorted together. The maximum data storage offered by SIMM is
32-bit/cycle.
• DIMM: has the row of connectors on both the sides (front and back) of the
module and connectors are independent. This resulted in twice the
capacity of DIMM with the same quantity of RAM and hence supporting the
64-bit processors (two readers see an album simultaneously from each
end).
• RIMM: has the row of connectors on both the sides (front and back) of the
module and connectors are independent. This resulted in twice the
capacity of DIMM with the same quantity of RAM and hence supporting the
64-bit processors (two readers see an album simultaneously from each
end).

35
SIMM, DIMM, RIMM

36
Memory controller
◼ Recall that in a dynamic memory chip, to reduce the number of
pins, multiplexed addresses are used.
◼ Address is divided into two parts:
▪ High-order address bits select a row in the array.
▪ They are provided first, and latched using RAS signal.
▪ Low-order address bits select a column in the selected row.
▪ They are provided later, and latched using CAS signal.
◼ However, a processor issues all address bits at the same time.
◼ In order to achieve the multiplexing, memory
controller circuit is inserted between the processor
and memory.
▪ Controller accepts complete address, R/W signal, and Request
for memory access from CPU and then forwards row and
column portions of the address to the memory and generates
RAS/CAS, R/W, and CS signals; however, data lines are
connected directly.

37
Memory controller (contd..)

Row/Colum
Addres n addre
s ss
RAS
R/ W
CAS
Memor
Reque controlle
y R/ W
Process st r Memor
or CS
Cloc y
k Cloc
k

Dat
a

38
◼ Q. A 1024×1024 array of 32-bit numbers is to be normalized as follows. For each column,
the largest element is found and all elements of the column are divided by this maximum
value. Assume that each page in the virtual memory consists of 4K bytes, and that 1M bytes
of the main memory are allocated for storing data during this computation. Suppose that it
takes 40 ms to load a page from the disk into the main memory when a page fault occurs.
◼ a. How many page faults would occur if the elements of the array are stored in column order
in the virtual memory?
◼ b. How many page faults would occur if the elements are stored in row order?
◼ c. Estimate the total time needed to perform this normalization for both arrangements.

◼ Ans. Each column (or row) consists of 1024, 32-bit numbers = 1024×32 bits = 1024×4×8
bits = 4×1024×8 bits = 4×1024×8 bits = 4K bytes = one page. Thus, 1M bytes = 1024×1024
= 256×4×1024 = 256×4K portion of the main memory consists of space for 256 pages that is
allocated for storing data during the computation. Also, each page holds 1024 numbers.
◼ a. Each column is one page; there will be 1024 page faults.
◼ b. Processing of entire columns, one at a time, would be very inefficient and slow. However,
if only one quarter of each column (for all columns) is processed before the next quarter is
brought in from the disk, then each element of the array must be loaded into the memory
twice. In this case, the number of page faults would be 2048.
◼ c. Assuming that the computation time needed to normalize the numbers is negligible
compared to the time needed to bring a page from the disk: total time for (a) is 1024×40 ms
= 41 s and total time for (b) is 2048×40 ms = 82 s
◼ Q. A computer has a cache, main memory, and a disk used for virtual memory. If a
referenced word is in the cache, 20 ns are required to access it. If it is in main
memory but not in the cache, 60 ns are needed to load it into the cache, and then the
reference is started again. If the word is not in main memory, 12 ms are required to
fetch the word from disk, followed by 60 ns to copy it to the cache, and then the
reference is started again. The cache hit ratio is 0.9 and the main-memory hit ratio
is 0.6. What is the average time in ns required to access a referenced word on this
system?

◼ Ans. There are three cases to consider:

Location of referenced Total probability of hit Total time for access in
word ns
In cache 0.9 20
Not in cache, but in (1-0.9)(0.6) = (0.1)(0.6) 60 + 20 = 80
main memory = 0.06
Not in cache or main (1-0.9)(1-0.6) =(0.1)(0.4) 12ms + 60 + 20 =
Memory = 0.04 12000080
◼ So the average access time would be:
◼ Avg = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns
Memory management
• Operating system is concerned with transferring programs
and data between secondary storage and main memory.
• Operating system needs memory routines in addition to the
other routines.
• Operating system routines are assembled into a virtual address
space called system space.
• It is separate from the space in which user application programs
reside, called user space.
• There may be a number of user spaces, one for each user.
• This is arranged by providing a separate page table for each
user program.
• In fact, virtual address space is divided into one system
space and several user spaces.
Memory management (cont’d)
• Recall that the memory management unit (MMU) translates
logical or virtual addresses into physical addresses.
• MMU uses the contents of PTBR to determine the address
of the page table to be used in the translation.
• By changing the contents of PTBR, operating system can switch
from one space to another.
• Though, physical main memory is shared by active pages of
system space and several user spaces, at any given time,
PTBR can point to one page table.
• Thus, only one page table can be used in the translation process at
a given time.
• Pages belonging to only one space are accessible at any given time.
Memory management (cont’d)
◼ When multiple, independent user programs coexist in the
main memory, how to ensure that one program does not
modify/destroy the contents of the other?
◼ Processor usually has two states of operation:
▪ Supervisor state
▪ User state
◼ Supervisor state:
▪ Operating system routines are executed.
◼ User state:
▪ User programs are executed.
▪ Some privileged machine instructions, e.g. modifying PTBR, can’t
be executed in user state.
▪ Prevents one user from accessing the page tables of other user
spaces or of the system space.
Other Performance Enhancements
Introducing Write Buffer
◼ Write-through:
• Each write operation involves writing a block into main memory.
• If the processor has to wait for write block operation to be complete,
it slows down the processor.
• The forced wait can be avoided by introducing write buffer to store
‘write block’ temporarily.
• The processor can place ‘write block’ into buffer and continue
execution. When no read request is on, ‘write block’ is moved from
buffer to main memory.
• If a subsequent read request references ‘write block’ that is still in
the buffer, it is referenced from the buffer itself.
◼ Write-back:
• A dirty block is written back to main memory.
• If a ‘new block’ is to be brought in cache at dirty block’s location due
to a read miss, the processor suffers forced wait till dirty block’s write
operation is over.
• The dirty block can be ejected from cache to place into write buffer,
and the ‘new block’ can be brought in cache.
• Afterwards, the dirty block is moved from buffer to main memory.
Other Performance Enhancements (Cont’d)
Prefetching
• New data are brought into the processor when they are
first needed.
• Processor has to wait before the data transfer is
complete.
• Prefetch the data into the cache before they are actually
needed or before a read miss occurs.
• Prefetching can be accomplished through software by
including a special instruction in the machine language
of the processor.
▪ Inclusion of prefetch instructions increases the length of the
programs.
• Prefetching can also be accomplished using hardware:
▪ Adding circuitry that attempts to discover patterns in memory
references and then prefetches according to this pattern.
Interleaving
• Divides main memory into number of modules.
◼ Each module has its own address buffer register (ABR) and data buffer register (DBR).
◼ Access more than one module at the same time.
◼ Aggregate data transfer rate to and from main memory increased.

• Arranges addressing so that consecutive addresses are

located in successive modules.
• Any request for access to consecutive memory locations
can keep several modules busy at the same time.
• As parallel access to these modules is possible, the
average rate of fetching words from the main memory
can be increased.
Methods of address layouts (1/2)
k bits m bits

Module Address in module MM address

ABR DBR ABR DBR ABR DBR

Module Module Module

0 i n- 1

◼ Consecutive words are placed in a module.

◼ High-order k bits of a memory address determine the
module.
◼ Low-order m bits of a memory address determine the
word within a module.
◼ When a block of words is transferred from main
memory to cache, only one module is busy at a time.
◼ However, at the same time the devices with DMA
ability may access other modules.
 Methods of address layouts (2/2)
m k
bits bits
Address in module Module MM
address

ABR DBR ABR DBR ABR DBR

Module Module Module

k
0 i 2 - 1

•Memory interleaving: more effective

•Consecutive addresses are located in successive modules.
•Low-order k bits of a memory address select a module.
•High-order m bits of a memory address name a location within
that module.
•While transferring a block of data, several memory modules
can be involved at the same time.
•Access to consecutive memory locations can keep several
modules busy at any one time in order to access in parallel.
 Interleaved Memory: Example
◼ Cache with 8-word blocks
and read miss occurs. m k
◼ Copy block that contains bit
Address in module
s
bit
Modul
s
MM
desired word from memory e address
to cache.
◼ To send address to main
memory = 1 clock cycle
◼ Say, a relatively slow DRAM AB DB AB DB AB DB
allows access to first word = 8 R R
Modul
R R
Modul
R R
Modul
clock cycles e 0 e i
k
e2 - 1
◼ Access subsequent words of
the block = 7×4 clock cycles, • 4-way interleaved memory
if we assume subsequent • First step is same.
words of the block need 4 • After 8 clock cycles, each module has
clock cycles per word; it is one word in DRB.
less as row address is • Transfer these words to cache, one word
at a time, during next 4 clock cycles.
decoded only once.
◼ Send one block to cache = 1 • During this time access next word in
each module.
clock cycle. • Another 4 clock cycles to transfer these
◼ Total time needed to load the words to cache.
desired block in cache = • Total time needed to load the desired
1+8+(7×4)+1 = 38 cycles block from interleaved memory =
1+8+4+4 = 17 cycles