Can Parallel Algorithms Enhance Serial Implementation?
Can Parallel Algorithms Enhance Serial Implementation?
Files
Publication or External Link
Date
1998-10-15
Authors
Vishkin, Uzi
Advisor
Citation
DRUM DOI
Abstract
Consider the serial emulation of a parallel algorithm. The thesis
presented in this paper is rather broad. It suggests that such a serial
emulation has the potential advantage of running on a serial machine
faster than a standard serial algorithm for the same problem.
The main concrete observation is very simple: just before the serial
emulation of a round of the parallel algorithm begins, the whole list of
memory addresses needed during this round is readily available; and, we
can start fetching all these addresses from secondary memories at this time.
This permits prefetching the data that will be needed in the next "time
window", perhaps by means of pipelining; these data will then be ready at
the fast memories when requested by the CPU. The possibility of
distributing memory addresses (or memory fetch units) at random over
memory modules, as has been proposed in the context of implementing the
parallel-random-access machine (PRAM) design space, is discussed.
This work also suggests that a multi-stage effort to build a parallel
machine may start with "parallel memories" and serial processing,
deferring parallel processing to a later stage. The general approach has
the following advantage: a user-friendly parallel programming language
can be used already in its first stage. This is in contrast to a practice
of compromising user-friendliness of parallel computer interfaces (i.e.,
parallel programming languages), and may offer a way for alleviating a
so-called "parallel software crisis".
It is too early to reach conclusions regarding the significance of the
thesis of this paper. Preliminary experimental results with respect to
the fundamental and practical problem of constructing suffix trees
indicate that drastic improvements in running time might be possible.
Serious attempts to follow it up are needed to determine its usefulness.
Parts of this paper are intentionally written in an informal way,
suppressing issues that will have to be resolved in the context of a
concrete implementation. The intention is to stimulate debate and provoke
suggestions and other specific approaches.
Validity of our thesis would imply that a standard computer science
curriculum, which prepares young graduates for a professional career of
over forty years, will have to include the topic of parallel algorithms
irrespective of whether (or when) parallel processing will succeed serial
processing in the general purpose computing market.
(Also cross-referenced as UMIACS-TR-91-145.1)