Locality of Reference

Analysis of a large number of typical program has shown that the references to memory at any given interval of time tend to be confined within a few localized areas in memory. This is phenomenon is known as the property of locality of reference.     

    Over short interval of time, the addresses generated by typical program refer to few localized areas of memory repeatedly, while the remainder of memory is accessed relatively infrequently.If the active portions of the program and data are placed in a fast small memory, the average memory time access time can be reduced, thus reducing the total execution time of the program. Such a fast small memory is referred to as a cache memory.

   When the CPU refers to memory and finds the word in cache it is said to produce a hit. If the word is not found in cache, it is in main memory  and it counts as miss. The ratio of the number of hits divided by the total CPU references to memory(hits + misses) is the hit ratio .

Hit ratio = hits/(hits + misses)

There are two different kinds of locality of reference:
  • Temporal locality: If a value is referenced, there is a high probability it will be referenced again a short time from now
  • Spatial locality: A value is stored in a certain location in storage (memory, disk,..). If this location is referenced, it is very probable that locations that are physically close to it will be referenced as well.
Locality of Reference
Rate this post

Leave a Reply