This page does not represent the most current semester of this course; it is present merely as an archive.

Implement a TLB wrapper around the page table interface from previous assignments. Note you will not need to implement a page table for this assignment; you’ll merely use its API, as defined in mlpt.h

1 Task

Implement a 4-way set-associative 16-set translation lookaside buffer with a single VPN → PA mapping per block1. In addition to its block, each cache line should also store

  • a valid bit
  • necessary bookkeeping to implement LRU replacement within the set

You should design your own data structures, etc, to make this work properly.

The public API should be the following tlb.h

Note that we do not have a tlb_allocate. This is by design: allocation is performed by software (a part of the operating system, accessed through a system call) and not by the hardware.

You should submit tlb.h, and other .h and .c files you create, and a Makefile that depends on mlpt.a for its implementation of translate and produces, as its default target, libtlb.a with a definition of the three functions listed above. And example target might look like

2 Separation of Concerns

Your TLB code must not depend on any implementation detail of your page tables. It may use translate, plus the #defines in config.h, and should append the page offset to the PPN it finds cached itself, but should not invoke any code or use any variables defined in your implementations of PA02 or PA03 besides translate, LEVELS, and POBITS. Each call to translate must be to a page-beginning address, and that only if it is not in the cache.

If POBITS is 12 and tlb_translate is invoke with addresses 0x12345, 0x12468, and 0x13579 in that order,

  • tlb_translate(0x12345) should invoke translate(0x12000),
  • tlb_translate(0x12468) should not invoke translate at all (it’s a cache hit), and
  • tlb_translate(0x13579) should invoke translate(0x13000)

3 Tips

You can test this code without a working implementation of multi-level page tables, possibly even more easily than you can with a working MLPT, by creating a stub: a special implementation of translate that returns specific values designed to let you test the tlb_ functions. Even something as simple as

gives enough behavior to test most TLB behaviors; adding some logging code to the stub can help make sure that translate is only called as needed.

TLBs typically do not have a CPU-write-to-TLB functionality, so they do not need to be write-through or write-back.

4 Examples

If you stub translate(va) as return va < 0x1234000 ? va + 0x20000 : -1; then the following code should work


  1. You may hard-code 4 and 16 in your implementation, though a design that has these in #defines may actually help you keep your code organized.