Would you like to make this site your homepage? It's fast and easy...
Yes, Please make this my home page!
================================================================================
Note 9.0 LSI-11/73 Cache Concepts No replies
JAWS::KAISER 307 lines 25-MAR-1985 09:18
--------------------------------------------------------------------------------
+---------------+ +-----------------+
| d i g i t a l | | uNOTE # 009 |
+---------------+ +-----------------+
+----------------------------------------------------+-----------------+
| Title: Cache Concepts and the LSI-11/73 | Date: 02-JUL-84 |
+----------------------------------------------------+-----------------+
| Originator: Charlie Giorgetti | Page 1 of 6 |
+----------------------------------------------------+-----------------+
The goal is to introduce the concept of cache and its particular
implementation on the LSI-11/73 (KDJ11-A). This is not a detailed
discussion of the different cache organizations and their impact on
system performance.
What Is A Cache ?
-----------------
The purpose of having a cache is to simulate a system having a large
amount of moderately fast memory. To do this the cache system relies on
a small amount of very fast, easily accessed memory (the cache), a
larger amount of slower, less expensive memory (the backing store), and
the statistics of program behavior.
The goal is to store some of the data and its associated addresses in
the cache and all of the data at its usual addresses (including the
currently cached data) in the backing store. If it can be arranged that
most of the time when the processor needs data it is located in fast
memory, then the program will execute more quickly, slowing down only
occasionally for main memory operations. The placement of data in the
cache should not be a concern to the programmer but is a consequence of
how the cache functions.
Figure 1 is an example of a memory organization showing a cache with
backing store. If the data needed by the microprocessor (uP) can be
found in the cache then it is accessed much faster due to the local data
path and faster cache memory than by having to access the backing store
on the slower system bus.
+-----------+ System Bus
+------+ CPU Internal Buses | System | For Memory and I/O Options
| |<-----------------+->| Bus |<-------------------------->
| uP | | | Interface | |
| |<----------+ | +-----------+ |
+------+ Fast Path | | +-------+---------+
to Cache | | | |
+-+------+--+ | System Memory |
| | | (Backing Store) |
| Cache | | |
| | +-----------------+
+-----------+
Figure 1 - An Example Memory System with Cache
Page 2
A cache memory system can only work if it can successfully predict most
of the time what memory locations the program will require. If a
program accessed data from memory in a completely random fashion, it
would be impossible to predict what data would be needed next. If this
was the case a cache would operate no better then a conventional memory
system.
Programs rarely generate random addresses. In many cases the subsequent
memory address referenced is often very near the current address
accessed. This is the principle of program locality. The next address
generated is in the neighborhood of the current address. This behavior
helps makes cache systems feasible.
The concept of program locality is not always adhered to, but is a
statement of how many programs behave. Many programs execute code in a
linear fashion or in loops with predictable results in next address
generation. Jumps and context switching give the appearance of random
address generation. The ability to determine what word a program will
reference next is never completely successful and therefore the correct
"guesses" are a statistical measure of the size and organization of the
cache, and the behavior of the program being executed.
The measure of a cache performance is a statistical evaluation of the
number of memory references found versus not found in cache. When
memory is referenced and the address is found in the cache this is known
as a hit. When it is not it is termed a miss. Cache performance is
usually stated in terms of the hit ratio or the miss ratio where these
are defined as:
Number of Cache Hits
Hit Ratio = ---------------------------------
Total Number of Memory References
Miss Ratio = 1 - Hit Ratio
The LSI-11/73 Cache Implementation
----------------------------------
The cache organization chosen must be one that can be implemented within
the physical and cost constraints of the design.
The LSI-11/73 implements a direct map cache. A direct map organization
has a single unique cache location for a given address and this is where
the associated data from backing store are maintained. This means an
access to cache requires one address comparison to determine if there is
a hit. The significance of this is that a small amount of circuitry is
required to perform the comparison operation. The LSI-11/73 has an 8
KByte cache. This means that there are 4096 unique address locations
each of which stores two bytes of information.
Page 3
The cache not only maintains the data from backing store but it also
includes other information that is needed to determine if its content is
valid. These are parity detection and valid entry checking. The
following diagram shows the logical layout of the cache and what each
field and its associated address in the cache is used for.
Binary Cache
Entry Address P V TAG P1 B1 P0 B0
+---+---+-------------+---+----------+---+----------+
000000000000 | | | | | | | |
+---+---+-------------+---+----------+---+----------+
000000000001 | | | | | | | |
+---+---+-------------+---+----------+---+----------+
000000000010 | | | | | | | |
+---+---+-------------+---+----------+---+----------+
. .
. .
. .
+---+---+-------------+---+----------+---+----------+
111111111101 | | | | | | | |
+---+---+-------------+---+----------+---+----------+
111111111110 | | | | | | | |
+---+---+-------------+---+----------+---+----------+
111111111111 | | | | | | | |
+---+---+-------------+---+----------+---+----------+
Figure 2 - LSI-11/73 Cache Layout
The Cache Entry Address is the address of one of 4096 entries within the
cache. This value has a one-to-one relationship with a field in each
address that is generated by the processor (described in the next
section on how the physical address accesses cache).
Each field has the following meaning:
Tag (TAG) - This nine bit field contains information that is
compared to the address label, described in the next section on
how the physical address accesses cache. When the physical
address is generated, the address label is compared to the tag
field. If there is a match it can be considered a hit provided
that there is entry validation and no parity errors.
Cache Data (B0 and B1) - These two bytes are the actual data
stored in cache.
Valid Bit (V) - The valid bit indicates whether the information
in B0 and B1 is usable as data if a cache hit occurs. The valid
bit is set when the entry is allocated during a cache update
which occurs as a result of a miss.
Tag Parity Bit - (P) - Even parity calculated for the value
stored in the tag field.
Page 4
Parity Bits (P0 and P1) - P0 is even parity calculated for the
data byte B0 and P1 is odd parity calculated for the data byte
B1.
When the processor generates a physical address, the on-board cache
control logic must determine if there is a hit by looking at the unique
location in cache. To determine what location to check, the cache
control logic considers each address generated as being made up of three
unique parts. The following are the three fields of a 22-bit address
(in an unmapped or 18-bit environment the label field is six or four
bits less respectfully):
21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
+--+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+--+ +--+
| | | | | | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+--+ +--+
|<-------- LABEL --------->| |<-------------- INDEX ------------>| BYTE
SELECT
Figure 2 - Components of a 22-bit Address For Cache Address Selection
Each field has the following meaning:
Index - This twelve bit field determines which one of the 4096
cache data entries to compare with for a cache hit. The index
field is the displacement into the cache and corresponds to the
Cache Entry Address.
Label - Once the location in the cache is selected, the nine bit
label field is compared to the tag field stored in the cache
entry under consideration. If the address label and the tag
field match, the valid bit is set, and there is no parity error,
then a hit has occurred.
Byte Select Bit - This bit determines if the reference is on an
odd or even byte boundary. All Q-bus reads are word only so
this bit has no effect on a cache read. Q-bus writes can access
either words or bytes. If there is a word write the cache will
be updated if there is a hit. If there is a miss a new cache
entry will be made. If there is a byte write, the cache will
only be updated if there is a hit. A miss will not create a new
entry on a byte write.
The LSI-11/73 direct map cache must update the backing store on a memory
write. The LSI-11/73 uses the write through method. With this
technique, writes to backing store occurs concurrently with cache
writes. The result is that the backing store always contains the same
data as the cache.
Page 5
Features Of The LSI-11/73 Cache
-------------------------------
The LSI-11/73 direct map cache has a number of features that assist in
the performance of the overall system in addition to the speed
enhancement as a result of faster memory access. These features consist
of the following:
o Q-bus DMA monitoring
o I/O page reference monitoring
o Memory management control of cache access
o Program control of cache parameters
o Statistical monitoring of cache performance
The LSI-11/73 cache control logic monitors the Q-bus during DMA
transactions. When an address that has its data stored in cache is
accessed during DMA, the cache and backing store contents might no
longer be the same. This is an unacceptable situation. The cache
control logic invalidates a cache entry if the address is used during
DMA. This also includes addresses used during Q-bus Block Mode DMA
transfers.
Memory references to the I/O page are not cached since that data is
volatile, meaning its contents can change without a Q-bus access. Since
the cache could end up with stale data, I/O references are not cached.
There are situations for which using the cache to store information for
faster access is not desirable. An example is a device that resides in
the I/O page, and is true in other instances as well. One situation is
a device that does not reside in the I/O page but can change its
contents without a bus reference, such as dual ported memory.
Another situation is partitioning and tuning an application for
instruction code execution versus data being manipulated. In this case
the instruction stream may execute many times over for different data
values. Speed enhancement can be obtained if the instructions are
cached while the data is not cached. By forcing the data never to be
cached it cannot replace instructions in the cache.
The memory management unit (MMU) of the LSI-11/73 can assist in this
situation. Pages of memory allocated for data can be marked to bypass
the cache and therefore not effect instructions that loop many times.
The cache and the MMU work together to achieve the goal of increased
system performance.
The dynamics of cache operation are under program control through use of
the Cache Control Register (CCR), an LSI-11/73 on-board register. This
register can "turn" the cache on or off, force cache parity errors for
diagnostic testing, and invalidate all cache entries. The details of
the CCR are described in the KDJ11-A CPU Module User's Guide (part
number EK-KDJ1A-UG-001).
During system design or at run-time the performance enhancements
provided by the cache system can be monitored under program control.
This is accomplished by using another LSI-11/73 on-board register the
Page 6
Hit/Miss Register (HMR). This register tracks the last six memory
references and indicates if a hit or miss took place. The details of
the HMR are also described in the KDJ11-A CPU Module User's Guide.
Summary
-------
Caches are a mechanism that can help improve overall system performance.
The dynamics of a given cache are dictated by the organization and the
behavior of the programs running on the machine. The LSI-11/73 cache is
designed to be flexible in its use, simple in implementation, and
enhance application performance.
More detailed discussions on how caches work and other cache
organizations can be found in computer architecture texts that have a
discussion of memory hierarchy.
