Mobile pipelines: Parallelizing left-looking algorithms using navigational programming

Abstract. Parallelizing a sequential algorithm—i.e., manually or automatically converting it into an equivalent parallel distributed algorithm—is an important problem. Ideally, the parallel algorithm should preserve the computational structure of the original sequential algorithm, display a high degree of parallelism, have low communication overhead, and be scalable. The difficulty of accomplishing this for a particular sequential algorithm depends on the nature of the algorithm and the specific model of parallelism under consideration. Generally, the so called “right-looking ” algorithms are easy to parallelize because they tend to have a significant amount of data parallelism. In these algorithms, data is “eagerly ” propagated to and consumed by subsequent computations immediately after it is produced, and so it does not need to be kept in temporary storage for extended periods of time. In this paper we consider the class of “left-looking ” sequential algorithms [1], which cannot be easily parallelized using the message-passing or distributed shared memory models. These algorithms are characterized by “lazy ” propagation of data. We show that these algorithms can be directly parallelized using the Navigational Programming model. We present performance data demonstrating the effectiveness of our approach.