Search

The structuring of algorithms suitable for execution on parallel processors is discussed. Two examples of such algorithms are given. The first example exhibits a restructuring of Bellman's dynamic programming technique; the second presents a method of parsing MAD-type statements in parallel.

This paper describes the recent development of parallel processing algorithms for solving optimal control problems for nonlinear dynamic systems. Both the deterministic and stochastic cases are considered. The resulting algorithms are applicable to a large range of parallel architecture computers, including Iliac IV, associative processors, and potential designs based on integrated circuit technology.

The design of efficient storage hierarchies generally involves the repeated running of "typical" program address traces through a simulated storage system while various hierarchy design parameters are adjusted. This paper describes a new and efficient method of determining, in one pass of an address trace, performance measures for a large class of demand-paged, multilevel storage systems utilizing a variety of mapping schemes and replacement algorithms. The technique depends on an algorithm classification, called "stack algorithms," examples of which are "least frequently used," "least recently used," "optimal," and "random replacement" algorithms. The techniques yield the exact access frequency to each storage device, which can be used to estimate the overall performance of actual storage hierarchies.

The computational theory of dynamic programming is examined from the viewpoint of parallel computation. A discussion of various forms of parallelism, the corresponding parallel algorithms, the applicability of the algorithms to different types of optimization problems, and their advantages over serial computation is presented. In addition, parallel aspects of various dimensionality reduction techniques such as state increment dynamic programming, successive approximations, and shift vectors are also given.

This paper presents new algorithms for the parallel evaluation of certain polynomial expression. In particular, for the parallel evaluation of xn,we introduce an algorithm which takes two steps of parallel division and [log2n] steps of parallel addition, while the usual algorithm takes [log2n] steps of parallel multiplication. Hence our algorithm is faster than the usual algorithms when multiplication takes more time than addition. Similar algorithm for the evaluation of other polynomial expressions are also introduced. Lower bounds on the time needed for the parallel evaluation of rational expressions are given. All the algorithms presented in the paper are shown to be asymptotically optimal. Moreover, we prove that by using parallelism the evaluation of any first order rational recurrence, e.g., [equation], and any non-linear polynomial recurrence can be sped up at most by a constant factor, no matter how many processors are used.