Jun Wang
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.
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- M. Chidester and A. George. Parallel simulation of chip-multiprocessor architectures. ACM Transactions on Modeling and Computer Simulation, 12(3):176--200, July 2002. Google ScholarDigital Library
- 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.Google Scholar
- R. DeVries. Reducing null messages in misra's distributed discrete event simulation method. IEEE Transactions on Software Engineering, 16(1):82--91, January 1990. Google ScholarDigital Library
- J. Duato, S. Yalamanchili, and L. Ni. Interconnection Networks, an Engineering Approach. Morgan Kaufmann, 2003.Google Scholar
- R. Fujimoto. Parallel and Distributed Simulation Systems. John Wiley & Sons, 2000. Google ScholarDigital Library
- Intel. Pin - a dynamic binary instrumentation tool. http://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumen%tation-tool.Google Scholar
- S. Keckler, K. Olukotun, and H. Hofstee, editors. Multicore Processors and Systems. Springer, 2009. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- manifold.gatech.edu. Manifold. http://manifold.gatech.edu.Google Scholar
- 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.Google ScholarCross Ref
- J. Misra. Distributed discrete event simulation. ACM Computing Surveys, 18(1):39--65, March 1986. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google Scholar
Index Terms
- Optimizing parallel simulation of multicore systems using domain-specific knowledge
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 ComputingThe 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 EuropeIn 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