Going through Rough Times: from Non-Equilibrium Surface Growth to Algorithmic Scalability
<|reference_start|>Going through Rough Times: from Non-Equilibrium Surface Growth to Algorithmic Scalability: 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.<|reference_end|>
@article{korniss2001going,
    title={Going through Rough Times: from Non-Equilibrium Surface Growth to
  Algorithmic Scalability},
    author={G. Korniss, M.A. Novotny, P.A. Rikvold, H. Guclu, and Z. Toroczkai},
    journal={Materials Research Society Symposium Proceedings Series Vol. 700,
  pp. 297-308, 2002},
    year={2001},
    archivePrefix={arXiv},
    eprint={cond-mat/0112103},
    primaryClass={cond-mat.stat-mech cond-mat.mtrl-sci cs.DC cs.PF physics.comp-ph}
}