aarons@cvaxa.sussex.ac.uk (Aaron Sloman) (05/23/88)
Several news-posters have commented on the requirement for paged virtual
memory systems (or the lack of requirement with falling costs of
memory).
There is one reason I want VM that has not been mentioned, namely that
many of the more sophisticated software packages sitting on disk are so
large that without the ability to start running after a few pages have
been read in, process start-up time is much too long.
It can be even worse if you have to read in the whole system across
ethernet. Starting up a big process from a diskless Sun PAGING over
ethernet is much faster than if the whole image had to be read in.
The argument depends on the fact that the kind of package I am talking
about has very many facilities within it with only a small, but
unpredictable, subset required for any one session of use.
Perhaps there are memory management techniques I am unaware of that
make it easy for portions of a large program to be read in as required,
without the cost of full virtual memory.
Anyhow, while disk access remains significantly slower than main memory,
something like paged virtual memory will remain highly desirable for
those of us who want to use large sophisticated software packages like
AI development environments, powerful editors, etc. EVEN if there is
enough physical memory for the whole package.
Aaron Sloman,
School of Cognitive Sciences, Univ of Sussex, Brighton, BN1 9QN, England
ARPANET : aarons%uk.ac.sussex.cvaxa@nss.cs.ucl.ac.uk
JANET aarons@cvaxa.sussex.ac.uk
BITNET: aarons%uk.ac.sussex.cvaxa@uk.ac
As a last resort (it costs us more...)
UUCP: ...mcvax!ukc!cvaxa!aarons
or aarons@cvaxa.uucpok@quintus.UUCP (Richard A. O'Keefe) (05/25/88)
In article <463@cvaxa.sussex.ac.uk>, aarons@cvaxa.sussex.ac.uk (Aaron Sloman) writes: > Perhaps there are memory management techniques I am unaware of that > make it easy for portions of a large program to be read in as required, > without the cost of full virtual memory. It depends on whether you identify "virtual memory" with paging: in a (genuine, not INTEL) segmented sytem (think of the OOZE system) you can bring into physical memory just the objects you currently need. The B6700 could and did page large data arrays, but it couldn't page code. Since each procedure was a separately swappable segment, that didn't matter much. No page tables, but easy partial loading.
billo@cmx.npac.syr.edu (Bill O) (05/25/88)
In article <1016@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >In article <463@cvaxa.sussex.ac.uk>, aarons@cvaxa.sussex.ac.uk (Aaron Sloman) writes: >> Perhaps there are memory management techniques I am unaware of that >> make it easy for portions of a large program to be read in as required, >> without the cost of full virtual memory. >... >The B6700 could and did page large data arrays, but it couldn't page >code. Since each procedure was a separately swappable segment, that >didn't matter much. No page tables, but easy partial loading. The B6700, at least the one that I knew and loved :-), did not do "paging" of either data or code. Yes, procedures were in their own segment -- that is the normal logical partitioning of code space. And data was also partitioned logically into segments; examples: rows of an array, stack trunks, heaps, etc. The "swapping" of these segments (code or data) is analogous to paging, but substitutes hardware-supported manipulation and checking of segment descriptors for TLB's and the like. (There's really no "free lunch" in the world of demand-driven loading and virtual memory.) It should also be said that demand-driven loading is as old as the hills, and pre-dates virtual memory. It used to be called "overlays". To do overlays one instructed the linker to link certain procedure calls to special procedures which loaded the appropriate code segment. The special procedure could be set-up to first check and see if the segment was already loaded, and just jump to it in that case. The cost here was a more expensive calling protocol, but not for every call -- only the ones which were requested to be overlays. The word overlay refers, of course, to the "virtual memory" aspect of this method: newly loaded procedures could replace ones already loaded. Overlays could be a really effective memory management tool in some cases, and I think they may still available as an option in some pc linkers. Bill O'Farrell, Northeast Parallel Architectures Center at Syracuse University (billo@cmx.npac.syr.edu)
jlg@beta.UUCP (Jim Giles) (05/26/88)
In article <463@cvaxa.sussex.ac.uk>, aarons@cvaxa.sussex.ac.uk (Aaron Sloman) writes: > [...] > Anyhow, while disk access remains significantly slower than main memory, > something like paged virtual memory will remain highly desirable for > those of us who want to use large sophisticated software packages like > AI development environments, powerful editors, etc. EVEN if there is > enough physical memory for the whole package. One of the things that makes virtual memory LESS useful than it used to be is the fact that disk is so slow compared to main memory (and CPU speed). If it takes less than the disk access time for your program to execute through a whole page of code, a busy multiprocessing environment may spend nearly all its time waiting on page faults. What's really needed is some form of mass storage that is faster than disk - implement a paging scheme off the intermediate storage (which in turn can page off disk in larger chunks?). In any case, fast startup is a minor convenience. The important thing is response time while running and turnaround for compute intensive jobs. To an extent, both of these requirements are incompatible with paging if the disk is VERY much slower than the CPU. There are no easy answers here.
ok@quintus.UUCP (Richard A. O'Keefe) (05/26/88)
In article <1016@cresswell.quintus.UUCP> I wrote > The B6700 could and did page large data arrays, but it couldn't page > code. Since each procedure was a separately swappable segment, that > didn't matter much. No page tables, but easy partial loading. > In article <508@cmx.npac.syr.edu>, billo@cmx.npac.syr.edu (Bill O) writes: > The B6700, at least the one that I knew and loved :-), did not do > "paging" of either data or code. Yes, it did page sufficiently large arrays. Look in the index under "segmented arrays". I think the page size was 256 48-bit words. (It was never quite clear from the manuals which things were written to disc with tag bits and which things were written without. Fortunately users never needed to know.) "DIRECT" and "VALUE" arrays were not paged.
dave@micropen (David F. Carlson) (05/26/88)
In article <19322@beta.UUCP>, jlg@beta.UUCP (Jim Giles) writes: > In article <463@cvaxa.sussex.ac.uk>, aarons@cvaxa.sussex.ac.uk (Aaron Sloman) writes: > > [...] > In any case, fast startup is a minor convenience. The important thing is > response time while running and turnaround for compute intensive jobs. > To an extent, both of these requirements are incompatible with paging > if the disk is VERY much slower than the CPU. There are no easy answers > here. I seem to remember that in BSD 4.1 on the VAX that a process was demand paged but in order to initialize the paging system the whole process needed to be loaded into core. Thus, the startup argument is specious. Is this correct or am I wrong as usual? -- David F. Carlson, Micropen, Inc. ...!{ames|harvard|rutgers|topaz|...}!rochester!ur-valhalla!micropen!dave "The faster I go, the behinder I get." --Lewis Carroll
stevew@nsc.nsc.com (Steve Wilson) (05/26/88)
In article <19322@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: >In article <463@cvaxa.sussex.ac.uk>, aarons@cvaxa.sussex.ac.uk (Aaron Sloman) writes: >> [...] >> Anyhow, while disk access remains significantly slower than main memory, >> something like paged virtual memory will remain highly desirable for >> those of us who want to use large sophisticated software packages like >> AI development environments, powerful editors, etc. EVEN if there is >> enough physical memory for the whole package. > >One of the things that makes virtual memory LESS useful than it used to be >is the fact that disk is so slow compared to main memory (and CPU speed). >If it takes less than the disk access time for your program to execute >through a whole page of code, a busy multiprocessing environment may spend >nearly all its time waiting on page faults. What's really needed is some >form of mass storage that is faster than disk - implement a paging scheme >off the intermediate storage (which in turn can page off disk in larger >chunks?). If a system is running below its "thrash" point, and assuming there are other useful things to do beside hang around in the idle loop, a multi-tasking system will suspend a job that ran into a page fault or blocked for I/O. At this point they'll move on to some other job. Also consider that USUALLY the execute-a-page then fault situation only occurs at process startup. This is where the concept of a "working set" comes from. Once that working set of pages is resident in main memory the occurance of page faults drop off. It makes more since to place more storage in the primary memory instead of an intermediate store. After all, that is where you want the code/data to wind up in the first place. Steve Wilson National Semiconductor [Universal disclaimer goes here]
tpmsph@ecsvax.UUCP (Thomas P. Morris) (05/27/88)
In article <19322@beta.UUCP>, jlg@beta.UUCP (Jim Giles) writes: > One of the things that makes virtual memory LESS useful than it used to be > is the fact that disk is so slow compared to main memory (and CPU speed). > If it takes less than the disk access time for your program to execute > through a whole page of code, a busy multiprocessing environment may spend > nearly all its time waiting on page faults. Your operating system doesn't have to actually page in only a single page of code or data at a time, though. Some operating systems use the concept of a `page fault cluster' or the number of pages of code or data which will be fetched from disk as a group upon a single `hard' page fault. (IE a fault which actually causes a read from disk) That way your OS can hide, to a certain extent, some of the cost of having to go to the disk. Yes, that first fault costs you a lot of time. But the time to read in 32 or 64 pages is not much worse than the time to read in just one. I would guess that if your program then only touches even ==one== of those other pre-paged/pre-fetched pages, instead of having to read it from the disk, then you have more than made up for the additional time it took to read 32 or 64 blocks, rather than just one. > ...... implement a paging scheme > off the intermediate storage (which in turn can page off disk in larger > chunks?). Exactly. See above. Your `intermediate storage' could, indeed, be your free-page list. That is, when your OS pre-fetches those pages, it could map only the `fault-causing' page into your working set. Those other pre-fetched pages could be added to the end of your free-page list, with your process's page table entries marking that they have been mapped, but are not currently valid. You need some other back-pointer lists, etc, but this is essentially the way that VMS handles its free-page list. When your process actually needs to touch any of those pre-fetched pages, if they are still on the free page list---not mapped to another process--- then you `soft fault' them from main memory into your working set. > > In any case, fast startup is a minor convenience. The important thing is > response time while running and turnaround for compute intensive jobs. > To an extent, both of these requirements are incompatible with paging > if the disk is VERY much slower than the CPU. There are no easy answers > here. You have to balance the cost of pre-fetching pages, not having those pages directly available to another process (on the free-page list), and the cost of giving your `compute intensive' jobs have such large working sets so that they only page in their initial pages and never fault again, against how the absolute loss of those pages is going to affect the page fault behaviour of your other processes. ----------------------------------------------------------------------------- Tom Morris BITNET: TOM@UNCSPHVX UNC School of Public Health UUCP : ...!mcnc!ecsvax!tpmsph ----------------------------------------------------------------------------- -- ----------------------------------------------------------------------------- Tom Morris BITNET: TOM@UNCSPHVX UNC School of Public Health UUCP : ...!mcnc!ecsvax!tpmsph -----------------------------------------------------------------------------
rcd@ico.ISC.COM (Dick Dunn) (05/27/88)
> One of the things that makes virtual memory LESS useful than it used to be > is the fact that disk is so slow compared to main memory (and CPU speed). > If it takes less than the disk access time for your program to execute > through a whole page of code, a busy multiprocessing environment may spend > nearly all its time waiting on page faults... Even if you have an older machine, where the disk:memory speed ratio isn't quite so horrible, the effect of paging up a program to get it running can be pretty appalling. A program will need a certain set of code and data to get going--for a typical C program, you need the page with crt0, some of the main program, scattered pieces of libc with stdio, the data for this stuff...it is common to see a program bring in a dozen pages which are quite predictable (from a static analysis of the program) in what might as well be considered random fashion. That's really expensive--disk transfer rates are no problem at all compared to seek and rotational latencies. Two things that ought to be worth trying: - Below some size threshold, unless you're really tight on physical memory, you might as well swap the whole program in instead of trying to let it fault itself in. - Could some analysis of code be used to derive a set of startup pages for a program? If so, you could list the pages in the object file somewhere--there's little point in starting up the program until you've got those pages present, and if you pre- load them all at once you can bring them in according to the best order for the disk (including not getting them mixed with requests from other programs running at the same time). -- Dick Dunn UUCP: {ncar,cbosgd,nbires}!ico!rcd (303)449-2870 ...If you get confused just listen to the music play...
ok@quintus.UUCP (Richard A. O'Keefe) (05/27/88)
I think it's worth introducing some clarification here. It's a pretty safe bet that Aaron Sloman had in mind programs like PopLog. This is an integrated "AI programming environment" containing Pop-11, Lisp (though why anyone would want Lisp when Pop is available ...), Prolog, and now, I believe, ML. Plus an extremely powerful editor called VED (VED is exceptional these days in owing nothing to Emacs). And then there is a very large library... To maximise the amount of shareable code, it would be nice to produce a "fully configured" image, but that could contain *many* megabytes of code. A typical program run once might touch only a megabyte (it might not, for example, use Lisp, though it probably would use VED). A *small* thump as chunks page in is ok, a *long* wait while the whole thing crawls in would not be. I imagine that packages like "S" are much the same: there is a very great deal of code which should ideally always "be there", but any one session is unlikely to use much of it. "Shared libraries" in SunOS 4.0 are *almost* what (classical) segmented machines provide, only clumsier, and they're relevant to this too.
paul@unisoft.UUCP (n) (05/28/88)
In article <508@cmx.npac.syr.edu> billo@cmx.npac.syr.edu (Bill O'Farrell) writes: >In article <1016@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >>In article <463@cvaxa.sussex.ac.uk>, aarons@cvaxa.sussex.ac.uk (Aaron Sloman) writes: >>The B6700 could and did page large data arrays, but it couldn't page > >The B6700, at least the one that I knew and loved :-), did not do >"paging" of either data or code. Yes, procedures were in their own Actually it did, the compiler made arrays bigger that 1023 words into things with doubly indirect pointers, the descriptor had a bit set (I think it was called 'segmented') that ment that when it was accessed it split the array into 256 word chunks, and referenced and array of normal descriptors, which in turn referenced the real memory (some of which could be paged). This of course was slower and (I think) the string opcodes didn't work on them, hence the Algol construct 'long array' which was how you created a non segmented array .... I too remember the 6700 with fond memories .... and for the Unix people out there - it had 'streams', of course called by a different name and with many of the details different but one could create an MCS with all the same functionality (and we did ...) Paul -- Paul Campbell, UniSoft Corp. 6121 Hollis, Emeryville, Ca E-mail: ..!{ucbvax,hoptoad}!unisoft!paul Nothing here represents the opinions of UniSoft or its employees (except me) "Nuclear war doesn't prove who's Right, just who's Left" (ABC news 10/13/87)
jlg@beta.UUCP (Jim Giles) (05/28/88)
In article <5129@nsc.nsc.com>, stevew@nsc.nsc.com (Steve Wilson) writes: > [...] Also consider that USUALLY the execute-a-page then fault situation > only occurs at process startup. This is where the concept of a "working > set" comes from. Once that working set of pages is resident in main memory > the occurance of page faults drop off. This is true for many programs, but the 'working set' idea only works for the code image of most scientific programs. The data image is often updated completely for each 'time-step' of a simulation, for example. Since data is MUCH larger than code these days, this could lead to constant page faulting. This problem is an example of the original statement I made on this subject: when the ratio of CPU speed to disk speed is high, virtual memory is not as attractive. The problem is not solved by such schemes as having larger page sizes or loading more than one page during page fault resolution - the issue still arises when the CPU gets faster in the next machine generation. And both these solutions make a page fault even more of a delay for the program. The basic issue here is that perhaps there are types of programming environments that don't benefit from virtual memory - especially if large memory machines are available.
chris@mimsy.UUCP (Chris Torek) (05/30/88)
In article <495@micropen> dave@micropen (David F. Carlson) writes: >I seem to remember that in BSD 4.1 on the VAX that a process was demand paged >but in order to initialize the paging system the whole process needed to be >loaded into core. No; the whole process is (and has been) loaded initially only for NMAGIC executables. The linker defaults to ZMAGIC (demand-paged-in). 4.1BSD did compile /usr/ucb/Mail with -n (NMAGIC). -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
chris@mimsy.UUCP (Chris Torek) (05/30/88)
In article <5149@ecsvax.UUCP> tpmsph@ecsvax.UUCP (Thomas P. Morris) writes: >Summary: You can cluster or prepage, too 4BSD does both. Prepaged pages are put on the free list and are available for reclaiming when referenced. The clustering is called `klustering' to distinguish it from 4BSD's other kind of clustering, which is simply treating several hardware pages as though they were a single page, to compensate for the small page size on the Vax. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
stevew@nsc.nsc.com (Steve Wilson) (05/31/88)
In article <19496@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: >In article <5129@nsc.nsc.com>, stevew@nsc.nsc.com (Steve Wilson) writes: >> [ Lotsa stuff deleted here] > >This is true for many programs, but the 'working set' idea only works >for the code image of most scientific programs. The data image is often >updated completely for each 'time-step' of a simulation, for example. >Since data is MUCH larger than code these days, this could lead to >constant page faulting. Yes, you've reached the point of thrashing which is DEATH to any application. I would suggest that you've reached a point where the application has grown beyond the capabilities of the hardware in use. For every machine design there is an "ideal" application set that the system architect has in mind. At some point, applications are going to exceed this ideal, and inherent limits of the design will surface. As an example, I can always find an application which is just a bit larger than the cache of the machine I'm running on. >This problem is an example of the original statement I made on this subject: >when the ratio of CPU speed to disk speed is high, virtual memory is not >as attractive. The problem is not solved by such schemes as having larger >page sizes or loading more than one page during page fault resolution - the >issue still arises when the CPU gets faster in the next machine generation. >And both these solutions make a page fault even more of a delay for the >program. > Please consider that the ratio CPU speed to disk speed has ALWAYS been this way. Manufacturers have gone to extremes over the years to defeat this limit, or at least minimize it! As an example, look at the HEAD-PER- TRACK disks used by Burroughs on their medium systems(B2000 series). These disk drives are large, and have a small storage capability, yet they reduced the latency due to disk I/O down to the rotational latency of the drive. >The basic issue here is that perhaps there are types of programming >environments that don't benefit from virtual memory - especially if large >memory machines are available. I'll certainly concede that there are problems which will benefit from a custom hardware/software environment. However, in the world of multi-programming systems, VM as applied to the "typical" applications that a given environment is crafted for is beneficial. Steve Wilson National Semiconductor [ Universal disclaimer goes here ]
elg@killer.UUCP (Eric Green) (06/01/88)
in article <5135@nsc.nsc.com>, stevew@nsc.nsc.com (Steve Wilson) says: > In article <19496@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: >>This problem is an example of the original statement I made on this subject: >>when the ratio of CPU speed to disk speed is high, virtual memory is not >>as attractive. The problem is not solved by such schemes as having larger Au contraire, virtual memory is not the villain you make it out to be. If you don't have VM, then your memory must be big enough to hold all of the program and data. If your memory is big enough to hold all program and data, plus you have VM, then, once the program is loaded into memory, there will be none of the "thrashing" that you so decry.... it takes little more time to page-fault a program into memory than it takes to load it straight into RAM, especially with today's faster CPU's. Note that the above was gleaned from the net the last time the VM argument came up (6 months ago?). Never re-invent etc. etc. (net.memory, how brief thou art!). -- Eric Lee Green {cuae2,ihnp4}!killer!elg Snail Mail P.O. Box 92191 Lafayette, LA 70509 "Is a dream a lie if it don't come true, or is it something worse?"
jlg@beta.UUCP (Jim Giles) (06/02/88)
In article <4257@killer.UUCP>, elg@killer.UUCP (Eric Green) writes: > in article <5135@nsc.nsc.com>, stevew@nsc.nsc.com (Steve Wilson) says: > > In article <19496@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: > >>This problem is an example of the original statement I made on this subject: > >>when the ratio of CPU speed to disk speed is high, virtual memory is not > >>as attractive. The problem is not solved by such schemes as having larger > > Au contraire, virtual memory is not the villain you make it out to be. If you > don't have VM, then your memory must be big enough to hold all of the program > and data. If your memory is big enough to hold all program and data, plus you > have VM, then, once the program is loaded into memory, there will be none of > the "thrashing" that you so decry.... it takes little more time to page-fault > a program into memory than it takes to load it straight into RAM, especially > with today's faster CPU's. > Au contraire yourself! Memory needn't be big enough for the whole program and data in order to benefit from eliminating VM. There are whole classes of programs that know AHEAD OF TIME what data they are going to need next. Such programs can start the I/O to read in pages of data ASYNCHRONOUSLY (so the data will already be in memory by the time the code is ready to use it). For these codes, VM is not a direct hindrance - but the time spend by the hardware doing page table look-ups or whatever is wasted. Before you say this class of programs is hypothetical or too small to care about, I should point out that most CPU cycles in this laboratory are spent running just this kind of program. Scientfic simulation codes very commonly run in the manner above. Furthermore, many of these codes could be modified in minutes to run problems too big for any machine currently made (or proposed). Such programs as these will always run more efficiently on machines WITHOUT VM. J. Giles Los Alamos
dwc@homxc.UUCP (Malaclypse the Elder) (06/02/88)
In article <5135@nsc.nsc.com>, stevew@nsc.nsc.com (Steve Wilson) writes: < In article <19496@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: < < <This problem is an example of the original statement I made on this subject: < <when the ratio of CPU speed to disk speed is high, virtual memory is not < <as attractive. The problem is not solved by such schemes as having larger < <page sizes or loading more than one page during page fault resolution - the < <issue still arises when the CPU gets faster in the next machine generation. < <And both these solutions make a page fault even more of a delay for the < <program. < < < < Please consider that the ratio CPU speed to disk speed has ALWAYS been < this way. Manufacturers have gone to extremes over the years to defeat < this limit, or at least minimize it! As an example, look at the HEAD-PER- < TRACK disks used by Burroughs on their medium systems(B2000 series). < These disk drives are large, and have a small storage capability, yet < they reduced the latency due to disk I/O down to the rotational latency < of the drive. < i think the point of the original posting is that of the effectiveness of main memory as a cache. if you look at the formula for the average access time in a memory hierarchy, the greater the difference between the access times, the greater the hit rate has to be to have an average access time that is closer to the faster speed. but i interpret it another way: as the speed difference gets bigger, you need more and more memory to get a high enough hit rate to achieve a decent average access time OR you need to restructure software to give a better hit rate. note that there is an analog at a lower level: cpu cycle times and main memory access times. and they are addressing this difference by adding more cache and changing software behavior (e.g. register oriented machines). danny chen ihnp4!homxc!dwc
elg@killer.UUCP (Eric Green) (06/04/88)
in article <19730@beta.UUCP>, jlg@beta.UUCP (Jim Giles) says: > In article <4257@killer.UUCP>, elg@killer.UUCP (Eric Green) writes: >> in article <5135@nsc.nsc.com>, stevew@nsc.nsc.com (Steve Wilson) says: >> > In article <19496@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: >> >>This problem is an example of the original statement I made on this subject: >> >>when the ratio of CPU speed to disk speed is high, virtual memory is not >> >>as attractive. The problem is not solved by such schemes as having larger >> >> Au contraire, virtual memory is not the villain you make it out to be. >> .... it takes little more time to page-fault >> a program into memory than it takes to load it straight into RAM, especially >> with today's faster CPU's. >> > Au contraire yourself! Memory needn't be big enough for the whole program > and data in order to benefit from eliminating VM. There are whole classes > of programs that know AHEAD OF TIME what data they are going to need next. Clarification: I was not addressing virtual memory vs. no virtual memory. I was addressing the "problem" of ratio of CPU speed to disk speed. The stereotypical example of a program that does not run well under VM is the large scientific array processing program. Such a program marches from one end of a huge array to the other, and by the time the last pages are accessed, the first pages have already been paged out of RAM (meaning that the next pass results in the whole array being paged back into RAM). Without VM, the program must explicitly handle the segmentation of data, and can make sure that as much is kept loaded as will fit in memory. With VM, the problem could possibly be handled -- but hasn't been, in the past. None of which has anything to do with the "problem" of "disk access so slow that it takes longer to load the page than it takes to execute it". VM makes little difference, there. -- Eric Lee Green {cuae2,ihnp4}!killer!elg Snail Mail P.O. Box 92191 Lafayette, LA 70509 "Is a dream a lie if it don't come true, or is it something worse?"
stevew@nsc.nsc.com (Steve Wilson) (06/07/88)
In article <4332@killer.UUCP> elg@killer.UUCP (Eric Green) writes: > [5 levels of redirection removed] > >Clarification: I was not addressing virtual memory vs. no virtual memory. I >was addressing the "problem" of ratio of CPU speed to disk speed. > >The stereotypical example of a program that does not run well under VM is the >large scientific array processing program. Such a program marches from one end >of a huge array to the other, and by the time the last pages are accessed, the >first pages have already been paged out of RAM (meaning that the next pass >results in the whole array being paged back into RAM). > What your talking about is certainly a problem, but I would argue it has more to do with HOW the VM is implemented on a specific processor, than whether VM itself interfears. If a "typical" scientific application requires 64Mb of array space to fit the entire data set of the problem into physical memory AND such memory is present, then the correct solution is to implement the VM hardware in such a way to allow all 64Mb to be mapped at the same time. Thus, paging is prevented in the "typical" case. Now the real trick is to define what the "typical" scientific application is.... If your reponse is that such an animal's attributes can't be defined, then I'm not sure there is a place to begin making other design trade-offs beyond this single issue. Steve Wilson National Semiconductor [Universal disclaimer goes here!]
jlg@beta.UUCP (Jim Giles) (06/07/88)
In article <4332@killer.UUCP>, elg@killer.UUCP (Eric Green) writes: > [...] > None of which has anything to do with the "problem" of "disk access so slow > that it takes longer to load the page than it takes to execute it". VM makes > little difference, there. [That is, VM makes little difference when the user code does it's own segmentation]. Well this is EXACTLY true. It makes little difference - which means it makes a difference. The reason that the user code, in these cases, does its own segmentation is that the runtime cost of a page or segment fault is so large (because the disk is so slow relative to memory). Since the user code is doing its own segmentation, the hardware for VM is not required. Therefore, any additional overhead caused by the presence of such hardware is undesireable. This overhead usually ammounts to about 5-10% slowdown of scalar memory references due to hardware table lookups. This is 'little difference', but it sufficient to reject the machine against one with similar design that doesn't have the VM penalty.
jlg@beta.UUCP (Jim Giles) (06/07/88)
In article <5144@nsc.nsc.com>, stevew@nsc.nsc.com (Steve Wilson) writes: > If a "typical" scientific application requires 64Mb of array space to > fit the entire data set of the problem into physical memory AND > such memory is present, then the correct solution is to implement the > VM hardware in such a way to allow all 64Mb to be mapped at the same > time. Thus, paging is prevented in the "typical" case. 64MB is only 8 million words - about typical for a small scientific production code. Most new supercomputers have more memory than that. Even so, most scientific production codes will soon be scaled up so that even the 32MW (that's million words) machines aren't big enough. I've heard that the Cray 2's with 256MW are only 'just' big enough for the applications that various users have (presumably they've scaled their problems down a bit in order to fit them in memory). The 'typical' scientific code is one that just barely fits the current maximum archetecture when the program is run in its simplest configuration. In other words, no matter how much memory you give me, I can find people who already have legitimate codes that use ALL of it. Not only that - these people would soon be asking for more. The one other thing these people have in common is that they neither need, nor particularly want, VM on any new machine. J. Giles Los Alamos P.S. This discussion comes up about once every 6 months. I should point out that I have no particular objection to VM in most computing environments. I wouldn't accept a machine like a SUN workstation if it didn't have VM. I probably wouldn't care much for a CRAY that DID have VM. The claim that VM is UNIVERSALLY desirable seems to me to be unreasoned dogma.
rw@beatnix.UUCP (Russell Williams) (06/07/88)
In article <4332@killer.UUCP> elg@killer.UUCP (Eric Green) writes: > >The stereotypical example of a program that does not run well under VM is the >large scientific array processing program. Such a program marches from one end >of a huge array to the other, and by the time the last pages are accessed, the >first pages have already been paged out of RAM (meaning that the next pass >results in the whole array being paged back into RAM). > >Without VM, the program must explicitly handle the segmentation of data, and >can make sure that as much is kept loaded as will fit in memory. With VM, the >problem could possibly be handled -- but hasn't been, in the past. Presumeably you mean to imply that the entire array won't fit in physical memory, but with explicit assignment of what goes and comes when, reasonable efficiency could be achieved. There's absolutely nothing incom- patible between VM and explicit control over page residence. Many memory managers support asynchronous (without-wait) requests to touch pages so they will be in memory when referenced later, or release pages which are no longer needed so that they are the prime candidates for replacement by incoming pages. It's far more convenient (and thus efficient) to have VM to manage large data spaces for you and provide explicit control only when needed, than to require explicit management of data residence. If explicit loading and unloading of data is more than hints to an MM, it is another serious source of bugs. Errors in overlay schemes result in wrong answers, errors in MM hints only in performance degradation. scheme Russell Williams ..uunet!elxsi!rw ..{ucbvax|ihnp4}!sun!elxsi!rw
jlg@beta.UUCP (Jim Giles) (06/09/88)
In article <802@elxsi.UUCP>, rw@beatnix.UUCP (Russell Williams) writes: > [...] > If explicit loading and unloading of data is more than hints to an MM, > it is another serious source of bugs. Errors in overlay schemes result in > wrong answers, errors in MM hints only in performance degradation. Memory management itself causes performance degradations also. In the case where the entire program fits main memory, any overhead in the memory interface due to memory management hardware is a waste. In the case where the MM 'hints' that you suggest using are always accurate, the memory management overhead is also just wasted time. Further, since most memory management hardware doesn't allow such hints, the penalty for codes which can accurately predict data usage is large indeed (MM often swaps out the very data that the code is going to need soonest). You're right that errors in software memory management can produce errors in the result. However, there are programming environments that do software MM (and have done so for years) without this source of errors becomming too burdensome. Large scale production codes in these places would just be penalized by adding hardware MM. Certainly, hardware MM without the 'hint' capacity would be totally unacceptable. Hardware memory management is just one of many useful tools in the designers toolbox. It is not an appropriate tool for ALL applications. J. Giles Los Alamos
jlg@beta.UUCP (Jim Giles) (06/10/88)
In article <10078@ames.arc.nasa.gov>, lamaster@ames.arc.nasa.gov (Hugh LaMaster) writes: > [...] > These advantages to memory management, well established for at least the > last 15 years, come at the penalty of expensive, power consumptive, space > consumptive associative registers. But not, in a properly designed system > (most systems I have seen have been properly designed), does it cause a > slowdown in memory access or, as has been implied several times, some sort > of other mysterious inefficiency. If this is the case, then I have never seen a 'properly designed' system. Overhead in the memory management hardware has been present in every VM system I've ever used. This includes the CDC vector machines. From what I've been able to find out form the hardware people, the Cyber VM accounts for a one clock delay in the speed of scalar memory references vs. what could have been achieved without the VM. To be sure, you can turn the VM off, but this doesn't speed the memory references since the memory mapping is still done (the identity transformation). > I claim, based on my experience, that, > other things being equal (e.g. clock speed of CPU), a memory mapped system > will always be "faster" than a non-memory-mapped system. Interestingly, I agree with this statement entirely. The problem is that 'other things' are seldom 'equal'. The thing that is most unequal between environments is the job-mix. Now, the job mix of most (even scientific) programming environments would probably benefit from VM in terms of throughput. But, if total throughput is a secondary consideration and turnaround of single production codes is paramount, then VM is probably a net loss - you would rather have the hardware spent on another vector multiply unit or something. The issue that NO ONE has yet responded to is this: a code which has predictable data usage patterns can pre-read (and post-write) data asynchronously - sometimes the code can run to completion without ever waiting for I/O to complete. No VM system I've ever seen can do this. And (in spite of suggestions) there is NO commercial machine presently available which even takes 'hints' about the data usage patterns. Even if such a machine DID exist, the best it could do is tie the speed of the non-VM code which does it's own asynchronous paging. To be sure, VM is great at increasing the throughput of multiprocessing systems with large numbers of users or independent jobs running at once. VM does nothing to help the turnaround of individual jobs in such a system (much less in a dedicated system in which turnaround is THE major criterion). J. Giles Los Alamos
lamaster@ames.arc.nasa.gov (Hugh LaMaster) (06/10/88)
In article <20128@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: >I've been able to find out form the hardware people, the Cyber VM accounts >for a one clock delay in the speed of scalar memory references vs. what There is also an address adder in the path in the Cray which adds a cycle. You have to generate the global address somehow. Admittedly, the adder takes up a lot less room than a VM associative register array. >The issue that NO ONE has yet responded to is this: a code which has >predictable data usage patterns can pre-read (and post-write) data >asynchronously - sometimes the code can run to completion without ever >waiting for I/O to complete. No VM system I've ever seen can do this. Actually, VSOS, the "old" Cyber 205 O/S, has user callable advise routines which do exactly this. They allow the user to tell the system in advance what pages will be needed, and which ones will not be needed. With careful programming, (exactly the same care as needed on a non-VM system to do the same job), it is possible to stream from disk at the full disk data rate. I am not aware of what CDC/ETA has done with respect to this on the new Unix system for this architecture now available on the ETA machines. If this feature is not available, it would be a significant loss. Another nice feature which many systems have these days is the ability to map files onto sections of VM. When this is combined with another VM feature, "VM readahead" on sections of VM, you can get the same performance from VM mapped data files that you got from reading ahead sequential files. ****************** A separate issue with VM systems is more of a psychological one. I have heard it argued that VM makes people lazy. While it is just as easy to write a lousy program on a non-VM system which performs poorly (a Cray doing random disk file accesses is just as slow as a Cyber 205 doing random paging) there is a gray area in the middle where it is easier to get, and therefore to accept, 50% of the maximum performance of a job. On a non-VM system, it is often almost as easy to get maximum I/O performance, once you have gone to trouble to restructure your job. So you tend to get more programs on a VM system which are doing just well enough to get by, but could be a lot better with some more effort. Of course, you could turn this around by assuming that your development time/costs were probably lower on the case where you got 50%. Probably hard to quantify... -- Hugh LaMaster, m/s 233-9, UUCP {topaz,lll-crg,ucbvax}! NASA Ames Research Center ames!lamaster Moffett Field, CA 94035 ARPA lamaster@ames.arpa Phone: (415)694-6117 ARPA lamaster@ames.arc.nasa.gov
chris@mimsy.UUCP (Chris Torek) (06/10/88)
In article <20128@beta.UUCP> jlg@beta.UUCP (Jim Giles) writes: >And (in spite of suggestions) there is NO commercial machine presently >available which even takes 'hints' about the data usage patterns. Even >if such a machine DID exist, the best it could do is tie the speed of >the non-VM code which does its own asynchronous paging. I will agree with the latter, but I think not with the former. /* * Copyright (c) 1982, 1986 Regents of the University of California. * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. * * @(#)vadvise.h 7.1 (Berkeley) 6/4/86 */ /* * Parameters to vadvise() to tell system of particular paging * behaviour: * VA_NORM Normal strategy * VA_ANOM Sampling page behaviour is not a win, don't bother * Suitable during GCs in LISP, or sequential or random * page referencing. * VA_SEQL Sequential behaviour expected. * VA_FLUSH Invalidate all page table entries. */ (Now, the *implementation* of VA_SEQL may leave rather much to be desired....) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris