Practical, transparent operating system support for superpages

ABSTRACT

Most general-purpose processors provide support for memory pages of large sizes, called superpages. Superpages enable each entry in the translation lookaside buffer (TLB) to map a large physical memory region into a virtual address space. This dramatically increases TLB coverage, reduces TLB misses, and promises performance improvements for many applications. However, supporting superpages poses several challenges to the operating system, in terms of superpage allocation and promotion tradeoffs, fragmentation control, etc. We analyze these issues, and propose the design of an effective superpage management system. We implement it in FreeBSD on the Alpha CPU, and evaluate it on real workloads and benchmarks. We obtain substantial performance benefits, often exceeding 30%; these benefits are sustained even under stressful workload scenarios.

REFERENCES

• 1: D. Bailey, T. Harris, W. Saphir, R. van der Wijngaart, A. Woo, and M. Yarrow. The NAS Parallel Benchmarks 2.0. Report NAS-95-020, NASA Ames Research Center, Moffett Field, CA, 1995.
• 2: Douglas W. Clark , Joel S. Emer, Performance of the VAX-11/780 translation buffer: simulation and measurement, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.31-62, Feb. 1985 [doi>10.1145/214451.214455]
• 3: Zhen Fang , Lixin Zhang , John B. Carter , Wilson C. Hsieh , Sally A. McKee, Reevaluating Online Superpage Promotion with Hardware Support, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.63, January 20-24, 2001
• 4: FIPS 180-1. Secure Hash Standard. Technical Report Publication 180-1, Federal Information Processing Standard (FIPS), National Institute of Standards and Technology, US Department of Commerce, Washington D.C., Apr. 1995.
• 5: M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, volume 3, Seattle, WA, May 1998.
• 6: N. Ganapathy and C. Schimmel. General purpose operating system support for multiple page sizes. In Proceedings of the USENIX 1998 Annual Technical Conference, Berkeley, CA, June 1998.
• 7: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 8: Imagemagick. http://www.imagemagick.org.
• 9: Gokul B. Kandiraju , Anand Sivasubramaniam, Characterizing the d-TLB behavior of SPEC CPU2000 benchmarks, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 10: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 11: R. E. Kessler , Mark D. Hill, Page placement algorithms for large real-indexed caches, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.338-359, Nov. 1992 [doi>10.1145/138873.138876]
• 12: Y. A. Khalidi, M. Talluri, M. N. Nelson, and D. Williams. Virtual memory support for multiple page sizes. In Proceedings of the Fourth IEEE Workshop on Workstation Operating Systems, Napa, CA, Oct. 1993.
• 13: J. C. Mogul. Big memories on the desktop. In Proceedings of the Fourth IEEE Workshop on Workstation Operating Systems, Napa, CA, Oct. 1993.
• 14: James L. Peterson , Theodore A. Norman, Buddy systems, Communications of the ACM, v.20 n.6, p.421-431, June 1977 [doi>10.1145/359605.359626]
• 15: J. Poskanzer. thttpd -- tiny/turbo/throttling HTTP server, http://www.acme.com/software/thttpd/.
• 16: Theodore H. Romer , Wayne H. Ohlrich , Anna R. Karlin , Brian N. Bershad, Reducing TLB and memory overhead using online superpage promotion, Proceedings of the 22nd annual international symposium on Computer architecture, p.176-187, June 22-24, 1995, S. Margherita Ligure, Italy
• 17: M. Rosenblum , E. Bugnion , S. A. Herrod , E. Witchel , A. Gupta, The impact of architectural trends on operating system performance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.285-298, December 03-06, 1995, Copper Mountain, Colorado, United States
• 18: Richard L. Sites , Richard T. Witek, Alpha AXP architecture reference manual (2nd ed.), Digital Press, Newton, MA, 1995
• 19: I. Subramanian, C. Mather, K. Peterson, and B. Raghunath. Implementation of multiple pagesize support in HP-UX. In Proceedings of the USENIX 1998 Annual Technical Conference, Berkeley, CA, June 1998.
• 20: Madhusudhan Talluri , Mark D. Hill, Surpassing the TLB performance of superpages with less operating system support, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.171-182, October 05-07, 1994, San Jose, California, United States
• 21: M. Talluri , M. D. Hill , Y. A. Khalidi, A new page table for 64-bit address spaces, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.184-200, December 03-06, 1995, Copper Mountain, Colorado, United States
• 22: Madhusudhan Talluri , Shing Kong , Mark D. Hill , David A. Patterson, Tradeoffs in supporting two page sizes, Proceedings of the 19th annual international symposium on Computer architecture, p.415-424, May 19-21, 1992, Queensland, Australia
• 23: Richard Uhlig , David Nagle , Tim Stanley , Trevor Mudge , Stuart Sechrest , Richard Brown, Design tradeoffs for software-managed TLBs, ACM Transactions on Computer Systems (TOCS), v.12 n.3, p.175-205, Aug. 1994 [doi>10.1145/185514.185515]
• 24: D. A. Wood , S. J. Eggers , G. Gibson , M. D. Hill , J. M. Pendleton, An in-cache address translation mechanism, Proceedings of the 13th annual international symposium on Computer architecture, p.358-365, June 02-05, 1986, Tokyo, Japan

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Management