Fighting the memory wall with assisted execution

ABSTRACT

Assisted execution is a form of simultaneous multithreading in which a set of auxiliary "assistant" threads, called nanothreads, is attached to each thread of an application. Nanothreads are lightweight threads which run on the same processor as the main (application) thread and help execute the main thread as fast as possible. Nanothreads exploit resources that are idled in the processor because of hazards due to program dependencies and memory access delays.Assisted execution has the potential to alter the current trade-offs between static and dynamic execution mechanisms. Nanothreads can monitor and reconfigure the underlying hardware, can emulate hardware and can profile applications with little or no interference to improve the program on-line or off-line.We demonstrate the power of assisted execution with an important application, namely data prefetching to fight the memory wall problem. Simulation results on several SPEC95 benchmarks show that sequential and stride prefetching implemented with nanothreads performs just as well as ideal hardware prefetchers.

REFERENCES

• 1: 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
• 2: 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]
• 3: Parthasarathy Ranganathan , Vijay S. Pai , Hazim Abdel-Shafi , Sarita V. Adve, The interaction of software prefetching with ILP processors in shared-memory systems, Proceedings of the 24th annual international symposium on Computer architecture, p.144-156, June 01-04, 1997, Denver, Colorado, United States
• 4: Jonas Skeppstedt , Michel Dubois, Hybrid compiler/hardware prefetching for multiprocessors using low-overhead cache miss traps, Proceedings of the international Conference on Parallel Processing, p.298-305, August 11-15, 1997
• 5: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 6: Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm , Dean M. Tullsen, Simultaneous Multithreading: A Platform for Next-Generation Processors, IEEE Micro, v.17 n.5, p.12-19, September 1997 [doi>10.1109/40.621209]
• 7: MIPS Technologies Inc., "R10000 Microprocessor User's Manual-Version 2.0," December 1996.
• 8: Mats Brorsson, Fredrik Dahlgren, Håkan Nilsson, and Per Stenström, "The CacheMire Test Bench -- A Flexible and Effective Approach for Simulation of Multiprocessors," Proceedings of 26th Annual Simulation Symposium, pp. 41--49, March 1993.
• 9: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 10: The SPEC Corporation, The SPEC95 Benchmark Suite, 1995.
• 11: 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
• 12: Yong Ho Song and Michel Dubois,"Assisted Execution", Technical Report #CENG 98-25, Department of EE-Systems, University of Southern California, October 1998.
• 13: Tor M. Aamodt , Paul Chow , Per Hammarlund , Hong Wang , John P. Shen, Hardware Support for Prescient Instruction Prefetch, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.84, February 14-18, 2004 [doi>10.1109/HPCA.2004.10028]
• 14: Craig Zilles , Gurindar Sohi, Execution-based prediction using speculative slices, Proceedings of the 28th annual international symposium on Computer architecture, p.2-13, June 30-July 04, 2001, Göteborg, Sweden
• 15: Chi-Keung Luk, Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors, Proceedings of the 28th annual international symposium on Computer architecture, p.40-51, June 30-July 04, 2001, Göteborg, Sweden
• 16: Robert S. Chappell , Francis Tseng , Adi Yoaz , Yale N. Patt, Difficult-path branch prediction using subordinate microthreads, Proceedings of the 29th annual international symposium on Computer architecture, p.307, May 25-29, 2002, Anchorage, Alaska
• 17: Craig B. Zilles , Joel S. Emer , Gurindar S. Sohi, The use of multithreading for exception handling, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.219-229, November 16-18, 1999, Haifa, Israel
• 18: Jamison D. Collins , Hong Wang , Dean M. Tullsen , Christopher Hughes , Yong-Fong Lee , Dan Lavery , John P. Shen, Speculative precomputation: long-range prefetching of delinquent loads, Proceedings of the 28th annual international symposium on Computer architecture, p.14-25, June 30-July 04, 2001, Göteborg, Sweden

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

General Terms:
Algorithms, Design, Performance

Keywords:
cache memories, latency tolerance, prefetching, simultaneous multithreading, superscalar processors