+

Cache Memory
Key Characteristics of Computer
Memory Systems

Table 4.1 Key Characteristics of Computer Memory Systems

+
Characteristics of Memory
Systems
◼ Location
◼ Refers to whether memory is internal and external to the computer
◼ Internal memory is often equated with main memory
◼ Processor requires its own local memory, in the form of registers
◼ Cache is another form of internal memory
◼ External memory consists of peripheral storage devices that are
accessible to the processor via I/O controllers

◼ Capacity
◼ Memory is typically expressed in terms of bytes

◼ Unit of transfer
◼ For internal memory the unit of transfer is equal to the number of
electrical lines into and out of the memory module
Method of Accessing Units of Data
Sequential Direct Random
Associative
access access access

Each addressable A word is retrieved

Memory is organized into
Involves a shared read- location in memory has a based on a portion of its
units of data called
write mechanism unique, physically wired- contents rather than its
records
in addressing mechanism address

Each location has its own

The time to access a
Individual blocks or addressing mechanism
Access must be made in given location is
records have a unique and retrieval time is
a specific linear independent of the
address based on constant independent of
sequence sequence of prior
physical location location or prior access
accesses and is constant
patterns

Any location can be

Cache memories may
selected at random and
Access time is variable Access time is variable employ associative
directly addressed and
access
accessed

Main memory and some

cache systems are
random access
Capacity and Performance:

The two most important characteristics of

memory

Three performance parameters are used:

Memory cycle time

Access time (latency) Transfer rate
•Access time plus any additional
•For random-access memory it is the time required before second •The rate at which data can be
time it takes to perform a read or access can commence transferred into or out of a memory
write operation •Additional time may be required unit
•For non-random-access memory it for transients to die out on signal •For random-access memory it is
is the time it takes to position the lines or to regenerate data if they equal to 1/(cycle time)
read-write mechanism at the are read destructively
desired location •Concerned with the system bus,
not the processor
+ Memory
◼ The most common forms are:
◼ Semiconductor memory
◼ Magnetic surface memory
◼ Optical
◼ Magneto-optical

◼ Several physical characteristics of data storage are important:

◼ Volatile memory
◼ Information decays naturally or is lost when electrical power is switched off
◼ Nonvolatile memory
◼ Once recorded, information remains without deterioration until deliberately changed
◼ No electrical power is needed to retain information
◼ Magnetic-surface memories
◼ Are nonvolatile
◼ Semiconductor memory
◼ May be either volatile or nonvolatile
◼ Nonerasable memory
◼ Cannot be altered, except by destroying the storage unit
◼ Semiconductor memory of this type is known as read-only memory (ROM)

◼ For random-access memory the organization is a key design issue

◼ Organization refers to the physical arrangement of bits to form words
+
Memory Hierarchy

◼ Design constraints on a computer’s memory can be summed

up by three questions:
◼ How much, how fast, how expensive

◼ There is a trade-off among capacity, access time, and cost

◼ Faster access time, greater cost per bit
◼ Greater capacity, smaller cost per bit
◼ Greater capacity, slower access time

◼ The way out of the memory dilemma is not to rely on a single

memory component or technology, but to employ a memory
hierarchy
+

Memory Hierarchy - Diagram

Cache and Main Memory
Cache/Main Memory Structure
+

Cache Read Operation - Flowchart

+

Typical Cache Organization

Elements of Cache Design

Table 4.2 Elements of Cache Design

+
Cache Addresses
Virtual Memory

◼ Virtual memory
◼ Facility that allows programs to address memory from a logical
point of view, without regard to the amount of main memory
physically available
◼ When used, the address fields of machine instructions contain
virtual addresses
◼ For reads to and writes from main memory, a hardware memory
management unit (MMU) translates each virtual address into a
physical address in main memory
+

Logical
and
Physical
Caches
Mapping Function
◼ Because there are fewer cache lines than main memory
blocks, an algorithm is needed for mapping main memory
blocks into cache lines

◼ Three techniques can be used:

Direct Associative Set Associative

• The simplest technique • Permits each main • A compromise that
• Maps each block of main memory block to be exhibits the strengths of
memory into only one loaded into any line of the both the direct and
possible cache line cache associative approaches
while reducing their
• The cache control logic disadvantages
interprets a memory
address simply as a Tag
and a Word field
• To determine whether a
block is in the cache, the
cache control logic must
simultaneously examine
every line’s Tag for a
match
+

Direct

Mapping
+

Mapping From
Main Memory
to Cache:

k-Way
Set Associative
+
Replacement Algorithms

◼ Once the cache has been filled, when a new block is brought
into the cache, one of the existing blocks must be replaced

◼ For direct mapping there is only one possible line for any
particular block and no choice is possible

◼ For the associative and set-associative techniques a

replacement algorithm is needed

◼ To achieve high speed, an algorithm must be implemented in

hardware
+
The four most common
replacement algorithms are:
◼ Least recently used (LRU)
◼ Most effective
◼ Replace that block in the set that has been in the cache longest with
no reference to it
◼ Because of its simplicity of implementation, LRU is the most popular
replacement algorithm

◼ First-in-first-out (FIFO)
◼ Replace that block in the set that has been in the cache longest
◼ Easily implemented as a round-robin or circular buffer technique

◼ Least frequently used (LFU)

◼ Replace that block in the set that has experienced the fewest
references
◼ Could be implemented by associating a counter with each line