research-article

Optimizing parallel simulation of multicore systems using domain-specific knowledge

Authors:

Zhenjiang Dong,

Sudhakar Yalamanchili,

George RileyAuthors Info & Claims

SIGSIM PADS '13: Proceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

Pages 127 - 136

https://doi.org/10.1145/2486092.2486108

Published: 19 May 2013 Publication History

Abstract

This paper presents two optimization techniques for the basic Null-message algorithm in the context of parallel simulation of multicore computer architectures. Unlike the general, application-independent optimization methods, these are application-specific optimizations that make use of system properties of the simulation application. We demonstrate in two aspects that the domain-specific knowledge offers great potential for optimization. First, it allows us to send Null-messages much less eagerly, thus greatly reducing the amount of Null-messages. Second, the internal state of the simulation application allows us to make conservative forecast of future outgoing events. This leads to the creation of an enhanced synchronization algorithm called Forecast Null-message algorithm, which, by combining the forecast from both sides of a link, can greatly improve the simulation look-ahead. Compared with the basic Null-message algorithm, our optimizations greatly reduce the number of Null-messages and increase simulation performance significantly as a result. On a subset of the PARSEC benchmarks, a maximum speedup of about 6 is achieved with 17 LPs.

References

[1]

C. Bienia and K. Li. Parsec 2.0: A new benchmark suite for chip-multiprocessors. Proceedings of the 5th Annual Workshop on Modeling, Benchmarking and Simulation, 2009.

[2]

K. Chandy and J. Misra. Distributed simulation: a case study in design and verification of distributed programs. IEEE Transactions on Software Engineering, SE-5(5):440--452, 1979.

Digital Library

[3]

J. Chen, L. Dabbiru, D. Wong, M. Annavaram, and M. Dubois. Adaptive and speculative slack simulations of cmps on cmps. Proceedings of the 43rd Annual IEEE/ACM International Symposium on Microarchitecture, pages 523--534, 2010.

Digital Library

[4]

M. Chidester and A. George. Parallel simulation of chip-multiprocessor architectures. ACM Transactions on Modeling and Computer Simulation, 12(3):176--200, July 2002.

Digital Library

[5]

P. Clements, F. Bachmann, L. Bass, D. Garlan, J. Ivers, R. Little, P. Merson, R. Nord, and J. Stafford. Documenting Software Architectures: Views and Beyond. Addison-Wesley, 2nd edition, 2011.

[6]

R. DeVries. Reducing null messages in misra's distributed discrete event simulation method. IEEE Transactions on Software Engineering, 16(1):82--91, January 1990.

Digital Library

[7]

J. Duato, S. Yalamanchili, and L. Ni. Interconnection Networks, an Engineering Approach. Morgan Kaufmann, 2003.

[8]

R. Fujimoto. Parallel and Distributed Simulation Systems. John Wiley & Sons, 2000.

Digital Library

[9]

Intel. Pin - a dynamic binary instrumentation tool. http://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumen%tation-tool.

[10]

S. Keckler, K. Olukotun, and H. Hofstee, editors. Multicore Processors and Systems. Springer, 2009.

Digital Library

[11]

C. Kersey, A. Rodrigues, and S. Yalamanchili. A universal parallel front-end for execution driven microarchitecture simulation. Proceedings of the 2012 Workshop on Rapid Simulation and Performance Evaluation Methods and Tools, pages 25--32, 2012.

Digital Library

[12]

G. Loh, S. Subramaniam, and Y. Xie. Zesto: A cycle-level simulator for highly detailed microarchitecture exploration. International Symposium on Performance Analysis of Software and Systems, pages 53--64, 2009.

[13]

manifold.gatech.edu. Manifold. http://manifold.gatech.edu.

[14]

J. Miller, H. Kasture, G.Kurian, C. Gruenwald, N. Beckmann, C. Celio, J. Eastep, and A. Agarwal. Graphite: A distributed parallel simulator for multicores. Proceedings of the 16th International Symposium on High-Performance Computer Architecture, pages 1--12, 2010.

[15]

J. Misra. Distributed discrete event simulation. ACM Computing Surveys, 18(1):39--65, March 1986.

Digital Library

[16]

A. Rodrigues, K. Hemmert, B. Barrett, C. Kersey, R. Oldfield, M. Weston, R. Risen, J. Cook, P. Rosenfeld, E. CooperBalls, and B.Jacob. The structural simulation toolkit. ACM SIGMETRICS Performance Evaluation Review, 38(4):37--42, March 2011.

Digital Library

[17]

W.-K. Su and C. Seitz. Variants of the chandy-misra-bryant distributed discrete-event simulation algorithm. Technical Report Caltech-CS-TR-88-22, California Institute of Technology, 1988.

Cited By

