Principle of Locality

The principle of locality states that programs access a relatively small portion of their address space at any instant of time.

Temporal Locality

The principle stating that if a data location is referenced then it will tend to be referenced again soon. Eg. loops.

Spatial Locality

The locality principle stating that if a data location is referenced, data locations with nearby addresses will tend to be referenced soon. Eg. instructions are accessed sequentially, sequential access to array.

Memory Hierarchy

A structure that uses multiple levels of memories; as the distance from the processor increases, the size of the memories and the access time both increase.

Block or Line

The minimum unit of information that can be either present or not present in a cache.

Cache Hit

If the data requested by the processor appears in some block in the upper level, this is called a hit.

Cache Miss

If the data is not found in the upper level, the request is called a miss.

Hit Rate

The fraction of memory accesses found in a level of the memory hierarchy.

Miss Rate

The fraction of memory accesses not found in a level of the memory hierarchy = (1 – Hit rate)

Hit Time

The time required to access a level of the memory hierarchy, including the time needed to determine whether the access is a hit or a miss.

Miss Penalty

The time required to fetch a block into a level of the memory hierarchy from the lower level, including the time to access the block, transmit it from one level to the other, insert it in the level that experienced the miss and then pass the block to the requester. The time to access the next level in the hierarchy is the major component of the miss penalty.

Prefetching

A technique in which data blocks needed in the future are brought into the cache early by the use of special instructions that specify the address of the block.