A case study in real-time parallel computation: Correcting algorithms

A correcting algorithm is one that receives an endless stream of corrections to its initial input data and terminates when all the corrections received have been taken into account. We give a characterization of correcting algorithms based on the theory of data-accumulating algorithms. In particular it is shown that an!, correcting algorithm exhibits superunitary behavior in a parallel computation setting if and only if the static counterpart of that correcting algorithm manifests a strictly; superunitary speedup. Since both classes of correcting and data-accumulating algorithms are included in the more general class of real-time algorithms, we show in fact that many problems from this class manifest superunitary behavior. Moreover, we give an example of a real-time parallel computation that pertains to neither of the two classes studied (namely, correcting and data-accumulating algorithms), but still manifests superunitary behavior, Because of the aforementioned results, the usual measures of performance for parallel algorithms (that is, speedup and efficiency) lose much of their ability to convey effectively the nature of the phenomenon taking place in the real-time case. We propose therefore a more expressive measure that captures all the relevant parameters of the computation. Our proposal is made in terms of a graphical representation, We state as an open problem the investigation of such a measure including finding an analytical form for it. (C) 2001 Academic Press.