Computer Architecture

Cache

Introduction

Cache is a key to the performance of a modern processor. Typically ~25% of instructions reference memory, so that memory access time is a critical factor in performance. By effectively reducing the cost of a memory access, caches enable the greater than one instruction/cycle goal for instruction throughput for modern processors. A further indication of the importance of cache may be gained from noting that out of 6.6x10⁶ transistors in the MIPS R10000, 4.4x10⁶ were used for primary caches. (This presumably includes TLBs as well as the instruction and data caches.)

Etymology

Cache comes from the French, cacher = to hide, presumably because a cache is transparent to, or hidden from, a programmer. Programmers do not generally "see" the cache: programs should run in the same way whether a cache is present or not. Cache should only affect the performance of a program.

Locality of Reference

locality of reference

etc

Temporal Locality

Once a location is referenced, there is a high probability that it will be referenced again in the near future.

Instructions

The simplest example of temporal locality is instructions in loops: once the loop is entered, all the instructions in the loop will be referenced again - perhaps many times - before the loop exits. However, commonly called subroutines and functions and interrupt handlers (eg the timer interrupt handler) also have the same property: if they are accessed once, then it's very likely that they will be accessed again soon.

Data

Many types of data exhibit temporal locality: at any point in a program there will tend to be some "hot" data that the program uses or updates many times before going on to another block of data. Some examples are:

Counters
Look-up Tables
Accumulation variables
Stack variables

Spatial Locality

When an instruction or datum is accessed it is very likely that nearby instructions or data will be accessed soon.

Instructions

It's obvious that an instruction stream will exhibit considerable spatial locality. In the absence of jumps, the next instruction to be executed is the one immediately following the current one.

Data

Data also shows considerable spatial locality - particularly when arrays or strings are accessed. Programs commonly step through an array from beginning to end, accessing each element of the array sequentially.

e-REdING. Biblioteca de la Escuela Superior de Ingenieros de Sevilla.