Tolerating late memory traps in ILP processors

ABSTRACT

ILP processors can execute a large number of instructions at the same time. Thus it becomes more and more difficult to support traps efficiently. On the other hand a current trend in architecture is to support various memory functions in software rather than hardware, usually by trapping the execution processor on a cache miss, TLB miss or a failed access to a local or remote memory. These late memory traps block the faulting instruction at the top of the active list, backing up the pipeline. Moreover the support for late memory traps may affect the performance of non-faulting memory instructions as well.In this paper we analyze the overhead caused by late memory traps in ILP processors and define several measures for this overhead. In order to tolerate late memory traps, we propose hardware prefetching of exception conditions and a tagged Store buffer to implement deferred traps on Stores. We show that, with these hardware optimizations, the overhead added by the lateness of traps is significantly reduced relative to the overhead of early traps. Because of caching effects the frequency of late memory traps usually decreases as they are taken deeper in the memory hierarchy and their overall impact on the execution time becomes negligible.

REFERENCES

• 1: 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
• 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: Michel Cekleov , Michel Dubois, Virtual-Address Caches, Part 2: Multiprocessor Issues, IEEE Micro, v.17 n.6, p.69-74, November 1997 [doi>10.1109/40.641599]
• 4: D. Chaiken , A. Agarwal, Software-extended coherent shared memory: performance and cost, Proceedings of the 21ST annual international symposium on Computer architecture, p.314-324, April 18-21, 1994, Chicago, Illinois, United States
• 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: D. R. Cheriton , G. A. Slavenburg , P. D. Boyle, Software-controlled caches in the VMP multiprocessor, Proceedings of the 13th annual international symposium on Computer architecture, p.366-374, June 02-05, 1986, Tokyo, Japan
• 7: Michel Dubois , Christoph Scheurich , Faye Briggs, Memory access buffering in multiprocessors, 25 years of the international symposia on Computer architecture (selected papers), p.320-328, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.285991]
• 8: Kourosh Gharachorloo , Anoop Gupta , John Hennessy, Performance evaluation of memory consistency models for shared-memory multiprocessors, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.245-257, April 08-11, 1991, Santa Clara, California, United States
• 9: Kourosh Gharachorloo, Anoop Gupta, and John Hennessy, "Two Techniques to Enhance the Performance of Memory Consistency Models", In Proceedings of the International Conference on Parallel Processing, pages 1355-1364, 1991
• 10: Håkan Grahn , Per Stenström, Efficient strategies for software-only protocols in shared-memory multiprocessors, Proceedings of the 22nd annual international symposium on Computer architecture, p.38-47, June 22-24, 1995, S. Margherita Ligure, Italy
• 11: Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.300-318, Nov. 1993 [doi>10.1145/161541.161544]
• 12: Mark Horowitz , Margaret Martonosi , Todd C. Mowry , Michael D. Smith, Informing memory operations: providing memory performance feedback in modern processors, Proceedings of the 23rd annual international symposium on Computer architecture, p.260-270, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 13: 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
• 14: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 15: Adrian Moga , Michel Dubois , Alain Gefflaut, Hardware Versus Software Implementation of COMA, Proceedings of the international Conference on Parallel Processing, p.248-256, August 11-15, 1997
• 16: David Nagle , Richard Uhlig , Tim Stanley , Stuart Sechrest , Trevor Mudge , Richard Brown, Design tradeoffs for software-managed TLBs, Proceedings of the 20th annual international symposium on Computer architecture, p.27-38, May 16-19, 1993, San Diego, California, United States
• 17: Vijay Pai, Parthasarathy Ranganathan, Sarita Adve, "RSIM Reference Manual", Technical Report 9705, Department of Electrical and Computer Engineering, Rice University, Aug, 1997
• 18: Vijay S. Pai , Parthasarathy Ranganathan , Sarita V. Adve , Tracy Harton, An evaluation of memory consistency models for shared-memory systems with ILP processors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.12-23, October 01-04, 1996, Cambridge, Massachusetts, United States
• 19: 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
• 20: Parthasarathy Ranganathan , Vijay S. Pai , Sarita V. Adve, Using speculative retirement and larger instruction windows to narrow the performance gap between memory consistency models, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.199-210, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258512]
• 21: Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.297-306, October 05-07, 1994, San Jose, California, United States
• 22: James E. Smith , Andrew R. Pleszkun, Implementation of precise interrupts in pipelined processors, Proceedings of the 12th annual international symposium on Computer architecture, p.36-44, June 17-19, 1985, Boston, Massachusetts, United States
• 23: Yong Ho Song and Michel Dubois,"Assisted Execution", Technical Report #CENG 98-25, Department of EE-Systems, University of Southern California, October 1998.
• 24: Mark Swanson , Leigh Stoller , John Carter, Increasing TLB reach using superpages backed by shadow memory, Proceedings of the 25th annual international symposium on Computer architecture, p.204-213, June 27-July 02, 1998, Barcelona, Spain
• 25: 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
• 26: Patricia Teller, and Allan Gottlieb. "Locating Multiprocessor TLBs at Memory," In Proceedings of the 27th Annual Hawaii International Conference on System Science, pages 554-563, 1994.
• 27: David Weaver and Tom Germond, "The SPARC Architecture Manual", version 9, Prentice Hall, t994.
• 28: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 29: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 30: Donald Yeung , John Kubiatowicz , Anant Agarwal, MGS: a multigrain shared memory system, Proceedings of the 23rd annual international symposium on Computer architecture, p.44-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Experimentation, Management, Measurement, Performance