Re: [PATCH] rmap 14

[Scott Kaplan <sfkaplan@cs.amherst.edu>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday, August 21, 2002, at 12:28 PM, Mel wrote:

> On Wed, 21 Aug 2002, Scott Kaplan wrote:
>
>> What papers are those?  We all try to keep up with the literature, but if
>> there's something that I've missed here, I'd love to know about it.
>
> For a start, I'm not reviewing litrature actively so I'm not up to date on
> papers at all, nor am I willing to get involved in a I Know More Papers
> Than You discussion here.

I wasn't trying to get into a contest.  When someone mentioned that they 
know of papers to support an interesting position, I just want to know 
what those papers are, as the resulting list may include some that I haven'
t seen.

> One that comes to mind I think was called Adaptive Page Replacement Based
> on Memory Reference Behaviour or something very similar to that name. I
> think it had something on collecting trace reference that was based on
> real programs.

Are you thinking of the paper on the SEQ replacement policy by Glass and 
Cao?  If so, be skeptical of their trace gathering methods.  They gathered 
and reduced their traces in an ad-hoc manner that left some serious 
limitations to the use of those traces.  They also don't mention reference 
behavior modeling at all; they simply gathered some traces based on the 
spec95 benchmark, tested their new page replacement policy, and showed the 
results.

> In Search of a Better Malloc I *think* had something on traces but it
> depended on synthetic traces for information that had some sort of uniform
> distribution. It struck me as been not particularly reliable but it was a
> method that appeared to be used in a number of other papers.

> I'm am almost definite that "Dynamic Storage Allocation, A Critical
> Review" has a section on traces and how they tended to be synthetic or
> generated by small custom programs and why this was a bad thing. I believe
> it talked briefly about how synthetic traces were used because they were
> really easy to produce, not because they were useful. Still, it highlights
> the problem of using predictable data.

Also try Johnstone and Wilson, ``The Memory Fragmentation Problem: Solved?
'' (International Symposium on Memory Management '98) -- it's a later 
version of that same work.  I'm unfamiliar with the second paper you 
mentioned, but you should also see Zorn and Grunwald, ``Evaluating Models 
of Memory Allocation'' (U. Colorado tech report from '92), in which they 
claim that many simple models are good, but none good enough to synthesize 
a full system workload.

For reference behavior, an old citation, but perhaps a useful one, is 
Richard Carr's ``Virtual Memory Management'' (Ph.D. thesis, 1984 or 
thereabouts), in which he address a number of approaches to modeling, 
their shortcomings, and then presents a new one that is probably better, 
but goes unvalidated against real program behavior.

> By and large, I found that papers on memory allocators tend to
> focus on trace data and it's usefulness more than page replacement papers
> did.  I could be wrong here though but don't quote me on that.

That's likely true.  Use of models for reference traces seemed to die out 
about 15 years ago, as gathering real reference traces became more 
feasible (larger storage, faster chips for compression, etc.)

Scott
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (Darwin)
Comment: For info see http://www.gnupg.org

iD8DBQE9Y95O8eFdWQtoOmgRAhOtAJ4s4tzA184T3UnxB37R+cxKsAcYNwCcCS0q
LVw0VCDFUy47oamDjWtaz54=
=1pLE
-----END PGP SIGNATURE-----

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/