334 CHAPTER 6 Performance with a capacity equal to that of the main memory, nearly as fast as the L2 cache. For a second example, if the primary device is main memory with 10 nanoseconds latency and the secondary device is magnetic disk with average latency of 10 milliseconds, the average latency of the multilevel memory is 0.99 3 10 nanoseconds 1 0.01 3 10 milliseconds 5 100.0099 microseconds That latency is substantially larger than the 10 nanosecond primary memory latency, but it is also much smaller than the 10 millisecond secondary memory latency. In essence, a multilevel memory just exploits the design hint optimize for the common case. Most applications are not so well behaved that one can identify a static set of infor- mation that is both small enough to fit in the primary device and for which reference is so concentrated that it is the target of 99% of all memory references. However, in many situations most memory references are to a small set of addresses for significant periods of time. As the application progresses, the area of concentration of access shifts, but its size still typically remains small. This concentration of access into a small but shifting locality is what makes an automatically managed multilevel memory sys- tem feasible. An application that exhibits such a concentration of accesses is said to have locality of reference. Analyzing the situation, we can think of a running application as generating a stream of virtual addresses, known as the reference string. A reference string can exhibit locality of reference in two ways: Temporal locality: the reference string contains several closely spaced refer- ences to the same address. Spatial locality: the reference string contains several closely spaced references to adjacent addresses. An automatically managed multilevel memory system can exploit temporal locality by keeping in the primary device those memory cells that appeared in the reference string recently--thus applying speculation. It can exploit spatial locality by moving into the primary device memory cells that are adjacent to those that have recently appeared in the reference string--a combination of speculation and batching (because issuing a get to a secondary device can retrieve a large block of data that can occupy many adjacent memory cells in the primary device). There are endless ways in which applications exhibit locality of reference: Programs are written as a sequence of instructions. Most of the time, the next instruction is stored in the memory cell that is physically adjacent to the previ- ous instruction, thus creating spatial locality. In addition, applications frequently execute a loop, which means there will be repeated references to the same instructions, creating temporal locality. Between loops, conditional tests, and jumps, it is common to see many instruction references directed to a small sub- set of all the instructions of an application for an extended time. In addition, depending on the conditional structure, large parts of an application program may not be exercised at all.