🚀 go-pugleaf

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)?
>...
>most recently used page is the one that will be used again the
>furthest in the future and the least recently used is the one that
>will be used soon. Thus, they do hand to hand combat with LRU
>algorithms. Therefore, it seems they want LRU for the text space
>(being as there's no particular reason to believe the text is any
>different than other programs, locality of reference applies) and MRU
>for their (impure) data space (probably LRU for the rest.) ...

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.  The knowledgable programmer,
however, can overlay just a few pages and therefore cut down on the
total I/O requirement of the code.  2) As with any built-in VM system,
ALL references to memory must be decoded for page address - which slows
down the memory interface.  This means that all memory traffic is slower
that it would have been without the VM system - even for those codes (or
parts of codes) which don't require the virtual memory.

J. Giles
Los Alamos

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)?
>>...
>>most recently used page is the one that will be used again the
>>furthest in the future and the least recently used is the one that
>>will be used soon. Thus, they do hand to hand combat with LRU
>>algorithms. Therefore, it seems they want LRU for the text space
>>(being as there's no particular reason to believe the text is any
>>different than other programs, locality of reference applies) and MRU
>>for their (impure) data space (probably LRU for the rest.) ...

Has anybody tried MAU (Most Average Use) approaches?

>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.  The knowledgable programmer,
>however, can overlay just a few pages and therefore cut down on the
>total I/O requirement of the code.  2) As with any built-in VM system,
>ALL references to memory must be decoded for page address - which slows
>down the memory interface.  This means that all memory traffic is slower
>that it would have been without the VM system - even for those codes (or
>parts of codes) which don't require the virtual memory.
>
>J. Giles
>Los Alamos

Question, is it a requirement that the data and/or text structure be a loop? 
If there are too many in-line macro expansions, "almost the same" code,
or anything that can be put into a tree, MAU might be a solution.

This should ideally be combined with look-ahead pre-fetch.  For example,
on the code side,

	main:		main:
	do a		call a
	if cond		if cond
	macro b		call b
	macro x
	else		else
	macro c		call c
	macrox
	endif		endif 
	macro x		call x
		
			b:
			call j
			call x
			return
			c:
			call k
			call x

Under MAU, main and x would be in core, the prefetch could pick up the first
few instructions of b and c, could be pre-fetched, and only j and k would
cause slowdown.

In the data case:

	struct btree		struct hier
	{			{
	   key			   struct keyrange {keylow,keyhigh,*hierp }[N]
	   btree_less*		   hier_less*
	   btree_greater*	   hier_greater*
	}			}

allows several keys to be examined before looking at the next block.
this also eliminates the need to look at as many blocks.

other examples such as circular queues can "rubber band" into multiple
queues, each a convenient size, with the middle elements being flushed
until needed.

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.

In article <1819@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes:
>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 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.  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.

If M-N is small compared to N, you could reduce the I/O requirement by
loading N-M pages, skipping every M-Nth one, and then after every M-N
pages, flush the most recent and load the most distantly needed (as
before except that only M-N pages are being swapped in and out).

There are other techniques (that I've mentioned in previous
submissions) that reduce the I/O load or increase the amount of
asynchronous I/O in many cases.  Most of these techniques would be
difficult to provide in a general purpose VM system.

You might argue that MRU should be modified to include the technique
I just mentioned.  But how does a demand driven system know what the value
of M is?  How does it know that M remains unchanged from one cycle to the
next?  What is 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?

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.

J. Giles
Los Alamos

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

In article <7847@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>The MRU [Most Recently Used] 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?

Yes, in two important ways: pageouts occur not when free pages are
exhausted, but when free pages are low; and pageins are performed
in advance if you have marked your process cyclic.  Let us assume
that N pages will fit, but that the OS wants to keep F pages free
and that it operates in `clusters' of C pages.  Initially, the
first C pages are loaded, then the next, and so on for N-F pages.
At this point pages N-F-2C through N-F-C+1 are flushed, with N-F
through N-F+C-1 being paged in.  The last few (V) pages are not
marked valid.  When the process touches page N-F+C-V, those V pages
are marked valid and the OS begins bringing in pages N-F+C through
N-F+2C-1, simultaneously paging out pages N-F-C through N-F-1.

To put it another way, the OS will try to keep a range of 2C pages
avialable.  If C is large enough, the only price is for the extra
faults that the O/S needs to discover that you are indeed about to
use the next group of pages.  (This is not necessarily negligible.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1516)
UUCP:	seismo!umcp-cs!chris
CSNet:	chris@umcp-cs		ARPA:	chris@mimsy.umd.edu