Stochastic Model of Massively Parallel Computation

A. Greenberg, V.A. Malyshev, S.Yu. Popov

1995, v.1, №4, 473-490


A problem of massive parallelism is considered, where $N$ processor units are used for large-scale simulation or computation. Processor unit $i$ has its accumulated local time variable $z_{i}(t)$. At Poisson time moments $t_{k}^{i}$, it gets a job and chooses randomly $I$ other units. If its local time does not exceed the local times of the chosen $I$ units, then $z_{i}(t_{k}^{i})$ is augmented by an independent random variable $\eta_{ik}$. In the large $N$ limit we obtain a deterministic nonlinear PDE for the density of local times. Subsequent corollaries are a travelling wave solution, the linear time growth of the mean local time etc.

Keywords: parallel computation,asymptotic independence


Please log in or register to leave a comment

There are no comments yet