Recency-based TLB preloading

ABSTRACT

Caching and other latency tolerating techniques have been quite successful in maintaining high memory system performance for general purpose processors. However, TLB misses have become a serious bottleneck as working sets are growing beyond the capacity of TLBs. This work presents one of the first attempts to hide TLB miss latency by using preloading techniques. We present results for traditional next-page TLB miss preloading - an approach shown to cut some of the misses. However, a key contribution of this work is a novel TLB miss prediction algorithm based on the concept of “recency”, and we show that it can predict over 55% of the TLB misses for the five commercial applications considered.

REFERENCES

• 1: Todd M. Austin , Gurindar S. Sohi, High-bandwidth address translation for multiple-issue processors, Proceedings of the 23rd annual international symposium on Computer architecture, p.158-167, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 2: Michel Cekleov , Michel Dubois, Virtual-Address Caches Part 1: Problems and Solutions in Uniprocessors, IEEE Micro, v.17 n.5, p.64-71, September 1997 [doi>10.1109/40.621215 ]
• 3: Jeffrey S. Chase , Henry M. Levy , Michael J. Feeley , Edward D. Lazowska, Sharing and protection in a single-address-space operating system, ACM Transactions on Computer Systems (TOCS), v.12 n.4, p.271-307, Nov. 1994 [doi>10.1145/195792.195795]
• 4: B.Chemlik, "The SHADE simulator", Sun Labs T.R. 1993.
• 5: 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
• 6: H.K.J. Chu, "Zero-Copy TCP in Solaris", in 1996 USENIX Annual Technical Conference, January 22-26, 1996, San Diego, California
• 7: 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]
• 8: Fredrik Dahlgren , Per Stenström, Evaluation of Hardware-Based Stride and Sequential Prefetching in Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.385-398, April 1996 [doi>10.1109/71.494633 ]
• 9: Jerry Huck , Jim Hays, Architectural support for translation table management in large address space machines, Proceedings of the 20th annual international symposium on Computer architecture, p.39-50, May 16-19, 1993, San Diego, California, United States
• 10: B. Jacob , T. Mudge, Software-Managed Address Translation, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.156, February 01-05, 1997
• 11: Bruce L. Jacob , Trevor N. Mudge, A look at several memory management units, TLB-refill mechanisms, and page table organizations, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.295-306, October 02-07, 1998, San Jose, California, United States
• 12: http://www.speech.cs.cmu.edu/speech/sphinx.html
• 13: K. Bala, M.F. Kaashoek, W.E.Weihl, "Software Prefetching and Caching for Translation Lookaside Buffers", in Proceedings of the First Symposium on Operating System Design and Implementation, November 1994.
• 14: R.L. Mattson, J. Gecsei, D. Slutz, and I.L. Traiger, "Evaluation Techniques for Storage Hierarchies", in IBM Systems Journal 9 (2):pp.78-117, 1970
• 15: Jang Suk Park , Gwang Seon Ahn, A software-controlled prefetching mechanism for software-managed TLBs, Microprocessing and Microprogramming, v.41 n.2, p.121-136, May 1995 [doi>10.1016/0165-6074(95)00003-7]
• 16: Xiaogang Qiu , Michel Dubois, Options for dynamic address translation in COMAs, Proceedings of the 25th annual international symposium on Computer architecture, p.214-225, June 27-July 02, 1998, Barcelona, Spain
• 17: Xiaogang Qiu , Michel Dubois, Tolerating late memory traps in ILP processors, Proceedings of the 26th annual international symposium on Computer architecture, p.76-87, May 01-04, 1999, Atlanta, Georgia, United States
• 18: 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
• 19: 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
• 20: Bob Wheeler , Brian N. Bershad, Consistency management for virtually indexed caches, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.124-136, October 12-15, 1992, Boston, Massachusetts, United States
• 21: http://www.fluent.com
• 22: http://www.newtek.com
• 23: pnmrotate, part of Net PBM distribution, version 7: ftp:// wuarchive.wustl.edu/graphics/graphics/packages/NetPBM
• 24: AMD K-7 Product announcement at microprocessor forum. http ://www.amd.com/products/cpg/k7/micropforum.html
• 25: HAL SPARC64-III, Microprocessor Report, Dec 8, 1997 http ://www.hal. com/home/sp arc 64- 3_mda.html
• 26: André Seznec, A case for two-way skewed-associative caches, Proceedings of the 20th annual international symposium on Computer architecture, p.169-178, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

General Terms:
Design, Management