FREE ELECTRONIC LIBRARY - Online materials, documents

Pages:     | 1 |   ...   | 3 | 4 ||

«Automated Design of Finite State Machine Predictors Timothy Sherwood Brad Calder Department of Computer Science and Engineering University of ...»

-- [ Page 5 ] --

We first examine using our automated approach to automatically generate a confidence estimation FSM to use for value prediction in a general purpose processor. The results show that we are able to automatically generate confidence estimation FSMs the can achieve higher accuracy for greater coverage than previously proposed saturating up/down counters. More importantly, our framework automatically finds a Pareto optimal curve of custom FSMs solutions for trading off accuracy versus coverage.

We also present a customized branch prediction architecture that makes use of these custom built finite state machine predictors. The FSM predictors are generated for branches that are not easily captured by local two-bit counters. These custom state machines take up little area, and can efficiently and accurately capture the global correlation behavior of the target application. The global correlation is shown to be captured across input sets and results are presented for a variety of predictor sizes. For all of the programs examined, our custom predictors achieve a misprediction rate less than a general purpose predictor of twice it’s size or more. For two of the programs, the custom branch misprediction rates are lower than general purpose predictors of five times their size.

References [1] S. G. Abraham and S. A. Mahlke. Automatic and efficient evaluation of memory hierarchies for embedded systems. In 32nd International Symposium on Microarchitecture, 1999.

[2] M. Burtscher and B.G. Zorn. Prediction outcome history-based confidence estimation for load value prediction. Journal of Instruction-Level Parallelism, 1, 1999.

[3] B. Calder, P. Feller, and A. Eustace. Value profiling and optimization. Journal of Instruction Level Parallelism, 1999.

[4] B. Calder and G. Reinman. A comparative survery of load speculation architectures. Journal of Instruction Level Parallelism, 2, 2000.

[5] B. Calder, G. Reinman, and D. Tullsen. Selective value prediction. In 26th Annual International Symposium on Computer Architecture, June 1999.

[6] I.-C. Chen, J.T. Coffey, and T.N. Mudge. Analysis of branch prediction via data compression. In Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, October 1996.

[7] T-F. Chen and J-L. Baer. Effective hardware-based data prefetching for high performance processors. IEEE Transactions on Computers, 5(44):609–623, May 1995.

[8] R. J. Eickemeyer and S. Vassiliadis. A load instruction unit for pipelined processors. IBM Journal of Research and Development, 37:547–564, July 1993.

[9] J. Emer and N. Gloy. A language for describing predictors and its application to automatic synthesis. In 24th Annual International Symposium on Computer Architecture, June 1997.

[10] G. Ezer. Xtensa with user defined dsp coprocessor microarchitectures. In Proceedings of the International Conference on Computer Design, 2000 (ICCD2000), pages 335–342, September 2000.

[11] J. A. Fisher, P. Faraboschi, and G. Desoli. Custom-fit processors: Letting applications define architectures. In 29th International Symposium on Microarchitecture, pages 324–335, December 1996.

[12] M. J. Flynn and R. I. Winner. Asic microprocessors. In 23th International Symposium on Microarchitecture, pages 237–243, 1990.

[13] F. Gabbay and A. Mendelson. Speculative execution based on value prediction. EE Department TR 1080, Technion Israel Institue of Technology, November 1996.

[14] J. Gonzalez and A. Gonzalez. The potential of data value speculation to boost ilp. In 12th International Conference on Supercomputing, 1998.

[15] R. E. Gonzalez. Xtensa: A configurable and extensible processor. IEEE Micro, 20(2):60–70, March-April 2000.

[16] D. Grunwald, A. Klauser, S. Manne, and A. Pleskun. Confidence estimation for speculation control. In 25th Annual International Symposium on Computer Architecture, June 1998.

[17] T.H. Heil and J.E. Smith. Selective dual path execution. Technical report, University of Wisconsin - Madison, November 1996.

[18] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[19] E. Jacobsen, E. Rotenberg, and J.E. Smith. Assigning confidence to conditional branch predictions. In 29th International Symposium on Microarchitecture, December 1996.

