Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!qantel!lll-lcc!lll-crg!nike!ll-xn!adelie!axiom!linus!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.arch
Subject: Re: VERY LARGE main memories: crypt
Message-ID: <1834@mmintl.UUCP>
Date: Thu, 25-Sep-86 14:40:38 EDT
Article-I.D.: mmintl.1834
Posted: Thu Sep 25 14:40:38 1986
Date-Received: Tue, 30-Sep-86 13:46:52 EDT
References: <1276@bu-cs.bu-cs.BU.EDU> <7537@lanl.ARPA> <1819@mmintl.UUCP> <7847@lanl.ARPA>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Organization: Multimate International, E. Hartford, CT
Lines: 69

In article <7847@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>The MRU algorithm (as far as I can see) does the following:
>    Assume M pages of data are to be used cyclically and only N pages
>    will fit.  Initially, the first page is loaded and the code begins
>    executing.  At the end of page 1, the next page is loaded, and so
>    on for N pages.  Now you have a choice to make, do you flush page
>    1 or page N to make room for N+1.  The MRU algorithm presumably
>    flushes page N (the most recently used).  And so you continue up
>    to page M.  Now on the second cycle through the data, the first N-
>    1 pages are already there, so no page fault occurs until page N is
>    needed.  Then a page fault occurs for every page until page M.
>
>This doesn't seem optimal to me.  Or did I get the algorithm wrong?
>In this case, even LRU (least recently used) seems more efficient since
>some, at least, of the I/O is done asynchronously.

As I noted in my footnote, it is only optimal assuming no overlap of I/O and
processing.  This will be true for any demand-driven paging scheme.  In
particular, an LRU scheme will differ from this in having a page fault for
*every* page reference (after the first N); there will be no asynchronous
I/O.

>The most efficient
>algorithm would be to load N pages at the start, when done with the first
>page flush it out and load the N+1st page - and so on: always flushing the
>most recently used and loading the most distantly required.  This makes
>all the I/O as asynchronous as possible.

Right; and this is still a MRU algorithm in the sense that the page chosen
to be flushed is the most recently used.  It is not a demand-driven paging
algorithm.

>What if some other data structure (like an equation of state, for
>example) is being referenced following a random pattern of use - at the
>same time that the cyclically used data is being traversed: how do
>I advise the VM system that some of the pages should be referenced
>MRU and some should be LRU?

This is indeed the fatal flaw in this scheme -- it works fairly well for
cyclic access, but it is terrible if *any* non-cyclic access is being
performed.  It will similarly perform quite badly for certain nearly cyclic
access patterns; e.g.,

for j = 1 to M;
   for i = 1 to j;
      access page i;

Since *very* few applications have a *purely* cyclic access pattern, an MRU
option is es essentially worthless.

>I can solve all the above problems explicitly if I have control over
>memory contents.  I can't off hand see any solution that a VM system
>could take advantage of.  A lot of work has been done in the
>optimization of memory management for scientific codes.  Many of the
>techniques that have resulted are not well suited to any demand driven
>context but, instead, rely upon knowledge of the data use patterns of
>specific algorithms.

I believe that most, if not all, of these *can* be implemented in a VM
system which has a "load this page for later reference" primitive, albeit
with some performance loss.  Whether this is worthwhile depends on the
overall usage pattern for the machine in question.  I don't doubt that there
are many instances where a non-virtual memory machine is the correct choice.
Such cases may in fact be in the process of becoming more common, as
personal computers/workstations become a viable alternative for less
demanding tasks.

Frank Adams                           ihnp4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108