30-06-2012, 01:06 PM
Memory-Hierarchy Design
[attachment=26271]
introduction
Computer pioneers correctly predicted that programmers would want unlimited
amounts of fast memory. An economical solution to that desire is a memory hierarchy,
which takes advantage of locality and cost/performance of memory
technologies. The principle of locality, presented in the first chapter, says that
most programs do not access all code or data uniformly (see section 1.6, page
38). This principle, plus the guideline that smaller hardware is faster, led to the
hierarchy based on memories of different speeds and sizes. Since fast memory is
expensive, a memory hierarchy is organized into several levels—each smaller,
faster, and more expensive per byte than the next level. The goal is to provide a
memory system with cost almost as low as the cheapest level of memory and
speed almost as fast as the fastest level. The levels of the hierarchy usually subset
one another; all data in one level is also found in the level below, and all data in
that lower level is found in the one below it, and so on until we reach the bottom
of the hierarchy. Note that each level maps addresses from a larger memory to a
smaller but faster memory higher in the hierarchy.
How is a block found if it is in the cache?
Caches have an address tag on each block frame that gives the block address. The
tag of every cache block that might contain the desired information is checked to
see if it matches the block address from the CPU. As a rule, all possible tags are
searched in parallel because speed is critical.
There must be a way to know that a cache block does not have valid information.
The most common procedure is to add a valid bit to the tag to say whether or
not this entry contains a valid address. If the bit is not set, there cannot be a match
on this address.
Which block should be replaced on a cache miss?
When a miss occurs, the cache controller must select a block to be replaced with
the desired data. A benefit of direct-mapped placement is that hardware decisions
are simplified—in fact, so simple that there is no choice: Only one block frame is
checked for a hit, and only that block can be replaced. With fully associative or
set-associative placement, there are many blocks to choose from on a miss. There
are two primary strategies employed for selecting which block to replace:
Random—To spread allocation uniformly, candidate blocks are randomly
selected. Some systems generate pseudorandom block numbers to get reproducible
behavior, which is particularly useful when debugging hardware.
Cache Performance
Because instruction count is independent of the hardware, it is tempting to evaluate
CPU performance using that number. As we saw in Chapter 1, however, such
indirect performance measures have waylaid many a computer designer. The
corresponding temptation for evaluating memory-hierarchy performance is to concentrate
on miss rate, because it, too, is independent of the speed of the hardware.
As we shall see, miss rate can be just as misleading as instruction count. A better
measure of memory-hierarchy performance is the average time to access memory:
[attachment=26271]
introduction
Computer pioneers correctly predicted that programmers would want unlimited
amounts of fast memory. An economical solution to that desire is a memory hierarchy,
which takes advantage of locality and cost/performance of memory
technologies. The principle of locality, presented in the first chapter, says that
most programs do not access all code or data uniformly (see section 1.6, page
38). This principle, plus the guideline that smaller hardware is faster, led to the
hierarchy based on memories of different speeds and sizes. Since fast memory is
expensive, a memory hierarchy is organized into several levels—each smaller,
faster, and more expensive per byte than the next level. The goal is to provide a
memory system with cost almost as low as the cheapest level of memory and
speed almost as fast as the fastest level. The levels of the hierarchy usually subset
one another; all data in one level is also found in the level below, and all data in
that lower level is found in the one below it, and so on until we reach the bottom
of the hierarchy. Note that each level maps addresses from a larger memory to a
smaller but faster memory higher in the hierarchy.
How is a block found if it is in the cache?
Caches have an address tag on each block frame that gives the block address. The
tag of every cache block that might contain the desired information is checked to
see if it matches the block address from the CPU. As a rule, all possible tags are
searched in parallel because speed is critical.
There must be a way to know that a cache block does not have valid information.
The most common procedure is to add a valid bit to the tag to say whether or
not this entry contains a valid address. If the bit is not set, there cannot be a match
on this address.
Which block should be replaced on a cache miss?
When a miss occurs, the cache controller must select a block to be replaced with
the desired data. A benefit of direct-mapped placement is that hardware decisions
are simplified—in fact, so simple that there is no choice: Only one block frame is
checked for a hit, and only that block can be replaced. With fully associative or
set-associative placement, there are many blocks to choose from on a miss. There
are two primary strategies employed for selecting which block to replace:
Random—To spread allocation uniformly, candidate blocks are randomly
selected. Some systems generate pseudorandom block numbers to get reproducible
behavior, which is particularly useful when debugging hardware.
Cache Performance
Because instruction count is independent of the hardware, it is tempting to evaluate
CPU performance using that number. As we saw in Chapter 1, however, such
indirect performance measures have waylaid many a computer designer. The
corresponding temptation for evaluating memory-hierarchy performance is to concentrate
on miss rate, because it, too, is independent of the speed of the hardware.
As we shall see, miss rate can be just as misleading as instruction count. A better
measure of memory-hierarchy performance is the average time to access memory: