Automated design of finite state machine predictors for customized processors

ABSTRACT

Customized processors use compiler analysis and design automation techniques to take a generalized architectural model and create a specific instance of it which is optimized to a given application or set of applications. These processors offer the promise of satisfying the high performance needs of the embedded community while simultaneously shrinking design times.

Finite State Machines (FSM) are a fundamental building block in computer architecture, and are used to control and optimize all types of prediction and speculation, now even in the embedded space. They are used for branch prediction, cache replacement policies, and confidence estimation and accuracy counters for a variety of optimizations.

In this paper, we present a framework for automated design of small FSM predictors for customized processors. Our approach can be used to automatically generate small FSM predictors to perform well over a suite of applications, tailored to a specific application, or even a specific instruction. We evaluate the use of these customized FSM predictors for branch prediction over a set of benchmarks.

REFERENCES

• 1: Santosh G. Abraham , Scott A. Mahlke, Automatic and efficient evaluation of memory hierarchies for embedded systems, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.114-125, November 16-18, 1999, Haifa, Israel
• 2: M. Burtscher and B.G. Zorn. Prediction outcome history-based confidence estimation for load value prediction. JoLtrnal of Instruction- Level Parallelism, 1, 1999.
• 3: B. Calder and G. Reinman. A comparative survery of load speculation architectures. Journal of lnstruction Level Parallelism, 2, 2000.
• 4: Brad Calder , Glenn Reinman , Dean M. Tullsen, Selective value prediction, Proceedings of the 26th annual international symposium on Computer architecture, p.64-74, May 01-04, 1999, Atlanta, Georgia, United States
• 5: I-Cheng K. Chen , John T. Coffey , Trevor N. Mudge, Analysis of branch prediction via data compression, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.128-137, October 01-04, 1996, Cambridge, Massachusetts, United States
• 6: Joel Emer , Nikolas Gloy, A language for describing predictors and its application to automatic synthesis, Proceedings of the 24th annual international symposium on Computer architecture, p.304-314, June 01-04, 1997, Denver, Colorado, United States
• 7: Gulbin Ezer, Xtensa with User Defined DSP Coprocessor Microarchitectures, Proceedings of the 2000 IEEE International Conference on Computer Design: VLSI in Computers & Processors, p.335, September 17-20, 2000
• 8: Joseph A. Fisher , Paolo Faraboschi , Giuseppe Desoli, Custom-fit processors: letting applications define architectures, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.324-335, December 02-04, 1996, Paris, France
• 9: M. J. Flynn , R. I. Winner, ASIC microprocessors, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.237-243, August 14-16, 1989, Dublin, Ireland
• 10: Ricardo E. Gonzalez, Xtensa: A Configurable and Extensible Processor, IEEE Micro, v.20 n.2, p.60-70, March 2000 [doi>10.1109/40.848473]
• 11: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 12: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 13: Erik Jacobsen , Eric Rotenberg , J. E. Smith, Assigning confidence to conditional branch predictions, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.142-152, December 02-04, 1996, Paris, France
• 14: S. Leibson. Xscale (strongarm-2) muscles in. Microprocessor Report, September 2000.
• 15: Srilatha Manne , Artur Klauser , Dirk Grunwald, Pipeline gating: speculation control for energy reduction, Proceedings of the 25th annual international symposium on Computer architecture, p.132-141, June 27-July 02, 1998, Barcelona, Spain
• 16: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 17: S. McFarling. Combining branch predictors. Technical Report TN-36, Digital Equipment Corporation, Western Research Lab, June 1993.
• 18: H. Mulder , R. J. Portier, Cost-effective design of application specific VLIW processors using the SCARCE framework, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.35-42, August 14-16, 1989, Dublin, Ireland
• 19: Enric Musoll, Predicting the usefulness of a block result: a micro-architectural technique for high-performance low-power processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.238-247, November 16-18, 1999, Haifa, Israel
• 20: B. Ramakrishna Rau , Michael S. Schlansker, Embedded Computing: New Directions in Architecture and Automation, Proceedings of the 7th International Conference on High Performance Computing, p.225-244, December 17-20, 2000
• 21: Rahul Razdan , Michael D. Smith, A high-performance microarchitecture with hardware-programmable functional units, Proceedings of the 27th annual international symposium on Microarchitecture, p.172-180, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192749]
• 22: R. Rudell and A. Sangiovanni-Vincentelli. Multiple-valued minimization for pla optimization. IEEE Transactions on Computer Aided Design, 6(5):727-750, 1987.
• 23: R. Schreiber, S. Aditya, B.R. Ran, V. Kathall, S. Mahlke, S. Abraham, and G. Snider. High-level synthesis of nonprogrammable hardware accelerators. Technical report, Hewlett Packard Reseach Labs, 2000. HPL-2000-31.
• 24: Timothy Sherwood , Brad Calder, Loop Termination Prediction, Proceedings of the Third International Symposium on High Performance Computing, p.73-87, October 16-18, 2000
• 25: Timothy Sherwood , Suleyman Sair , Brad Calder, Predictor-directed stream buffers, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.42-53, December 2000, Monterey, California, United States [doi>10.1145/360128.360135]
• 26: 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
• 27: C.D. Snyder. Fpga processors cores get serious. Microprocessor Report, 14(9), September 2000.
• 28: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 29: Gary Tyson , Matthew Farrens , John Matthews , Andrew R. Pleszkun, Managing data caches using selective cache line replacement, International Journal of Parallel Programming, v.25 n.3, p.213-242, June 1997 [doi>10.1007/BF02700036]
• 30: G. Tyson, K. Lick, and M. Fattens. Limited dual path execution. Technical Report CSE-TR 345-97, University of Michigan, 1997.
• 31: 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
• 32: Zhi Alex Ye , Andreas Moshovos , Scott Hauck , Prithviraj Banerjee, CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit, Proceedings of the 27th annual international symposium on Computer architecture, p.225-235, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

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

  C. Computer Systems Organization

  J. Computer Applications

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

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