12.

1 The Memory Hierarchy and Cache Memory

12.1.1 Caches and Memory Management Units
12.2 Cache Architecture
12.2.1 Basic Architecture of a Cache Memory
12.2.2 Basic Operation of a Cache Controller
12.2.3 The Relationship between Cache and Main Memory
12.2.4 Set Associativity
12.2.5 Write Buffers
12.2.6 Measuring Cache Efficiency
12.3 Cache Policy
12.3.1 Write Policy—Writeback or Writethrough
12.3.2 Cache Line Replacement Policies
12.3.3 Allocation Policy on a Cache Miss
12.4 Coprocessor 15 and Caches
12.5 Flushing and Cleaning Cache Memory
12.5.1 Flushing ARM Cached Cores
12.5.2 Cleaning ARM Cached Cores
12.5.3 Cleaning the D-Cache
12.5.4 Cleaning the D-Cache Using Way and Set Index Addressing
12.5.5 Cleaning the D-Cache Using the Test-Clean Command
12.5.6 Cleaning the D-Cache in Intel XScale SA-110 and Intel StrongARM Cores
12.5.7 Cleaning and Flushing Portions of a Cache
12.6 Cache Lockdown
12.6.1 Locking Code and Data in Cache
12.6.2 Locking a Cache by Incrementing the Way Index
12.6.3 Locking a Cache Using Lock Bits
12.6.4 Locking Cache Lines in the Intel XScale SA-110
12.7 Caches and Software Performance
12.8 Summary
 Chapter
Caches 12
A cache is a small, fast array of memory placed between the processor core and main
memory that stores portions of recently referenced main memory. The processor uses
cache memory instead of main memory whenever possible to increase system performance.
The goal of a cache is to reduce the memory access bottleneck imposed on the processor
core by slow memory.
Often used with a cache is a write buffer—a very small first-in-first-out (FIFO) memory
placed between the processor core and main memory. The purpose of a write buffer is to
free the processor core and cache memory from the slow write time associated with writing
to main memory.
The word cache is a French word meaning “a concealed place for storage.” When applied
to ARM embedded systems, this definition is very accurate. The cache memory and write
buffer hardware when added to a processor core are designed to be transparent to software
code execution, and thus previously written software does not need to be rewritten for use
on a cached core. Both the cache and write buffer have additional control hardware that
automatically handles the movement of code and data between the processor and main
memory. However, knowing the details of a processor’s cache design can help you create
programs that run faster on a specific ARM core.
Since the majority of this chapter is about the wonderful things a cache can do to make
programs run faster, the question arises, “Are there any drawbacks created by having a cache
in your system?” The answer is yes. The main drawback is the difficulty of determining the
execution time of a program. Why this is a problem will become evident shortly.
Since cache memory only represents a very small portion of main memory, the cache fills
quickly during program execution. Once full, the cache controller frequently evicts existing
code or data from cache memory to make more room for the new code or data. This eviction
process tends to occur randomly, leaving some data in cache and removing others. Thus,
at any given instant in time, a value may or may not be stored in cache memory.

403
404 Chapter 12 Caches

Because data may or may not be present in cache at any given point in time, the execution
time of a routine may vary slightly from run to run due to the difference between the time
it takes to use data immediately out of cache memory and the time it takes to load a cache
line from main memory.
So, with that caveat, we begin by showing where caches fit in a standard memory hier-
archy and introduce the principle of locality of reference to explain why a cache improves
system performance. We then describe cache architectures in general and define a set of
terms used by the ARM community. We end the chapter with example code showing how
to clean and flush caches and to lock code and data segments in cache.

12.1 The Memory Hierarchy and Cache Memory

In Chapter 1 we introduced the memory hierarchy in a computer system. Figure 12.1
reviews some of this information to show where a cache and write buffer fit in the
hierarchy.

Processor
Register file
core
Chip
Tightly coupled
memory Level 1 cache Write buffer

SRAM
Main
memory
Board DRAM

Flash and other board-level nonvolatile memory

Read path
Device
Secondary
Disk, tape, and network storage
storage Write path

Figure 12.1 Memory hierarchy.

 12.1 The Memory Hierarchy and Cache Memory 405

