B2Sim:: a fast micro-architecture simulator based on basic block characterization

ABSTRACT

State-of-the-art architectural simulators support cycle accurate pipeline execution of application programs. However, it takes days and weeks to complete the simulation of even a moderate-size program. During the execution of a program, program behavior does not change randomly but changes over time in a predictable/periodic manner. This behavior provides the opportunity to limit the use of a pipeline simulator. More precisely, this paper presents a hybrid simulation engine, named B²Sim for (cycle-characterized) Basic Block based Simulator, where a fast cache simulator e.g., sim-cache and a slow pipeline simulator e.g., sim-outorder are employed together. B²Sim reduces the runtime of architectural simulation engines by making use of the instruction behavior within executed basic blocks. We have integrated B²Sim into SimpleScalar and have achieved on average a factor of 3.3 times speedup on the SPEC2000 benchmark and Media-bench programs compared to conventional pipeline simulator while maintaining the accuracy of the simulation results with less than 1% CPI error on average.

REFERENCES

• 1: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 2: Tim. Sherwood, B. Calder, "Time Varying Behavior of Programs," UCSD Technical Reports, Aug. 1999.
• 3: Timothy Sherwood , Erez Perelman , Brad Calder, Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.3-14, September 08-12, 2001
• 4: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 5: G. Hamerly, E. Perelman, J. Lau, B. Calder, "Simpoint 3.0: Faster and More Flexible Program Analysis," Journal of Instruction Level Parallelism 7 (JILP), 2005.
• 6: Ashutosh S. Dhodapkar , James E. Smith, Comparing Program Phase Detection Techniques, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.217, December 03-05, 2003
• 7: Mehrdad Reshadi , Prabhat Mishra , Nikil Dutt, Instruction set compiled simulation: a technique for fast and flexible instruction set simulation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776026]
• 8: M. Poncino , Jianwen Zhu, DynamoSim: a trace-based dynamically compiled instruction set simulator, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.131-136, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382557]
• 9: Achim Nohl , Gunnar Braun , Oliver Schliebusch , Rainer Leupers , Heinrich Meyr , Andreas Hoffmann, A universal technique for fast and flexible instruction-set architecture simulation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513927]
• 10: M. Lajolo, L. Lavagno, A. S. Vincentelli, "Fast Instruction Cache Simulation Strategies in a Hardware/Software Co-design Environment," In Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC), 1999.
• 11: SimpleScalar LLC: http://www.simplescalar.com/
• 12: T. Meyerowitz, A. S. Vincentelli, "Modeling Micro-architectural Performance using Metropolis: Memory System Modeling," SRC Report, Feb. 2003.
• 13: Standard Performance Evaluation Corporation (SPEC) http://www.spec.org
• 14: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: Simple tutorial version 4 at: http://www.simplescalar.com/

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Design, Measurement, Performance

Keywords:
basic block, micro-architecture simulation, program behavior