Contents
Supplement to material in section 5.2.
Includes notation presented in class.
Motivation
Memory system implemented using memory devices.
Loads and stores are performed frequently.
Fast memory devices are expensive and cannot be made too large.
Cheap memory devices are slow.
By organizing these devices into a cache performance will be ...
... almost as fast as expensive devices ...
... almost as cheap as slow devices.
Idea
Use cheap devices to implement (real part of) address space.
Use expensive devices to duplicate parts of address space.
Hit
If accessed data in expensive devices, data returned quickly.
Called a hit.
Miss
If accessed data not in expensive devices ...
... data copied from cheap to expensive devices ...
... and passed to processor (taking much more time than a hit).
Called a miss.
Organization of Simple Cache
Uses two memories, called data and tag. (Both expensive.)
Data memory holds copies of data held by cheap devices.
Tag memory holds information about data held in data memory.
Terminology
Address Space
The set of addresses defined in the ISA.
These are the addresses that load and store operands refer to.
Usually specified in the number of bits in an address' binary representation.
Symbol used in class: a.
Typical values:
DLX and older ISAs, a=32,
DEC Alpha, Sun SPARC V9, a=64.
Unit of Addressability
What a memory address refers to; defined by the ISA.
Sometimes called a character.
Symbol used in class: c
In most systems, c=8 bits.
Bus Width
The number of bits brought into the processor in a single accesses.
The number of bits accessed by an instruction may be less, the other bits are ignored.
This is an implementation feature.
Symbol used in class w.
In any reasonable system w is a multiple of c.
Typical values, w=64 bits.
Relationship Between Address and Data on Bus
If w=c then data on bus is for a single address.
If w/c=2 then data on bus is for two consecutive addresses.
If w/c=D then data on bus is for D consecutive addresses.
If the load instruction referred to less than w/c addresses the processor hardware would have to extract the characters needed.
Line (also called block)
The unit of storage in a cache.
Consists of one or more bus-width's worth of data.
On a miss an entire line's worth of data copied from main memory.
The size of a line usually given in terms of characters.
Symbols used in class: L line size in characters, l=log2L.
Set
A part of a cache.
A set contains one or more lines.
The number of lines in a set is called the associativity.
Symbol: s, log2 of the number of sets.
Address Fields
The location of accessed data in a cache is determined in part by bits (fields) in the data address.
The fields are described below.
Alignment
Bits: 0:(d-1)
where d = log2(w/c) (characters per bus width).
Assuming aligned fetches, the d least significant bits of an address will either be zero or ignored.
This part of the address is ignored by the cache.
These bits are labeled "offset" in figure 5.8. Three of those five offset bits are actually alignment bits.
Offset
Bits: d:(l-1),
The part of the line to be accessed.
(A line can hold more than one bus-width worth of data.)
This and the index are used to look up the data in each of the data memories.
These bits are labeled "offset" in figure 5.8. Two of those five bits are offset bits as defined here and are shown connected (along with index) to the address inputs of the data memories.
Index
Bits: l:(l+s-1)
The set to be accessed.
Used to look up a tag in each of the tag memories.
Along with the offset, used to look up the data in each of the data memories.
These are labeled "index" in figure 5.8 and are shown connecting to the data and tag memories.
Tag
Bits: (l+s):(a-1)
The part of the address stored in the tag memories.
The number of tags stored per set is equal to the associativity.
The tags that are retrieved (see index, above) are compared to the tag of the address being accessed.
There is a hit if a tag matches and the corresponding valid bit is 1.
Labeled "tag" in figure 5.8. The figure omits the data-in port to the tag memories, which is used for writing a new tag and valid bit on cache replacement.
David M. Koppelman - koppel@ee.lsu.edu | Modified 29 Apr 1998 15:20 (20:20 UTC) |