Increasing the instruction fetch rate via multiple branch prediction and a branch address cache

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Increasing the instruction fetch rate via multiple branch prediction and a branch address cache

Full text

Pdf (1.13 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 7th international conference on Supercomputing table of contents

Tokyo, Japan

Pages: 67 - 76

Year of Publication: 1993

ISBN:0-89791-600-X

Authors

Tse-Yu Yeh	Univ. of Michigan, Ann Arbor
Deborah T. Marr	Univ. of Michigan, Ann Arbor
Yale N. Patt	Univ. of Michigan, Ann Arbor

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 50, Citation Count: 39

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/165939.165956 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
	2	J. Lee and A. J. Smith, "Branch Prediction Strategies and Branch Target Buffer Deign", IEEE Computer, (Jan. 1984), pp.6-22.
	3	Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace scheduling compiler, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.180-192, October 1987, Palo Alto, California, United States
	4	B. Ramakrishna Rau , David W. L. Yen , Wei Yen , Ross A. Towie, The Cydra 5 Departmental Supercomputer: Design Philosophies, Decisions, and Trade-Offs, Computer, v.22 n.1, p.12-26, 28-30, 32-35, January 1989 [doi>10.1109/2.19820]
	5	Michael Butler , Tse-Yu Yeh , Yale Patt , Mitch Alsup , Hunter Scales , Michael Shebanow, Single instruction stream parallelism is greater than two, Proceedings of the 18th annual international symposium on Computer architecture, p.276-286, May 27-30, 1991, Toronto, Ontario, Canada
	6	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]
	7	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
	8	Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
	9	Tse-Yu Yeh , Yale N. Patt, A comprehensive instruction fetch mechanism for a processor supporting speculative execution, Proceedings of the 25th annual international symposium on Microarchitecture, p.129-139, December 01-04, 1992, Portland, Oregon, United States
	10	Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
	11	Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]

