🚀 go-pugleaf

A similar discussion came up a few months ago, in the context of
"how much memory is it reasonable to try to hang off my type X
machine?"  I expressed some confusion over conclusions drawn by
someone else (it may have been Barry Shein, whose article I am
replying to), who maintained steadfastly that there was a limit
beyond which it was not useful to go.  The argument really only
applies to machines with virtual memory, and it goes like this:

Your memory is organized in pages which are mapped from various
process's virtual spaces into the physical memory addressing.  It
takes a certain number of MM table entries to map a certain amount
of memory (considering a single VM architecture).  You want to
improve performance by reducing paging; it seems logical to do
this by increasing main memory.

Now.  By adding more main memory, you *do* decrease paging, which
is obviously a good thing.  However, you also make memory mapping
more time-consuming (more page table entries to maintain), so
there's a tradeoff here.  You might be able to expand the memory
to, say, 16M without taking any hits - the upper limit depends,
of course, on your VM archi- tecture.  Beyond this limit, the
page table has to be expanded, and maintaining it becomes more
complicated.  Eventually you reach a point where the time saved
by not paging is less than the extra time spent maintaining the
mapping table.  This is the point where you should just give up
trying to speed up your system by adding more memory.

Is this right?  It's sort of off the top of my head, and I may
have gotten some of the details wrong (what details, I hear you
ask?) but it seems to convey the gist of the argument...


Phil Kos			  ...!decvax!decuac
The Johns Hopkins Hospital                         > !aplcen!osiris!phil
Baltimore, MD			...!allegra!umcp-cs

"In the end there's still that song,
Comes crying like the wind
Down every lonely street that's ever been." - Robert Hunter

> 	Barry Shein, Boston University writes
> ... consider:
> 
> A one MIP machine zeroing memory in a loop:
> 
> 		CLRL	R1
> 	LOOP:
> 		CLRL	(R1)+
> 		CMPL	R1,HIMEM
> 		BNE	LOOP
> 
> would (theoretical machine) take 3 * (1G/1M) or 3000 seconds or
> a little less than one hour to complete. It's hard to believe
> such a machine could make -effective- use of that much memory.

That calculation left out the word size (or were you talking about 1GW
versus 1Gb?)  Thus, for a 32 bit 1 MIPS machine, clearing 1 Gb of memory
would take (3 / 1M) * (1  Gb / 4) = 750 seconds or 12.5 minutes.

Of course, for general purpose computation, Barry's point is correct,
you can't use huge amounts of memory.

However, data base machines benefit greatly from the reduced overhead
if all data is available in memory, even if they don't touch much of it
at any time.

Also, our Convex C-1, when doing vector operations, can touch 8 bytes
every 100 ns, so to zero a 1Gb space  takes (1 Gb / 8) /10M = 12.5 seconds.

Cheers,
Rich Hammond	Bellcore

In article <1130@bu-cs.bu-cs.BU.EDU>, bzs@bu-cs.BU.EDU (Barry Shein) writes:
> The point is it is not clear that increasing memories unbounded
> produces unbounded performance gains, in fact, it almost certainly
> doesn't.

As a matter of interest, studies we did some time ago with IBM MVS
indicated that performance reaches a maximum and then begins to
deteriorate slowly. Not a general result, of course, but food for
thought.  BTW, we offer up to 512MB of mainstore on our systems.

> 
> You need a CPU (or more than one) to do something with all this
> wonderful stuff you have in memory.
> 
> Of course, assuming the memory were free and reasonably random behavior
> I agree that a huge memory would have some value to a database application
> that filled the memory, but I doubt it would be a reasonable thing to
> do unless memory prices dropped drastically. You'd probably be better
> off putting your money into the processor (the context of the argument
> seemed to imply smaller processors, obviously Cray is already up against
> that limit.)
> 

But what do you do when you can't put any more money into the processor?
Not only Cray is up against that limit.
-- 
Mike Taylor                        ...!{ihnp4,hplabs,amd,sun}!amdahl!mat

