Better exploration of region-level value locality with integrated computation reuse and value prediction

ABSTRACT

Computation-reuse and value-prediction are two recent techniques for improving microprocessor performance by exploiting value localities. They both aim at breaking the data dependence limit in traditional processors. In this paper, we propose a speculative multithreading scheme in which the same hardware can be efficiently used for both computation reuse and value prediction. For the SpecInt95 benchmarks, our experiment shows that the integrated approach significantly out-performs either computation reuse or value prediction alone. For example, the integrated approach improves over computation reuse from a speedup of 1.25 to 1.40, and improves over value prediction from 1.28 to 1.40. In particular, the integrated approach out-performs a computation reuse configuration that has twice as much reuse buffer entries (from a speedup 1.33 to 1.40). Furthermore, unlike the computation reuse approach, the performance of the integrated approach does not rely on value profile during region formation and thus our approach is more suitable for production systems.

REFERENCES

• 1: Haitham Akkary , Michael A. Driscoll, A dynamic multithreading processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.226-236, November 1998, Dallas, Texas, United States
• 2: Todd M. Austin, DIVA: a reliable substrate for deep submicron microarchitecture design, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.196-207, November 16-18, 1999, Haifa, Israel
• 3: Brad Calder , Peter Feller , Alan Eustace, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.259-269, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 4: Saugata Chatterjee , Chris Weaver , Todd Austin, Efficient checker processor design, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.87-97, December 2000, Monterey, California, United States [doi>10.1145/360128.360139]
• 5: Daniel A. Connors , Wen-mei W. Hwu, Compiler-directed dynamic computation reuse: rationale and initial results, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.158-169, November 16-18, 1999, Haifa, Israel
• 6: Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.222-233, November 2000, Cambridge, Massachusetts, United States
• 7: S. Dutta and M. Franklin. Block-Level Prediction for Wide- Issue Superscalar Processors. Proc. of the 1 st International Conference on Algorithms and Architectures for Parallel Processing, Vol. 1, pp. 143-152, 1995.
• 8: Chao-Ying Fu , Matthew D. Jennings , Sergei Y. Larin , Thomas M. Conte, Value speculation scheduling for high performance processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.262-271, October 02-07, 1998, San Jose, California, United States
• 9: Freddy Gabbay , Avi Mendelson, Using value prediction to increase the power of speculative execution hardware, ACM Transactions on Computer Systems (TOCS), v.16 n.3, p.234-270, Aug. 1998 [doi>10.1145/290409.290411]
• 10: Jian Huang , David J. Lilja, Extending Value Reuse to Basic Blocks with Compiler Support, IEEE Transactions on Computers, v.49 n.4, p.331-347, April 2000 [doi>10.1109/12.844346]
• 11: Jian Huang , David J. Lilja, Exploring Sub-Block Value Reuse for Superscalar Processors, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.100, October 15-19, 2000
• 12: Intel Corp. Intel 1A-64 Architecture Software Developer's Manual, Jan. 2000. Vol. 1-4. http://developer.intel.com/design/ia-64/manuals/index.htm.
• 13: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 14: Kevin M. Lepak , Mikko H. Lipasti, On the value locality of store instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.182-191, June 2000, Vancouver, British Columbia, Canada
• 15: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 16: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 17: 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
• 18: Pedro Marcuello , Jordi Tubella , Antonio González, Value prediction for speculative multithreaded architectures, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.230-236, November 16-18, 1999, Haifa, Israel
• 19: Tarun Nakra , Rajiv Gupta , Mary Lou Soffa, Value prediction in VLIW machines, Proceedings of the 26th annual international symposium on Computer architecture, p.258-269, May 01-04, 1999, Atlanta, Georgia, United States
• 20: Zach Purser , Karthik Sundaramoorthy , Eric Rotenberg, A study of slipstream processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.269-280, December 2000, Monterey, California, United States [doi>10.1145/360128.360155]
• 21: Yiannakis Sazeides , James E. Smith, The predictability of data values, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.248-258, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 22: Mauricio Jose Serrano, Performance tradeoffs in multistreamed superscalar architectures, University of California at Santa Barbara, Santa Barbara, CA, 1994
• 23: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 24: Avinash Sodani , Gurindar S. Sohi, An empirical analysis of instruction repetition, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.35-45, October 02-07, 1998, San Jose, California, United States
• 25: Avinash Sodani , Gurindar S. Sohi, Understanding the differences between value prediction and instruction reuse, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.205-215, November 1998, Dallas, Texas, United States
• 26: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 27: 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
• 28: 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
• 29: Dean M. Tullsen , John S. Seng, Storageless value prediction using prior register values, Proceedings of the 26th annual international symposium on Computer architecture, p.270-279, May 01-04, 1999, Atlanta, Georgia, United States
• 30: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  C. Computer Systems Organization
  C.0 GENERAL

      Nouns: Systems Application Architecture

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

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

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