CACHE MEMORIES FOR PDP-1 1 FAMILY COMPUTERS 265

understanding of the operation of a set associative cache is aided by Figure 1. The n bit Mp address is divided into three fields of 1, i, and b bits. Assume that there are 2ⁱ sets. The i-bit index field selects one of these sets. The A portion of each AD pair is compared against the 1-bit label field* of the Mp address. If there is a match, the b-bit byte field selects the byte (or other sub-unit) in the D portion of the matched AD pair.

Figure 1. Address fields for a set associative cache.

If there is no match, Mp is accessed and (generally) a new AD pair is moved into the cache. Which of the AD pairs to be replaced in the set is selected by the replacement algorithm. Typical replacement algorithms are: first in, first out (FIFO); least recently used (LRU), or random (RAND).

There are two limiting cases of the set associative organization. When the number of sets is the cache size in blocks, only a single hardware comparator is needed. The resulting organization is called direct mapped. It is the simplest form of cache organization. When there is only one set, clearly a fully associative cache results.

So far in the discussion there has been no distinction made between read and write accesses. When the Pc makes a write access, ultimately Mp must be updated. There are two obvious times when this can be done. First is at the time the write access is made. Both Mp and the cache (if there is a hit) are updated simultaneously. This strategy is termed write-through. Alternatively, only the cache can be updated on a write hit, and only when the updated AD pair is re placed on some future miss is Mp updated. This strategy is termed write-back. The choice between these two strategies involves systems considerations which are beyond the scope of this paper. t

There are other possible asymmetries in the handling of reads and writes. One possibility is that after a write miss an AD pair corresponding to that access is not stored in the cache. This is termed no-write-allocate. The alternative is, of course, termed write-allocate.

The understanding of memory hierarchies (and programs) has not reached the point where cache performance can be predicted analytically as a function of cache organizational parameters. As a consequence, the studying of cache memory behavior is done through simulation. (Some cache simulation results for other computer architectures are reported in [Conti et al, 1968; Meade, 1970; Bell et a!., 1974; Gibson, 1967].) For the purposes of this study, a two part simulator was constructed.

The first part was a PDP-l 1 simulator. This is a PDP-l 1 program which runs other PDP-1 1 programs interpretively. A variety of properties of the interpreted programs can be collected, including the sequence of generated Mp addresses. The latter is termed an address trace. The address trace is processed by the second part, the cache simulator. This is parameterized by cache organization and determines the miss ratio for a given address trace.

_____________________

* Note that, in a set associative cache, only the label field must be stored in the cache AD pair - not the entire Mp address.

t For the PDP- 11/70 system, write-through was chosen. The main impact of this is that each write access, as well as each read miss, results in an Mp access. Data suggests that, in PDP-l is, about 10 percent of Pc accesses are writes.