Page placement algorithms for large real-indexed caches

ABSTRACT

When a computer system supports both paged virtual memory and large real-indexed caches, cache performance depends in part on the main memory page placement. To date, most operating systems place pages by selecting an arbitrary page frame from a pool of page frames that have been made available by the page replacement algorithm. We give a simple model that shows that this naive (arbitrary) page placement leads to up to 30% unnecessary cache conflicts. We develop several page placement algorithms, called careful-mapping algorithms, that try to select a page frame (from the pool of available page frames) that is likely to reduce cache contention. Using trace-driven simulation, we find that careful mapping results in 10–20% fewer (dynamic) cache misses than naive mapping (for a direct-mapped real-indexed multimegabyte cache). Thus, our results suggest that careful mapping by the operating system can get about half the cache miss reduction that a cache size (or associativity) doubling can.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
	2	Özalp Babaoglu , William Joy, Converting a swap-based system to do paging in an architecture lacking page-referenced bits, Proceedings of the eighth ACM symposium on Operating systems principles, p.78-86, December 14-16, 1981, Pacific Grove, California, United States
	3	J.-L. Baer , W.-H. Wang, On the inclusion properties for multi-level cache hierarchies, Proceedings of the 15th Annual International Symposium on Computer architecture, p.73-80, May 30-June 02, 1988, Honolulu, Hawaii, United States
	4	BORG, A., t~SSLER, R. E., L^ZAN& G., AND WALL, D.W. Long address traces from RISC machines: Generation and analysis. Res. Rep. 89/14, Western Research Laboratory, Digital Equipment Corporation, Palo Alto, Calif., 1989.
	5	Anita Borg , R. E. Kessler , David W. Wall, Generation and analysis of very long address traces, Proceedings of the 17th annual international symposium on Computer Architecture, p.270-279, May 28-31, 1990, Seattle, Washington, United States
	6	Brian K. Bray , William L. Lunch , Michael J. Flynn, Page allocation to reduce access time of physical caches, Stanford University, Stanford, CA, 1990
	7	Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
	8	FERRARI, D. The improvement of program behavior. IEEE Comput. (Nov. 1976), 39 47.
	9	James R. Goodman, Coherency for multiprocessor virtual address caches, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.72-81, October 1987, Palo Alto, California, United States
	10	James R. Goodman , Men-chow Chiang, The use of static column ram as a memory hierarchy, Proceedings of the 11th annual international symposium on Computer architecture, p.167-173, January 1984
	11	M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
	12	W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
	13	KAPLAN, K. R., AND WINDER, R.O. Cache-based computer systems. IEEE Comput. G, 3 (Mar. 1973), 30 36.
	14	KELLY, E. Personal communications. 1990.
	15	Richard Eugene Kessler, Analysis of multi-megabyte secondary CPU cache memories, University of Wisconsin at Madison, Madison, WI, 1992
	16	KESSLER, R. E., AND HILL, M.D. Miss reduction in large, real-indexed caches. Computer Sciences Tech. Rep. #940, Univ. of Wisconsin--Madison, 1990.
	17	Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
	18	S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
	19	NIELSEN, M. J. K. Titan system manual. Res. Rep. 86/1, Western Research Laboratory, Digital Equipment Corporation, Palo Alto, Calif., 1986.
	20	S. Przybylski , M. Horowitz , J. Hennessy, Characteristics of performance-optimal multi-level cache hierarchies, Proceedings of the 16th annual international symposium on Computer architecture, p.114-121, April 1989, Jerusalem, Israel
	21	R. L. Sites , A. Agarwal, Multiprocessor cache analysis using ATUM, Proceedings of the 15th Annual International Symposium on Computer architecture, p.186-195, May 30-June 02, 1988, Honolulu, Hawaii, United States
	22	Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
	23	James W. Stamos, Static grouping of small objects to enhance performance of a paged virtual memory, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.155-180, May 1984 [doi>10.1145/190.194]
	24	George Taylor , Peter Davies , Michael Farmwald, The TLB slice—a low-cost high-speed address translation mechanism, Proceedings of the 17th annual international symposium on Computer Architecture, p.355-363, May 28-31, 1990, Seattle, Washington, United States
	25	Dominique Thiebaut , Harold S. Stone, Footprints in the cache, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.305-329, Nov. 1987 [doi>10.1145/29868.32979]
	26	W. H. Wang , J.-L. Baer , H. M. Levy, Organization and performance of a two-level virtual-real cache hierarchy, Proceedings of the 16th annual international symposium on Computer architecture, p.140-148, April 1989, Jerusalem, Israel

Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading