Reasons For Large Main Memories
R. James Nusbaum
Some very good reasons for large main memories seem to have been ignored
in the recent discussion. For a multiprocess machine large main memories
obviously eliminate paging, which is a significant system overhead. There
are also certain single user systems which can easily use 10 meg or more
of address space. These systems are Lisp systems. It is easy and in fact
desirable to have a very large main memory so that the entire system can
reside in silicon and not on disk. This very problem crops up in HP's new
line of AI workstations based on 68020s with 8 meg of main memory. A simple
application can easily build a core image of well over 8 meg. When it comes
time to garbage collect, the garbage collection process must swap pages in
and out of main memory. Since the disks in these machines are fairly slow
garbage collection can take 30 or 40 seconds. Paging can also cause problems
when traversing a large data structure (data structures of over 2 meg are
easy to build) which resides on multiple pages. While it is true that
sophisticated software can overcome some of the paging problems, in many
cases the cost of more memory is less than the total cost of developing
this software. In todays world silicon is often cheaper than programmer time.
Jim Nusbaum
Duke University CS Dept.
Durham, NC
Peter S. Shenkin
>
>Some very good reasons for large main memories seem to have been ignored
>are... certain single user systems which can easily use 10 meg or more
>of address space. These systems are Lisp systems....
And how about APL machines?
Peter S. Shenkin Columbia Univ. Biology Dept., NY, NY 10027
{philabs,rna}!cubsvax!peters cubsvax!pet...@columbia.ARPA
Dave Hsu
>
>Some very good reasons for large main memories seem to have been ignored
>in the recent discussion.
>... While it is true that
>sophisticated software can overcome some of the paging problems, in many
>cases the cost of more memory is less than the total cost of developing
>this software. In todays world silicon is often cheaper than programmer time.
>
>Jim Nusbaum
>Duke University CS Dept.
>Durham, NC
All good and well, Jim, but not the topic of discussion. By `large' we
mean on the order of Gbytes, not Mbytes, at which point various other
factors in the system design can degrade performance substantially.
With a database of hundreds of Gbytes, the paging problems facing a
hypothetical programmer with one or two Gbytes of RAM can actually be much
worse than those facing a programmer with one or two Mbytes worth.
All it takes is a few zillion page faults, and the time lost in page-
search-and-replacement can easily exceed the time gained by a slightly
reduced number of accesses.
babbling again,
-dave
--
David Hsu (301) 454-1433 || -8798 || -8715 "I know no-thing!" -eneevax
Communications & Signal Processing Laboratory / EE Systems Staff
Systems Research Center, Bldg 093 / Engineering Computer Facility
The University of Maryland -~- College Park, MD 20742
ARPA: h...@eneevax.umd.edu UUCP: [seismo,allegra,rlgvax]!umcp-cs!eneevax!hsu
"Electro-nuclear carburetion seems fine..."
Scot E. Wilcoxon
(I was reading it for tax change info :-) I'll point out "Giving Computers
an Elephant's Memory" in BW, Sept 1 86, pg 50. Mostly about Princeton's M3
(Massive Memory Machine), but also mentions some applications for it and
several companies working on huge memories.
As a mostly-application programmer, I'm deferring comments on the present
pagefaults-and-other-problems discussion to those more knowledgeable.
As a system administrator and sometimes OS tinkerer, I expect a machine
with huge memories will let it be tuned through OS parameters (we're
currently replacing three machines partially because SCO didn't give
us a way to configure XENIX* on them).
* XENIX is a trademark of Microsoft Corporation. Nobody else wanted it.
--
Scot E. Wilcoxon Minn Ed Comp Corp {quest,dicome,meccts}!mecc!sewilco
45 03 N 93 08 W (612)481-3507 {{caip!meccts},ihnp4,philabs}!mecc!sewilco
Laws are society's common sense, recorded for the stupid.
The alert question everything anyway.
Jim Hutchison
As memory prices drop and other economic things come to pass,
suddenly we have people asking for big fast memory. Maybe RAM,
maybe SUPER disk, maybe super-cooled core. Whatever it is going
to be, paging will still go on. (Atleast thats a best guess, but
I digress)
Decoding an address is a look up. Simple cascades will not cut it in
the GB or TB range (you laughed at the first guy who said Gig, how
about Tera! :-). Log(n) is nice, but seconds (plural) is not all that
fun for finding a page, even if you go for 8,16 legged trees (base
8,16).
Perhaps having clusters of pages, grouping allocations. This would
help for 2000+ user systems (giving everyone their own cluster or even
one per process), but would fail miserably for the 2GB data base.
Each process having a page translation table, and a VM system which
could grok processes or would only look in one place (via another
translation table perhaps).
It keeps coming back to that translation.
Well how about a mix. A reasonable N MB of virtual memory paged
by whatever scheme you have in hand, and N TB of physical memory
mapped way out somewhere. You could have the real near and the
virtual far if you wanted. Probably easier for faulting and all
that noise. You still have a VM machine, its just that the VM
is way out there where you may not have to use it.
Yes, this rapes the virtual memory environment. Segmentation comes
to mind as something to put on top of the two for protection and
address monkeying (every process gets to have its space start at 0
or whatever makes life easy).
Dabble, yes, flames if you must, please be informative with them.
--
Jim Hutchison UUCP: {dcdwest,ucbvax}!sdcsvax!hutch
ARPA: hu...@sdcsvax.ucsd.edu
"Disclaim, disclaim, off to post I go."
Jeff Lee
>fun for finding a page, even if you go for 8,16 legged trees (base
>8,16).
As the memories get bigger, all of a sudden random replacement
starts to look not so bad.... :-)
--
Jeff Lee
CSNet: Jeff @ GATech ARPA: Jeff%GATech.CSNet @ CSNet-Relay.ARPA
uucp: ...!{akgua,allegra,hplabs,ihnp4,linus,seismo,ulysses}!gatech!jeff
Jerry Natowitz
How about increasing the page size proportionally to the memory
size. If you got gigabytes to burn what's wrong with a 1 meg page?
--
Jerry Natowitz (HASA - A division)
Bell Labs HR 2A-214
201-615-5178 (no CORNET)
ihnp4!houxm!hropus!jin
or ihnp4!opus!jin
Isn't it interesting how the beautiful little red flower in the forest
becomes so ugly when you discover it's a candy wrapper.
Peter S. Shenkin
more. Most jobs could just grab a partition of core and live there till they
die. Another partition could be used to run a virtual machine in for bigger
jobs, which perhaps could be run as batch jobs in off-hours more profitably...
Jerry Natowitz
I think my definition of virtual memory might be out of synch with
others. Cheap large memories mean that we would be able to do away
with demand paging. We would still need address translation unless
every process was written in position independent code (no address
constants at assembly/compile time etc.) Does virtual memory imply
demand paging or just address translation?
R. James Nusbaum
>
>All good and well, Jim, but not the topic of discussion. By `large' we
>mean on the order of Gbytes, not Mbytes, at which point various other
>factors in the system design can degrade performance substantially.
>With a database of hundreds of Gbytes, the paging problems facing a
>hypothetical programmer with one or two Gbytes of RAM can actually be much
>worse than those facing a programmer with one or two Mbytes worth.
>All it takes is a few zillion page faults, and the time lost in page-
>search-and-replacement can easily exceed the time gained by a slightly
>reduced number of accesses.
>
>babbling again,
>
>-dave
>--
>David Hsu (301) 454-1433 || -8798 || -8715 "I know no-thing!" -eneevax
Your point is also true. However many Lisp systems are single user systems.
Having even a couple of hundred megawords of memory could totally eliminate
paging, as the entire system could be resident. Take the Symbolics for
instance. It has a 200Mb disk used for paging and some middle amount of
memory (maybe 16Mb). We have run many complex systems in this 200Mb size.
If we had 200Mb of memory then we would have no need for paging at all! This
would significantly speed up many applications.
Even 200Mb won't be enough in the near future for some applications, mainly
the VLSI cad systems I've worked on. And considering the large word size
of some Lisp machine designs (in order to have tag bits) 200Mb can work out
to be only 40Mw. My whole point, which I admit I didn't get across well, was
that some systems could totally eliminate paging by having huge amounts of
actual memory. These systems would generally be single user systems, like
Lisp, APL and possibly Prolog machines.
Jim Nusbaum
Barry Shein
From: r...@duke.UUCP (R. James Nusbaum)
>Your point is also true. However many Lisp systems are single user systems.
>Having even a couple of hundred megawords of memory could totally eliminate
>paging, as the entire system could be resident. Take the Symbolics for
>instance. It has a 200Mb disk used for paging and some middle amount of
>memory (maybe 16Mb). We have run many complex systems in this 200Mb size.
>If we had 200Mb of memory then we would have no need for paging at all! This
>would significantly speed up many applications.
But you still miss the point. In the first place, move this to GigaBytes,
obviously adding a few more megabytes is not interesting (so why do people
keep going back to it?) Even 200MB is quite different than 5X that or
more.
Now, ok, you eliminated paging, garbage collection has become a field
service thing. But, could you do anything useful with all that memory
and that (relatively) itty-bitty processor? How long would it take you
to do a MEMQ of a list of a few HUNDRED MILLION lisp objects long?
etc. Paging is only an advantage at some interim and relatively low
point (100-200MB perhaps, probably less.)
Now, I could see a lisp-machine type saying that only garbage
collecting on Xmas day would be a big win, if they could actually
accomplish that, and would otherwise run 'reasonable' programs.
Somehow though I suspect it won't work that way. More like the machine
down every Sunday for garbage collection (though I suppose many
long-running applications could be checkpointed to disk and a simple
re-boot would suffice.)
There might be hope here, it's more or less like using memory in
a way similar to a write-once CD, you "never" reuse scratch memory,
when you run out you put a new disk in (ie. re-boot.)
Ok, but still obviously not cost-effective (the magic ingredient that
gets thrown out whenever this topic starts getting discussed, 1GB of
memory is going to cost you around $1M [there's more than chips
involved, don't just tell me the 1MB price * 1,000, you'll need
backplane, power-supplies etc etc, if your figures come to $500K,
fine, same thing], how many of us would buy a lisp-machine to run one
application for $500-$1M? $250K?)
-Barry Shein, Boston University
Jim Hutchison
Zeroing of pages need not be done all at once.
Right now, if you have extra memory lying about (unusual yes, but read on),
it does not get 0'd until somebody grabs a "blank" page. How about a mode
like "0 on reference"? There is "copy on write" in some places, why not?
Then you only have to worry about 1 page at a time. Extra swap space is not
costing you anything, why should extra memory? Huh?
--
Jim Hutchison UUCP: {dcdwest,ucbvax}!sdcsvax!hutch
ARPA: Hu...@sdcsvax.ucsd.edu
"The fog crept in on little cats feet" -CS
Henry Spencer
The odds are that the demand for address space will continue to grow faster
than the memory sizes. In any case, people who argue on this basis miss an
important point: virtual memory is not a substitute for real memory. To
quote one of my friends over at HCR: "real memory for real performance".
The point of virtual memory is not that it's as useful as real memory -- it
is useful in direct proportion to the extent to which it is backed by real
memory -- but that it turns a hard limit into a soft limit. If you do not
have virtual memory, then a job which doesn't quite fit is unrunnable. If
you do not have virtual memory, and your main memory is slightly over-
committed, then much more drastic measures like swapping will have to be
used, with much more serious impact on performance. Virtual memory does
increase the effective size of memory for many applications (big number-
crunching things are often an exception, which is why virtual memory is
not popular in that community; it doesn't do them much good), but it also
makes performance degrade gradually, instead of sharply and disastrously,
when memory is slightly short.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,decvax,pyramid}!utzoo!henry
Henry Spencer
"Virtual memory", strictly speaking, refers to memory that acts like it's
always there but sometimes isn't. That is, demand paging or some analogous
scheme (paging is not the only memory-management technique possible, and
demand paging is not the only page-fetching policy possible). Address
translation, by itself, is not virtual memory.
Henry Spencer
> Having even a couple of hundred megawords of memory could totally eliminate
Well, today it could be. Two years from now, in the Lisp community, who
knows? If you drop the ability to do virtual memory, then there is an
awfully sharp cost jump when a program goes from 200MW of memory to 200M+1W.
All of a sudden none of those 200MW machines can run it any more.
There is a lot to be said for memory-rich systems, particularly for Lisp
applications, but discarding virtual memory is throwing out the baby with
the bathwater.
pre...@ccvaxa.uucp
> /* Written 4:40 pm Sep 5, 1986 by b...@bu-cs.BU.EDU in ccvaxa:net.arch */
> Now, ok, you eliminated paging, garbage collection has become a field
> service thing. But, could you do anything useful with all that memory
> and that (relatively) itty-bitty processor? How long would it take you
> to do a MEMQ of a list of a few HUNDRED MILLION lisp objects long?
> etc.
----------
Have you not heard of indexes? Hash tables? Arrays? There are any
number of ways to use memory that don't involve scanning it. A 2GB
database of bibliographic references (such as Dialog or LEXIS might
have) would run A LOT FASTER if it lived in main memory and wasn't
pounding on the disk interface all the time. That's not a single-user
example in today's world (it could be eventually, marketed to
libraries and universities), but I have no doubt you can think of
applications that are fully indexed, doing few scans, but using
many, many bytes of data. The reason you want it in memory is that
you don't know which bytes you'll want or what order you'll want them
in.
----------
> Ok, but still obviously not cost-effective (the magic ingredient that
> gets thrown out whenever this topic starts getting discussed, 1GB of
> memory is going to cost you around $1M
----------
Please allow the user to determine what's cost effective. If what
you're doing is evaluating huge matrices of seismic data and you
need to do them in N hours because there's a rights auction coming
up, a million may not be an impediment, especially if the machine
can be used as a time-shared engine at times when there isn't a need
for haste.
Betting on those prices holding is about as sensible as betting on
access times holding...
--
scott preece
gould/csd - urbana
uucp: ihnp4!uiucdcs!ccvaxa!preece
arpa: preece@gswd-vms
R. James Nusbaum
>
>>From: r...@duke.UUCP (R. James Nusbaum)
>>Your point is also true. However many Lisp systems are single user systems.
>>Having even a couple of hundred megawords of memory could totally eliminate
[ omitted to save space]
>>If we had 200Mb of memory then we would have no need for paging at all! This
>>would significantly speed up many applications.
>
>But you still miss the point. In the first place, move this to GigaBytes,
>obviously adding a few more megabytes is not interesting (so why do people
>keep going back to it?) Even 200MB is quite different than 5X that or
>more.
>Now, ok, you eliminated paging, garbage collection has become a field
>service thing. But, could you do anything useful with all that memory
>and that (relatively) itty-bitty processor? How long would it take you
>to do a MEMQ of a list of a few HUNDRED MILLION lisp objects long?
>etc. Paging is only an advantage at some interim and relatively low
>point (100-200MB perhaps, probably less.)
Anyone who would have a list 100,000,000 objects long is a a poor Lisp
programmer. In case you haven't heard Lisp has things called arrays and
yes, I know of many things which I could do with that itty-bitty
processor. The following is an example:
I have a VLSI CAD system which divides the chip surface into small squares.
Each square can be occupied by a cell (a circuit description). I would
love to have at least a 512x512 array of these cells. Note: a cell may
be an empty cell, no circuitry. That means I need 262,144 locations in
my array, each containing a cell pointer (32 bits). In a full array
each pointer would point to an object (not a Lisp object, an object-oriented
programming object) which I would like to be large. The larger the
object the faster it is to do things like repaint the screen because of
less information sharing and pointer chasing. Let's assume a 1k object.
We're already up to 268,440,000 bytes. Now add simulation data to the
objects, now add color to the visual description of the objects, now
add different representations, now add the code to handle these objects.
We are already over 1Gb, I assure you.
Now throw in the monkey wrench which would kill any smart paging scheme of
a virtual memory system. It's called the user. The user is viewing
these objects on his screen. He can move his view to any location on
the array, he can scroll the screen, he can zoom in or out, he can
change voltage levels at any node in the circuit.
Now if I can hold all these objects in main memory then the user won't
have to wait for multiple pages to be made resident when he decides
to look at a different part of the circuit. Users, especially non-
technical ones, hate to wait.
I'm not saying that an application like this cannot be done in much
less memory, it has been. But even on a Symbolics (pretty much
the fastest widely available Lisp machine) it is slow, slow, SLOW.
>Now, I could see a lisp-machine type saying that only garbage
>collecting on Xmas day would be a big win, if they could actually
>accomplish that, and would otherwise run 'reasonable' programs.
>Somehow though I suspect it won't work that way. More like the machine
>down every Sunday for garbage collection (though I suppose many
>long-running applications could be checkpointed to disk and a simple
>re-boot would suffice.)
This is pretty much exactly what happens. To my knowledge the Symbolics
at a certain university (not the one I'm at now) has never had to
garbage collect during a run session. When a session is over the world
is saved and a garbage collection is run. This is really a function
of a large virtual memory space, and has nothing much to do with
physical memory space.
It certainly would take a long time to garbage collect 1-4Gb. Fortunately
there are things like incremental garbage collection, parallel garbage
collection, and garbage collection hardware to help out. All I've ever
said is that a global garbage collection would be much faster if the whole
world were resident in physical memory.
>Ok, but still obviously not cost-effective (the magic ingredient that
>gets thrown out whenever this topic starts getting discussed, 1GB of
>memory is going to cost you around $1M [there's more than chips
>involved, don't just tell me the 1MB price * 1,000, you'll need
>backplane, power-supplies etc etc, if your figures come to $500K,
>fine, same thing], how many of us would buy a lisp-machine to run one
>application for $500-$1M? $250K?)
>
> -Barry Shein, Boston University
If you're going to use todays cost figures the whole discussion, which
originally asked about large physical memories for minicomputers, becomes
a little ridiculous. I certainly expect memory prices to keep going
down until the physical limits of chip manufacturing are reached. I
think we are still a good ways away from that wall.
I will argue no more. I think that if you give me memory for free, I'll
take as much as I can get for a single-user system, up to the limit of
the logical address space.
Jim Nusbaum
Kenneth Ng
>
> I think my definition of virtual memory might be out of synch with
> others. Cheap large memories mean that we would be able to do away
> with demand paging.
Memory may be becoming cheaper, but the addressing range of processors
is becoming bigger. The IBM XA (I think) is supposed to support 31
bit addressing, and the Intel 386 is supposed to address 48 bit
addressing! We still have several generations to go, unless we
settle for very BIG memory boards.
> Jerry Natowitz (HASA - A division)
> Bell Labs HR 2A-214
> 201-615-5178 (no CORNET)
> ihnp4!houxm!hropus!jin
> or ihnp4!opus!jin
--
Kenneth Ng: Post office: NJIT - CCCC, Newark New Jersey 07102
uucp(for a while) ihnp4!allegra!bellcore!argus!ken
*** WARNING: NOT k...@bellcore.uucp ***
!psuvax1!cmcl2!ciap!andromeda!argus!ken
bitnet(prefered) k...@orion.bitnet
--- Please resend any mail between 10 Aug and 16 Aug:
--- the mailer broke and we had billions and billions of
--- bits scattered on the floor.
Ed Gould
>"Virtual memory", strictly speaking, refers to memory that acts like it's
>always there but sometimes isn't.
I would quibble slightly. To me, virtual memory refers to a memory space
that is different than the physical memory of the machine. A PDP-11
has a virtual memory space of 2^16 bytes, or perhaps 2*2^16 bytes. But
some models of the machine have a physical memory space of nearly 2^22
bytes.
This is not what most people - including me - usually mean when casually
talking about virtual memory. Then, it does refer to a virtual space that
is larger than the available physical space (available either because
the remainder is allocated to other uses, or not physically present),
and is managed by some technique like demand paging that allows partly-
resident processes to execute.
--
Ed Gould mt Xinu, 2560 Ninth St., Berkeley, CA 94710 USA
{ucbvax,decvax}!mtxinu!ed +1 415 644 0146
"A man of quality is not threatened by a woman of equality."
Greg Noel
>> ... Does virtual memory imply demand paging or just address translation?
>
>"Virtual memory", strictly speaking, refers to memory that acts like it's
>always there but sometimes isn't. That is, demand paging or some analogous
>scheme (paging is not the only memory-management technique possible, and
>demand paging is not the only page-fetching policy possible). Address
>translation, by itself, is not virtual memory.
Hmmmmm..... I think I want to take issue with this. Although what Henry
says is valid, his point is too narrow. Two immediate counter-examples are
the SDS-940 (later the XDS-940) and the PDP-11, both of which are virtual-
memory machines, and yet essentially just only do address translation. (I
know, I know, later versions of the PDP-11 can restart instructions; the
point remains.)
Perhaps more to the point would be to say that the memory image seen by the
program is independent of the real memory provided by the machine. That is,
the operating system can assign arbitrary portions of real memory to the
program and this mapping can change over time.
In this context, some amusing definitions:
Real: You've got it, and you know you've got it.
Transparent: You've got it, but you don't know you've got it.
Virtual: You don't have it, but you don't know it.
--
-- Greg Noel, NCR Rancho Bernardo Gr...@ncr-sd.UUCP or Gr...@nosc.ARPA
Wayne Knapp
Just because you have a large memory doesn't mean you have to use all
of it for running progams. How about:
1. Move your file system in to memory. ( Big bennifits.)
( Just back up the memory image every so often )
2. Increasing your working memory space as the work load increases.
( Hey it is stupid design to make the operation system worry about
9999 Gbytes when you only need 2 Mbytes. )
3. Huge neat programs and experiments. Virtual memory is a drag! I want
progams to fly. Give me 1000 Gbytes of linear space for my program.
I have options to check things to do, can't wait for slow IO.
4. Storing full length movies in Ram, and view by page flipping.
5. Hiding stuff from system cops.
6. Wow! I could use some really big lookup tables to speed up
calculations.
7. Recursion anyone? How about recursive compilers, hmm makes me wonder.
* many more things I haven't even dreamed of yet!
Okay so page tables are a little bigger, big deal you have room to spare.
It is your own problem if you think you have to maintain tables for the whole
memory. Programs are larger, but who cares. Bring on the big memories, I
for one can make use of them!
Wayne Knapp
P.S. The only problem I see is ram testing. Maybe a second processor
would be useful. There should be at least two processors in every pot anyway.
Kendall Auel
>In article <70...@utzoo.UUCP> he...@utzoo.UUCP (Henry Spencer) writes:
>>> ... Does virtual memory imply demand paging or just address translation?
> ... Perhaps more to the point would be to say that the memory image seen by
> the program is independent of the real memory provided by the machine.
I had always thought that virtual memory meant address translation only, and
that a memory hierarchy (cache, RAM, disk, tape, ...) did not necessarily
exist in a virtual memory system. When I looked it up, however, my textbooks
speak of virtual memory as a way to map backing store into the address space
of the processor:
"Virtual memory is a technique which allows the execution of
processes that may not be completely in memory. The main visible
advantage of this scheme is that user programs can be larger
than physical memory."
- Peterson & Silberschatz; _Operating_Systems_Concepts_
"Virtual memory provides the user with a memory that can be larger
than physical Mp. The virtual memory system handles overlays in a
user-transparent manner by deferring the binding between user and
physical addresses until instruction execution time."
- Siewiorek, Bell, Newell; _Computer_Structures:_Principles_and_
Examples_
I got two points from this reading. 1) Virtual memory *technically* implies
only address translation, and 2) The main advantage to using virtual memory
is to extend physical memory via a backing store (disk, drum, ...). Thus, the
concept of virtual memory for all intents and purposes implies swapping memory
to and from a disk, as well as address translation.
Kendall Auel
Tektronix, Inc.
Stanley Friesen
>Zeroing of pages need not be done all at once.
>Right now, if you have extra memory lying about (unusual yes, but read on),
>it does not get 0'd until somebody grabs a "blank" page. How about a mode
>like "0 on reference"? There is "copy on write" in some places, why not?
>Then you only have to worry about 1 page at a time. Extra swap space is not
>costing you anything, why should extra memory? Huh?
As a matter of fact demand-paged UNIX's(Sys Vr2+ & BSD 4.x) do exactly
that! They call them zero-fill pages. It is implemented using page
table entries with the valid bit off and a software flag marking the
entry a zero-fill page. On a page fault from such a page the kernal
allocates a free page frame and zeros it.
---
Sarima (Stanley Friesen)
UUCP: {ttidca|ihnp4|sdcrdcf|quad1|nrcvax|bellcore|logico}!psivax!friesen
ARPA: ??
Jon Krueger
>I have a VLSI CAD system which divides the chip surface into small squares.
>any location on the array, he can scroll the screen, he can zoom in or out,
>he can change voltage levels at any node in the circuit.
>
>Now if I can hold all these objects in main memory then the user won't
>have to wait for multiple pages to be made resident when he decides
>to look at a different part of the circuit. Users, especially non-
>technical ones, hate to wait.
1) You have non-technical users who use your VLSI CAD system?
2) You find it unacceptable to wait for objects to page in, but it's
acceptable to wait for the entire working set to be made resident
every time you run the system or look at a new chip? Seems like
the latter will take a lot longer than the former. Now you'll
argue, "Sure, but it'll happen less often!" How true. It'll
also happen less often that a user will examine an less-recently
examined object than a more-recently-examined.
In other words, you don't want to make the user wait for some objects
more than others. He should be able to perform any operation on any
object with good, predictable, response time. It's ok that you may
waste memory in keeping resident most objects which are never required.
Perhaps your application is small enough and your memory is large
enough so you can afford to waste memory. But there will be a cost
associated with doing business this way: startup time will be
the time required to make the entire chip representation resident,
roughly the speed of your disk. You'll pay this price whenever you
save changes to your chip, examine a new chip, or quit the application.
If you think paging in a few pages is slow, wait until you see
how long it takes to completely read in or write out every page,
whether needed or not, accessed or not, modified or not.
>I will argue no more. I think that if you give me memory for free, I'll
>take as much as I can get for a single-user system, up to the limit of
>the logical address space.
>
>Jim Nusbaum
If you give me address bits for free, I'll take as much as I can, up to some
reasonable limit (2^200 perhaps?), and build environments and applications
that make smooth and intelligent tradeoffs between current memory prices,
application sizes, and required performance levels, and that automatically
move the tradeoffs to reflect changes in memory prices. A virtual memory
system with LRU demand paging is the popular solution. I'm sure better ones
will emerge. Ever-bigger physical configurations are not a solution.
They're a new set of problems...
-- 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
Henry Spencer
> >always there but sometimes isn't. That is, demand paging or some analogous
>
> Hmmmmm..... I think I want to take issue with this. Although what Henry
> says is valid, his point is too narrow. Two immediate counter-examples are
> the SDS-940 (later the XDS-940) and the PDP-11, both of which are virtual-
I assure you that the PDP-11 is *not* considered a virtual-memory machine,
not by DEC, not by anyone who knows the machine and knows what the words
mean. (Well, you can sort of do virtual memory on the 11, but none of the
popular operating systems bother.) Why do you think the Berkeley Unixes
also go by the name "VMUNIX"? The "VM" part stands for "virtual memory",
which earlier Unixes -- on the 11, and on the VAX with address translation
but no demand paging -- were not.
> Perhaps more to the point would be to say that the memory image seen by the
> program is independent of the real memory provided by the machine...
This would be a reasonable meaning for the term "virtual memory", but it is
not the standard one. Check any good operating-systems textbook.
Henry Spencer
> >always there but sometimes isn't.
>
It would be reasonable to use "virtual memory" to denote that concept, but
that is not in fact the concept that it *does* denote. In the same way,
"RAM" stands for "random-access memory", which one would think should include
things like EPROMs... but in fact "RAM" is now an idiom whose meaning is
not identical to the literal meaning of the words it is derived from. So
with "virtual memory".
> This is not what most people - including me - usually mean when casually
> talking about virtual memory...
That's because your casual talk uses the phrase in its correct, idiomatic,
meaning, rather than attempting to read it literally and impute to it a
meaning that it never had.
Henry Spencer
A potentially useful approach, but remember that most file systems contain
a modest amount of heavily-used stuff and a lot of seldom-used stuff. It
may be better to use that memory for a big, intelligently-managed buffer
cache, which will give 90% of the speedup while using 10% of the memory.
(Or, alternatively, will give 90% of the speedup for a filesystem ten times
as large, using the same amount of memory.)
> 7. Recursion anyone? How about recursive compilers, hmm makes me wonder.
The PDP11 cc, running in a distinctly small address space, is a recursive
design.
Henry Spencer
> that a memory hierarchy (cache, RAM, disk, tape, ...) did not necessarily
> exist in a virtual memory system. When I looked it up, however, my textbooks
> speak of virtual memory as a way to map backing store into the address space
>
> I got two points from this reading. 1) Virtual memory *technically* implies
> only address translation, and 2) The main advantage to using virtual memory
Can you explain how you arrived at those points from the evidence presented?
Your textbooks clearly state that virtual memory IS the extension of physical
memory via a backing store. They are correct; the phrase first came into
use to describe exactly that concept. It's true that its literal meaning is
a bit different, but that's true of any idiomatic term. The literal meaning
of "computer" is "something which computes, i.e. does arithmetic". This then
includes a human with a slide rule (in fact, fifty years ago "computer" was
the job title for a desk-calculator operator) and probably does not include
a database machine (which does little or no arithmetic). But that's not the
meaning normally understood for "computer".
Greg Noel
>In article <11...@ncr-sd.UUCP> gr...@ncr-sd.UUCP (Greg Noel) writes:
>> the program is independent of the real memory provided by the machine.
>I had always thought that virtual memory meant address translation only, and
>that a memory hierarchy (cache, RAM, disk, tape, ...) did not necessarily
>exist in a virtual memory system.
This is true. In fact, I have seen a design for an embedded computer with no
backing store that used virtual memory to improve its real memory utilization.
The tasks ran in a largish virtual space and the unallocated memory simply
wasn't mapped. The memory allocator had some heuristics to minimize the number
of pages occupied and didn't hesitate to leave large sections of the virtual
memory unused and unmapped. Typically, fragmentation causes you to run out of
space when there is as much as one-third of the memory still available (see
Knuth, Vol. I for details); with this scheme, we could depend upon functioning
with over 90% utilization, and often over 95% -- it was like adding half again
as much memory......
I wish my Amiga used this trick; it's irritating to run out of memory when
the system claims that it still has 220K free.......
>When I looked it up, however, my textbooks
>speak of virtual memory as a way to map backing store into the address space
>of the processor: [.... quotes deleted .....]
>
>I got two points from this reading. 1) Virtual memory *technically* implies
>only address translation, and 2) The main advantage to using virtual memory
>is to extend physical memory via a backing store (disk, drum, ...). Thus, the
>concept of virtual memory for all intents and purposes implies swapping memory
>to and from a disk, as well as address translation.
An accurate assessment, I think. Although there are reasons to separate the
two concepts, they work so well together that it is hard to consider them
independantly.
Jim Giles
>...
>2) You find it unacceptable to wait for objects to page in, but it's
>acceptable to wait for the entire working set to be made resident
>every time you run the system or look at a new chip? Seems like
>the latter will take a lot longer than the former. Now you'll
>argue, "Sure, but it'll happen less often!" How true. It'll
>also happen less often that a user will examine an less-recently
>examined object than a more-recently-examined.
This assumes that the CAD system is written VERY badly. The system
should be able to function perfectly well without it's entire working
set. It should only read in that part of the data which is required
to satisfy the users request.
"Aha!" you say. "That's what virtual memory does!" And you're right.
But, by making this paging a responsibility of the CAD system instead
of the hardware, you allow those applications which don't need virtual
memory to proceed without the overhead of a slow memory interface.
J. Giles
Los Alamos
Eric Lee Green
Re: What is virtual memory?:
One of the big programmer benefits of modern operating systems is that
they give each user his own "virtual machine" to run his programs on,
that is, to some extent, each program thinks it has the machine all to
itself, and doesn't have to worry about what other processes are
doing. Virtual memory is basicaly the "memory" of this virtual
machine. For example, in the PDP-11 example -- each process thought it
was running on a 64K machine. While on this Vax, each program thinks
it is running on a 4 gigabyte machine. While on the 80286, the
machine's virtual memory consists of the fact that it makes it look to
each process as if it can access 64,000 64k segments. Note that paging
is not the only way to do things -- the 80286 has no paging and yet
its memory management scheme certainly qualifies as "virtual memory",
while the PDP-11 also swapped out its 64K segments when something else
needed to be run. But, basically, the point is:
a) Each process is given its own virtual machine, which has a constant
amount of memory, so that
b) programs can be designed for that virtual amount of memory, and do
not have to contain a bunch of special clauses for when the actual
physical amount of memory changes sometime in the future.
The grossest abuse of course is VM, where not only do they make it
look like the process is running on its own processor, but has its own
directly addressible i/o devices also. Talk about taking things to
extremes!
Eric
--
Eric Green {akgua,ut-sally}!usl!elg
(Snail Mail P.O. Box 92191, Lafayette, LA 70509)
-- Tengo lo mismo que doy y solo sirve al presente.
Jon Krueger
>The CAD system should be able to function perfectly well without its entire
>working set...It should only read in that part of the data which is required
>to satisfy the user's request...By making this paging a responsibility of the
>CAD system instead of the hardware, you allow those applications which don't
>need virtual memory to proceed without the overhead of a slow memory
>interface.
I can arbitrarily divide up applications into types as follows:
1. applications which fit into physical spaces and
available physical memory sizes
2. applications which can trivially manage their own
spaces, with acceptable development and maintainence
costs, which achieve comparable levels of performance
to their virtual memory equivalents
3. applications which can trivially manage their own
spaces, with acceptable development and maintainence
costs, which achieve higher levels of performance
than their virtual memory equivalents
4. applications which can be made to manage their own
spaces, but cost more or perform less than their
virtual memory equivalents
5. applications with no known algorithms to manage their
own space, which could conceivably by made to do so at
some cost in development or performance
Applications of type 1 and 2 don't require large spaces, either physical or
virtual. You point out that they would run faster without virtual address
translation. You've got me there. For a given space into which an
application fits, it will run faster if the space is physical. If your
applications don't require any other benefits of virtual memory, such as
memory protection or easy relocation, you're free to run them in your
favorite physical space. You can now buy small physical spaces cheaply and
easily. The demands of such applications are not a significant
architectural problem in 1986.
I invite anyone to submit examples of type 3. I haven't got any, but I
suspect there are a few.
Applications of type 4 and 5 require or benefit from large spaces. It has
been shown elsewhere that virtual spaces provide the same spaces as physical
ones, at 10% of the cost for 90% of the performance.
The problem seems to be that you're running applications of type 1 and 2 on
systems designed to handle types 4 and 5. I suggest you move them to small,
cheap, systems. If you don't need the benefits of virtual memory, you
shouldn't be asked to pay its costs. Has anyone seen a multiprocessor scheme
where some processors maintain physical spaces and others virtual? I'll
take one where the kernel moves each image to the first free processor that
supports an appropriately sized space, where the larger spaces are more
likely to be virtual, and the smaller ones physical. Anyone heard of such a
beast?
-- jon
--
--> Jon Krueger
uucp: {seismo, allegra, decvax, cmcl2, topaz, harvard}!rochester!ur-tut!tuba
Phone: (716) 275-2811 work, 235-1495 home BITNET: TUBA@UORDBV
Jim Giles
>...
> spaces, with acceptable development and maintainence
> costs, which achieve higher levels of performance
> than their virtual memory equivalents
>I invite anyone to submit examples of type 3. I haven't got any, but I
>suspect there are a few.
Yes, quite a few! It is my opinion that a large share of all scientific
computing falls into this category. Certainly several of those I've
written (parts of) or used.
I wrote an EMP simulation code (Electro-Magnetic Pulse), for example, which
was essentially a large 3-d grid with a satellite model inside - you hit it
with x-rays and iterate Maxwell's equations on the grid. Maxwell's
equations require you to keep 9 numbers for each position in the grid: 3
Electric field components, 3 Magnetic field components, and 3 current
density components (x-rays knock free charges off the body of the satellite
and the drift of these charges through the EM field cause current).
Now, take a rectangular grid that's 100 cells on a side: or 1 Million cells
(100^3). That's 9 million floating point numbers for the grid. This
clearly didn't fit in the CDC 7600 I was using at the time (1975), so
I had to 'page' the grid. This was made fairly easy by the cyclical
nature of the required accesses: as soon as I was done with a plane
(that is: I had updated a plane of the grid and all its neighbors) I
could flush it out to disk and start reading the furthest ahead plane
that would now fit (so that the input MIGHT complete before I needed the
data).
Note that the 'paging' activity took place in a natural dividing point
of the code: outside the 'plane' loop. As a result of this, the inner
2 loops of the code (a 3-d loop, remember) were optimized as if the whole
problem fit memory. Smaller grids were handled similarly - only the
'paging' might be done on a number of planes of the grid instead of one at
a time. On a large grid, the 'paging' scheme could be moved into the next
lower loop and the 'pages' would have been half-planes or even strips of
the grid. For a very small grid (one that almost fits memory), the paging
scheme could be modified to swap only a few planes (the actual technique
was to keep the whole grid of each component of the field that would fit
and only page the remaining components of the field).
Since all the paging activity was isolated in the outer loops of the code,
and since there was no additional address decoding circuitry in the memory
interface, I claim that this code clearly works faster than it would
have on a VM system. I had no VM computer to benchmark against at the
time, so I don't have numbers to prove this claim (even if you were
likely to believe benchmark results that you couldn't test yourself).
Very many scientific codes have similar structure to the one described
above: all finite differencing codes - of course, finite element codes,
etc.. Since this is the case I claim that your class 3 set is well
occupied by real world production programs.
J. Giles
Los Alamos
ag...@ccvaxa.uucp
... > Large main memories... Scientific codes can effectively do their
... > own memory management, and do not need to be penalized by VM HW.
J. Giles et al have pretty much persuaded me that virtual memory isn't
always a good thing (it wasn't hard - I was already there).
But, unless you are selling computers strictly to the non-virtual scientific
crowd, a computer manufacturer will probably want to have virtual memory for
his general purpose customers. Your market offering might run like this:
1. A general purpose machine/OS with virtual memory
1'. The ability to turn off virtual memory in machine/OS 1,
for efficiency of important scientific codes.
2. A strictly scientific machine that doesn't have virtual memory
hardware at all, so scientific codes that don't use virtual
memory pay no penalty at all.
Assumption: you will probably want these machines to be architecturally
compatible, to save development cost for peripherals and assembly language
code, and so that marketing can tell customers that you have a binary
compatible family of machines... (sigh).
Q1: What features should a machine have so that it can span both virtual and
non-virtual systems?
Q2: In the non-virtual, scientific, machine 2 do you really want to be
running a multi-tasking system?
Q3: In a multi-tasking OS, can you mix virtual and non-virtual processes?
If the answer to Q2 is no, you're running a batch system, and you don't
need much special support in the instruction set, at least, to span virtual
and non-virtual systems. Same thing even if you are doing batch style
multitasking, so long as you don't need to swap processes out and move
them around in core.
What if your customers' answer to Q2 is yes? (Cray seems to think so, with
their UNIX). If you need to swap processes out and dynamically relocate them
in core, what IS features do you need?
I think this question was answered a long time ago - base registers.
Now, my real question is what exactly you need to make base registers useful.
Any takers?
I'm not sure that Q3 is an important question. You're only going to mix
virtual and non-virtual processes if there is a speed advantage to be gained
by turning off translation. Ie. running with the identity map would be
equivalent, except for TLB misses.
Andy "Krazy" Glew. Gould CSD-Urbana. USEnet: ihnp4!uiucdcs!ccvaxa!aglew
1101 E. University, Urbana, IL 61801 ARPAnet: aglew@gswd-vms
jo...@peora.uucp
>shouldn't be asked to pay its costs. Has anyone seen a multiprocessor scheme
>where some processors maintain physical spaces and others virtual? I'll
I haven't seen it done on a processor basis, but I've seen it
done on a task by task basis. On our OS32MT operating most tasks
run in real memory, but you can specify a virtual task manange-
ment option at link time. All tasks run with address relocation
hardware enabled, while virtual tasks actually have routines
to handle page faults linked in. This means that the size of
the working set of the task is fixed at load time, rather
than sharing a common pool with other virtual tasks. There is
an additional problem in that the page size is a rather
unwieldy 64KB.
Also on MVS back on IBM mainframes there is a V=R where the
whole task is loaded into a contiguous chunk of real memory.
This was generally used with small tasks with critical
performance.
--
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
Greg Noel
>I assure you that the PDP-11 is *not* considered a virtual-memory machine,
>not by DEC, not by anyone who knows the machine and knows what the words
>mean.
That's an awfully snippy comment. Just because the virtual space is smaller
than the physical doesn't mean that it isn't a virtual machine.
>Why do you think the Berkeley Unixes
>also go by the name "VMUNIX"? The "VM" part stands for "virtual memory",
>which earlier Unixes -- on the 11, and on the VAX with address translation
>but no demand paging -- were not.
"You can call a tail a leg, but that doesn't make it one."
(Actually, that's not quite correct, either. Indeed, "VMUNIX" is a virtual
memory operating system -- but then, so were the earlier ones.)
I will agree that an extremely strong motivation for virtual memory is so
that you are not required to have all of your program residing in physical
memory. I will even agree that most virtual memory systems use some form
of paging (or whatnot) for memory management -- but that doesn't mean that
the concepts are the same, or that virtual memory mandates paging. There
are other, perfectly valid reasons to have virtual memory.
I think the problem here is one of age. Henry is probably too young to have
heard the terms used correctly and is using the (usually very reasonable)
assumption that if A and B always occur together, then A implies B. On the
other hand, I worked on the Project Genie time-sharing system (one of the two
original ARPA-funded time-sharing projects; the other was Project Multics),
so I can claim some degree of expertise on the topic.
The fundamental concept of virtual memory is that a large name space (the
virtual memory) can be partially mapped to a smaller name space (the physical
memory) with the remainder of the space unmapped. Uttering a name that is
not mapped causes some sort of an exception mechanism, but the semantics of
that exception are not part of the virtual memory model. Admittedly, the
concept is not terribly interesting unless you postulate some exception
semantics, but paging is just one potential set of exception semantics, not
the \only/ one.
Henry Spencer
> I think the problem here is one of age. Henry is probably too young to have
> heard the terms used correctly and is using the (usually very reasonable)
This is an amusing juxtaposition. Greg, please see any good computer-science
dictionary and encyclopedia for the *modern* meaning of "virtual memory".
What it was considered to mean twenty years ago is not relevant; that's a
very long time ago in this field. The meanings of words are defined by how
they are used, not by how they used to be used.
Phil Ngai
>
>>I assure you that the PDP-11 is *not* considered a virtual-memory machine,
>>not by DEC, not by anyone who knows the machine and knows what the words
>>mean.
>
>That's an awfully snippy comment. Just because the virtual space is smaller
>than the physical doesn't mean that it isn't a virtual machine.
I think there is a confusion here on Greg's part between virtual
address space and virtual memory. No one who has studied PDP-11 memory
management will deny that some PDP-11s support virtual addressing. In
fact, VAX stands for Virtual Address eXtension, implying that the
virtual address concept is not new to DEC's product line. However,
this is not the same as virtual memory, as Greg seems to think. The
VAX architecture handbook goes on to say "a virtual memory system is
used to provide a large address space while allowing programs to run
on hardware configurations that actually have smaller memory sizes."
>>Why do you think the Berkeley Unixes
>>also go by the name "VMUNIX"? The "VM" part stands for "virtual memory",
>>which earlier Unixes -- on the 11, and on the VAX with address translation
>>but no demand paging -- were not.
>
>"You can call a tail a leg, but that doesn't make it one."
>
>(Actually, that's not quite correct, either. Indeed, "VMUNIX" is a virtual
>memory operating system -- but then, so were the earlier ones.)
I don't see any basis at all for this claim that the earlier forms of
Unix were virtual memory operating systems. Virtual address space,
yes, for memory management is very important to a multi-tasking
operating system. But virtual memory, no.
--
DIP stands for DECnet-DOS Installation Procedure.
Phil Ngai +1 408 749 5720
UUCP: {ucbvax,decwrl,ihnp4,allegra}!amdcad!phil
ARPA: amdcad!ph...@decwrl.dec.com
Bruzzini
> dictionary and encyclopedia for the *modern* meaning of "virtual memory".
From my dictionary of computer terms:
virtual memory: The mapping of a program address into a physical memory
address, usually done by hardware.
paging: The operation of moving pages of information to and from
secondary storage
Daryl Monge NET: ihnp4!ihelp!dlm
AT&T CIS: 72717,65
Bell Labs
Naperville, Ill.
Jim Giles
>What it was considered to mean twenty years ago is not relevant; that's a
>very long time ago in this field. The meanings of words are defined by how
>they are used, not by how they used to be used.
Quite so. I remember when 'hacker' was a derogatory term. I still use
it that way, but no one else seems to.
J. Giles
Los Alamos
t...@cae780.uucp
>
> From my dictionary of computer terms:
>
> virtual memory: The mapping of a program address into a physical memory
> address, usually done by hardware.
>
>
> AT&T CIS: 72717,65
> Bell Labs
> Naperville, Ill.
I don't know which computer dictionary you are using. To me,
virtual memory is a logical memory. The address space of
virtaul memory is, usually, >> that of physical one. The
mapping is just a mechanism to convert the logical memory
space to the physical one (in run time). I believe you
need a better dictiionary.
Richard Mateosian
>>used to be used.
>Quite so. I remember when 'hacker' was a derogatory term. I still use
>it that way, but no one else seems to.
I remember when 'mainframe' meant 'the computer' (as opposed to the tape
unit or the card reader or the I/O channel -- other big gray boxes in the
computer room).
Richard Mateosian ...ucbvax!ucbiris!srm 2919 Forest Avenue
415/540-7745 s...@iris.Berkeley.EDU Berkeley, CA 94705
Jeff Gilliam
that "virtual memory" is an ill-defined term. Let us accept that fact
and get on to other topics.
--
Jeff Gilliam {ucbvax,pyramid,nsc}!voder!jeff