The innermost level of the hierarchy is at the processor core. This memory is so tightly
coupled to the processor that in many ways it is difficult to think of it as separate from
the processor. This memory is known as a register file. These registers are integral to the
processor core and provide the fastest possible memory access in the system.
At the primary level, memory components are connected to the processor core through
dedicated on-chip interfaces. It is at this level we find tightly coupled memory (TCM) and
level 1 cache. We talk more about caches in a moment.
Also at the primary level is main memory. It includes volatile components like SRAM
and DRAM, and nonvolatile components like flash memory. The purpose of main memory
is to hold programs while they are running on a system.
The next level is secondary storage—large, slow, relatively inexpensive mass storage
devices such as disk drives or removable memory. Also included in this level is data derived
from peripheral devices, which are characterized by their extremely long access times.
Secondary memory is used to store unused portions of very large programs that do not fit
in main memory and programs that are not currently executing.
It is useful to note that a memory hierarchy depends as much on architectural design as
on the technology surrounding it. For example, TCM and SRAM are of the same technology
yet differ in architectural placement: TCM is located on the chip, while SRAM is located on
a board.
A cache may be incorporated between any level in the hierarchy where there is a
significant access time difference between memory components. A cache can improve
system performance whenever such a difference exists. A cache memory system takes
information stored in a lower level of the hierarchy and temporarily moves it to a higher
level.
Figure 12.1 includes a level 1 (L1) cache and write buffer. The L1 cache is an array of
high-speed, on-chip memory that temporarily holds code and data from a slower level.
A cache holds this information to decrease the time required to access both instructions
and data. The write buffer is a very small FIFO buffer that supports writes to main memory
from the cache.
Not shown in the figure is a level 2 (L2) cache. An L2 cache is located between the
L1 cache and slower memory. The L1 and L2 caches are also known as the primary and
secondary caches.
Figure 12.2 shows the relationship that a cache has with main memory system and the
processor core. The upper half of the figure shows a block diagram of a system without a
cache. Main memory is accessed directly by the processor core using the datatypes supported
by the processor core. The lower half of the diagram shows a system with a cache. The cache
memory is much faster than main memory and thus responds quickly to data requests by
the core. The cache’s relationship with main memory involves the transfer of small blocks
of data between the slower main memory to the faster cache memory. These blocks of data
are known as cache lines. The write buffer acts as a temporary buffer that frees available
space in the cache memory. The cache transfers a cache line to the write buffer at high speed
and then the write buffer drains it to main memory at slow speed.
406 Chapter 12 Caches

Word, byte access

Processor Main
core Slow memory
Noncached system

Word, byte Block

access transfer
Processor Cache Main
core Fast Slow memory
Fast Write Slow
buffer

Word, byte access

Slow

Cached system

Figure 12.2 Relationship that a cache has between the processor core and main memory.

12.1.1 Caches and Memory Management Units

If a cached core supports virtual memory, it can be located between the core and the memory
management unit (MMU), or between the MMU and physical memory. Placement of the
cache before or after the MMU determines the addressing realm the cache operates in
and how a programmer views the cache memory system. Figure 12.3 shows the difference
between the two caches.
A logical cache stores data in a virtual address space. A logical cache is located between
the processor and the MMU. The processor can access data from a logical cache directly
without going through the MMU. A logical cache is also known as a virtual cache.
A physical cache stores memory using physical addresses. A physical cache is located
between the MMU and main memory. For the processor to access memory, the MMU
must first translate the virtual address to a physical address before the cache memory can
provide data to the core.
ARM cached cores with an MMU use logical caches for processor families ARM7
through ARM10, including the Intel StrongARM and Intel XScale processors. The ARM11
processor family uses a physical cache. See Chapter 14 for additional information on the
operation of the MMU.
The improvement a cache provides is possible because computer programs execute
in nonrandom ways. Predictable program execution is the key to the success of cached
systems. If a program’s accesses to memory were random, a cache would provide little
 12.1 The Memory Hierarchy and Cache Memory 407

Virtual Physical
memory memory

Offset Address bus

Translation
base
MMU

Cache

Data bus

Processor Main
Logical cache memory

Virtual Physical
memory memory

Offset Address bus

Translation
base
MMU
Cache

Data bus

