Phantom-BTB: a virtualized branch target buffer design

ABSTRACT

Modern processors use branch target buffers (BTBs) to predict the target address of branches such that they can fetch ahead in the instruction stream increasing concurrency and performance. Ideally, BTBs would be sufficiently large to capture the entire working set of the application and sufficiently small for fast access and practical on-chip dedicated storage. Depending on the application, these requirements are at odds.

This work introduces a BTB design that accommodates large instruction footprints without dedicating expensive onchip resources. In the proposed Phantom-BTB (PBTB) design, a conventional BTB is augmented with a virtual table that collects branch target information as the application runs. The virtual table does not have fixed dedicated storage. Instead, it is transparently allocated, on demand, in the on-chip caches, at cache line granularity. The entries in the virtual table are proactively prefetched and installed in the dedicated conventional BTB, thus, increasing its perceived capacity. Experimental results with commercial workloads under full-system simulation demonstrate that PBTB improves IPC performance over a 1K-entry BTB by 6.9% on average and up to 12.7%, with a storage overhead of only 8%. Overall, the virtualized design performs within 1% of a conventional 4K-entry, single-cycle access BTB, while the dedicated storage is 3.6 times smaller.

REFERENCES

• 1: First the tick, now the tock: Next generation Intel microarchitecture (Nehalem). White Paper, Intel Co., 2008.
• 2: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 3: Alaa R. Alameldeen , David A. Wood, Variability in Architectural Simulations of Multi-Threaded Workloads, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.7, February 08-12, 2003
• 4: Branch Behavior of a Commercial OLTP Workload on Intel IA32 Processors, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.242, September 16-18, 2002
• 5: Luiz André Barroso , Kourosh Gharachorloo , Edouard Bugnion, Memory system characterization of commercial workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.3-14, June 27-July 02, 1998, Barcelona, Spain
• 6: Ioana Burcea and Andreas Moshovos. Virtualizing branch target buffers. Technical report, University of Toronto, 2008. www.eecg.toronto.edu/~ioana/papers/pbtb tech rep.pdf.
• 7: Ioana Burcea , Stephen Somogyi , Andreas Moshovos , Babak Falsafi, Predictor virtualization, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 8: Po-Yung Chang , Eric Hao , Yale N. Patt, Target prediction for indirect jumps, Proceedings of the 24th annual international symposium on Computer architecture, p.274-283, June 01-04, 1997, Denver, Colorado, United States
• 9: Karel Driesen , Urs Hölzle, The cascaded predictor: economical and adaptive branch target prediction, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.249-258, November 1998, Dallas, Texas, United States
• 10: Philip G. Emma, Allan M. Hartstein, Brian R. Prasky, Thomas R. Puzak, Moinuddin K. A. Qureshi, and Vijayalakshmi Srinivasan. Context lookahead storage structures. IBM, U.S. Patent 7337271 B2, 2008.
• 11: Barry Fagin , Kathryn Russell, Partial resolution in branch target buffers, Proceedings of the 28th annual international symposium on Microarchitecture, p.193-198, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 12: Nikolaos Hardavellas , Stephen Somogyi , Thomas F. Wenisch , Roland E. Wunderlich , Shelley Chen , Jangwoo Kim , Babak Falsafi , James C. Hoe , Andreas G. Nowatzyk, SimFlex: a fast, accurate, flexible full-system simulation framework for performance evaluation of server architecture, ACM SIGMETRICS Performance Evaluation Review, v.31 n.4, p.31-34, March 2004 [doi>10.1145/1054907.1054914]
• 13: R. B. Hilgendorf, G. J. Heim, and W. Rosenstiel. Evaluation of branch-prediction methods on traces from commercial applications. IBM Journal of Research and Development, 43(4), 1999.
• 14: Daniel A. Jiménez, Reconsidering Complex Branch Predictors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.43, February 08-12, 2003
• 15: Daniel A. Jiménez , Stephen W. Keckler , Calvin Lin, The impact of delay on the design of branch predictors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.67-76, December 2000, Monterey, California, United States [doi>10.1145/360128.360137]
• 16: Jose A. Joao , Onur Mutlu , Hyesoon Kim , Rishi Agarwal , Yale N. Patt, Improving the performance of object-oriented languages with dynamic predication of indirect jumps, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 17: David R. Kaeli , Philip G. Emma, Branch history table prediction of moving target branches due to subroutine returns, Proceedings of the 18th annual international symposium on Computer architecture, p.34-42, May 27-30, 1991, Toronto, Ontario, Canada
• 18: Kimberly Keeton , David A. Patterson , Yong Qiang He , Roger C. Raphael , Walter E. Baker, Performance characterization of a Quad Pentium Pro SMP using OLTP workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.15-26, June 27-July 02, 1998, Barcelona, Spain
• 19: Chetana N. Keltcher , Kevin J. McGrath , Ardsher Ahmed , Pat Conway, The AMD Opteron Processor for Multiprocessor Servers, IEEE Micro, v.23 n.2, p.66-76, March 2003 [doi>10.1109/MM.2003.1196116]
• 20: Ryotaro Kobayashi, Yuji Yamada, Hideki Ando, and Toshio Shimada. A cost-effective branch target buffer with a two-level table organization. In Proceedings of the 2nd International Symposium of Low-Power and High-Speed Chips (COOL Chips II), 1999.
• 21: J. K. F. Lee , A. J. Smith, Branch Prediction Strategies and Branch Target Buffer Design, Computer, v.17 n.1, p.6-22, January 1984 [doi>10.1109/MC.1984.1658927]
• 22: Tao Li , Ravi Bhargava , Lizy Kurian John, Adapting branch-target buffer to improve the target predictability of java code, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.109-130, June 2005 [doi>10.1145/1071604.1071605]
• 23: Albert Meixner , Daniel J. Sorin, Unified microprocessor core storage, Proceedings of the 4th international conference on Computing frontiers, May 07-09, 2007, Ischia, Italy [doi>10.1145/1242531.1242538]
• 24: Ravi Nair, Dynamic path-based branch correlation, Proceedings of the 28th annual international symposium on Microarchitecture, p.15-23, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 25: C. H. Perleberg , A. J. Smith, Branch Target Buffer Design and Optimization, IEEE Transactions on Computers, v.42 n.4, p.396-412, April 1993 [doi>10.1109/12.214687]
• 26: Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Reconfigurable caches and their application to media processing, Proceedings of the 27th annual international symposium on Computer architecture, p.214-224, June 2000, Vancouver, British Columbia, Canada
• 27: 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, May 25-29, 2002, Anchorage, Alaska
• 28: Ed H. Sussenguth. Instruction sequence control. IBM, U.S. Patent 3559183, 1971.
• 29: Tse-Yu Yeh , Yale N. Patt, Branch history table indexing to prevent pipeline bubbles in wide-issue superscalar processors, Proceedings of the 26th annual international symposium on Microarchitecture, p.164-175, December 01-03, 1993, Austin, Texas, United States
• 30: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia

INDEX TERMS

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

General Terms:
Design, Measurement, Performance

Keywords:
branch target buffer, predictor metadata prefetching, predictor virtualization