Empirical Study on Entity Interaction Graph of Large-Scale Parallel Simulations
Abstract
The entity interaction graph is an important metaphor for understanding the simulation execution of complex systems on parallel computing environment. Current performance tuning techniques often explore interrelated factors affecting performance, but ignore systematic analysis on the structure and behavior of entity interactions. This paper reports an empirical study on the entity interaction graphs of three systems chosen from different domains: Internet models, molecular dynamics, and social dynamics, respectively. The results of complex networks analysis on the entity interaction graphs demonstrate that the heterogeneous distribution of connections and highly clustering are universal in these complex systems. Generally, these properties are not obvious at the system modeling stage. Moreover, mutual information theory is used to measure the ``principle of persistence" as the predictability of partitioning on multiple processors. This study facilitates better understanding and quantifying of the interaction complexity and provides implications on performance tuning for parallel simulation of large- scale complex systems.
References
[1]
R. M. Fujimoto, Parallel and Distributed Simulation Systems. Wiley-Interscience, January 2000.
[2]
Y. Yao and Y. Zhang, "Solution for analytic simulation based on parallel processing," Journal of System Simulation, vol. 20(24), pp. 6617-6621, 2008.
[3]
R. Winter, "Modeling the internet routing topology - in less than 24h," in ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation (PADS'09), 2009, pp. 72-79.
[4]
N. J. Krogan and G. Cagney, "Global landscape of protein complexes in the yeast saccharomyces cerevisiae," Nature, vol. 440(7084), pp. 637-643, 2006.
[5]
L. Barrett, S. Eubank, V. S. A. Kumar, and M. V. Marathe, "Understanding large scale social and infrastructure networks: A simulation based approach," SIAM news: The Mathematics of Networks, 2004.
[6]
H. Levin, M. Schapira, and A. Zohar, "Interdomain routing and games," in Proceedings of the 40th annual ACM symposium on Theory of computing (STOC'08), 2008, pp. 57-66.
[7]
W. S. Hlavacek, J. R. Faeder, M. L. Blinov, A. S. Perelson, and B. Goldstein, "The complexity of complexes in signal transduction," Biotechnology and Bioengineering, vol. 84(7), pp. 783-794, 2003.
[8]
V. Balakrishnan, P. Frey, N. B. Abu-Ghazaleh, and P. A. Wilsey, "A framework for performance analysis of parallel discrete event simulators," in Proceedings of the 29th conference on Winter simulation (WSC '97), 1997, pp. 429-436.
[9]
J. Liu, D. Nicol, B. Premore, and A. Poplawski, "Performance prediction of a parallel simulator," in Proceedingsof the Thirteenth Workshop on Parallel and Distributed Simulation, 1999, pp. 156-164.
[10]
C. Carothers and K. S. Perumalla, "On deciding between conservative and optimistic approaches on massively parallel platforms," in Proceedings of the 2010 Winter Simulation Conference, 2010, pp. 678-687.
[11]
G. Zheng, "Achieving high performance on extremely large parallel machines: performance prediction and load balancing," Ph.D. dissertation, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 2005.
[12]
A. Bhatelé, L. V. Kalé, and S. Kumar, "Dynamic topology aware load balancing algorithms for molecular dynamics applications," in Proceedings of the 23rd international conference on Supercomputing (ICS'09), 2009, pp. 110-116.
[13]
S. Thulasidasan, S. Kasiviswanathan, S. Eidenbenz, and P. Romero, "Explicit spatial scattering for load balancing in conservatively synchronized parallel discrete event simulations," in 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation (PADS), May 2010, pp. 1-8.
[14]
B. Hou and Y. Yao, "Commpar: A community-based model partitioning approach for large-scale networked social dynamics simulation," in IEEE/ACM 14th International Symposium on Distributed Simulation and Real Time Applications (DS-RT), 2010, pp. 7-13.
[15]
A.-L. Barabási, "Scale-Free Networks: A Decade and Beyond," Science, vol. 325, no. 5939, pp. 412-413, 2009.
[16]
G. Yaun, C. Carothers, and S. Kalyanaraman, "Large-scale tcp models using optimistic parallel simulation," in Proceedings. Seventeenth Workshop on Parallel and Distributed Simulation (PADS 2003), 2003, pp. 153-162.
[17]
C. Carothers, D. Bauer, and S. Pearce, "Ross: a high-performance, low memory, modular time warp system," in Proceedings of the Fourteenth Workshop on Parallel and Distributed Simulation (PADS 2000), 2000, pp. 53-60.
[18]
J. Phillips, G. Zheng, S. Kumar, and L. Kale, "Namd: Biomolecular simulation on thousands of processors," in ACM/IEEE 2002 Conference Supercomputing, 2002, p. 36.
[19]
L. V. Kale and S. Krishnan, "Charm++: A portable concurrent object oriented system based on c++," in Proceedings of the Conference on Object Oriented Programming Systems, Languages and Applications, 1993, pp. 91-108.
[20]
B. Hou, Y. Yao, B. Wang, and D. Liao, "Supe-net: an efficient parallel simulation environment for large-scale networked social dynamics." in 2010 IEEE/ACM International Conference on Green Computing and Communications & 2010 IEEE/ACM International Conference on Cyber, Physical and Social Computing, 2010, pp. 628-635.
[21]
A. Clauset, C. R. Shalizi, and M. E. J. Newman, "Power-law distributions in empirical data," SIAM Rev., vol. 51, pp. 661-703, November 2009.
[22]
M. E. J. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577-8582, 2006.
[23]
A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," Phys. Rev. E, vol. 70, no. 6, p. 066111, Dec 2004.
[24]
S. Fortunato, "Community detection in graphs," Physics Reports, vol. 486, no. 3-5, pp. 75-174, 2010.
[25]
T. M. Cover and J. A. Thomas, Elements of information theory. New York, NY, USA: Wiley-Interscience, 1991.
[26]
G. Karypis and V. Kumar, "Multilevel k-way partitioning scheme for irregular graphs," Journal of Parallel and Distributed Computing, vol. 48, p. 96C129, 1998.
Recommendations
An experimental study of a parallel shortest path algorithm for solving large-scale graph instances
Proceedings of the Meeting on Algorithm Engineering & ExpermimentsWe present an experimental study of the single source shortest path problem with non-negative edge weights (NSSP) on large-scale graphs using the Δ-stepping parallel algorithm. We report performance results on the Cray MTA-2, a multithreaded parallel ...
Performance prediction of large parallel applications using parallel simulations
Accurate simulation of large parallel applications can be facilitated with the use of direct execution and parallel discrete event simulation. This paper describes the use of COMPASS, a direct execution-driven, parallel simulator for performance ...
A Parallel Simulator for Large-Scale Parallel Computers
GCC '10: Proceedings of the 2010 Ninth International Conference on Grid and Cloud ComputingThis paper describes the design and application of an execution-driven parallel simulator for predicting performance of Large-Scale Parallel Computers. The simulator can be used in hardware validation and software development for large-scale parallel ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2011
187 pages
ISBN:9781457713637
Sponsors
Publisher
IEEE Computer Society
United States
Publication History
Published: 14 June 2011
Check for updates
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 398 of 779 submissions, 51%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 39Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in