Processor Main
Physical cache memory

Figure 12.3 Logical and physical caches.

improvement to overall system performance. The principle of locality of reference explains

the performance improvement provided by the addition of a cache memory to a system.
This principle states that computer software programs frequently run small loops of code
that repeatedly operate on local sections of data memory.
The repeated use of the same code or data in memory, or those very near, is the reason
a cache improves performance. By loading the referenced code or data into faster memory
when first accessed, each subsequent access will be much faster. It is the repeated access to
the faster memory that improves performance.
408 Chapter 12 Caches

The cache makes use of this repeated local reference in both time and space. If the
reference is in time, it is called temporal locality. If it is by address proximity, then it is called
spatial locality.

12.2 Cache Architecture

ARM uses two bus architectures in its cached cores, the Von Neumann and the Harvard.
The Von Neumann and Harvard bus architectures differ in the separation of the instruction
and data paths between the core and memory. A different cache design is used to support
the two architectures.
In processor cores using the Von Neumann architecture, there is a single cache used
for instruction and data. This type of cache is known as a unified cache. A unified cache
memory contains both instruction and data values.
The Harvard architecture has separate instruction and data buses to improve overall
system performance, but supporting the two buses requires two caches. In processor cores
using the Harvard architecture, there are two caches: an instruction cache (I-cache) and
a data cache (D-cache). This type of cache is known as a split cache. In a split cache,
instructions are stored in the instruction cache and data values are stored in the data cache.
We introduce the basic architecture of caches by showing a unified cache in Figure 12.4.
The two main elements of a cache are the cache controller and the cache memory. The
cache memory is a dedicated memory array accessed in units called cache lines. The cache
controller uses different portions of the address issued by the processor during a memory
request to select parts of cache memory. We will present the architecture of the cache
memory first and then proceed to the details of the cache controller.

12.2.1 Basic Architecture of a Cache Memory

A simple cache memory is shown on the right side of Figure 12.4. It has three main parts:
a directory store, a data section, and status information. All three parts of the cache memory
are present for each cache line.
The cache must know where the information stored in a cache line originates from in
main memory. It uses a directory store to hold the address identifying where the cache line
was copied from main memory. The directory entry is known as a cache-tag.
A cache memory must also store the data read from main memory. This information is
held in the data section (see Figure 12.4).
The size of a cache is defined as the actual code or data the cache can store from main
memory. Not included in the cache size is the cache memory required to support cache-tags
or status bits.
There are also status bits in cache memory to maintain state information. Two common
status bits are the valid bit and dirty bit. A valid bit marks a cache line as active, meaning
it contains live data originally taken from main memory and is currently available to the
 12.2 Cache Architecture 409

Address issued Cache Cache

by processor core controller memory
31 Miss
Directory
Hit store Status Data

Tag
Compare Cache-tag v d word3 word2 word1 word0 Cache
Cache-tag v d word3 word2 word1 word0 line
12 Cache-tag v d word3 word2 word1 word0
.
11 .
.
Set Cache-tag v d word3 word2 word1 word0
index Cache-tag v d word3 word2 word1 word0 Address/data
Cache-tag v d word3 word2 word1 word0 bus
4 Cache-tag v d word3 word2 word1 word0
3
Cache-tag v d word3 word2 word1 word0
Data
index
0

Figure 12.4 A 4 KB cache consisting of 256 cache lines of four 32-bit words.

processor core on demand. A dirty bit defines whether or not a cache line contains data
that is different from the value it represents in main memory. We explain dirty bits in more
detail in Section 12.3.1.

12.2.2 Basic Operation of a Cache Controller

The cache controller is hardware that copies code or data from main memory to cache
memory automatically. It performs this task automatically to conceal cache operation from
the software it supports. Thus, the same application software can run unaltered on systems
with and without a cache.
The cache controller intercepts read and write memory requests before passing them on
to the memory controller. It processes a request by dividing the address of the request into
three fields, the tag field, the set index field, and the data index field. The three bit fields are
shown in Figure 12.4.
First, the controller uses the set index portion of the address to locate the cache line
within the cache memory that might hold the requested code or data. This cache line
contains the cache-tag and status bits, which the controller uses to determine the actual
data stored there.