Efficient design space exploration of high performance embedded out-of-order processors

ABSTRACT

Previous work on efficient customized processor design primarily focused on in-order architectures. However, with the recent introduction of out-of-order processors for high-end high-performance embedded applications, researchers and designers need to address how to automate the design process of customized out-of-order processors. Because of the parallel execution of independent instructions in out-of-order processors, in-order processor design methodologies which subdivide the search space in independent components are unlikely to be effective in terms of accuracy for designing out-of-order processors. In this paper we propose and evaluate various automated single- and multi-objective optimizations for exploring out-of-order processor designs. We conclude that the newly proposed genetic local search algorithm outperforms all other search algorithms in terms of accuracy. In addition, we propose two-phase simulation in which the first phase explores the design space through statistical simulation; a region of interest is then simulated through detailed simulation in the second phase. We show that simulation time speedups can be obtained of a factor 2.2X to 7.3X using two-phase simulation.

REFERENCES

• 1: Jakob Axelsson, Architecture Synthesis and Partitioning of Real-Time Systems: A Comparison of Three Heuristic Search Strategies, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.161, March 24-26, 1997
• 2: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 3: Lieven Eeckhout , Robert H. Bell Jr. , Bastiaan Stougie , Koen De Bosschere , Lizy K. John, Control Flow Modeling in Statistical Simulation for Accurate and Efficient Processor Design Studies, Proceedings of the 31st annual international symposium on Computer architecture, p.350, June 19-23, 2004, München, Germany
• 4: William Fornaciari , Donatella Sciuto , Cristina Silvano , Vittorio Zaccaria, A design framework to efficiently explore energy-delay tradeoffs, Proceedings of the ninth international symposium on Hardware/software codesign, p.260-265, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371752]
• 5: Matthias Gries, Methods for evaluating and covering the design space during early design development, Integration, the VLSI Journal, v.38 n.2, p.131-183, December 2004 [doi>10.1016/j.vlsi.2004.06.001]
• 6: G. J. Hekstra, P. B. G. D. La Hei, and F. W. Sijstermans. Tri-Media CPU64 design space exploration. In ICCD, Oct. 2001.
• 7: A. Jaszkiewicz. Multiple Objective Metaheuristic Algorithms for Combinatorial Optimization. PhD thesis, Poznan University of Technology, Poland, 2001.
• 8: Vinod Kathail , Shail Aditya , Robert Schreiber , B. Ramakrishna Rau , Darren C. Cronquist , Mukund Sivaraman, PICO: Automatically Designing Custom Computers, Computer, v.35 n.9, p.39-47, September 2002 [doi>10.1109/MC.2002.1033026]
• 9: S. Mohanty , V. K. Prasanna , S. Neema , J. Davis, Rapid design space exploration of heterogeneous embedded systems using symbolic search and multi-granular simulation, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 10: Sébastien Nussbaum , James E. Smith, Modeling Superscalar Processors via Statistical Simulation, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.15-24, September 08-12, 2001
• 11: Mark Oskin , Frederic T. Chong , Matthew Farrens, HLS: combining statistical and symbolic simulation to guide microprocessor designs, Proceedings of the 27th annual international symposium on Computer architecture, p.71-82, June 2000, Vancouver, British Columbia, Canada
• 12: Maurizio Palesi , Tony Givargis, Multi-objective design space exploration using genetic algorithms, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774804]
• 13: Timothy Sherwood , Mark Oskin , Brad Calder, Balancing design options with Sherpa, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023843]
• 14: G. Snider. Spacewalker: Automated design space exploration for embedded computer systems. Tech Report HPL-2001-220, HP Laboratories Palo Alto, Sept. 2001.
• 15: V. Srinivasan , S. Radhakrishnan , R. Vemuri, Hardware/software partitioning with integrated hardware design space exploration, Proceedings of the conference on Design, automation and test in Europe, p.28-35, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 16: Rabin A. Sugumar , Santosh G. Abraham, Efficient simulation of caches under optimal replacement with applications to miss characterization, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.24-35, May 10-14, 1993, Santa Clara, California, United States
• 17: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the strength pareto evolutionary algorithm. Tech Report TIK-Report 103, ETH Zurich, May 2001.
• 18: E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257--271, Nov. 1999.