[20] A. Klauser, A. Paithankar, and D. Grunwald. Selective eager execution on the polypath architecture. In 25th Annual International Symposium on Computer Architecture, June 1998.

[21] S. Leibson. Xscale (strongarm-2) muscles in. Microprocessor Report, September 2000.

[22] M. H. Lipasti, C. B. Wilkerson, and J. P. Shen. Value locality and load value prediction. In 17th International Conference on Architectural Support for Programming Languages and operating Systems, pages 138–147, October 1996.

[23] M.H. Lipasti and J.P. Shen. Exceeding the dataflow limit via value prediction. In 29th International Symposium on Microarchitecture, December 1996.

[24] S. Manne, A. Klauser, and D. Grunwald. Pipeline gating: Speculation control for energy reduction. In 25th Annual International Symposium on Computer Architecture, June 1998.

[25] S. McFarling. Program optimization for instruction caches. In Proceedings of the Third International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS III), pages 183–191, April 1989.

[26] S. McFarling. Combining branch predictors. Technical Report TN-36, Digital Equipment Corporation, Western Research Lab, June 1993.

[27] H. Mulder and R. J. Portier. Cost-effective design of application specific vliw processors using the scarce framework.

In 22th International Symposium on Microarchitecture, 1989.

[28] E. Musoll. Predicting the usefulness of a block result: a micro-architectural technique for high-performance low-power processors. In 32nd International Symposium on Microarchitecture, November 1999.

[29] B. Ramakrishna Rau and Michael S. Schlansker. Embedded computing: New directions in architecture and automation.

In 7th International Conference on High-Performance Computing (HiPC2000), 2000.

[30] R. Razdan and M. D. Smith. A high-performance microarchitecture with hardware-programmable functional units. In 27th International Symposium on Microarchitecture, pages 172–180, 1994.

[31] G. Reinman and B. Calder. Predictive techniques for aggressive load speculation. In 31st International Symposium on Microarchitecture, 1998.

[32] R. Rudell and A. Sangiovanni-Vincentelli. Multiple-valued minimization for pla optimization. IEEE Transactions on Computer Aided Design, 6(5):727–750, 1987.

[33] Y. Sazeides and J. E. Smith. The predictability of data values. In 30th International Symposium on Microarchitecture, pages 248–258, December 1997.

[34] R. Schreiber, S. Aditya, B.R. Rau, V. Kathail, S. Mahlke, S. Abraham, and G. Snider. High-level synthesis of nonprogrammable hardware accelerators. Technical report, Hewlett Packard Reseach Labs, 2000. HPL-2000-31.

[35] T. Sherwood and B. Calder. Loop termination prediction. In 3rd International Symposium on High Performance Computing, October 2000.

[36] T. Sherwood and B. Calder. Automated design of finite state machine predictors for customized processors. In 28th Annual Intl. Symposium on Computer Architecture, June 2001.

[37] T. Sherwood, E. Perelman, and B. Calder. Basic block distribution analysis to find periodic behavior and simulation points in applications. In International Conference on Parallel Architectures and Compilation Techniques, September 2001.

[38] T. Sherwood, E. Perelman, G. Hamerly, and B. Calder. Automatically characterizing large scale program behavior. In Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, October

2002. http://www.cs.ucsd.edu/users/calder/simpoint/.

[39] T. Sherwood, S. Sair, and B. Calder. Predictor-directed stream buffers. In 33rd International Symposium on Microarchitecture, December 2000.

[40] J. E. Smith. A study of branch prediction strategies. In 8th Annual International Symposium of Computer Architecture, pages 135–148. ACM, 1981.

[41] C.D. Snyder. Fpga processors cores get serious. Microprocessor Report, 14(9), September 2000.

[42] G.S. Sohi, S.E. Breach, and T.N. Vijaykumar. Multiscalar processors. In 22nd Annual International Symposium on Computer Architecture, pages 414–425, June 1995.

