Phase guided sampling for efficient parallel application simulation

ABSTRACT

Simulating chip-multiprocessor systems (CMP) can take a long time. For single-threaded workloads, earlier work has shown the utility of phase analysis, that is identification of repetitive program behaviors, in reducing overall simulation time while maintaining an acceptable loss in accuracy. To cope with multithreaded workloads, a combination of phases from all executing threads must be taken into consideration since inter-thread interference may distort the homogeneity of each phases' true performance. Unfortunately, phase analysis does not work for multithreaded (MT) workloads because the possible phase combinations in an inherently nondeterministic execution model grows exponentially with the number of threads. To this end, we propose a new technique to reduce the number of simulation samples by synthesizing samples from similar phase combinations. We present a simple cost function for measuring the similarity between phase combinations and by using the individual thread samples from the similar phase combinations, a new sample can be constructed. This cost function provides a convenient control knob for exploiting tradeoffs between simulation speed and accuracy. Our experimental results show that in most cases, properly setting the cost function's threshold can yield a reduction in sampling by 90%, while maintaining error to less than 5%.

REFERENCES

• 1: http://www.intel.com/software/products/vtune.
• 2: http://www.vastsystems.com.
• 3: M. V. Biesbrouck, L. Eeckhout, and B. Calder. Considering all starting points for simultaneous multithreading simulation. In IEEE International Symposium on Performance Analysis of Systems and Software, March 2006.
• 4: M. Van Biesbrouck , T. Sherwood , B. Calder, A co-phase matrix to guide simultaneous multithreading simulation, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.45-56, March 10-12, 2004
• 5: H. Jin, M. Frumkin, and J. Yan. The openmp implementation of nas parallel benchmarks and its performance. In NAS Technical Report NAS-99-011, October 1999.
• 6: Joshua L. Kihm , Daniel A. Connors, Statistical Simulation of Multithreaded Architectures, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.67-74, September 27-29, 2005 [doi>10.1109/MASCOT.2005.69]
• 7: J. Lau, E. Perelman, G. Hamerly, T. Sherwood, and B. Calder. Motivation for variable length intervals and hierarchical pahse behavior. In IEEE International Symposium on Performance Analysis of Systems and Software, March 2005.
• 8: V. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet Physics Doklady, February 1966.
• 9: Harish Patil , Robert Cohn , Mark Charney , Rajiv Kapoor , Andrew Sun , Anand Karunanidhi, Pinpointing Representative Portions of Large Intel® Itanium® Programs with Dynamic Instrumentation, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.81-92, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.28]
• 10: Erez Perelman , Greg Hamerly , Michael Van Biesbrouck , Timothy Sherwood , Brad Calder, Using SimPoint for accurate and efficient simulation, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 11: E. Perelman, M. Polito, J.-Y. Bouguet, J. Sampson, B. Calder, and C. Dulong. Detecting phases in parallel applications on shared memory architectures. In IEEE International Parallel and Distributed Processing Symposium, April 2006.
• 12: T. Sherwood, E. Perelman, G. Hamerly, S. Sair, and B. Calder. Discovering and exploiting program phases. In IEEE Micro, December 2003.
• 13: 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
• 14: Joshua J. Yi , Sreekumar V. Kodakara , Resit Sendag , David J. Lilja , Douglas M. Hawkins, Characterizing and Comparing Prevailing Simulation Techniques, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.266-277, February 12-16, 2005 [doi>10.1109/HPCA.2005.8]
• 15: Joshua J. Yi , David J. Lilja, Simulation of Computer Architectures: Simulators, Benchmarks, Methodologies, and Recommendations, IEEE Transactions on Computers, v.55 n.3, p.268-280, March 2006 [doi>10.1109/TC.2006.44]

INDEX TERMS

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

General Terms:
Measurement, Performance

Keywords:
chip multiprocessors, multithreading, phase analysis, sampling, simulation