CITED BY 39

	Pierre Michaud , André Seznec , Stéphan Jourdan, An Exploration of Instruction Fetch Requirement in Out-of-Order Superscalar Processors, International Journal of Parallel Programming, v.29 n.1, p.35-58, February 2001
	Eric Hao , Po-Yung Chang , Marius Evers , Yale N. Patt, Increasing the Instruction Fetch Rate via Block-Structured Instruction Set Architectures, International Journal of Parallel Programming, v.26 n.4, p.449-478, August 1998
	Freddy Gabbay , Avi Mendelson, The effect of instruction fetch bandwidth on value prediction, ACM SIGARCH Computer Architecture News, v.26 n.3, p.272-281, June 1998
	Simonjit Dutta , Manoj Franklin, Control flow prediction with tree-like subgraphs for superscalar processors, Proceedings of the 28th annual international symposium on Microarchitecture, p.258-263, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	Quinn Jacobson , Eric Rotenberg , James E. Smith, Path-based next trace prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	Eric Hao , Po-Yung Chang , Marius Evers , Yale N. Patt, Increasing the instruction fetch rate via block-structured instruction set architectures, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.191-200, December 02-04, 1996, Paris, France
	Stevan Vlaovic , Edward S. Davidson, Boosting trace cache performance with nonhead miss speculation, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
	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
	Bryan Black , Bohuslav Rychlik , John Paul Shen, The block-based trace cache, ACM SIGARCH Computer Architecture News, v.27 n.2, p.196-207, May 1999
	Sangyeun Cho , Pen-Chung Yew , Gyungho Lee, Decoupling local variable accesses in a wide-issue superscalar processor, ACM SIGARCH Computer Architecture News, v.27 n.2, p.100-110, May 1999
	Steven Wallace , Nader Bagherzadeh, Modeled and Measured Instruction Fetching Performance for Superscalar Microprocessors, IEEE Transactions on Parallel and Distributed Systems, v.9 n.6, p.570-578, June 1998
	Toni Juan , Juan J. Navarro , Olivier Temam, Data caches for superscalar processors, Proceedings of the 11th international conference on Supercomputing, p.60-67, July 07-11, 1997, Vienna, Austria
	Ravi Nair , Martin E. Hopkins, Exploiting instruction level parallelism in processors by caching scheduled groups, ACM SIGARCH Computer Architecture News, v.25 n.2, p.13-25, May 1997
	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
	Sangyeun Cho , Pen-Chung Yew , Gyungho Lee, A High-Bandwidth Memory Pipeline for Wide Issue Processors, IEEE Transactions on Computers, v.50 n.7, p.709-723, July 2001
	Sriram Vajapeyam , Tulika Mitra, Improving superscalar instruction dispatch and issue by exploiting dynamic code sequences, ACM SIGARCH Computer Architecture News, v.25 n.2, p.1-12, May 1997
	Bradley C. Kuszmaul , Dana S. Henry , Gabriel H. Loh, A comparison of scalable superscalar processors, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.126-137, June 27-30, 1999, Saint Malo, France
	Ronnie E. King , Robert F. Roggio , J. Gray Killinger, Programming skills for a changing world: back to the basics, Journal of Computing Sciences in Colleges, v.19 n.3, p.249-257, January 2004
	Alex Ramirez , Oliverio J. Santana , Josep L. Larriba-Pey , Mateo Valero, Fetching instruction streams, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
	Dionisios N. Pnevmatikatos , Manoj Franklin , Gurindar S. Sohi, Control flow prediction for dynamic ILP processors, Proceedings of the 26th annual international symposium on Microarchitecture, p.153-163, December 01-03, 1993, Austin, Texas, United States
	André Seznec , Stéphan Jourdan , Pascal Sainrat , Pierre Michaud, Multiple-block ahead branch predictors, ACM SIGOPS Operating Systems Review, v.30 n.5, p.116-127, Dec. 1996
	Sang-hyuk Lee , Il-kwan Kim , Lynn Choi, Branch predictor design and performance estimation for a high performance embedded microprocessor, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Ryan Rakvic , Bryan Black , John Paul Shen, Completion time multiple branch prediction for enhancing trace cache performance, ACM SIGARCH Computer Architecture News, v.28 n.2, p.47-58, May 2000
	Eric Rotenberg , Steve Bennett , James E. Smith, A Trace Cache Microarchitecture and Evaluation, IEEE Transactions on Computers, v.48 n.2, p.111-120, February 1999
	André Seznec , Antony Fraboulet, Effective ahead pipelining of instruction block address generation, ACM SIGARCH Computer Architecture News, v.31 n.2, May 2003
	Oliverio J. Santana , Alex Ramirez , Josep L. Larriba-Pey , Mateo Valero, A low-complexity fetch architecture for high-performance superscalar processors, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.2, p.220-245, June 2004
	Alex Ramirez , Josep L. Larriba-Pey , Mateo Valero, Software Trace Cache, IEEE Transactions on Computers, v.54 n.1, p.22-35, January 2005
	Simonjit Dutta , Manoj Franklin, Control Flow Prediction Schemes for Wide-Issue Superscalar Processors, IEEE Transactions on Parallel and Distributed Systems, v.10 n.4, p.346-359, April 1999
	Sanjay Jeram Patel , Daniel Holmes Friendly , Yale N. Patt, Evaluation of Design Options for the Trace Cache Fetch Mechanism, IEEE Transactions on Computers, v.48 n.2, p.193-204, February 1999
	Chunrong Lai , Shih-Lien Lu , Yurong Chen , Trista Chen, Improving branch prediction accuracy with parallel conservative correctors, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
	Pedro Marcuello , Antonio González , Jordi Tubella, Speculative multithreaded processors, Proceedings of the 12th international conference on Supercomputing, p.77-84, July 1998, Melbourne, Australia
	Sangyeun Cho , Pen-Chung Yew , Gyungho Lee, Access region locality for high-bandwidth processor memory system design, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.136-146, November 16-18, 1999, Haifa, Israel
	Shu-Lin Hwang , Feipei Lai, Two cache lines prediction for a wide-issue micro-architecture, Australian Computer Science Communications, v.23 n.4, p.71-79, January 2001
	Alex Ramírez , Josep-L. Larriba-Pey , Carlos Navarro , Josep Torrellas , Mateo Valero, Software trace cache, Proceedings of the 13th international conference on Supercomputing, p.119-126, June 20-25, 1999, Rhodes, Greece
	Michele Co , Dee A. B. Weikle , Kevin Skadron, Evaluating trace cache energy efficiency, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.4, p.450-476, December 2006
	Juan C. Moure , Domingo Benítez , Dolores I. Rexachs , Emilio Luque, Wide and efficient trace prediction using the local trace predictor, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Hyesoon Kim , José A. Joao , Onur Mutlu , Chang Joo Lee , Yale N. Patt , Robert Cohn, VPC prediction: reducing the cost of indirect branches via hardware-based dynamic devirtualization, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
	Alex Ramirez , Josep Ll. Larriba-Pey , Carlos Navarro , Mateo Valero , Josep Torrellas, Software Trace Cache for Commercial Applications, International Journal of Parallel Programming, v.30 n.5, p.373-395, October 2002

INDEX TERMS

Primary Classification:
C. Computer Systems Organization
C.5 COMPUTER SYSTEM IMPLEMENTATION
C.5.1 Large and Medium ("Mainframe") Computers
Subjects: Super (very large) computers

Additional Classification:
B. Hardware
B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
B.1.2 Control Structure Performance Analysis and Design Aids
Subjects: Simulation**
B.3 MEMORY STRUCTURES
B.3.2 Design Styles
Subjects: Cache memories

C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Parallel processors**

General Terms:
Algorithms, Design, Experimentation, Performance, Theory, Verification

REVIEW

"Mihail Sadeanu : Reviewer"

The authors present a hardware mechanism to predict multiple branches (MBs) and fetch multiple nonconsecutive basic blocks (MNC BB) simultaneously in each clock cycle (CC), which is viable and effective. The proposed solution fully utilizes th more...

Collaborative Colleagues:

Tse-Yu Yeh: colleagues

Deborah T. Marr: colleagues

Yale N. Patt: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player