TLB and effective access time

Why it exists

With the page table in main memory, every memory reference needs two accesses: one to read the page-table entry, one to read the data. That halves the speed of the machine. The cure is the same as for slow memory generally: cache the recent results. The translation lookaside buffer (TLB) is a small, very fast memory that holds recently used (page number, frame number) pairs. Most references find their translation there and cost almost nothing extra. GATE asks you, nearly every year, to compute the effective (average) memory access time from the hit ratio and the access times, with a TLB, with a multilevel table and sometimes with page faults.

Prerequisites

You need the page table and the translation from paging; the idea of a cache with a hit ratio comes from the memory hierarchy.

Precise definitions

TLB. A small associative (content-addressable) memory: it compares the page number of the address with the page numbers of all its entries at once, and on a match returns the frame number. Typical sizes are 32 to 1024 entries. Each entry holds the page number, the frame number and protection bits.

Translation with a TLB.

1. The page number $p$ is presented to the TLB.
2. TLB hit: the frame number is returned at once; the physical address is formed. Cost: the TLB lookup plus one memory access (the data).
3. TLB miss: the page table in memory is consulted (one memory access for a single-level table, $k$ for a $k$-level table); the translation is then copied into the TLB (replacing an entry, often the least recently used, if the TLB is full), and the data is accessed.

Hit ratio $h$. The fraction of references whose translation is found in the TLB. A hit ratio of 98% means 2% of references take the slow path.

Effective access time (EAT). Let $t$ be the TLB access time, $m$ the memory access time and $k$ the number of page-table levels (1 for a single table). With the TLB searched first and the page table consulted only on a miss:

$\text{EAT} = h\,(t + m) + (1 - h)\,\bigl(t + k\,m + m\bigr) = h\,(t + m) + (1 - h)\,\bigl(t + (k + 1)\,m\bigr).$

A hit costs $t + m$; a miss costs the failed TLB lookup $t$, the $k$ table accesses and the data access $m$. Special cases:

• TLB time negligible ($t = 0$) and single level: $\text{EAT} = h\,m + (1 - h)\,2m = m\,(2 - h)$.
• Without a TLB: $\text{EAT} = (k + 1)\,m$, so $2m$ for a single table.
• Perfect hit ratio $h = 1$: $t + m$.

If a question searches the TLB and the page table in parallel, the TLB lookup overlaps the start of the table walk, so a miss costs about $(k + 1)\,m$ instead of $t + (k + 1)\,m$; read the wording. The default in textbooks, and in the formula above, is sequential.

With page faults too. If a fraction $p$ of references (after the translation) faults, with service time $T_f$:

$\text{EAT} = (1 - p)\,\text{EAT}_{translation + access} + p\,T_f,$

where the first term is the time computed above. (Some questions write the page-table and fault parts together in one formula; derive it from the cases.)

TLB reach. The memory covered by the TLB: $\text{entries} \times \text{page size}$. With 64 entries and 4 KB pages the reach is 256 KB; the hit ratio is high if the working set of the program fits in the reach. Larger pages (or several page sizes) enlarge the reach.

Address-space identifiers and flushing. The TLB's entries belong to one process's page table. On a context switch, either the TLB is flushed (all entries invalidated; the new process starts with all misses), or each entry carries an address-space identifier (ASID) (or process id) and an entry is used only if its ASID matches the running process, so entries can survive a context switch (context switch). When a page table entry changes (a page is replaced), the matching TLB entry must be invalidated.

Who handles a miss. In most architectures the hardware walks the page table on a miss; in others (MIPS, SPARC) the miss traps to the operating system, which loads the entry (a software-managed TLB).

How it works

The animation sends ten references through a TLB of four entries (replacement: least recently used). The TLB table (top left) shows its current entries; the page table is below it. A hit costs $10 + 100 = 110$ ns. A miss costs $10 + 100 + 100 = 210$ ns: the TLB lookup, the page-table access (the page-table row is highlighted) and the data access, after which the entry is copied into the TLB. With this stream five of the ten references hit, so the hit ratio is 0.5 and the average time is exactly the formula's: $0.5 \times 110 + 0.5 \times 210 = 160$ ns.

Worked examples

#include <stdio.h>
 
#define SIZE 4
 
