Parallel real-time computation: sometimes quantity means quality

摘要

We show that within the paradigm of real time computation, someclasses of problems have the property that a solution to a problem inthe class, when computed in parallel, is far superior in quality thanthe best one obtained on a sequential computer. Examples from theseclasses are presented. In each case, the solution obtained in parallelis significantly, provably, and consistently better than a sequentialone. It is important to note that the purpose of the paper is not todemonstrate merely that a parallel computer can obtain a better solutionto a computational problem than one derived sequentially. The latter isan interesting (and often surprising) observation in its own right, butwe wish to go further. It is shown that the improvement in quality canbe arbitrarily high (and certainly superlinear in the number ofprocessors used by the parallel computer). This result is akin tosuperlinear speedup, a phenomenon itself originally thought to beimpossible