Associative Memory and the Page Table

The implementation of the page table is vital to the efficiency of the virtual memory technique, for each memory reference must also include a reference to the page table. The fastest solution is a set of dedicated registers to hold the page table but this method is impractical for large page tables because of the expense. But keeping the page table in main memory could cause intolerable delays because even only one memory access for the page table involves a slowdown of 100 percent and large page tables can require more than one memory access. The solution is to augment the page table with special high-speed memory made up of associative registers or translation lookaside buffers (TLBs) which are called ASSOCIATIVE MEMORY.

Each of these associative memory registers contains a key and a value. The keys to associative memory registers can all be compared simultaneously. If a match is found, the value corresponding to the key is output. This returned value contains the physical address of the logical page and an access code to indicate its presence in main memory.

Associative memory registers are very expensive so only the most frequently accessed pages should be represented by them. How many associative memory registers are required for a virtual memory implementation to run efficiently? The percentage of times a page is found in the associative memory registers is called the HIT RATIO. The effective access time of the virtual memory system can be computed by multiplying the hit ratio by the access time using associative memory and adding (1 - the hit ratio) times the access time using the main memory page table. (Remember, using the page table requires an extra access to main memory.) This total is then compared to the time for a simple access to the main memory.

For example: If the access time for main memory is 120 nanoseconds and the access time for associative memory is 15 nanoseconds and the hit ratio is 85 percent, then access time = .85 x (15 + 120) + (1 - .85) x (15 + 120 +120) = 153 nanoseconds. Since the simple access time is 120 nanoseconds, this represents a slowdown of 27 percent compared to the simple main memory access.

What would the slowdown be if the hit ratio were increased to 95 percent?

The Intel 80486 CPU has a 98 percent hit ratio with only 32 associative memory registers.

Also see [D1] pp. 161-165, [D2] and [T1] pp. 101-107 .

---