ASYNCHRONOUS ANALYSIS OF PARALLEL DYNAMIC-PROGRAMMING ALGORITHMS

We examine a very simple asynchronous model of parallel computation th at assumes the time to compute a task is random, following some probab ility distribution. The goal of this model is to capture the effects o f unpredictable delays on processors, due to communication delays or c ache misses, for example. Using techniques from queueing theory and oc cupancy problems, we use this model to analyze two parallel dynamic pr ogramming algorithms. We show that this model is simple to analyze and correctly predicts which algorithm will perform better in practice. T he algorithms we consider are a pipeline algorithm, where each process or i computes in order the entries of rows i, i + p, and so on, where p is the number of processors; and a diagonal algorithm, where entries along each diagonal extending from the left to the top of the table a re computed in turn. It is likely that the techniques used here can be useful in the analysis of other algorithms that use barriers or pipel ining techniques.