Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!lll-lcc!qantel!hplabs!pyramid!ucat!pesnta!amd!amdcad!amdimage!prls!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.arch
Subject: Re: VERY LARGE main memories: crypt
Message-ID: <1819@mmintl.UUCP>
Date: Thu, 18-Sep-86 17:52:37 EDT
Article-I.D.: mmintl.1819
Posted: Thu Sep 18 17:52:37 1986
Date-Received: Sun, 21-Sep-86 22:06:36 EDT
References: <1276@bu-cs.bu-cs.BU.EDU> <7537@lanl.ARPA>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Organization: Multimate International, E. Hartford, CT
Lines: 32

In article <7537@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>In article <1276@bu-cs.bu-cs.BU.EDU> bzs@bu-cs.BU.EDU (Barry Shein) writes:
>>Am I missing something? What's the huge problem with this hypothetical
>>vadvise(CYCLIC)? Isn't it just MRU (most recently used)?
>The are two thing wrong with this scheme.  1) Suppose that you problem
>fails to fit in main memory by only a few page sizes.  The above scheme
>will cycle each and every page of the whole data structure into memory
>and back out again on every time step.

No it won't.  Only the number of pages which don't fit are read in each
cycle.  (E.g., if there are 103 pages and 100 will fit, 3 are read each
cycle.)  In fact, MRU behaves optimally[1][2] for a purely cyclic access
pattern.  In particular, it has less I/O overhead than setting aside a few
pages at the end to be overlaid.

>The knowledgable programmer,
>however, can overlay just a few pages and therefore cut down on the
>total I/O requirement of the code.

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

[1] Assuming that only demand-loading is used.  As long as I/O can be done
simultaneously with computation, lookahead will improve performance.  Even
with lookahead, MRU is still optimal for the selection of the next page to
be swapped out.

[2] This also assumes that all accesses to external store are equivalent.
If the complete data set does not fit on one cylinder of the disk, this
assumption will likely be violated, at least if no other program is executing
on the same machine.  The optimal solution in the general case is not
obvious.