Scalability of Parallel Discrete-Event Algorithms

We continue our previous studies [1-4] of scalability of parallel discrete event simulations (PDES). Previously, ignoring communication overhead, we have shown that ALL short- ranged PDES can be made perfectly scalable [2]. These works simulated the PDES simulations and used ideas of non- equilibrium surface growth to analyze the virtual time surfaces of PDES. We present results that expand on these results in two ways. First, we also include communication times in the simulations. For short-ranged simulations we observe perfect scalability including communication times. Second, we study relaxation of the short-ranged requirement. Rather we limit the number of sites each processing element can communicate with. Hence we study scalability of systems with sparse communication patterns.\newline [1] G. Korniss et al, Phys. Rev. Lett., vol. 84, p. 1341 (2000).\newline [2] G. Korniss et al, Science, vol. 299, p. 677 (2003).\newline [3] A. Kolakowska, et al, Phys. Rev. E, vol. 68, 046705 (2003).\newline [4] L.N. Shchur and M.A. Novotny, Phys. Rev. E, vol. 70, 026703 (2004).