[43] A. Srivastava and A. Eustace. Atom: A system for building customized program analysis tools. In Proceedings of the Conference on Programming Language Design and Implementation, pages 196–205. ACM, 1994.

[44] J. Tubella and A. Gonzalez. Control speculation in multithreaded processors through dynamic loop detection. In 4th International Symposium on High Performance Computer Architecture, February 1998.

[45] G. Tyson, M. Farrens, J. Mathews, and A. Pleszken. Managing data caches using selective cache line replacement.

International Journal of Parallel Programming, 25(3), 1997.

[46] G. Tyson, K. Lick, and M. Farrens. Limited dual path execution. Technical Report CSE-TR 345-97, University of Michigan, 1997.

[47] S. Wallace, B. Calder, and D.M. Tullsen. Threaded multiple path execution. In 22nd Annual International Symposium on Computer Architecture, June 1998.

[48] K. Wang and M. Franklin. Highly accurate data value prediction using hybrid predictors. In 30th Annual International Symposium on Microarchitecture, December 1997.

[49] T.Y. Yeh and Y.N. Patt. A comparison of dynamic branch predictors that use two levels of branch history. In 20th Annual International Symposium on Computer Architecture, pages 257–266, San Diego, CA, May 1993. ACM.

[50] A. Zhi, A. Moshovos, S. Hauck, and P. Banerjee. Chimaera: A high performance architecture with a tightly-coupled

Pages:     | 1 |   ...   | 3 | 4 ||

Similar works:

«Multiframe Steel Codes Windows Version 16 User Manual © Bentley Systems, Incorporated 2013 License & Copyright Multiframe Steel Codes software & User Manual © 2013 Bentley Systems, Incorporated iii Table of Contents License & Copyright Table of Contents About this manual Chapter 1 Getting Started About Multiframe Steel Codes Design Codes Installing Multiframe Steel Codes Starting Multiframe Steel Codes Adding or Removing Steel Design Codes Design Overview Design Members Bending Checks Tension...»

«SOLANO COMMUNITY COLLEGE DISTRICT GOVERNING BOARD UNADOPTED MINUTES August 18, 2010 1. CALL TO ORDER A meeting of the Solano Community College District Governing Board was called to order at 6:30 p.m., on Wednesday, August 18, 2010, in the Administration Building, Room 626, at 4000 Suisun Valley Road, Fairfield, California 94534, by Board President Honeychurch. 2. PLEDGE OF ALLEGIANCE TO THE FLAG OF THE UNITED STATES OF AMERICA Board President Honeychurch led those present in the pledge of...»

«Taunton School Boys' Outdoor and Indoor Hockey Records (with Girls' Hockey Top Ten Performances) Mr J P Evans started hockey at Taunton School in the Spring Term of 1937. The weather was poor that term and the only match was against a Masters XI at the end of term (the result of which is unknown). The first recorded School hockey match was at home against King's College, Taunton in the Spring Term of 1938. Taunton School won the game 2-1. Since then hockey has grown in to a major sport in the...»

«PREPARING AND APPLYING DECORATIVE WOOD VENEERS AND INLAYS TO SUBSTRATES Prepared by James MacGregor for the Decorative Wood Veneers Association as part of a trade training education resource on the use of natural timber veneers – December 2004 This project was produced in collaboration with the: ACKNOWLEDGEMENTS This resource is based on Australia National Training Authority ABC 607 – “Veneer Processes”, input from the “Manual for Decorative Wood Veneering Technology” by Dr Barbara...»

«HEADMASTER‟S LETTER AND INFORMATION July 2012 Contents Headmaster‟s Letter Medical Centre information Riding at King‟s 6th form Bar approval form A Level & GCSE results information & dates Extra time in exams/Learning Support Fixture List Michaelmas 2012 (pdf attached) 11 July 2012 Dear Parents What a wet old term it‟s been. As I write this the sun is just about breaking through, though the forecast remains steadfastly gloomy. Despite the weather we had a very upbeat Parents‟ Day, I...»

