CSE Roadmap

Core tier · about 5 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: One EAT (20 minutes)

A memory access takes 80 ns, the TLB lookup takes 5 ns, a miss costs one extra table read of 80 ns. The hit ratio is 90%. Find the EAT.

Done when: 0.9 × 85 + 0.1 × 165 = 93 ns.

Hint

A hit costs 5 + 80, a miss 5 + 80 + 80.

Easy 2: TLB reach (20 minutes)

A TLB has 128 entries. Find its reach with 4 KiB pages and with 2 MiB pages.

Done when: 512 KiB and 256 MiB.

Hint

128 × 4 KiB; 128 × 2 MiB.

Easy 3: Miss ratio of a loop (20 minutes)

A loop reads an array of 8-byte values one after another, with 4 KiB pages. What is the miss ratio of the TLB for the array?

Done when: 1 in 512, about 0.2%.

Hint

4,096 / 8 values in each page.

Medium

Medium 1: A table of EATs (45 minutes)

With a 100 ns access, a 10 ns lookup and three table levels, compute the EAT for hit ratios of 99%, 95%, 90% and 70%.

Done when: four values, with the miss time of 410 ns shown: 113, 125, 140 and 200 ns.

Hint

A miss with three levels costs 10 + 3 × 100 + 100 = 410 ns.

Medium 2: Required hit ratio (45 minutes)

With the numbers of Medium 1, find the lowest hit ratio for which the slowdown over a bare 100 ns access stays under 20%.

Done when: a hit ratio of about 0.967 (290 / 300), with the working shown.

Hint

Solve h × 110 + (1 − h) × 410 ≤ 120.

Medium 3: Sequential and random (60 minutes)

Write a program that sums a 256 MiB array in order, and then reads the same array in random order of pages (one read per page). Report the time per access of each.

Done when: two numbers in ns, with a sentence tying the difference to locality.

Hint

Use rand to shuffle the page order, and time only the reads.

Hard

Hard 1: Measure your TLB curve (90 minutes)

Build the pointer chain test. Run it for 4 to 32,768 pages, and plot or tabulate the time per access. Mark the first step.

Done when: a table like section 3, with the number of pages where the first jump occurs.

Hint

Put each pointer at a different offset inside its page, so that cache lines differ.

Hard 2: Cache or TLB? (90 minutes)

Change the test so that all pointers sit in the same 4 KiB page but the chain is still long, and compare with the one-pointer-per-page chain of the same number of cache lines.

Done when: two curves and a statement of how much of the rise comes from the TLB.

Hint

Keep the number of distinct cache lines equal in both tests.

Hard 3: Context switch cost (90 minutes)

Run two processes that each walk a 1 MiB array repeatedly, pinned to the same processor, with a switch forced by a pipe ping-pong. Compare the time per switch with the time when each runs alone.

Done when: a measured cost per switch, and a note on how much might come from TLB and cache refills.

Hint

Use sched_setaffinity to pin both processes to processor 0.