MemoryArchitecture.pdf

Memory Architecture

Memor

y Architecture

Chapter Six

6.1

Chapter Overview

This chapter discusses the memory hierarch

y – the dif

ferent types and performance le

els of memory

found on a typical 80x86 computer system. Man

y programmers tend to vie

w memory as this big neb

ulous

block of storage that holds v

alues for future use. From a semantic point of vie

, this is a reasonable vie

, from a performance point of vie

w there are man

y dif

ferent kinds of memory and using the wrong

one or using one form improperly can ha

e a dramatically ne

ati

e impact on the performance of a program.

This chapter discusses the memory hierarch

y and ho

w to best use it within your programs.

6.2

The Memory Hierarchy

Most modern programs can beneﬁ

t greatly from a lar

ge amount of v

ery f

ast memory

A ph

ysical reality

, is that as a memory de

vice gets lar

ger

, it tends to get slo

wer

. F

or e

xample, cache memories (see

“Cache Memory” on page

153

) are v

ery f

ast b

ut are also small and e

xpensi

e. Main memory is ine

xpensi

and lar

ge, b

ut is slo

w (requiring w

ait states, see

“W

ait States” on page

151

The memory hierarch

y is a

mechanism of comparing the cost and performance of the v

arious places we can store data and instructions.

Figure 6.1

pro

vides a look at one possible form of the memory hierarch

Registers

Level One Cache

Increasing

Cost,

Increasing

Speed,

Decreasing

Size.

Level Two Cache

Main Memory

NUMA

Virtual Memory

File Storage

Network Storage

Decreasing

Cost,

Decreasing

Speed,

Increasing

Size.

Near-Line Storage

Off-Line Storage

Hard Copy

Figure 6.1

The Memory Hierarchy

At the top le

el of the memory hierarch

y are the CPU’

s general purpose

gisters.

The re

gisters pro

vide

the f

astest access to data possible on the 80x86 CPU.

The re

gister ﬁ

le is also the smallest memory object in

the memory hierarch

y (with just eight general purpose re

gisters a

ailable). By virtue of the f

act that it is vir

tually impossible to add more re

gisters to the 80x86, re

gisters are also the most e

xpensi

e memory locations.

Beta Draft - Do not distribute

Page

303

Chapter Six

Volume Two

Note that we can include FPU, MMX, SIMD, and other CPU re

gisters in this class as well.

These additional

gisters do not change the f

act that there are a v

ery limited number of re

gisters and the cost per byte is quite

high (ﬁ

guring the cost of the CPU di

vided by the number of bytes of re

gister a

ailable).

orking our w

ay do

wn, the

el One Cache system is the ne

xt highest performance subsystem in the

memory hierarch

. On the 80x86 CPUs, the Le

el One Cache is pro

vided on-chip by Intel and cannot be

xpanded.

The size is usually quite small (typically between 4Kbytes and 32Kbytes), though much lar

ger

than the re

gisters a

ailable on the CPU chip.

Although the Le

el One Cache size is ﬁ

ed on the CPU and

you cannot e

xpand it, the cost per byte of cache memory is much lo

wer than that of the re

gisters because the

cache contains f

ar more storage than is a

ailable in all the combined re

gisters.

The

o Cache is present on some CPUs, on other CPUs it is the system designer’

s task to incor

porate this cache (if it is present at all). F

or e

xample, most Pentium II, III, and IV CPUs ha

e a le

el tw

cache as part of the CPU package, b

ut man

y of Intel’

s Celeron chips do not

The Le

o Cache is gen

erally much lar

ger than the le

el one cache (e.g., 256 or 512KBytes v

ersus 16 Kilobytes). On CPUs where

vel Two Cache as part of the CPU package, the cache is not expandable. It is still lower

cost than the Level One Cache because we amortize the cost of the CPU across all the bytes in the Level Two

Cache. On systems where the Level Two Cache is external, many system designers let the end user select

the cache size and upgrade the size. For economic reasons, external caches are actually more expensive than

caches that are part of the CPU package, but the cost per bit at the transistor level is still equivalent to the

in-package caches.

Below the Level Two Cache system in the memory hierarchy falls the main memory subsystem. This is

the general-purpose, relatively low-cost memory found in most computer systems. Typically, this is DRAM

or some similar inexpensive memory technology.

Below main memory is the NUMA category. NUMA, which stands for NonUniform Memory Access is

a bit of a misnomer here. NUMA means that different types of memory have different access times. There-

fore, the term NUMA is fairly descriptive of the entire memory hierarchy. In Figure 6.1a, however, we’ll use

the term NUMA to describe blocks of memory that are electronically similar to main memory but for one

reason or another operate signiﬁcantly slower than main memory. A good example is the memory on a video

display card. Access to memory on video display cards is often much slower than access to main memory.

Other peripheral devices that provide a block of shared memory between the CPU and the peripheral proba-

bly have similar access times as this video card example. Another example of NUMA includes certain

slower memory technologies like Flash Memory that have signiﬁcant slower access and transfers times than

standard semiconductor RAM. We’ll use the term NUMA in this chapter to describe these blocks of mem-

ory that look like main memory but run at slower speeds.

Most modern computer systems implement a Virtual Memory scheme that lets them simulate main

memory using storage on a disk drive. While disks are signiﬁcantly slower than main memory, the cost per

bit is also signiﬁcantly lower. Therefore, it is far less expensive (by three orders of magnitude) to keep some

data on magnetic storage rather than in main memory. A Virtual Memory subsystem is responsible for trans-

parently copying data between the disk and main memory as needed by a program.

File Storage also uses disk media to store program data. However, it is the program’s responsibility to

store and retrieve ﬁle data. In many instances, this is a bit slower than using Virtual Memory, hence the

lower position in the memory hierarchy 2 .

Below File Storage in the memory hierarchy comes Network Storage. At this level a program is keep-

ing data on a different system that connects the program’s system via a network. With Network Storage you

can implement Virtual Memory, File Storage, and a system known as Distributed Shared Memory (where

processes running on different computer systems share data in a common block of memory and communi-

cate changes to that block across the network).

Virtual Memory, File Storage, and Network Storage are examples of so-called on-line memory sub-

systems . Memory access via these mechanism is slower than main memory access, but when a program

1. Note, by the way, that the level two cache on the Pentium CPUs is typically not on the same chip as the CPU. Instead, Intel

packages a separate chip inside the box housing the Pentium CPU and wires this second chip (containing the level two cache)

directly to the Pentium CPU inside the package.

2. Note, however, that in some degenerate cases Virtual Memory can be much slower than ﬁle access.

Page

304

Beta Draft - Do not distribute

Intel includes the Le

Memory Architecture

requests data from one of these memory devices, the device is ready and able to respond to the request as

quickly as is physically possible. This is not true for the remaining levels in the memory hierarchy.

The Near-Line and Off-Line Storage subsystems are not immediately ready to respond to a program’s

request for data. An Off-Line Storage system keeps its data in electronic form (usually magnetic or optical)

but on media that is not (necessarily) connected to the computer system while the program that needs the

data is running. Examples of Off-Line Storage include magnetic tapes, disk cartridges, optical disks, and

ﬂoppy diskettes. When a program needs data from an off-line medium, the program must stop and wait for a

someone or something to mount the appropriate media on the computer system. This delay can be quite

long (perhaps the computer operator decided to take a coffee break?). Near-Line Storage uses the same

media as Off-Line Storage, the difference is that the system holds the media in a special robotic jukebox

device that can automatically mount the desired media when some program requests it. Tapes and remov-

able media are among the most inexpensive electronic data storage formats available. Hence, these media

are great for storing large amounts of data for long time periods.

Hard Copy storage is simply a print-out (in one form or another) of some data. If a program requests

some data and that data is present only in hard copy form, someone will have to manually enter the data into

the computer. Paper (or other hard copy media) is probably the least expensive form of memory, at least for

certain data types.

6.3 How the Memory Hierarchy Operates

The whole point of the memory hierarchy is to allow reasonably fast access to a large amount of mem-

ory. If only a little memory was necessary, we’d use fast static RAM (i.e., the stuff they make cache memory

out of) for everything. If speed wasn’t necessary, we’d just use low-cost dynamic RAM for everything. The

whole idea of the memory hierarchy is that we can take advantage of the principle of locality of reference

(see “Cache Memory” on page 153) to move often-referenced data into fast memory and leave less-used data

in slower memory. Unfortunately, the selection of often-used versus lesser-used data varies over the execu-

tion of any given program. Therefore, we cannot simply place our data at various levels in the memory hier-

archy and leave the data alone throughout the execution of the program. Instead, the memory subsystems

need to be able to move data between themselves dynamically to adjust for changes in locality of reference

during the program’s execution.

Moving data between the registers and the rest of the memory hierarchy is strictly a program function.

The program, of course, loads data into registers and stores register data into memory using instructions like

MOV. It is strictly the programmer’s or compiler’s responsibility to select an instruction sequence that keeps

heavily referenced data in the registers as long as possible.

The program is largely unaware of the memory hierarchy. In fact, the program only explicitly controls

access to main memory and those components of the memory hierarchy at the ﬁle storage level and below

(since manipulating ﬁles is a program-speciﬁc operation). In particular, cache access and virtual memory

operation are generally transparent to the program. That is, access to these levels of the memory hierarchy

usually take place without any intervention on the program’s part. The program just accesses main memory

and the hardware (and operating system) take care of the rest.

Of course, if the program really accessed main memory on each access, the program would run quite

slowly since modern DRAM main memory subsystems are much slower than the CPU. The job of the cache

memory subsystems (and the cache controller) is to move data between main memory and the cache so that

the CPU can quickly access data in the cache. Likewise, if data is not available in main memory, but is avail-

able in slower virtual memory, the virtual memory subsystem is responsible for moving the data from hard

disk to main memory (and then the caching subsystem may move the data from main memory to cache for

even faster access by the CPU).

With few exceptions, most transparent memory subsystem accesses always take place between one level

of the memory hierarchy and the level immediately below or above it. For example, the CPU rarely accesses

main memory directly. Instead, when the CPU requests data from memory, the Level One Cache subsystem

takes over. If the requested data is in the cache, then the Level One Cache subsystem returns the data and

that’s the end of the memory access. On the other hand if the data is not present in the level one cache, then

Beta Draft - Do not distribute

Page 305

Chapter Six

Volume Two

it passes the request on down to the Level Two Cache subsystem. If the Level Two Cache subsystem has the

data, it returns this data to the Level One Cache, which then returns the data to the CPU. Note that requests

for this same data in the near future will come from the Level One Cache rather than the Level Two Cache

since the Level One Cache now has a copy of the data.

If neither the Level One nor Level Two Cache subsystems have a copy of the data, then the memory sub-

system goes to main memory to get the data. If found in main memory, then the memory subsystems copy

this data to the Level Two Cache which passes it to the Level One Cache which gives it to the CPU. Once

again, the data is now in the Level One Cache, so any references to this data in the near future will come

from the Level One Cache.

If the data is not present in main memory, but is present in Virtual Memory on some storage device, the

operating system takes over, reads the data from disk (or other devices, such as a network storage server) and

places this data in main memory. Main memory then passes this data through the caches to the CPU.

Because of locality of reference, the largest percentage of memory accesses take place in the Level One

Cache system. The next largest percentage of accesses occur in the Level Two Cache subsystems. The most

infrequent accesses take place in Virtual Memory.

6.4 Relative Performance of Memory Subsystems

If you take another look at Figure 6.1 you’ll notice that the speed of the various levels increases at the

higher levels of the memory hierarchy. A good question to ask, and one we’ll hope to answer in this section,

is "how much faster is each successive level in the memory hierarchy?" It actually ranges from "almost no

difference" to "four orders of magnitude" as you’ll seem momentarily.

Registers are, unquestionably, the best place to store data you need to access quickly. Accessing a regis-

ter never requires any extra time 3 . Further, instructions that access data can almost always access that data in

a register. Such instructions already encode the register "address" as part of the MOD-REG-R/M byte (see

“Encoding Instruction Operands” on page 290 ). Therefore, it never takes any extra bits in an instruction to use a

instruction encoding. This makes the instruction longer which means fewer of them can sit in the cache or in

a prefetch queue. Hence, the program may run slower if it uses memory operands more often than register

operands simply due to the instruction size difference.

If you read Intel’s instruction timing tables, you’ll see that they claim that an instruction like

"mov( someVar, ecx );" is supposed to run as fast as an instruction of the form "mov( ebx, ecx );" However,

if you read the ﬁne print, you’ll ﬁnd that they make several assumptions about the former instruction. First,

they assume that someVar’s value is present in the level one cache memory. If it is not, then the cache con-

troller needs to look in the level two cache, in main memory, or worse, on disk in the virtual memory sub-

system. All of a sudden, this instruction that should execute in one cycle (e.g., one nanosecond on a one

gigahertz processor) requires several milliseconds to execution. That’s over six orders of magnitude differ-

ence, if you’re counting. Now granted, locality of reference suggests that future accesses to this variable will

take place in one cycle. However, if you access someVar’s value one million times immediately thereafter,

the average access time of each instruction will be two cycles because of the large amount of time needed to

access someVar the very ﬁrst time (when it was on a disk in the virtual memory system). Now granted, the

likelihood that some variable will be on disk in the virtual memory subsystem is quite low. But there is a

three orders of magnitude difference in performance between the level one cache subsystem and the main

memory subsystem. So if the program has to bring in the data from main memory, 999 accesses later you’re

still paying an average cost of two cycles for the instruction that Intel’s documentation claims should execute

in one cycle. Note that register accesses never suffer from this problem. Hence, register accesses are much

faster.

3. Okay, strictly speaking this is not true. However, we’ll ignore data hazards in this discussion and assume that the program-

mer or compiler has scheduled their instructions properly to avoid pipeline stalls due to data hazards with register data.

Page 306

Beta Draft - Do not distribute

Memory Architecture

The difference between the level one and level two cache systems is not so dramatic. Usually, a level

two caching subsystem introduces between one and eight wait states (see “Wait States” on page 151). The

difference is usually much greater, though, if the secondary cache is not packaged together with the CPU.

On a one gigahertz processor the level one cache must respond within one nanosecond if the cache oper-

ates with zero wait states (note that some processors actually introduce wait states in accesses to the level

one cache, but system designers try not to do this). Accessing data in the level two cache is always slower

than in the level one cache and there is always the equivalent of at least one wait state, perhaps more, when

accessing data in the level two cache. The reason is quite simple – it takes the CPU time to determine that

the data it is seeking is not in the L1 (level one) cache; by the time it determines that the data is not present,

the memory access cycle is nearly complete and there is no time to access the data in the L2 (level two)

cache.

It may also be that the L2 cache is slower than the L1 cache. This is usually done in order to make the

L2 cache less expensive. Also, larger memory subsystems tend to be slower than smaller ones, and L2

caches are usually 16 to 64 times larger than the L1 cache, hence they are usually slower as well. Finally,

because L2 caches are not usually on the same silicon chip as the CPU, there are some delays associated

with getting data in and out of the cache. All this adds up to additional wait states when accessing data in the

L2 cache. As noted above, the L2 cache can be as much as an order of magnitude slower than the L1 cache.

Another difference between the L1 and L2 caches is the amount of data the system fetches when there is

an L1 cache miss. When the CPU fetches data from the L1 cache, it generally fetches (or writes) only the

data requested. If you execute a "mov( al, memory);" instruction, the CPU writes only a single byte to the

cache. Likewise, if you execute "mov( mem32, eax );" then the CPU reads 32 bits from the L1 cache.

Access to memory subsystems below the L1 cache, however, do not work in small chucks like this. Usually,

memory subsystems read blocks (or cache lines ) of data whenever accessing lower levels of the memory

hierarchy. For example, if you execute the "mov( mem32, eax );" instruction and mem32’s value is not in the

L1 cache, the cache controller doesn’t simply read mem32’s value from the L2 cache (assuming it’s present

there). Instead, the cache controller will actually read a block of bytes (generally 16, 32, or 64 bytes, this

depends on the particular processor) from the lower memory levels. The hope is that spatial locality exists

and reading a block of bytes will speed up accesses to adjacent objects in memory 4 . The bad news, however,

is that the "mov( mem32, eax );" instruction doesn’t complete until the L1 cache reads the entire cache line

(of 16, 32, 64, etc., bytes) from the L2 cache. Although the program may amortize the cost of reading this

block of bytes over future accesses to adjacent memory locations, there is a large passage of time between

the request for mem32 and the actual completion of the "mov( mem32, eax );" instruction. This excess time

is known as latency. As noted, the hope is that extra time will be worth the cost when future accesses to adja-

cent memory locations occur; however, if the program does not access memory objects adjacent to mem32 ,

this latency is lost time.

A similar performance gulf separates the L2 cache and main memory. Main memory is typically an

order of magnitude slower than the L2 cache. Again the L2 cache reads data from main memory in blocks

(cache lines) to speed up access to adjacent memory elements.

There is a three to four order of magnitude difference in performance between standard DRAM and disk

storage. To overcome this difference, there is usually a two to three orders of magnitude difference in size

between the L2 cache and the main memory. In other words, the idea is "if the access time difference

between main memory and virtual memory is two orders of magnitude greater than the difference between

the L2 cache and main memory, then we’d better make sure we have two orders of magnitude more main

memory than we have L2 cache." This keeps the performance loss to a reasonable level since we access vir-

tual memory on disk two orders of magnitude less often.

We will not consider the performance of the other memory hierarchy subsystems since they are more or

less under programmer control (their access is not automatic by the CPU or operating system). Hence, very

little can be said about how frequently a program will access them.

4. Note that reading a block of n bytes is much faster than n reads of one byte. So this scheme is many times faster if spatial

locality does occur in the program. For information about spatial locality, see “Cache Memory” on page 153.

Beta Draft - Do not distribute

Page 307

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: