Standard page table:
address space is 61 bits in byte
number of pages = 2^61 / 1K = 2^51;
Page Table Size = 2^51 * (PTE size) = 2^52 bytes
Inverted page table:
Total frames = 64k / 1K = 64;
Page Table Size = 64* (PTE size) = 128 bytes
Inverted: contains one entry per physical frame as opposed to one for each virtual page as in the case of standard page tables. This makes it much smaller compared to standard page tables. However, the lookup time can be very high, because the whole table has to be linearly searched typically.
Hashed: maintains a hash-table of virtual-to-physical translations. Has the advantage of inverted tables (smaller size compared to standard tables) while the lookup is much faster compared to inverted tables: typically 1 or 2 accesses.
2 memory accesses: page lookup followed by actual access => 2*200ns = 400ns
75% * TLB hit-time + 25% * TLB miss-time = 75% * 200ns + 25% * 400ns = 250ns
Overhead on Cache-misses = 14cycles
Overhead on TLB-miss = 99cycles
# cache misses = 1000 * 20% * 10% = 20
# TLB misses = 1000 * 20% * 5% = 10
Total cycles = 1000cycles + (overhead due to cache misses) + (overhead due to TLB misses)
= 1000 + (20 * 14) + (10 * 99) = 1000 + 280 + 990 = 2270 cycles
Alpha: a standard page table with software-managed TLB.
PowerPC: uses inverted and hashed page tables with hardware-managed TLB.
Alpha: The TLB is managed by the OS directly through PALcode. PTEs are loaded from hardware registers into the TLB. The not-most-recently-used replacement policy is used.
PowerPC : A paged segmentation system is used. The hardware loads an entire PTE group into the TLB.
Alpha: The OS supports an 8Kbytes page size and 64-bit addressing.
PowerPC: A 52-bit segmented virtual address space for 32-bit implementations of the architecture or an 80-bit segmented virtual address space for 64-bit implementations of the architecture.
Yes: If an address can never be accessed or if the page is not in physical memory, it couldn’t be in either TLB or the cache.
Yes: If the size of cache is larger than the total size of pages that have translation entries in the TLB.
The case when a TLB miss and cache hit happens at the same time would be one, but it is typically avoided.
Alpha: The PAL loads the PTEs from a hardware register into the TLB.
PowerPC: The hardware loads an entire PTE group and performs a linear search for a matching virtual address. If the PTE is not found in the first PTE group, the hardware performs a second lookup to a different PTE group, based on a secondary hash.