[ This may not reflect my opinion, let alone anyone else's.  ]

With regards to Shein's law (zeroing memory in N seconds):

I heard DEC's VP of research, C. Gordon Bell while at Caltech in 1976. As part
of his guest lecture (discussing PDP11 architecture), he commented that a
memory which cycled in 1uS gave rise to 1 Meg as a reasonable upper bound for
storage, with memory size and access time trading off in direct proportion
for other values. Ivan Sutherland (CS chairman at the time) then proposed
that a maxim for good design was "being able to initialize memory in one
second", and Bell agreed. This is really a bandwidth measure, as the memory
is presumably filled via DMA, if it is to run at its full bandwidth.  It is
useful as a measure of CPU speed assuming that the CPU cycles at rates
comparable to the main memory cycle time (which may not be true with
architectures with huge memories a/o multiprocessors). This could account for
a factor of N on newer designs. 

    /Alan Paeth, University of Waterloo

	One thing that no one has mentioned so far  that you could do
	with very large memories is table lookups. Sure everyone knows
	that a table lookup is faster than than a calculated solution
	almost all the time, but how many people would it occur to to use
	it if the resulting table would be several hundred megabytes
	or even larger? It seems to me that this could be significant
	in some applications, like weather forcasting.
-- 
     Joel Upchurch @ CONCURRENT Computer Corporation (A Perkin-Elmer Company)
     Southern Development Center
     2486 Sand Lake Road/ Orlando, Florida 32809/ (305)850-1031
     {decvax!ucf-cs, ihnp4!pesnta, vax135!petsd, akgua!codas}!peora!joel

In article <2289@peora.UUCP> joel@peora.UUCP (Joel Upchurch) writes:
> 	One thing that no one has mentioned so far  that you could do
> 	with very large memories is table lookups.

	OK, let's talk bizarre (1/2 :-)).  Imagine the stateword of a
process as all the bits in that process's memory strung end to end.  If you
take this as a memory address, you could implement your CPU as a simple
lookup table; for each possible state there is only one possible next state
that a process can get to.  All you have to do is do a simple table lookup
to find the next state.

	Of course, you need a mighty big memory to build the lookup table
(not to mention the non-trivial amount of CPU time to calculate what values
go where in the table).  How much memory?  Well, I just did a size on
/bin/* (11/750 running 4.2 BSD).  Running the results through colex to get
the decimal total and desc to get descriptive statistics (both from Gary
Perlman's very nice UNIX|STAT package) I get (with a sample size of 60;
this excludes the shell scripts /bin/true and /bin/false):

------------------------------------------------------------
        Mean      Median    Midpoint   Geometric    Harmonic
   35343.000   27394.000   57622.000   32294.059   30172.889
------------------------------------------------------------
          SD   Quart Dev       Range     SE mean
   17635.600    7553.000   77052.000    2276.746
------------------------------------------------------------
     Minimum  Quartile 1  Quartile 2  Quartile 3     Maximum
   19096.000   24372.000   27394.000   39478.000   96148.000
------------------------------------------------------------

	The smallest program was /bin/echo (20k to echo argv!?); the
largest was /bin/as at 96k.  So, assuming most processes will fit into 100
kbytes, that means you need a LUT with an 800k bit long address.  Talk
about BFM's!  As I think I've mentioned before, it is believed that there
are approximately 2^200 electrons in the universe.  Since it is unlikely
that anybody would want to reference more things than there are electrons
in the universe, 200 bits seems like a good upper bound for the length of a
memory address.

-- 
Roy Smith, {allegra,philabs}!phri!roy
System Administrator, Public Health Research Institute
455 First Avenue, New York, NY 10016

[Net.arch has been discussing applications of very large main memories,
on the close order of a gigabyte.]

In article <2289@peora.UUCP>, joel@peora.UUCP (Joel Upchurch) writes:
> 	One thing that no one has mentioned so far  that you could do
> 	with very large memories is table lookups.

This is certainly a useful technique in cryptography.  Someone wrote
a paper on how to break DES that involved writing many megabytes of stuff
on magtape so you could get it back quickly later when breaking an
encrypted message.  Things would be a lot more tractable if the table
was in RAM instead.

Even a medium sized company or country could probably buy enough RAM
to decrypt DES quickly.
-- 
John Gilmore  {sun,ptsfa,lll-crg,ihnp4}!hoptoad!gnu   jgilmore@lll-crg.arpa
		     May the Source be with you!

In article <1046@hoptoad.uucp> gnu@hoptoad.uucp (John Gilmore) writes:
>This is certainly a useful technique in cryptography.  Someone wrote
>a paper on how to break DES that involved writing many megabytes of stuff
>on magtape so you could get it back quickly later when breaking an
>encrypted message.  Things would be a lot more tractable if the table
>was in RAM instead.
>
>Even a medium sized company or country could probably buy enough RAM
>to decrypt DES quickly.

   While I'm not a big fan of DES, I don't think this is very accurate.
Unless there is some radically new method that no one outside NSA knows
about (I'm not ruling this out; it just seems that there is no sensible
way to discuss it), there is no way that a single-processor machine is
going to break DES in a reasonable period of time.  And that is what
this discussion is about, large single-processor (or perhaps a few
processors, but not hundreds or thousands) machines with large amounts
of memory.

   -- David desJardins

In article <1130@bu-cs.bu-cs.BU.EDU> bzs@bu-cs.BU.EDU (Barry Shein) writes:
>...
>As I brought up once before, I still think there may be some constant
>N which completes the sentence "never buy more memory than you can
>zero out in N seconds" [I call it Shein's law of memory but some have
>claimed that Amdahl may have said something similar, great minds run
>in the same gutters :-]
>...
>A one MIP machine zeroing memory in a loop:
>
>		CLRL	R1
>	LOOP:
>		CLRL	(R1)+
>		CMPL	R1,HIMEM
>		BNE	LOOP
>
>would (theoretical machine) take 3 * (1G/1M) or 3000 seconds or
>a little less than one hour to complete. It's hard to believe
>such a machine could make -effective- use of that much memory.
>

The task of zeroing memory on the Cray 2 with 256MW (=2GB) should take
less than 5-10 seconds.  You must remember that a one MIP machine is
pathetically slow compared to a Cray (at least for vector operations
like zeroing memory, searching, sorting, and many scientific
applications).

By the way, why does everyone assume that large memory is for database
applications and such.  I can think of LOTS of scientific applications
for large memory machines - none of which involve databases in any way.

J. Giles
Los Alamos

In article <7144@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>The task of zeroing memory on the Cray 2 with 256MW (=2GB) should take
>less than 5-10 seconds.  You must remember that a one MIP machine is
>pathetically slow compared to a Cray (at least for vector operations
>like zeroing memory, searching, sorting, and many scientific
>applications).
>

I made a slight error (by an order of magnitude) - The Cray 2 should
take about .5 to 1.0 seconds to clear all its memory.

It seems that large memory machines are obviously desireable.  In
lattice guage theory a single lattice could easily use all the Cray 2
memory. 3-d hydro codes also use enormous ammounts of memory.
Furthermore, applications like these make frequent references to the
entire data structure (ie. the whole array is updated every single
time-step).

The desirability of paging for such machines is not so obvious.
Consider a code which updates a large array on each step through a
loop (each time-step).  If the central memory is too small to hold the
entire array and you have a virtual memory scheme, some part of the
array will get swapped out on each time step.  Most likely, it will be
the least recently used page that gets swapped - the very one that you
will need first on the subsequent time step!  You are now in a
situation of chasing you tail around memory - losing time all the
while.

Without virtual memory though, your code can anticipate the problem by
initializing asynchronous I/O long before it needs to use the data.
And, since it's not driven by page faults, you can select only a
particular part of the array to be swapped - thus minimizing I/O.
This kind of programming effort is somewhat unfasionable these days,
but it's exactly the sort of thing that most programmers that use
these big machines immediately do.  They bought the machine because
the critical issue was SPEED - and anything that reduces this speed
(like virtual memory) is to be shunned.  (Cyber 205 users usually
turn off the virtual memory when they need speed, Crays don't even
have virtual memory.)

On the other hand, a small memory - single user machine (like my SUN
workstation) should never be built without virtual memory.  The
desirability of a feature should always be driven entirely be the
purpose of the machine.

J. Giles
Los Alamos

In article <7144@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>The task of zeroing memory on the Cray 2 with 256MW (=2GB) should take
>less than 5-10 seconds.  You must remember that a one MIP machine is
>pathetically slow compared to a Cray (at least for vector operations
>like zeroing memory, searching, sorting, and many scientific
>applications).
>

I made a slight error (by an order of magnitude) - The Cray 2 should
take about .5 to 1.0 seconds to clear all its memory.

It seems that large memory machines are obviously desireable.  In
lattice guage theory a single lattice could easily use all the Cray 2
memory. 3-d hydro codes also use enormous ammounts of memory.
Furthermore, applications like these make frequent references to the
entire data structure (ie. the whole array is updated every single
time-step).

The desirability of paging for such machines is not so obvious.
Consider a code which updates a large array on each step through a
loop (each time-step).  If the central memory is too small to hold the
entire array and you have a virtual memory scheme, some part of the
array will get swapped out on each time step.  Most likely, it will be
the least recently used page that gets swapped - the very one that you
will need first on the subsequent time step!  You are now in a
situation of chasing you tail around memory - losing time all the
while.

Without virtual memory though, your code can anticipate the problem by
initializing asynchronous I/O long before it needs to use the data.
And, since it's not driven by page faults, you can select only a
particular part of the array to be swapped - thus minimizing I/O.
This kind of programming effort is somewhat unfasionable these days,
but it's exactly the sort of thing that most programmers that use
these big machines immediately do.  They bought the machine because
the critical issue was SPEED - and anything that reduces this speed
(like virtual memory) is to be shunned.  (Cyber 205 users usually
turn off the virtual memory when they need speed, Crays don't even
have virtual memory.)

On the other hand, a small memory - single user machine (like my SUN
workstation) should never be built without virtual memory.  The
desirability of a feature should always be driven entirely be the
purpose of the machine.

J. Giles
Los Alamos

> The desirability of paging for such machines is not so obvious.
> Consider a code which updates a large array on each step through a
> loop (each time-step).  If the central memory is too small to hold the
> entire array and you have a virtual memory scheme, some part of the
> array will get swapped out on each time step.  Most likely, it will be
> the least recently used page that gets swapped - the very one that you
> will need first on the subsequent time step!...

Jim, all that you have established here is that LRU is a thoroughly bad
virtual-memory policy for a scientific program.  Few people will argue that.
You have also more-or-less established that a program which behaves in
the manner you suggest will not benefit much from virtual memory; its
performance will degrade badly when it starts paging.  Few will argue that
either.  Not all programs behave that way, though.

You have *not* established that virtual memory, as such, is a poor idea.
It is quite possible to combine demand fetching with prefetching of things
that are expected to be needed soon.  It's probably even a good idea when
trying to page scientific programs.  It *is* harder to get right, which is
why you don't see it done much.

> Without virtual memory though, your code can anticipate the problem by
> initializing asynchronous I/O long before it needs to use the data.
> And, since it's not driven by page faults, you can select only a
> particular part of the array to be swapped - thus minimizing I/O.
> This kind of programming effort is somewhat unfasionable these days...

With some reason.  What you're saying is that because the operating-system
people are too lazy to devise paging algorithms that are useful for large
scientific programs, the programmers should be required to do it themselves.
Apart from the matter of constantly reinventing the wheel, there is also
the problem that it's a lot of work to get it right -- program reference
patterns are notorious for being hard to predict beforehand, which means
experimenting and then twiddling the code to match the results.  This
may perhaps not be needed for really straightforward array-mashing code,
but I remain a bit skeptical:  historically, the batting average on statements
like "this program obviously has the following reference pattern..." is
close to zero.  I wouldn't be surprised if a lot of scientific code, with
its carefully hand-twiddled asynchronous I/O, is in fact managing its
memory rather inefficiently.  Especially if the code has been revised, or
moved to a new machine (or a new variant of the old one), since the last
tuning job was done.

> ... They bought the machine because
> the critical issue was SPEED - and anything that reduces this speed
> (like virtual memory) is to be shunned.  (Cyber 205 users usually
> turn off the virtual memory when they need speed, Crays don't even
> have virtual memory.)

I think you may be confusing two issues here.  The reason the Crays don't
have virtual memory is not because asynchronous I/O is superior to paging,
but because non-trivial address translation hurts memory-access time.  Are
the Cyber 205 users turning the virtual memory off because they don't trust
the paging algorithm, or because the machine will run even a memory-resident
program faster with it off?  I'd bet it's the latter.  Now *that* is a
legitimate and well-justified reason for not using virtual memory.
-- 
				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,decvax,pyramid}!utzoo!henry

This is not directly related to the discussion about large main
memories, but I thought I would try to supply some information
about the CDC Cyber 205, since we have one of these beasties.  The
context is the comparison between the Cray, which does not use virtual
memory, and the 205, which does.

The hardware part of virtual memory on the 205 is implemented using a
two level lookup table to translate virtual page addresses to physical
pages.  The first level is a 16 entry set of "associative registers"
(ARs) which can do this mapping in 1 cycle.  These are similar to the
"translation lookaside buffer" on other virtual memory machines, except
smaller.  The second level is the "space table", which has an entry for
each occupied real memory page (plus some dummy entries used by the
system).  This table resides at a fixed address in real memory and its
first 16 entries are loaded into the associative registers.  That is,
the ARs cache the first 16 entries of the space table.

When a memory reference cannot be mapped using the associative
registers, the affected instruction is suspended, the ARs are stored
into the start of the space table, the space table is searched for the
mapping at a rate of two entries per cycle until the match is found,
the match is moved to the first entry in the space table, the ARs are
reloaded from the space table, and the instruction is resumed.  (If a
mapping is not found, this constitutes a page fault, which I am
ignoring.)  The ARs need to be stored and reloaded because they are
kept in LRU order by the hardware, and thus rapidly get out of sync
with the part of the space table they are caching.  The overhead for
stopping, saving, reloading, and restarting is about 80 cycles.
(Choke!)

When running in monitor mode, all memory references are physical
references, but take just as long to execute.  I suspect, but have not
checked the prints to be sure, that monitor mode just forces the ARs to
always respond with the identity map.

With that as background,

1) Whatever programming technique you use on a Cray to fit ten pounds
of data into 5 pounds of real memory will also work on the 205.  That
is, if your program can be run on a Cray with X Mwords of memory, it
will run on a 205 with X Mwords of memory WITHOUT FAULTING.

2) Monitor mode on the 205 disables external interrupts, so I seriously
doubt that any sites are running their 205's "with virtual memory
disabled".

3) Nonetheless, I ran some timing tests to determine the cost of space
table searches (which would not happen in monitor mode, due to the
faked identity map).  Using as a test case a vector add of two arrays
into a third array, each array one third the size of available real
memory, I came up with a cost of 0.48% with 4 Mwords and 1.5% for 32
Mwords (both assuming a page size of 64k words, which is the largest
available on the 205).  Over the course of a day, the latter amounts to
about 22 minutes.

The previous example has about the best AR hit rate for code which
still references every word of real memory just once.  If the code were
a gather/scatter which touched only one word per page, the cost would
be a whopping 32800% for a 32 Mword system.

Fortunately, most codes have better locality of reference than either
of these, so there is little incentive to run a 205 as a single user,
real memory system.

4) Note that the previous test compares the 205 with itself.  That is,
from the results we cannot determine how much faster the 205 would run
if it had no virtual memory at all, only how much faster it would run
if we don't use what is there.  The 205, like the Cray, is very
parallel, so it is possible that the AR mapping takes place at the same
time as other functions and ends up adding nothing to the total
execution time of memory reference instructions which find a hit in the
ARs.  (Again, I haven't checked this against the prints or microcode.)

5) The 205's ancestor, the STAR-100, had at most 1 Mword of memory, and
thus all real memory could be mapped with just the ARs (if you used
only the large page size).  It would have been nice if CDC could have
kept this property as they increased the size of central memory.

(My .signature is copied from someone else's [Hi Tom] so I can't guarantee
I am really reachable where it says, nor even that it gets included.  So
far as I can tell, news is voodoo.)

-- 
Dale Talcott                            Systems programmer
ARPANET: aeh@j.cc.Purdue.EDU            Purdue University Computing Center
 BITNET: AEH@PURCCVM                    Mathematical Sciences Bldg.
 USENET: aeh@pucc-j.UUCP                West Lafayette, IN 47907
  Phone: (317) 494-1787

In article <7094@utzoo.UUCP> henry@utzoo.UUCP (Henry Spencer) writes:
>...
>With some reason.  What you're saying is that because the operating-system
>people are too lazy to devise paging algorithms that are useful for large
>scientific programs, the programmers should be required to do it themselves.
>Apart from the matter of constantly reinventing the wheel, there is also
>the problem that it's a lot of work to get it right -- program reference
>patterns are notorious for being hard to predict beforehand, which means
>experimenting and then twiddling the code to match the results.

It's not just that the operating system or hardware designers are too lazy
to come up with a good scheme.  The problem is that any scheme they DO come
up with must work for general cases.  That is, it can't take advantage of
special knowledge of a specific algorithm.

The individual applications programmer CAN take advantage of such knowledge.
To be sure, this is an expensive and difficult programming project.  But,
if you've just spent $10-$20 million on a fast machine, you aren't going
to balk at a few million more in programmer man-hours to get the speed
that you shelled out so much cash for.

Since hardware (for whatever reason) can run faster without virtual memory,
there will always be a market among the high-end users for machines that
don't have it.  Since these are the sort of machines with the Very large
memories that are talking about, I question the desirability of virtual
memory on them.

As a final note: there are some types of algorithm for which it is
extremely easy to predict the data usage patterns.  Most Finite-Difference
and Finite-Element codes are of this kind.  These applications involve a
small number of very large arrays which are referenced cyclically.  Other
applications, like image manipulation and particle transport, have somewhat
more difficult patterns, but there are known methods for dealing with them.
These are the types of codes which form the predominant workload for
today's large memory supercomputers (whether bought by oil companies or
government).  Now, it might be convenient to implement virtual memory
schemes which are useful in this context, but I doubt that the extra
overhead in the memory interface would be justified - especially since
the explicit methods for dealing with them are fairly easy to implement.

In article <2993@h.cc.purdue.edu> aeh@h.cc.purdue.edu.UUCP (Dale Talcott) writes:
>...
>1) Whatever programming technique you use on a Cray to fit ten pounds
>of data into 5 pounds of real memory will also work on the 205.  That
>is, if your program can be run on a Cray with X Mwords of memory, it
>will run on a 205 with X Mwords of memory WITHOUT FAULTING.
>
>2) Monitor mode on the 205 disables external interrupts, so I seriously
>doubt that any sites are running their 205's "with virtual memory
>disabled".
>
Since the trip through the Associative registers costs a machine cycle on
the 205, that means that every memory reference is delayed by at least that
ammount.  (Actually, I suspect that the cost may be higher in that the
selection of the clock rate may have been partially driven by this memory
interface.)  Most memory references are, of course, overlapped by other
computation - so you might think that the extra clock may be negligable.
Unfortunately, as we all found out, a sizable part of execution time in
a 'real' application is inherently scaler.  And for this code, an extra
clock in the memory interface usually means an extra clock over-all.  This
may be part of the explanation of the fact that Crays seem to outperform
Cybers even when small benchmarks indicate the opposite should be true.
(The other reason is the MUCH longer setup time for vector operations
on the Cyber, which can only be offset if the vector sizes are very long
on average.  The distribution of vector lengths within a computation is
not that simple, but it seems that there tend to be a lot of short vectors
in 'real' codes.)

I suspect that the main saving on the Cyber of going into monitor mode is
to prevent parts of your data from being swapped out when you don't want
it to be.  This prevents a page fault later.  As I said before, most of
the programmers I know who have run codes on Cybers prefer to have the
virtual memory off.

In article <7331@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>In article <7094@utzoo.UUCP> henry@utzoo.UUCP (Henry Spencer) writes:
>>...
>>With some reason.  What you're saying is that because the operating-system
>>people are too lazy to devise paging algorithms that are useful for large
>>scientific programs, the programmers should be required to do it themselves.
>>Apart from the matter of constantly reinventing the wheel, there is also
>>the problem that it's a lot of work to get it right -- program reference
>>patterns are notorious for being hard to predict beforehand, which means
>>experimenting and then twiddling the code to match the results.
>
>It's not just that the operating system or hardware designers are too lazy
>to come up with a good scheme.  The problem is that any scheme they DO come
>up with must work for general cases.  That is, it can't take advantage of
>special knowledge of a specific algorithm.
>
Rather than having the user explicitly implement a suitable paging
algorithm for his program, couldn't the operating system have a
facility like the UNIX vadvise system call?  According to the vadvise
man page, the call vadvise(V_ANOM) warns the pager that LRU is not
a suitable algorithm for this particular job.  Perhaps this could be
expanded to include calls like vadvise(V_CYCLIC) to indicate that
the program wants to cyclically reference large arrays.  Of course,
the difficulty would be for the pager to work out which pages corresponded
to these arrays, particularly in the case of two or more arrays which
are traversed in parallel.

Michael Clase
mclase@watdaisy.uucp (for one more week)

In article <7331@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>It's not just that the operating system or hardware designers are too lazy
>to come up with a good scheme.  The problem is that any scheme they DO come
>up with must work for general cases.  That is, it can't take advantage of
>special knowledge of a specific algorithm....The individual applications
>programmer CAN take advantage of such knowledge.  To be sure, this is an
>expensive and difficult programming project...[but] there are some types of
>algorithm for which it is extremely easy to predict the data usage
>patterns.  Now, it might be convenient to implement virtual memory schemes
>which are useful in this context, but I doubt that the extra overhead in the
>memory interface would be justified - especially since the explicit methods
>for dealing with them are fairly easy to implement.

1) Doubtless you can show me cases where it's "extremely easy" to predict
data usage patterns.  Can you show me one where it's easy to predict the
code usage patterns?  I want VM to free me from overlays, or code space
management, not file structuring, or data space management.

>if you've just spent $10-$20 million on a fast machine, you aren't going
>to balk at a few million more in programmer man-hours to get the speed
>that you shelled out so much cash for.
2) Can we measure the win?  Can you provide figures on performance
improvements for either data or code space management by application
programmers over mechanisms provided by operating system or hardware
designers?  Have you any actual examples, how much was the improvement for a
specific application you're familiar with?  Can we state a general rule,
expected returns on applications programmers managing their own code and/or
data spaces?  Can you state the breakeven point, how many millions of
dollars I should be willing to spend before I improve on the operating
system's paging?

					-- jon
-- 
--> Jon Krueger
uucp: {seismo, allegra, decvax, cmcl2, topaz, harvard}!rochester!ur-tut!tuba
Phone: (716) 275-2811 work, 473-4124 home	BITNET: TUBA@UORDBV
USMAIL:  Taylor Hall, University of Rochester, Rochester NY  14627 

In article <676@ur-tut.UUCP> tuba@ur-tut.UUCP (Jon Krueger) writes:
>...
>1) Doubtless you can show me cases where it's "extremely easy" to predict
>data usage patterns.  Can you show me one where it's easy to predict the
>code usage patterns?  I want VM to free me from overlays, or code space
>management, not file structuring, or data space management.

In this context, it is important to note that code memory is ALWAYS
trivially small compared to data memory for scientific codes.  This is NOT
just conjecture, the memory used by code has been less than a few percent
of the total memory requirement for every scientific program I've ever
seen.  Furthermore, code usage patterns in these programs ARE easy to
determine for the same reason that the data usage patterns are - the
thing is in a large time-loop: it does physics on the grid, then it
rezones (if necessary), then it dumps a graphic description of the
grid (if requested), then it goes back for the next time step...

To be sure, people use overlays to save even the small space required by
code.  But this is fairly trivial - the physics, rezone, and graphics
subroutines are the ones to be overlayed.  And those programs which
can fit in main memory ARE NOT PENALIZED BY THE PRESENCE OF ADDITIONAL
OVERHEAD IN THE MEMORY INTERFACE!!!

There really are applications which don't benefit very much from a VM
system.  This will remain true as long as VM systems add ANY overhead
at all to the memory interface.

J. Giles
Los Alamos

In article <676@ur-tut.UUCP> tuba@ur-tut.UUCP (Jon Krueger) writes:
>...
>1) Doubtless you can show me cases where it's "extremely easy" to predict
>data usage patterns.  Can you show me one where it's easy to predict the
>code usage patterns?  I want VM to free me from overlays, or code space
>management, not file structuring, or data space management.

Another thing to remember here is that most of the large scale scientific
codes that run on large memory supercomputers have existed for many
years.  As a result, the usage patterns (both of data and code) are well
known.  These already contain sophisticated memory management routines
that are taylored for the specific code.  When moving to a new and larger
machine, these usage patterns don't change - just the scale of the
memory involved.  The main problems in porting these codes to a new
machine tend to be numerical (different arithmetic on the new hardware),
or incompatibilities in the language (the compiler on the new machine
recognizes a different set of Fortran extensions).

The result of all this is that the people who do large scale scientific
computing have already resolved the memory management problems.  A VM
system would not save them any time, on the contrary - it would require
additional work in trying to rearrange code and data usage patterns to
minimize page faulting.

J. Giles
Los Alamos

In article <7331@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>to come up with a good scheme.  The problem is that any scheme they DO come
>up with must work for general cases.  That is, it can't take advantage of
>special knowledge of a specific algorithm.
>
>The individual applications programmer CAN take advantage of such knowledge.

vmadvise() ???  I don't think BSD ever got it fully off of the ground, but
it has interesting applications to you.  It was a way of sharing your
specific paging knowledge which is bought by time, with the OS.  This will
not save you from page translation cost, but it does allow you to advise
the OS on differences your program has from the general case.  It also allows
the OS to play any strange games that can be played to squeeze those extra
pennies out of your XXXXX.

-- 
    Jim Hutchison   UUCP:	{dcdwest,ucbvax}!sdcsvax!hutch
		    ARPA:	Hutch@sdcsvax.ucsd.edu
	"The fog crept in on little cats feet" -CS

Cray users often like to boast that very large main memories such as the
Cray 2 obviate the need for virtual memory.  J. Giles stated recently that
Cyber 205 users "turn off" virtual memory.  I work at a site which has a
Cray X-MP, a Cyber 205, and a Cray-2 (Ames Research Center).  I would like
to state for the record that there are considerable advantages to having a
machine have memory mapping virtual memory architecture, even though there
is no apparent single job performance advantage.  

Picture a very large (almost all of real memory) batch job running on a Cray.
Suppose that there is some interactive debugging going on (The Cyber 205 VSOS
operating system and the Cray CTSS operating system are both interactive and
have very nice interactive debuggers.)  The large batch job will have to be
written out to disk in entirety on the Cray before the small interactive job
can be rolled in.  That might take tens of seconds on a Cray 2.  What if only
a few pages had to be paged out as on the Cyber 205?  The batch job would
proceed with only a few pages missing, and the total swap time in any case
would be only a few tenths of a second.  There are many hypothetical examples
which can be imagined which are confirmed, in my experience, in real life:

All other things being equal, virtual memory systems have better throughput
than non virtual memory systems of equivalent memory size and CPU speed.

Virtual memory systems are better suited to mixed large batch and interactive
loads, and are capable of better response time at an equivalent overhead than
non virtual memory systems.

Anyone who has had to deal with setting policies for user memory allocations
on a Seymour Cray machine (from CDC 6600 days to the Cray 2) will know what
kind of trade offs are necessary and why often these machines have been run
batch only with users limited to half of the overall available memory.

Now, a reasonable question to ask on a fast machine is, how much CPU real
estate is going to be consumed by dynamic address translation hardware,
because added logic is going to slow a very fast machine down.   Cray has
kept his machines very simple architecturally, and has a much smaller 
number of gates than other comparable machines (e.g. Cray 1's and 2's
run between 600000 to 700000 gates per CPU, while the Cyber 205 has about
1.3 million, roughly twice as many), which may help explain why Cray has
always had the fastest clock in the supercomputer business (another factor
is that Cray is obviously a packaging genius).  

Conclusion:  An computer architect always has to trade off design features
to build a real machine, and in some cases virtual memory may have to be
traded off, but in the real world of operating a machine, virtual memory
is a significant advantage, other things being equal.

   Hugh LaMaster, m/s 233-9,   UUCP:  {seismo,hplabs}!nike!pioneer!lamaster 
   NASA Ames Research Center   ARPA:  lamaster@ames-pioneer.arpa
   Moffett Field, CA 94035     ARPA:  lamaster%pioneer@ames.arpa
   Phone:  (415)694-6117       ARPA:  lamaster@ames.arc.nasa.gov

"The reasonable man adapts himself to the world, the unreasonable man
adapts the world to himself, therefore, all progress depends on the
unreasonable man." -- George Bernard Shaw

("Any opinions expressed herein are solely the responsibility of the
author and do not represent the opinions of NASA or the U.S. Government")

        I once was a system programmer for a CDC 7600 site.  We ran many
scientific programs, but lacked virtual memory.  Some programs used almost
all of memory.  These jobs might run faster than the same ones would with
less memory, but overall system performance suffered.  For example, a
compilation might not fit in memory alongside a huge scientific job.  If
the compilation runs alone, the CPU will be idle much of the time it runs.
Yet the scientific program might have considerable unused code and/or data
(e.g., the input data for this run does not select Calcomp plots, so those
routines are never called and their data areas are never referenced;
another likely possibility is that some dimensions are much larger than
required).  If either job runs alone, then it wants as much memory as it
can get.  With virtual memory, the operating system can simultaneously
load the heavily used parts of BOTH jobs in the machine, for better
overall performance.
-- 
			Peter Montgomery

	{aero,allegra,bmcg,burdvax,hplabs,
	 ihnp4,psivax,randvax,sdcsvax,trwrb}!sdcrdcf!pmontgom

Don't blame me for the crowded freeways - I don't drive.

In article <2077@sdcsvax.UUCP> hutch@sdcsvax.UUCP (Jim Hutchison) writes:
>...
>vmadvise() ???  I don't think BSD ever got it fully off of the ground, but
>it has interesting applications to you.  It was a way of sharing your
>specific paging knowledge which is bought by time, with the OS.  This will
>not save you from page translation cost, but it does allow you to advise
>the OS on differences your program has from the general case.  It also allows
>the OS to play any strange games that can be played to squeeze those extra
>pennies out of your XXXXX.
>
My document lists this as VADVISE().  It only has two settings which,
apparently, optimize for random order (that is, it ignores the recent
usage patterns), or it optimizes for the most frequently and recently
referenced pages (the default).  The MAN page contains a note that
this feature was included mainly to support LISP, which has fairly
random access patterns.

This doesn't seem to give the kind of control over memory contents that
I am used to.  It certainly doesn't seem likely to work well for an
algorithm that has some 'randomly' used data, some cyclically used data,
and some frequently used data (or some such mix).

The VADVISE() doc also mentions (under 'BUGS') that this 'Will go away
soon, being replaced by a per page *madvise* facility.' MADVISE looks
like it will have more control over memory contents (but still not
complete control).  It looks also like it will entail the same degree
of work to use it effectively as direct user control would require.
So the bottom line is: we still don't have complete control, we still
need to do a lot of work on our own, and we still have a slower memory
interface than necessary.

J. Giles
Los Alamos

In article <609@nike.UUCP> lamaster@pioneer.UUCP (Hugh LaMaster) writes:
>Cray users often like to boast that very large main memories such as the
>Cray 2 obviate the need for virtual memory.  J. Giles stated recently that
>Cyber 205 users "turn off" virtual memory.  I work at a site which has a
>Cray X-MP, a Cyber 205, and a Cray-2 (Ames Research Center).  I would like
>to state for the record that there are considerable advantages to having a
>machine have memory mapping virtual memory architecture, even though there
>is no apparent single job performance advantage.  
>
>Picture a very large (almost all of real memory) batch job running on a Cray.
>Suppose that there is some interactive debugging going on (The Cyber 205 VSOS
>operating system and the Cray CTSS operating system are both interactive and
>have very nice interactive debuggers.)  The large batch job will have to be
>written out to disk in entirety on the Cray before the small interactive job
>can be rolled in.  That might take tens of seconds on a Cray 2.  What if only
>a few pages had to be paged out as on the Cyber 205?  The batch job would
>proceed with only a few pages missing, and the total swap time in any case
>would be only a few tenths of a second.  There are many hypothetical examples
>which can be imagined which are confirmed, in my experience, in real life:

You obviously don't have enough Crays!  Now if you had 3 X/MPs (like
we do) you could configure one for interactive use, and the others for
batch use :-).

Seriously: yes there is a trade-off between throughput, interactivity,
and single process speed.  We have to configure our maximum job size
to no more than 3/4 the total memory during the day to allow for
interactive processes.  We also reduce maximum memory residency time
during the day.  We wouldn't have to do this with a virtual memory
system (nor with a total batch operating system).

During the night, when most large scale programs are run, the
operating system is reconfigured to optimize the speen of individual
codes.  On a virtual memory system, this is not possible (at least not
completely - you can't truly rid yourself of the overhead inherent in
the VM interface).  It is the fast turn-around on large night jobs that
is attractive to our users - the ability to also debug interactively
during the day is a useful bonus.

New Crays are coming out now with SSD memory devices (Solid State Disk).
The increased speed of these devices, compared to disk, might make VM
seem to be attractive once more.  Seymore's attitude is (what else):
if it's made of solid state memory - why not make it part of the central
memory of the machine?  The Cray 3 is not currently expected to have an
SSD, but is is expected to fill the entire 32 bit address space with
central memory (that's 32 GB or 4 GW).  Seymore thinks 32 bits is too
small for an address!

This is another problem with virtual memory - central memory is
starting to get cheaper and bigger than the disk memory.  The biggest
disk drive available with a Cray these days is a DD-49 (holds about
151 MW).  One memory image of the 4GW Cray 3 would fill 26 DD-49s to
capacity.  What are you going to operate virtual memory out of?

J. Giles
Los Alamos

In article <3013@sdcrdcf.UUCP> pmontgom@sdcrdcf.UUCP (Peter Montgomery) writes:
>
>        I once was a system programmer for a CDC 7600 site.  We ran many
>scientific programs, but lacked virtual memory.  Some programs used almost
>all of memory.  These jobs might run faster than the same ones would with
>less memory, but overall system performance suffered.  For example, a
>compilation might not fit in memory alongside a huge scientific job.  If
>the compilation runs alone, the CPU will be idle much of the time it runs.
>Yet the scientific program might have considerable unused code and/or data
>(e.g., the input data for this run does not select Calcomp plots, so those
>routines are never called and their data areas are never referenced;
>another likely possibility is that some dimensions are much larger than
>required).  If either job runs alone, then it wants as much memory as it
>can get.  With virtual memory, the operating system can simultaneously
>load the heavily used parts of BOTH jobs in the machine, for better
>overall performance.

Yes, I agree.  The 7600 probably would have been better off with
virtual memory.  They only had 262 KW of memory (at most - the address
bus was 18 bits, I never saw a 7600 configured with this much).  These
days, 262 KW is only one 64th of the available memory on a 16 MW
machine.  You can afford to load 50-100 KW of unused code into memory,
it's less than one percent(of memory).

The times have changed, the calcomp plotting routines still take up
the same amount of space but the total memory has grown by 100 fold
(soon to be 1000 fold).  The code for the scientific part of the
calculation hasn't changed much either.  The extra memory is being
used by data, not code.  And it is the data in a scientific code that
gets the most use (and the largest part of the data gets the largest
use - the grid, mesh, lattice, particle descriptions, etc.).  It doesn't
trouble me to load unused code, it takes up so little space anyway.

To be sure, there is still a trade-off between throughput and
individual job speed.  I claim that there are types of application in
which this trade-off sould be resolved in favor of job speed.  In this
kind of application, virtual memory in not desireable and is getting
less desireable as machine speed and central memory size increases.

J. Giles
Los Alamos

One important point that I forgot to mention in previous posting:
On a machine with memory mapping (Cyber-205 for example) there is only a very
small penalty for reclaiming a small amount of memory for another task.  On a
very large main memory system, this is an important point.  A 256 MW Cray-2
(with approx. 4 ns clock) would take 1 second to completely copy main memory.
Unfortunately, this is exactly what is required to reclaim memory on the Cray-2
or any other machine which requires memory to be contiguous.  This is an 
important contribution to system overhead, even in batch mode, but can become
a major bottleneck.  This combines with the already mentioned problems to
produce effectively even poorer memory utilization, because there is a limit
on how frequently memory can be packed in order to make available space
usable.  That there is no such problem on a virtual memory machine is an
additional benefit to virtual memory.  J. Giles is correct in stating
that if single job STEP (or single program) speed is the most important
criterion, there is probably no advantage to a virtual memory machine, as
long as the individual job steps take hundreds of seconds or more.  And, as
stated earlier, there is a price to pay for virtual memory:  the extra 
cpu logic it takes to implement it, which undoubtedly slows the cpu by
some amount.  It may be interesting to note that CDC gave the future 
existence of very large main memories as one of the reasons for designing
the virtual memory architecture of the new Cyber 800 and 900 series (NOS/VE)
machines as they did.  They stated that memory management of main memory 
would be too inefficient without it.

   Hugh LaMaster, m/s 233-9,   UUCP:  {seismo,hplabs}!nike!pioneer!lamaster 
   NASA Ames Research Center   ARPA:  lamaster@ames-pioneer.arpa
   Moffett Field, CA 94035     ARPA:  lamaster%pioneer@ames.arpa
   Phone:  (415)694-6117       ARPA:  lamaster@ames.arc.nasa.gov

"The reasonable man adapts himself to the world, the unreasonable man
adapts the world to himself, therefore, all progress depends on the
unreasonable man." -- George Bernard Shaw

("Any opinions expressed herein are solely the responsibility of the
author and do not represent the opinions of NASA or the U.S. Government")

In article <7839@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>Seymore [Cray] thinks 32 bits is too small for an address!

He's right, too.

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

In article <627@nike.UUCP> lamaster@pioneer.UUCP (Hugh LaMaster) writes:
>One important point that I forgot to mention in previous posting:
>On a machine with memory mapping (Cyber-205 for example) there is only a very
>small penalty for reclaiming a small amount of memory for another task.  On a
>very large main memory system, this is an important point.  A 256 MW Cray-2
>(with approx. 4 ns clock) would take 1 second to completely copy main memory.
>Unfortunately, this is exactly what is required to reclaim memory on the Cray-2
>or any other machine which requires memory to be contiguous.
>...

This is not really true.  There is no reason inherent in a non-VM
system which requires it to swap the whole large program out in order
to make room for the smaller one.  The only absolute requirement is
that the large program must be entirely resident while it is running.

As it happens, the systems currently running on Cray machines drop
entire memory images when swapping for space.  But this is not a
requirement - only a simplification of the duties of the operating
system.

J. Giles
Los Alamos

The "anti-virtual" memory discussions seem to be concentrating on whether
Supercomputers need virtual memory.  Note that these machines are in a sense
special purpose* machines with the following characteristics:

	They are pushing the "state of the art" in memory and processor
	design.

	They are intended for large scale, vectored, mostly floating point
	calculations.

	They are expensive to purchase and operate.

	They are usually sold and purchased to support a few computationally
	intensive applications (which may run for hours or days even on a
	Cray).

In this environment virtual memory is probably a hindrance rather than a help.

However, as time passes, larger memories and faster processors will be
available for more conventional general purpose computers.  I believe that
virtual memory will be essential for the management of the larger memories
in many of the environments in which these systems will be used.


---------
* I know they are special purpose in the sense that they can perform any
  application which any other "general purpose" machine can perform.  But,
  how many people purchase a Cray to do timesharing, text editing or
  business EDP?  And if they do what do you suppose Seymore Cray's answer
  would be to someone who complains about the number of users who can get
  good emacs response?

In article <589@celerity.UUCP> jjw@celerity.UUCP (Jim (JJ) Whelan) writes:
>The "anti-virtual" memory discussions seem to be concentrating on whether
>Supercomputers need virtual memory.  Note that these machines are in a sense
>special purpose* machines ...
>...
>However, as time passes, larger memories and faster processors will be
>available for more conventional general purpose computers.  I believe that
>virtual memory will be essential for the management of the larger memories
>in many of the environments in which these systems will be used.
>
This has been my point all along.  I never claimed that virtual memory
was universally bad, only that it is counterproductive in SOME
applications.  The main opposition to this view has come from those
supporters of VM who think that all applications are better with VM.

>---------
>* I know they are special purpose in the sense that they can perform any
>  application which any other "general purpose" machine can perform.  But,
>  how many people purchase a Cray to do timesharing, text editing or
>  business EDP?  And if they do what do you suppose Seymore Cray's answer
>  would be to someone who complains about the number of users who can get
>  good emacs response?

It is interesting to note however, that Crays have a better price-
performance ratio, even on these tasks, than VAXEN do.  But then,
nearly everything has a better price-performance ratio than a VAX!

J. Giles
Los Alamos