Speculative precomputation: long-range prefetching of delinquent loads

ABSTRACT

This paper explores Speculative Precomputation, a technique that uses idle thread context in a multithreaded architecture to improve performance of single-threaded applications. It attacks program stalls from data cache misses by pre-computing future memory accesses in available thread contexts, and prefetching these data. This technique is evaluated by simulating the performance of a research processor based on the Itanium™ ISA supporting Simultaneous Multithreading. Two primary forms of Speculative Precomputation are evaluated. If only the non-speculative thread spawns speculative threads, performance gains of up to 30% are achieved when assuming ideal hardware. However, this speedup drops considerably with more realistic hardware assumptions. Permitting speculative threads to directly spawn additional speculative threads reduces the overhead associated with spawning threads and enables significantly more aggressive speculation, overcoming this limitation. Even with realistic costs for spawning threads, speedups as high as 169% are achieved, with an average speedup of 76%.

REFERENCES

• 1: S.G. Abraham and B. R. Rau. Predicting load latencies using cache profiling. In Hewlett Packard Lab, Technical Report HPL-94-110, Dec. 1994.
• 2: Jay Bharadwaj , William Y. Chen , Weihaw Chuang , Gerolf Hoflehner , Kishore Menezes , Kalyan Muthukumar , Jim Pierce, The Intel IA-64 Compiler Code Generator, IEEE Micro, v.20 n.5, p.44-53, September 2000 [doi>10.1109/40.877949]
• 3: Martin Christopher Carlisle, Olden: parallelizing programs with dynamic data structures on distributed-memory machines, Princeton University, Princeton, NJ, 1996
• 4: Robert S. Chappell , Jared Stark , Sangwook P. Kim , Steven K. Reinhardt , Yale N. Patt, Simultaneous subordinate microthreading (SSMT), Proceedings of the 26th annual international symposium on Computer architecture, p.186-195, May 01-04, 1999, Atlanta, Georgia, United States
• 5: J. Emer. Simultaneous multithreading: Multiplying Alpha's performance. In Microprocessor Forum, Oct. 1999.
• 6: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• 7: Jerry Huck , Dale Morris , Jonathan Ross , Allan Knies , Hans Mulder , Rumi Zahir, Introducing the IA-64 Architecture, IEEE Micro, v.20 n.5, p.12-23, September 2000 [doi>10.1109/40.877947]
• 8: Intel Corporation. Intel IA-64 architecture software developer's manual.
• 9: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 10: Yul H. Kim , Mark D. Hill , David A. Wood, Implementing stack simulation for highly-associative memories, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.212-213, May 21-24, 1991, San Diego, California, United States
• 11: Rakesh Krishnaiyer , Dattatraya Kulkarni , Daniel Lavery , Wei Li , Chu-cheow Lim , John Ng , David Sehr, An Advanced Optimizer for the IA-64 Architecture, IEEE Micro, v.20 n.6, p.60-68, November 2000 [doi>10.1109/40.888704]
• 12: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 13: Amir Roth , Gurindar S. Sohi, Speculative Data-Driven Multithreading, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.37, January 20-24, 2001
• 14: Harsh Sharangpani , Ken Arora, Itanium Processor Microarchitecture, IEEE Micro, v.20 n.5, p.24-43, September 2000 [doi>10.1109/40.877948]
• 15: Y. Song and M. Dubois. Assisted execution. In Tcchnicai Report CENG 98-25, Department of EE-Systems, UniversiO' of Southern Californm, Oct. 1998.
• 16: SPEC. SPEC cpu2000 documentation. In http://www.spec.org/osg/cpu2OOO/docs/.
• 17: Karthik Sundaramoorthy , Zach Purser , Eric Rotenburg, Slipstream processors: improving both performance and fault tolerance, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.257-268, November 2000, Cambridge, Massachusetts, United States
• 18: D. Tullsen. Simulation and modeling of a simultaneous multitbreaded processor. In 22nd Annual Computer Measurement Group Conference, Dec. 1996.
• 19: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 20: 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
• 21: R. Uhlig, R. Fishtein, O. Gershon, 1. Hirsh, and H. Wang. SoftSDV: A presilicon software development environment for the IA-64 architecture. In lntel Technology Journal, 4th Quarter 1999.
• 22: Steven Wallace , Brad Calder , Dean M. Tullsen, Threaded multiple path execution, Proceedings of the 25th annual international symposium on Computer architecture, p.238-249, June 27-July 02, 1998, Barcelona, Spain
• 23: H. Wang et al. A conjugate flow processor. In Docket No. 884.225US1. Patent Pending, May 2000.
• 24: Cliff Young , Nicolas Gloy , Michael D. Smith, A comparative analysis of schemes for correlated branch prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.276-286, June 22-24, 1995, S. Margherita Ligure, Italy
• 25: Craig B. Zilles , Gurindar S. Sohi, Understanding the backward slices of performance degrading instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.172-181, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL

      Nouns: Systems Application Architecture

Additional Classification:
  C. Computer Systems Organization

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Threads

General Terms:
Design, Experimentation, Measurement, Performance, Theory