Optimally universal parallel computers
Leslie Gabriel Valiant · Philosophical Transactions of the Royal Society of London Series A Mathematical and Physical Sciences · 1988
Abstract It is shown that any program written for the idealized shared-memory model of parallel computation can be simulated on a hypercube architecture with only constant factor inefficiency, provided that the original program has a certain amount of parallel slackness.