Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rochester!ritcv!cci632!rb
From: rb@cci632.UUCP (Rex Ballard)
Newsgroups: net.arch
Subject: Re: VERY LARGE main memories: crypt
Message-ID: <367@cci632.UUCP>
Date: Wed, 17-Sep-86 22:30:21 EDT
Article-I.D.: cci632.367
Posted: Wed Sep 17 22:30:21 1986
Date-Received: Fri, 19-Sep-86 22:26:22 EDT
References: <1276@bu-cs.bu-cs.BU.EDU> <7537@lanl.ARPA>
Reply-To: rb@ccird1.UUCP (Rex Ballard)
Organization: CCI, Rochester Development, Rochester, NY
Lines: 75
Summary: LRU,MRU,MAU,Lookahead.

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.