Andelfinger PXu YEckhoff DCai WKnoll A(2020)Fidelity and Performance of State Fast-forwarding in Microscopic Traffic SimulationsACM Transactions on Modeling and Computer Simulation10.1145/336601930:2(1-26)Online publication date: 10-Apr-2020
https://dl.acm.org/doi/10.1145/3366019
Andelfinger PXu YCai WEckhoff DKnoll AQuaglia FPellegrini ATheodoropoulos G(2018)Fast-Forwarding Agent States to Accelerate Microscopic Traffic SimulationsProceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3200921.3200923(113-124)Online publication date: 14-May-2018
https://dl.acm.org/doi/10.1145/3200921.3200923
Dong ZWang JRiley GYalamanchili SBarros FPerumalla KEwald R(2014)An efficient front-end for timing-directed parallel simulation of multi-core systemProceedings of the 7th International ICST Conference on Simulation Tools and Techniques10.4108/icst.simutools.2014.254638(201-206)Online publication date: 17-Mar-2014
https://dl.acm.org/doi/10.4108/icst.simutools.2014.254638
Show More Cited By

Index Terms

Optimizing parallel simulation of multicore systems using domain-specific knowledge
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
      1. Discrete-event simulation
      2. Massively parallel and high-performance simulations

Recommendations

FNM: An Enhanced Null-Message Algorithm for Parallel Simulation of Multicore Systems

As multicore computer systems become increasingly complex, parallel simulation is becoming an important tool for exploring design space and evaluating design tradeoffs. The key to the success of parallel simulation is the ability to maintain a high ...
Parallel discrete event simulation for DEVS cellular models using a GPU
HPC '12: Proceedings of the 2012 Symposium on High Performance Computing

The discrete event systems specification (DEVS) simulation has been studied to analyze complex homogeneous systems which is represented by the cellular models. In the simulation of large-scale DEVS cellular model, it requires a high-performance ...
Parallel VHDL simulation
DATE '98: Proceedings of the conference on Design, automation and test in Europe

In this paper we evaluate parallel VHDL simulation based on conservative parallel discrete event simulation (conservative PDES) algorithms. We focus on a conservative simulation algorithm based on critical and external distances. This algorithm exploits ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSIM PADS '13: Proceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

May 2013

426 pages

ISBN:9781450319201

DOI:10.1145/2486092

General Chair:
Margaret L. Loper
Georgia Institute of Technology, USA
,
Program Chair:
Gabriel A. Wainer
Carleton University, Canada

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSIM-PADS '13

Sponsor:

SIGSIM

SIGSIM-PADS '13: SIGSIM Principles of Advanced Discrete Simulation

May 19 - 22, 2013

Québec, Montr©al, Canada

Acceptance Rates

SIGSIM PADS '13 Paper Acceptance Rate 29 of 75 submissions, 39%;

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
162
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Andelfinger PXu YEckhoff DCai WKnoll A(2020)Fidelity and Performance of State Fast-forwarding in Microscopic Traffic SimulationsACM Transactions on Modeling and Computer Simulation10.1145/336601930:2(1-26)Online publication date: 10-Apr-2020
https://dl.acm.org/doi/10.1145/3366019
Andelfinger PXu YCai WEckhoff DKnoll AQuaglia FPellegrini ATheodoropoulos G(2018)Fast-Forwarding Agent States to Accelerate Microscopic Traffic SimulationsProceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3200921.3200923(113-124)Online publication date: 14-May-2018
https://dl.acm.org/doi/10.1145/3200921.3200923
Dong ZWang JRiley GYalamanchili SBarros FPerumalla KEwald R(2014)An efficient front-end for timing-directed parallel simulation of multi-core systemProceedings of the 7th International ICST Conference on Simulation Tools and Techniques10.4108/icst.simutools.2014.254638(201-206)Online publication date: 17-Mar-2014
https://dl.acm.org/doi/10.4108/icst.simutools.2014.254638
Andelfinger PJünemann KHartenstein HBarros FPerumalla KEwald R(2014)Parallelism potentials in distributed simulations of Kademlia-based peer-to-peer networksProceedings of the 7th International ICST Conference on Simulation Tools and Techniques10.4108/icst.simutools.2014.254609(41-50)Online publication date: 17-Mar-2014
https://dl.acm.org/doi/10.4108/icst.simutools.2014.254609
Wang JBeu JBheda RConte TDong ZKersey CRasquinha MRiley GSong WXiao HXu PYalamanchili S(2014)Manifold: A parallel simulation framework for multicore systems2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS.2014.6844466(106-115)Online publication date: Mar-2014
https://doi.org/10.1109/ISPASS.2014.6844466
Dong ZWang JRiley GYalamanchili S(2013)A Study of the Effect of Partitioning on Parallel Simulation of Multicore SystemsProceedings of the 2013 IEEE 21st International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems10.1109/MASCOTS.2013.55(375-379)Online publication date: 14-Aug-2013
https://dl.acm.org/doi/10.1109/MASCOTS.2013.55

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten