next up previous

2.2 Memories     continued...

Locality of reference can be exploited in the following way. Instead of building the entire memory out of the same material, construct a hierarchy of memories, each with different capacities and access times. At the top of the hierarchy there will be a small memory, perhaps only a few KB, built from the fastest chips. The bottom of the hierarchy will be the largest but slowest memory. The processor will be connected to the top of the hierarchy, i.e. when it fetches an instruction it will send its request to the small, fast memory. If this memory contains the requested item, it will respond, and the request is satisfied. If a memory does not have an item, it forwards the request to the next lower level in the hierarchy.

The key idea is that when the lower levels of the hierarchy send a value from location x to the next level up, they also send the contents of x + 1, x + 2, etc. If locality of reference holds, there is a high probability there will soon be a request for one of these other items; if there is, that request will be satisfied immediately by the upper level memory.