On Efficient Simulations of Systolic Arrays by Random-Access Machines
Óscar H. Ibarra, Michael A. Palis · SIAM Journal on Computing · 1987
We give efficient simulations of systolic arrays by unit-cost random-access machines (RAM’s). For example, we show that a one-dimensional systolic array operating in linear time can be simulated by a RAM in $O({{n^2 } / {\log ^2 n}})$ time. For the case of a two-dimensional systolic array, the simulation time is $O({{n^3 } / {\log ^{{3 / 2}} n}})$.