TY - GEN

T1 - Asynchronous updates in large parallel systems

AU - Greenberg, Albert G.

AU - Shenker, S.

AU - Stolyar, Alexander L.

N1 - Publisher Copyright:
© 1996 ACM.

PY - 1996/5/15

Y1 - 1996/5/15

N2 - Lubachevsky [5] introduced a new parallel simulation technique intended for systems with limited interactions between their many components or sites. Each site has a local simulation time, and the states of the sites are updated asynchronously. This asynchronous updating appears to allow the simulation to achieve a high degree of parallelism, with very low overhead in processor synchronization. The key issue for this asynchronous updating technique is: how fast do the local times make progress in the large system limit? We show that in a simple K-random interaction model the local times progress at a rate 1/(K + 1). More importantly, we find that the asymptotic distribution of local times is described by a traveling wave solution with exponentially decaying tails. In terms of the parallel simulation, though the interactions are local, a very high degree of global synchronization results, and this synchronization is succinctly described by the traveling wave solution. Moreover, we report on experiments that suggest that the traveling wave solution is universal; i.e., it holds in realistic scenarios (out of reach of our analysis) where interactions among sites are not random.

AB - Lubachevsky [5] introduced a new parallel simulation technique intended for systems with limited interactions between their many components or sites. Each site has a local simulation time, and the states of the sites are updated asynchronously. This asynchronous updating appears to allow the simulation to achieve a high degree of parallelism, with very low overhead in processor synchronization. The key issue for this asynchronous updating technique is: how fast do the local times make progress in the large system limit? We show that in a simple K-random interaction model the local times progress at a rate 1/(K + 1). More importantly, we find that the asymptotic distribution of local times is described by a traveling wave solution with exponentially decaying tails. In terms of the parallel simulation, though the interactions are local, a very high degree of global synchronization results, and this synchronization is succinctly described by the traveling wave solution. Moreover, we report on experiments that suggest that the traveling wave solution is universal; i.e., it holds in realistic scenarios (out of reach of our analysis) where interactions among sites are not random.

UR - http://www.scopus.com/inward/record.url?scp=84964554627&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84964554627&partnerID=8YFLogxK

U2 - 10.1145/233013.233028

DO - 10.1145/233013.233028

M3 - Conference contribution

AN - SCOPUS:84964554627

T3 - SIGMETRICS 1996 - Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

SP - 91

EP - 103

BT - SIGMETRICS 1996 - Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

PB - Association for Computing Machinery, Inc

T2 - 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1996

Y2 - 23 May 1996 through 26 May 1996

ER -