Associative Memory and the Page Table
The implementation of the page table is vital to the efficiency of the virtual memory technique, because 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. The solution is to augment the page with special high-speed memkory 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 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? 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 a simple main memory access.
What would
the slowdown be if the hit ratio was increased to 95 percent?
Access time = .95 x (15 + 120) +
.05 (15 + 240) = 141.00 which represents a slowdown of 17 per cent.
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 .
