Asynchronous Analysis of Para1 le1 Dynamic Programming Algorithms
Gary Lewandowski, Anne Condon, Eric Bach · 1996
We examine a very simple asynchronous model of parallel computation that assumes the time to compute a task is random, following some probability distribution. The goal of this model is to capture the effects of unpiredictable delays on processors, due to communication delays or cache misses, for example. Using techniques from queueing theory and occupancy problems, we use this model to analyze two parallel dynamic programming algorithms. We show that this model is simple to analyze and correctly predicts which algorithm will perform better in practice. The algorithms we consider are ,a pipeline algorithm, where each processor icomputes 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 are computed in turn. It is likely that the techniques used here can be useful in the analysis of other algorithms that use barriers or pipelining techniques. Index Terms-Parallel dynamic programming, asynchronous algorithms, parallel models of computation, queueing theory, analysis of algorithms. +