mcheng@rennet.cs.wisc.edu (Chin-Long (Michael) Cheng) (08/21/90)
Are you running programs that are potentially slowed down by the virtual memory (VM) policy in your machine? I'm looking for ways to improve VM performance by using policies that differ from global CLOCK. I would appreciate any help with the following: a) Descriptions of programs that you think can run faster if different VM policies (replacement + prefetch + user assisted) were used. b) Sample programs segments that you can give me so that I can study the performance for different policies. (Even if you don't know if there will be improvements.) A textbook example would be Gaussian Elimination when the size of the array is bigger than physical memory. When eliminating the lower diagonal, prefetching the next row while working on the current row can be a big help. I am, however, looking for "real-life" programs. That is, program segments that you use regularly for your work. Thanks in advance. Any discussions welcome. Mike mcheng@rennet.cs.wisc.edu
sjs%iconsys@uunet.UU.NET (Steve Sears) (08/28/90)
In article <6189@darkstar.ucsc.edu> mcheng@rennet.cs.wisc.edu (Chin-Long (Michael) Cheng) writes: > >Are you running programs that are potentially slowed down by the >virtual memory (VM) policy in your machine? I'm looking for ways to improve >VM performance by using policies that differ from global CLOCK. >I would appreciate any help with the following: > >a) Descriptions of programs that you think can run faster if different >VM policies (replacement + prefetch + user assisted) were used. I don't have any user programs I can give you, but I have just been through this cycle and perhaps I can throw some ideas out that may be of interest. >A textbook example would be Gaussian Elimination when the size of the ... A problem with Gaussian Elimination type algorithms is the dependency on the reference set behaving in a certain way. There are a number of programs that either have a tight locality, or have a behavior which lends itself to predictive paging. However, in working with threads based processes and data data bases, I have found that predictive paging is almost always counter-productive (notice that we are talking about a subset of computing here, so these observations are not general purpose). This is due to tight locality mixed with seemingly random address jumps, as observed from VM. We have observed, under multi-threaded and data-base environments, that locality exists in several different address ranges per process (or thread). So the problem we faced had to deal with the replacement algorithm. We gave the user the capability to alert the OS that a data page would be required in the near future via a system call, but found that it *generally* added very little. However, for a small class of problems, for example a backup process, this yielded nice speed improvements. Upon examining the VM policies of our machine, there was one obvious flaw in the replacement algorithm; it didn't have enough information to be intelligent. The basic algorithm used a reference bit in the mapping structure, which alerted the VM scanner to pages in use, and got reset after each pass through. To state the obvious, if a page did not get used after one pass of the scanner, it is assumed quiescent and is a candidate to swap out. This can be a real problem for shared pages, for process involved in distributed resources that take a relatively long time to respond, and for machines that have busy processes thrashing about and using pages up quickly. Unnecessary swapping results in degraded performance of the whole machine, and in severe cases may result in process starvation. There are quit a number of algorithms around that overcome this type of problem, including maintaining a VM free list and expanding the state kept on each page, which are a couple of things we did. We came up with and implemented several ideas in this vein. The results were dramatic. We had far less swapping, much quicker dispatch times, and found our fault rate went down. This response is probably overkill for your posting. But a word of caution that has served us well; be wary of small applications, single user tests, and tests that have high start up costs - predictive paging algorithms will always win if initialization is high enough to be a factor. >Mike >mcheng@rennet.cs.wisc.edu Steve