int main(void) {
    int stream[10] = {1, 2, 1, 1, 3, 2, 2, 4, 1, 5};
    int tlb[SIZE], used[SIZE], count = 0, hits = 0;
    double total = 0, t_tlb = 10, t_mem = 100;
    for (int t = 0; t < 10; t++) {
        int slot = -1;
        for (int i = 0; i < count; i++) if (tlb[i] == stream[t]) slot = i;
        if (slot >= 0) { hits++; total += t_tlb + t_mem; }
        else {
            total += t_tlb + 2 * t_mem;
            if (count < SIZE) slot = count++;
            else { slot = 0; for (int i = 1; i < SIZE; i++) if (used[i] < used[slot]) slot = i; }
            tlb[slot] = stream[t];
        }
        used[slot] = t;
    }
    double h = hits / 10.0;
    printf("TLB of %d entries: %d hits in 10 references, h = %.1f, average time %.1f ns\n", SIZE, hits, h, total / 10);
    printf("formula h(t + m) + (1 - h)(t + 2m) = %.1f ns\n", h * (t_tlb + t_mem) + (1 - h) * (t_tlb + 2 * t_mem));
    /* effective access time for several hit ratios: one-level and two-level page tables, TLB 10 ns, memory 100 ns */
    for (double hr = 0.5; hr <= 1.0001; hr += 0.1) {
        double one = hr * (t_tlb + t_mem) + (1 - hr) * (t_tlb + 2 * t_mem);
        double two = hr * (t_tlb + t_mem) + (1 - hr) * (t_tlb + 3 * t_mem);
        printf("h = %.1f: one-level %.1f ns, two-level %.1f ns\n", hr, one, two);
    }
    printf("TLB reach with 64 entries and 4 KB pages: %d KB\n", 64 * 4);
    return 0;
}

TLB of 4 entries: 5 hits in 10 references, h = 0.5, average time 160.0 ns
formula h(t + m) + (1 - h)(t + 2m) = 160.0 ns
h = 0.5: one-level 160.0 ns, two-level 210.0 ns
h = 0.6: one-level 150.0 ns, two-level 190.0 ns
h = 0.7: one-level 140.0 ns, two-level 170.0 ns
h = 0.8: one-level 130.0 ns, two-level 150.0 ns
h = 0.9: one-level 120.0 ns, two-level 130.0 ns
h = 1.0: one-level 110.0 ns, two-level 110.0 ns
TLB reach with 64 entries and 4 KB pages: 256 KB

Cheat box

Traps and GATE patterns

Connections

The TLB fixes the doubled cost of paging, and matters even more for the multilevel tables of page table structures, where a miss costs several accesses. It is a cache like the ones in cache performance, with the same hit-ratio arithmetic. It interacts with context switching (flush or ASID) and with the page faults of virtual memory.

PYQs

A system has a Translation Lookaside Buffer
(TLB) that has a reach of 1 MB. TLB reach is
defined as the total amount of physical memory that
can be accessed through the TLB entries.

The paging system uses pages of size 4 KB. The
virtual address space is 64 GB and physical address
space is 1 GB.

If each TLB entry stores:
●
a 4-bit process id
●
page number
●
frame number
●
a 2-bit control field

then the size of the TLB (in bytes) is ______.

Note:
1K = 210, 1M = 220, 1G = 230.

Consider a system that has a cache memory unit and
a memory management unit (MMU). The address
input to the cache memory is a physical address. The
MMU has a Translation Lookaside Buffer (TLB).
Assume that when a page is evicted from main
memory, the corresponding blocks in the cache are
marked invalid.

For a given memory reference, which of the following
sequences of events can NEVER happen?

Which one of the following statements is FALSE?

Consider a paging system that uses a 1-level page
table residing in main memory and a TLB for
address translation. Each main memory access
takes 100 ns and TLB lookup takes 20 ns. Each
page transfer to/from the disk takes 5000 ns.
Assume that the TLB hit ratio is 95%, page fault
rate is 10%. Assume that for 20% of the total page
faults, a dirty page has to be written back to disk
before the required page is read in from disk. TLB
update time is negligible. The average memory
access time in ns (round off to 1 decimal place) is
______.

Assume that in a certain computer, the virtual
addresses are 64 bits long and the physical
addresses are 48 bits long. The memory is word
addressable. The page size is 8 kB and the word
size is 4 bytes. The Translation Look-aside Buffer
(TLB) in the address translation path has 128 valid
entries. At most how many distinct virtual
addresses can be translated without any TLB miss?

Consider a process executing on an operating system
that uses demand paging. The average time for a
memory access in the system is M units if the
corresponding memory page is available in memory
and D units if the memory access causes a page fault.
It has been experimentally measured that the average
time taken for a memory access in the process is X
units.

Which one of the following is the correct expression
for the page fault rate experienced by the process?

A computer system implements a 40-bit virtual
address, page size of 8 kilobytes, and a 128-entry
translation look-aside buffer (TLB organized into 32
sets each having four ways. Assume that the TLB tag
does not store any process id. The minimum length of
the TLB tag in bits is _________.

Consider a paging hardware with a TLB. Assume
that the entire page table and all the pages are in the
physical memory. It takes 10 ms to search the TLB
and 80 ms to access the physical memory. If the
TLB hit ratio is 0.6, the effective memory access
time (in milliseconds) is ______

Let the page fault service time to 10 ms in a
computer with average memory access time being
20 ns. If one page fault is generated for every 106
memory accesses, what is the effective access time
for the memory?

A CPU generates 32-bit virtual addresses. The page
size is 4 KB. The processor has a translation look-
aside buffer (TLB) which can hold a total of 128 page
table entries and is 4-way set associative. The
minimum size of the TLB tag is

Self-check

Revision card

References