Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!mcsun!ukc!dcl-cs!aber-cs!odin!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.arch Subject: Re: Paging page tables Message-ID: Date: 2 Jul 90 21:41:11 GMT References: <3300142@m.cs.uiuc.edu> <4137@taux01.nsc.com> <1990Jun29.213236.4888@cbnewsh.att.com> <3341@goanna.cs.rmit.oz.au> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 51 In-reply-to: ok@goanna.cs.rmit.oz.au's message of 30 Jun 90 06:36:01 GMT In article <3341@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: One really beautiful idea is to stand the whole thing on its head and have your page tables map from *physical* pages to *virtual*, so that the space taken up by page tables is a fixed fraction of the size of *physical* memory. This is the technique used on the IBM RT PC. And on virtually all the Manchester University machines for the last few dozen years (major exception being the MU5). (1) Would someone who really understands the technique care to post a short description? Each physical page contains the segments and page number of the virtual page mapped to it. When a translation is needed, all physical page are looked up to see which one contains the given virtual page. The lookup can be sped up in various ways; firstly by caching a few translations, secondly by using an hash index or parallel search hardware. It is fairly obvious from this description that shared memory is not easy with a reverse map MMU, but it can be done. (2) When I read the RT PC bumf, I was _sure_ that I had seen the technique described before, but I couldn't and still can't remember where. Does anyone know where the "inverted page tables" idea was first published/used? The very first virtual memory machine, the Manchester Atlas (MU4), used inverted page tables. A very good description of their latest scheme, the MU6 MMU, is contained in a thesis available on request from them. (3) IBM hold the patent. Is any other manufacturer known to have been granted licence to use the technique? IBM has invented virtual memory, IBM has patented reverse map MMUs, what is good for IBM is good for IBM :-(. This subject has already been discussed; I have had in a drawer a paper on a very simple reverse map MMU design (two ROMs and one RAM) for many years now, and when I get the nerve to publish it... Well, after all IBM never sued Manchester University for having dared copy their inventions and patents a few years early :-). In another thread the abuses of the patent system are discussed. Well, every time I think of IBM and virtual memory... -- Piercarlo "Peter" Grandi | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk