Mapping dynamic programming onto modular linear systolic arrays

Summary In this paper we propose a novel way of deriving a family of fully-pipelined linear systolic algorithms for the computation of the solutions of a dynamic programming problem. In many instances, modularity is an important feature of these algorithms. One may simply add more processors to the array as the size of the problem increases. Each cell has a fixed amount of local storage and the time delay between two consecutive cells of the array is constant. The time complexity and the number of cells in our array tend ton²+O(n) andn²/ +O(n), respectively, as increases. This represents the best known performance for such an algorithm.Jean Frédéric Myoupo received his B.Sc in mathematics from the University of Yaounde, Cameroon, in 1980, and the M.S. and Ph.D. degrees both in applied mathematics from the Université Paul Sabatier de Toulouse, France in 1981 and 1983 respectively. From 1983 to 1985, he was lecturer at the Université de Sherbrooke, Québec, Canada. From 1985 to 1990, he was Assistant-Professor at the University of Yaounde, Cameroon. Since October 1990, he has been Associate-Professor in the department d'Informatique and Laboratoire de Recherche en Informatique (L.R.I.) of the Université de Paris-Sud, France. His current research interests include design of systolic algorithms and architectures, parallel and distributed processing.