Date: Thu, 20 Nov 1997 23:23:36 -0500 (EST) From: "John S. Dyson" <toor@dyson.iquest.net> To: koshy@india.hp.com (A Joseph Koshy) Cc: freebsd-hackers@freebsd.org Subject: Re: References for page coloring algorithms? Message-ID: <199711210423.XAA01323@dyson.iquest.net> In-Reply-To: <199711210318.TAA25525@palrel1.hp.com> from A Joseph Koshy at "Nov 21, 97 08:42:13 am"
next in thread | previous in thread | raw e-mail | index | archive | help
A Joseph Koshy said: > > Does any literature exist on the page coloring algorithm used in FreeBSD? > If so, I'd appreciate it if someone could forward/post references. I > didn't find any previous discussion on this topic in the archives. > > I came across the following ACM paper on page coloring for direct mapped > caches, but the schemes described there are substantially different from > the FreeBSD code: > > R. E. Kessler and Mark D. Hill, > Page Placement Algorithms for Large Real-Indexed Caches, > ACM TOCS, Vol. 10, No. 4, November 1992, pp. 338-359. > That is the primary document that spurred me on, to write the coloring code. Our coloring code is a scheme that does not cause additional paging (note that another paper that they came up with showed that coloring can cause additional paging, or less efficient memory utlization.) The algorithm is my invention, so there are no explicit references. If you want, I can send you a userland simulation for the method (I used it to demonstrate correctness, and debug the algorithm.) If you notice (by running lat_mem_rd from lmbench), our coloring algorithm is practically 100% effective. -- John dyson@freebsd.org jdyson@nc.com
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199711210423.XAA01323>