Can Parallel Algorithms Enhance Serial Implementation?

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)