To experiment with prefetching, we extend our base architecture as follows. We augment the instruction set to include a prefetch instruction that uses a base-plus-offset addressing format and is defined not to take any memory exceptions. The advantages of these properties will be discussed in more detail later in Section , but the basic idea is that base-plus-offset addressing minimizes register usage to avoid spilling, and the non-excepting property allows considerable flexibility in scheduling prefetches (e.g., it is acceptable to prefetch off the end of an array if a proper epilog cannot be constructed). Both levels of the cache are lockup-free  in the sense that multiple prefetches can be outstanding along with either a single load or store miss. The primary cache is checked in the cycle the prefetch instruction is executed. If the line is already in the cache, the prefetch is discarded. Otherwise, the prefetch is sent to a prefetch issue buffer, which is a structure that maintains the state of outstanding prefetches. For our study, we assume a rather aggressive design of a prefetch issue buffer that contains 16 entries. If the prefetch issue buffer is already full, the processor is stalled until there is an available entry. (Later, in Section , we compare this with an architecture where prefetches are simply dropped if the buffer is full.) The secondary cache is also checked before the prefetch goes to memory. We model contention for the memory bus by assuming a maximum pipelining rate of one access every 20 cycles. Once the prefetched line returns, it is placed in both levels of the cache hierarchy. Filling the primary cache requires 4 cycles of exclusive access to the cache tags-during this time, the processor cannot execute any loads or stores; if it attempts to do so, it is stalled.
Since regular cache misses stall the processor, they are given priority over prefetch accesses both for the memory bus and the cache tags. We assume, however, that an ongoing prefetch access cannot be interrupted. As a result, a secondary cache miss may be delayed by as many as 20 cycles (memory pipeline occupancy time) when it tries to access memory. Similarly the processor may be stalled for up to 4 cycles (cache-tag busy time) when it executes a load or store. If a cache miss occurs for a line for which there is an outstanding prefetch waiting in the issue buffer, the miss is given immediate priority and the prefetch request is removed from the buffer. If the prefetch has already been issued to the memory system, any partial latency hiding that might have occurred is taken into account.