Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-14T10:24:11.650Z Has data issue: false hasContentIssue false
  • English
  • Français

Going Through Rough Times: from Non-Equilibrium Surface Growth to Algorithmic Scalability

Published online by Cambridge University Press:  17 March 2011

G. Korniss,
M.A. Novotny,
P.A. Rikvold,
H. Guclu and
Z. Toroczkai
G. Korniss
Affiliation:
Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180-3590, USA
M.A. Novotny
Affiliation:
Department of Physics and Astronomy and Engineering Research Center, Mississippi State University, Mississippi State, MS 39762-5167, USA
P.A. Rikvold
Affiliation:
School of Computational Science and Information Technology, Department of Physics, and Center for Materials Research and Technology, Florida State University, Tallahassee, FL 32306, USA
H. Guclu
Affiliation:
Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180-3590, USA
Z. Toroczkai
Affiliation:
Theoretical Division and Center for Nonlinear Studies, MS-B258 Los Alamos National Laboratory, Los Alamos, NM 87545, USA
Get access

Abstract

Efficient and faithful parallel simulation of large asynchronous systems is a challenging computational problem. It requires using the concept of local simulated times and a synchronization scheme. We study the scalability of massively parallel algorithms for discrete-event simulations which employ conservative synchronization to enforce causality. We do this by looking at the simulated time horizon as a complex evolving system, and we identify its universal characteristics. We find that the time horizon for the conservative parallel discrete-event simulation scheme exhibits Kardar-Parisi-Zhang-like kinetic roughening. This implies that the algorithm is asymptotically scalable in the sense that the average progress rate of the simulation approaches a non-zero constant. It also implies, however, that there are diverging memory requirements associated with such schemes.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

REFERENCES

1. Fujimoto, R., Commun. of the ACM 33, 30 (1990).Google Scholar
2. Nicol, D.M. and Fujimoto, R.M., Annals of Operations Research 53 249 (1994).Google Scholar
3. Binder, K. and Heermann, D.W., Monte Carlo Simulation in Statistical Physics. An Introduction, 3rd ed. (Springer, Berlin, 1997).Google Scholar
4. Lubachevsky, B.D., Complex Systems 1, 1099 (1987).Google Scholar
5. Lubachevsky, B.D., J. Comput. Phys. 75, 103 (1988).Google Scholar
6. Glauber, R.J., J. Math. Phys. 4, 294 (1963).Google Scholar
7. Chandy, K.M. and Misra, J., IEEE Trans. on Softw. Eng. SE–5, 440 (1979).Google Scholar
8. Chandy, K.M. and Misra, J., Commun. ACM 24, 198 (1981).Google Scholar
9. Jefferson, D.R., Assoc. Comput. Mach. Trans. Programming Languages and Systems 7, 404 (1985).Google Scholar
10. Korniss, G., Novotny, M.A., and Rikvold, P.A., J. Comput. Phys. 153, 488 (1999).Google Scholar
11. Korniss, G., White, C.J., Rikvold, P.A., and Novotny, M.A., Phys. Rev. E 63, 016120 (2001).Google Scholar
12. Korniss, G., Toroczkai, Z., Novotny, M.A., and Rikvold, P.A., Phys. Rev. Lett. 84, 1351 (2000).Google Scholar
13. Korniss, G., Novotny, M.A., Toroczkai, Z., and Rikvold, P.A., in Computer Simulation Studies in Condensed Matter Physics XIII, Springer Proceedings in Physics, Vol. 86, editors Landau, D.P., Lewis, S.P., and Schüttler, H.-B. (Springer-Verlag, Berlin, Heidelberg, 2001), pp. 183–188.Google Scholar
14. Frontiers in Problem Solving: Phase Transitions and Complexity, edited by Hogg, T., Huberman, B.A., and Williams, C., Artif. Intell. 81 issue 1-2 (1996).Google Scholar
15. Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., and Troyansky, L., Nature (London) 400, 133 (1999).Google Scholar
16. Overeinder, B.J., Distributed Event-driven Simulation: Scheduling Stategies and Resource Management, Ph.D. thesis, Universiteit van Amsterdam (2000).Google Scholar
17. Overeinder, B.J., Schoneveld, A., and Sloot, P.M.A., Proceedings of the 15th Workshop on Parallel and Distributed Simulation (IEEE Comput. Soc., Los Alamitos, CA, 2001) pp. 145–152.Google Scholar
18. Barabási, A.-L. and Stanley, H.E., Fractal Concepts in Surface Growth (Cambridge University Press, Cambridge, 1995).Google Scholar
19. Halpin-Healy, Timothy and Zhang, Yi-Cheng, Phys. Rep. 254 215 (1995).Google Scholar
20. Krug, J., Adv. Phys. 46, 139 (1997).Google Scholar
21. Greenberg, A.G., Shenker, S., and Stolyar, A.L., Proc. ACM SIGMETRICS, Performance Eval. Rev. 24, 91 (1996).Google Scholar
22. Kardar, M., Parisi, G., and Zhang, Y.-C., Phys. Rev. Lett. 56, 889 (1986).Google Scholar
23. Family, F. and Vicsek, T., J. Phys. A 18, L75 (1985).Google Scholar
24. Edwards, S.F. and Wilkinson, D.R., Proc. R. Soc. London, Ser A 381, 17 (1982).Google Scholar
25. Foltin, G., Oerding, K., Rácz, Z., Workman, R.L., and Zia, R.K.P., Phys. Rev. E 50, R639 (1994).Google Scholar
26. Toroczkai, Z., Korniss, G., Sarma, S. Das, and Zia, R.K.P., Phys. Rev. E 62, 276 (2000).Google Scholar
27. Krug, J. and Meakin, P., J. Phys. A 23, L987 (1990).Google Scholar
28. Korniss, G., Novotny, M.A., Kolakowska, A.K., and Guclu, H., “Statistical Properties of the Simulated Time Horizon in Conservative Parallel Discrete-Event Simulations”, accepted for the Proceedings of ACM Symposium On Applied Computing, Madrid, Spain (2002).Google Scholar
29. Raychaudhuri, S., Cranston, M., Przybyla, C., and Shapir, Y., Phys. Rev. Lett. 87, 136101 (2001).Google Scholar
30. Kolakowska, A.K., Novotny, M.A., and Korniss, G., unpublished.Google Scholar