An Algorithm for Solving Linear Recurrence Systems on Parallel and Pipelined Machines
Author:
Open Access
- 1 March 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-30 (3) , 190-206
Abstract
A new algorithm for the solution of linear recurrence systems on parallel or pipelined computers is described. Time bounds, speed-up and efficiency for SIMD and MIMD computers with fixed number of arithmetic elements (AE's), as well as for pipelined computers with fixed number of stages per operation, are obtained. The model of each computer is discussed in detail to explain better performance of the pipelined model. A simple modification in the design of AE's for parallel computers makes parallel model superior.Keywords
This publication has 7 references indexed in Scilit:
- Practical Parallel Band Triangular System SolversACM Transactions on Mathematical Software, 1978
- Solving Triangular Systems on a Parallel ComputerSIAM Journal on Numerical Analysis, 1977
- The Complexity of Parallel Evaluation of Linear RecurrencesJournal of the ACM, 1977
- Time and Parallel Processor Bounds for Linear Recurrence SystemsIEEE Transactions on Computers, 1975
- Parallel Solution of Recurrence ProblemsIBM Journal of Research and Development, 1974
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence EquationsIEEE Transactions on Computers, 1973
- Maximal rate pipelined solutions to recurrence problems1973