Stochastic Model of Massively Parallel Computation

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

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

ABSTRACT

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