Path: utzoo!attcan!uunet!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!think!bbn!bbn.com!lkaplan
From: lkaplan@bbn.com (Larry Kaplan)
Newsgroups: comp.arch
Subject: Re: Inverted Page Tables
Summary: Butterfly implementation
Message-ID: <52903@bbn.COM>
Date: 2 Mar 90 16:16:21 GMT
References: <37877@cornell.UUCP>
Sender: news@bbn.COM
Reply-To: lkaplan@BBN.COM (Larry Kaplan)
Distribution: comp
Organization: Bolt Beranek and Newman Inc., Cambridge MA
Lines: 56

In article <37877@cornell.UUCP> huff@cs.cornell.edu (Richard Huff) writes:
>Someone suggested that Mach handles large sparse address spaces
>efficiently.  But Mach's architecture independent pmap module simply
>implements an inverted page table in software; although their IPT's are
>on a per process basis, rather than using a single IPT for the entire
>machine.  So I still see IPT's as the only way to manage huge virtual
>address spaces.

I'm not sure the efficiency refers to the data structures you mention.
The VM system uses a doubly linked-list of structures to define regions
of user (and kernel) virtual address space.  These regions need not be 
contiguous.  This is probably the efficiency referred to.  BBN has rewritten 
the Mach VM system from scratch for the TC2000 (Butterfly II) and has 
enhanced this data structure by also storing it as a balanced binary tree.  
This speeds lookups into the virtual memory map.

>Now here's an interesting research problem:  What is the most efficient
>way to manage large virtual address spaces on NUMA (non uniform memory
>access) shared memory MIMD machines?  ...
>
>What is currently being done, or being proposed, for such large NUMA
>MIMD machines?  How does the Butterfly II, Ultracomputer, or RP3 do
>virtual to physical address translation?  Do they employ a separate
>virtual address space per process?  Is it 32-bits, or larger?

Again, for the adding of mappings of virtual addresses to physical memory,
I believe the Mach style is fine.  The problem comes when removing or 
reclaiming a physical page for other use.  This is where the inverted
page tables come into play as you must notify all processes which map
the page that their mapping is no longer valid.  For each physical page in
the system, there is a software page descriptor (residing on the same node as
the physical page) that contains a list of all {process, virtual address} pairs
that map the page.  This list can grow to be fairly long and in that sense
is not efficiently scalable.  Note however, that the invalidation required
is fairly cheap except for the possible need for a TLB shoot to a remote node.
BBN's TLB shoot code uses a clock based algorithm that eliminates the need
for most of these TLB shoots.

The TC2000 does indeed have a separate 32 bit virtual address space per 
process as, I believe, do most UNIX VM implementations.

For more information about BBN's new VM and pmap implementations, see the paper
"Highly Parallel Virtual Memory Management in Large-Scale Shared Memory
Multiprocessors" by D. Barach et. al.  This paper has been submitted to
the ICPP 1990.

>
>Richard Huff
>huff@svax.cs.cornell.edu

#include <std_disclaimer>
_______________________________________________________________________________
				 ____ \ / ____
Laurence S. Kaplan		|    \ 0 /    |		BBN Advanced Computers
lkaplan@bbn.com			 \____|||____/		10 Fawcett St.
(617) 873-2431			  /__/ | \__\		Cambridge, MA  02238