Systolic Array Synthesis: Computability and Time Cones.
Abstract
Many important algorithms in signal and image processing, speech and pattern recognition of matrix computations consist of coupled systems of recurrence equations. Systolic arrays are regular networks of tightly coupled simple processors with limited storage that provide cost effective high throughput implementations of many such algorithms. While there are some mathematical techniques for finding efficient schedules for uniform recurrence equations, there is no general theory for more general systems of recurrence equations. The first elements of such a theory are presented in this paper and constitute a significant step towards establishing a complete methodology that determines systolic array implementations for a very general class of coupled systems of recurrence equations; these implementations exhibit provably optimal computation time while satisfying various user-specified constraints.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1986
- Accession Number
- ADA168697
Entities
People
- Ilse C. Ipsen
- Jean-marc Delosme
Organizations
- Yale University