«MISSIONAL CHURCH PJ Smyth CONTENTS PART 1: A COMMUNITY ON MISSION 1.1 A high view of church 1.2 A community on mission 1.3 The church as a family 1.4 Guarding community whilst on mission PART 2: ON MISSION DELIBERATELY 2.1 A theological basis for missional church 2.2 Guarding mission whilst being a community 2.3 Seven steps to becoming a missional church PART 3: ON MISSION CONTEXUALLY 3.1 Culture and contextualization 3.2 Master class in contextualization: Paul in Athens PART 1 A COMMUNITY ON...»

«Virginia Beach Unified Softball League (VBUSL) Pigtail Softball March 2013 Southside Softball League (VBUSL) BYLAWS (FAST PITCH). The object of this league shall be.To provide a wholesome and enjoyable recreational activity for the participants. To develop character, skill, sportsmanship, and good will among teams and individuals participating.PLAYER ELIGIBILITY AND AGE GROUPS 1. This league is open to girls,5 – 7 and 7 -9 years of age. A player’s age on May 1st determines her eligibility....»

«Smart Vending Anywhere System Solution For UTILITY COMPANY SHENZHEN INHEMETER CO., LTD Smart Vending Anywhere System Solution CONTENTS 1. System Introduction 1.1 Smart Vending System Diagram 1.2 Vending Solution 1.3 System Structure 2. Smart Vending Anywhere (SMARTvend) 2.1 System Introduction 2.2 System Features 2.3 System Server 2.4 Vending Station 2.5 Third Party Data Interface 2.6 Compatibility and Expansibility 2.7 Load bearing Capacity 2.8 Transaction capacity 2.9 Report Export 2.10 The...»

«VOX 2011 The Magazine of the Academy of Saint Cecilia Contributions to our magazine and newsletter are always welcome, and should be posted or emailed to our address: The Academy of St Cecilia c/o Music Department Cathedral House Westminster Bridge Road LONDON SE1 7HY Tel: 020 8682 4431 Email: master@academyofsaintcecilia.com VOX The Magazine of the Academy of Saint Cecilia Master Mark Johnson www.academyofsaintcecilia.com The Academy of St Cecilia Patrons: The Most Hon. The Marquess of...»

«FACULTAD de FILOSOFÍA Y LETRAS DEPARTAMENTO de FILOLOGÍA INGLESA Grado en Estudios Ingleses TRABAJO DE FIN DE GRADO A Nightmarish Tomorrow: Orwellian Methods of Social Control in Contemporary Dystopian Literature Pablo Peláez Galán Tutora: Tamara Pérez Fernández 2014/2015 ABSTRACT Dystopian literature is considered a branch of science fiction which writers use to portray a futuristic dark vision of the world, generally dominated by technology and a totalitarian ruling government that...»

«AWARENESS BOUND AND UNBOUND: REALIZING THE NATURE OF ATTENTION David R. Loy Theology Department, Xavier University, Cincinnati No wisdom can we get hold of, no highest perfection, No Bodhisattva, no thought of enlightenment either. When told of this, if not bewildered and in no way anxious, A Bodhisattva courses in the Tathagata’s wisdom. In form, in feeling, will, perception and awareness Nowhere in them they find a place to rest on. Without a home they wander, dharmas never hold them, Nor...»

«DISCUSSION PAPER SERIES IZA DP No. 1975 Five Open Questions About Prediction Markets Justin Wolfers Eric Zitzewitz February 2006 Forschungsinstitut zur Zukunft der Arbeit Institute for the Study of Labor Five Open Questions About Prediction Markets Justin Wolfers Wharton, University of Pennsylvania, CEPR, NBER and IZA Bonn Eric Zitzewitz Stanford GSB Discussion Paper No. 1975 February 2006 IZA P.O. Box 7240 53072 Bonn Germany Phone: +49-228-3894-0 Fax: +49-228-3894-180 Email: iza@iza.org Any...»

<<  HOME   |    CONTACTS
2017 www.thesis.dislib.info - Online materials, documents

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.