Reducing TLB and memory overhead using online superpage promotion

ABSTRACT

Modern microprocessors contain small TLBs that maintain a cache of recently used translations. A TLB's coverage is the sum of the number of bytes mapped by each entry. Applications with working sets larger than the TLB coverage will perform poorly due to high TLB miss rates. Superpages have been proposed as a mechanism for increasing TLB coverage. A superpageis a virtual memory page with size and alignment that are a power of two multiple of the system's base page size. In this paper, we describe online policies for superpage management that monitor TLB miss traffic to decide when a superpage should be constructed. Our policies take into account both the benefit of a superpage promotion (potential for preventing future misses) and the cost (page copying). Although our approach increases the cost of each TLB miss, the net effect is to improve total execution time by eliminating a large number of misses without significantly increasing memory usage, thereby improving system performance.

REFERENCES

• Appel & Li 91: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.96-107, April 08-11, 1991, Santa Clara, California, United States
• Babaoglu & Joy 81: Ö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
• Bala et al 94: Bala, K., Kaashoek, E, and Weihl, W. Software Prefetching and Caching forTranslanon Buffers. In Proceedings of the 1st USENIX Symposium on Operating System Design and Implementation, pages 243-254, November 1994.
• Blanck & Krueger 92: Greg Blanck , Steve Krueger, The SuperSPARC microprocessor, Proceedings of the thirty-seventh international conference on COMPCON, p.136-141, January 1992, San Francisco, California, United States
• Cao et al 94: Cao, P, Felten, E, and Li, K Implementation and Performance of Apphcation-ControlIed Fde Caching. In Proceedings of the 1st USENIX Symposium on Operating System Design andlmplementatton, pages 165- 177, November 1994.
• Carter et al 91: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• Chambers 93: Chambers, C. The Cecil Language: Speclficanon and Rationale. Technical Report 93-03-05, University of Washington, March 1993.
• Chen et al. 92: J. Bradley Chen , Anita Borg , Norman P. Jouppi, A simulation based study of TLB performance, Proceedings of the 19th annual international symposium on Computer architecture, p.114-123, May 19-21, 1992, Queensland, Australia
• Dig 92: Digital Eqmpment Corporation. DECchip 21064-AA Microproce,~sor, Hardware Reference Manual, 1992. Order Number: EC-N0079-72.
• Dutton et al. 92: Dutton, T., Eiref, D., Kurth, H., Reisert, j., and Stewart, R. The Design of the DEC 3000 AXP Systems, Two High-Performance Workstations. Digital Technical Journal, 4(4) 66-81, 1992 Special Issue.
• Hauck & Borriello 95: Hauck, S. and Borriello, G An Evaluation of Bipartitioning Techniques Submitted for pubhcation to IEEE Transactaons on Computer-Aided Design of Integrated Clrcmts and Systems, 1995.
• Hosking & Moss 93: Antony L. Hosking , J. Eliot B. Moss, Protection traps and alternatives for memory management of an object-oriented language, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.106-119, December 05-08, 1993, Asheville, North Carolina, United States
• Kane & Heinrich 92: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Karlin et al. 88: Karlin, A., Manasse, M, Rudolph, L, and Sleator, D Competitive Snoopy Caching. Algorithmica, 3(1 ):70-1 t 9, 1988.
• Karlin et al. 91: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• Khalidi et al 93: Khali&, Y A, Talluri, M, Nelson, M, and Williams, D Virtual Memory Support for Multiple Page Sizes In Proceedings of the Fourth Workshop on Workstation Operating Systems, pages 104-109, October 1993
• Mogul 93: Mogul, J Big Memories on the Desktop In Proceedings oJ the Fourth Workshop on Workstatton Operatmg S)wtems, pages 110-115, October 1993
• Ramakrishnan et al. 93: Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan , Praveen Seshadri, Implementation of the CORAL deductive database system, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.167-176, May 25-28, 1993, Washington, D.C., United States
• Rashid et al 87: Richard Rashid , Avadis Tevanian , Michael Young , David Golub , Robert Baron, Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.31-39, October 1987, Palo Alto, California, United States
• Sleator & Tarjan 85: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• Srivastava & Eustace 94: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• Talluri & Hill 94: 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
• Talluri et al 92: 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
• Young et al 87: M. Young , A. Tevanian , R. Rashid , D. Golub , J. Eppinger, The duality of memory and communication in the implementation of a multiprocessor operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.63-76, November 08-11, 1987, Austin, Texas, United States
• Zekaukas et al 94: Zekaukas, M., Sawdon, W, and Bershad, B. Software Write Detection for Dlsmbuted Shared Memory In Proceedings of the 1st USENIX Symposium on Operating System Design and lmpIementatton, pages 87- 100, November 1994.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Virtual memory

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Measurement, Performance