Recycling waste: exploiting wrong-path execution to improve branch prediction

ABSTRACT

Despite continuous improvement in branch prediction algorithms, branch misprediction remains a major limitation on microprocessor performance. As pipelines are widened or stretched deeper, branch prediction will become even more crucial. This paper taps into a currently wasted resource, wrong-path execution, to help improve branch prediction. Due to control independence, often the outcomes of branches that are executed along the wrong-path match the outcomes on the correct-path. Current branch prediction methods rely on correlation between branches on the correct path, therefore leaving potentially useful wrong-path branch information unexploited. We present in this paper a new, very simple, and very effective method that extends branch prediction to allow the recycling of wrong-path branch outcomes at the fetch stage. Simulations of deeply pipelined processors using a selected set of SpecInt 2000 and other benchmarks, with more than 5 branch mispredictions per thousand micro-operations, show that branch misprediction rate can be reduced by up to 30%. Depending on the pipeline depth, the corresponding average performance improvement varies from 5% to 20%.

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: Murali Annavaram , Jignesh M. Patel , Edward S. Davidson, Data prefetching by dependence graph precomputation, Proceedings of the 28th annual international symposium on Computer architecture, p.52-61, June 30-July 04, 2001, Göteborg, Sweden
• 3: 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
• 4: R. S. Chappell, J. Stark, S. Kim, S. Reinhardt, and Y. N. Patt. Simultaneous Subordinate Microthreading (SSMT). In Proceedings of the 28th Annual International Symposium on Computer Architecture, 2001.
• 5: Jamison D. Collins , Dean M. Tullsen , Hong Wang , John P. Shen, Dynamic speculative precomputation, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 6: 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
• 7: James David Dundas , Trevor Mudge, Improving processor performance by dynamically pre-processing the instruction stream, 1998
• 8: James Dundas , Trevor Mudge, Improving data cache performance by pre-executing instructions under a cache miss, Proceedings of the 11th international conference on Supercomputing, p.68-75, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263597]
• 9: A. Hartstein , Thomas R. Puzak, The optimum pipeline depth for a microprocessor, Proceedings of the 29th annual international symposium on Computer architecture, p.7, May 25-29, 2002, Anchorage, Alaska
• 10: G. Hinton, D. Sager, M. Upton, D. Boggs, D. Carmean, A. Kyker, and P. Roussel. The Microarchitecture of the Pentium® 4 Processor. In Intel Technical Journal, Q1 2001 Issue.
• 11: Daniel A. Jiménez , Calvin Lin, Dynamic Branch Prediction with Perceptrons, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.197, January 20-24, 2001
• 12: 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
• 13: S. McFarling. Combining Branch Predictors. Technical Report TN-36, Digital Western Research Laboratory, June 1993.
• 14: O. Mutlu, J. Stark, C. Wilkerson, and Y. N. Patt. Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors. In Proceedings of the 8th International Symposium on High Performance Computer Architecture, 2002.
• 15: Amir Roth , Gurindar S. Sohi, Register integration: a simple and efficient implementation of squash reuse, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.223-234, December 2000, Monterey, California, United States [doi>10.1145/360128.360151]
• 16: André Seznec , Stephen Felix , Venkata Krishnan , Yiannakis Sazeides, Design tradeoffs for the Alpha EV8 conditional branch predictor, Proceedings of the 29th annual international symposium on Computer architecture, p.295, May 25-29, 2002, Anchorage, Alaska
• 17: 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
• 18: Eric Sprangle , Doug Carmean, Increasing processor performance by implementing deeper pipelines, Proceedings of the 29th annual international symposium on Computer architecture, p.25, May 25-29, 2002, Anchorage, Alaska
• 19: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]
• 20: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: RISC/CISC, VLIW architectures

General Terms:
Design, Performance

Keywords:
branch prediction, deep pipelines, instruction reuse