Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!gatech!hubcap!ncrcae!ncr-sd!hp-sdd!ucsdhub!sdcsvax!darrell
From: avie@wb1.cs.cmu.edu (Avadis Tevanian)
Newsgroups: comp.os.research
Subject: Re: Life with TLB and no PT
Message-ID: <3072@sdcsvax.UCSD.EDU>
Date: Thu, 30-Apr-87 20:04:00 EDT
Article-I.D.: sdcsvax.3072
Posted: Thu Apr 30 20:04:00 1987
Date-Received: Sun, 3-May-87 03:28:37 EDT
Sender: darrell@sdcsvax.UCSD.EDU
Organization: Carnegie-Mellon University, CS/RI
Lines: 41
Approved: mod-os@sdcsvax.uucp

In article <3027@sdcsvax.UCSD.EDU> stuart@CS.ROCHESTER.EDU (Stuart Friedberg) writes:
>Prodded by something Avie Tevanian of the MACH research group said,
>I have been considering life with a translation lookaside buffer (TLB)
>but without hardware page tables (PT).

As many have pointed out, building hardware with only a TLB is not a
problem.  What I find interesting; however, is that there has been virtually
no discussion of advantages of a non-PT system other than the obvious
simplification of the hardware.  Sure, you delete some hardware and add a
bit of software that emulates what the hardware would have done.

What is more interesting (from my point of view) is the new opportunities
created by a hardware design that frees you from page table maintenance
without suffering performance degradation due to page faults.  That is,
given that we want to make more flexible use of virtual memory (at least we
do in Mach) for shared libraries, mapped files, shared memory, truly spare
addressing, etc..., does a hardware design with only a TLB help?

I think the answer is yes.  Consider, what you really want for the features
I mentioned is essentially an associative memory that maps arbitrary virtual
addresses (tagged by some ID) to physical addresses.  Page table designs, in
general, have the problem that they are, well, tables.  Tables are not an
efficient data representation for highly sparse structures, or even for
somewhat sparse structures (for example, an address space that was
fragmented due to mapping and unmapping many files of varying sizes).  Most
page table designs have tried to solve this problem using multi-level
tree-like tables... but this only complicates the software that must manage
those tables.

As it turns out, it is relatively easy to design high-level data structures
that describe complex address spaces compactly... we have written several
papers about this in the context of the Mach VM system.  However, since
these are fairly high-level data structures, it is not clear that
virtual-to-physical translation based on these structures is appropriate for
hardware.  That's where the TLB comes in.  If your TLB is efficient enough
(high enough hit ratio), it becomes feasible to allow the full-blown page
fault handler to be run at page fault time.  Of course, you can play
arbitrarily complex games to cache translations in addition to those
maintained by the TLB to eliminate some for the full-blown page faults.

	Avie