Compile-time virtual memory

Idea: Modify the GNU C compiler to handle address translation in software. Then look at ways of optimising this overhead out.

Motivation: Address translation is an extremely complicated part of CPU design. It is a common source of errors, and it has a pernicious effect on performance.

The performance impact comes firstly from the time taken to look every address up in a page table (TLB - translation lookaside buffer). This is normally small and often zero since it can be done in parallel with access to the primary cache.

However there are other performance penalties. For example, when a page fault occurs, a conventional operating system traps to a generic fault handler and saves the faulting program's state. If we handle this in software, the compiler can generate optimised code for the specific point where the fault occurs. There are also penalties because of caches.

Another interesting aspect of this is user-specified interrupt handlers. In a conventional OS this is very hard indeed to do fast: you need to switch into the user's address space in the handler, and then you run the risk of getting a page fault. With software address translation both these problems disappear.

Finally, a system with software-managed virtual memory can give the user program complete control over its memory resource allocation. For example, it can choose appropriate page sizes (not necessarily constant), appropriate page table data structures, and it can schedule its work to use RAM-resident data while waiting for a disk access to be satisfied.

The problems are

Security: does this mean the compiler has to be trusted? Well; if so, maybe that's not so bad after all, if it gives us important performance advantages.
Performance: although I have indicated ways in which performance might be improved, it would be very slow if we had to to the TLB lookup in software for every memory reference. However, things need not be this bad. For example, we should be able to do a lot with loops, moving repeated checks for accesses to the same page to the start of the loop. Similarly with stacks, and fields of a record whose base address is OK.

The job: Modify the GNU C compiler so that every time a pointer is used, address translation is done first (this has already been done in an earlier project, see below). Establish a suite of benchmark programs, and evaluate the performance of the resulting code. Go back and look at ways of improving this performance by improving gcc's optimisation of your code. Study applications.

Reading:

Richard Jones project report (here).

Various research papers, e.g. Application-level virtual memory.

Equipment: Unix workstation.

Recommended tools: Unix, C, GNU C compiler.

Suitability: This is a research-level project with enormous potential scope. The basic prerequisites are 1) insight into performance, architecture and applications issues, 2) the practical ability to get complicated software to do what you want, and the imagination and clarity of thought to design good experiments.