On high-speed computing with a programmable linear array

Peizong Lee, Zvi M. Kedem

Research output: Contribution to journalArticlepeer-review

Abstract

It has been observed by many researchers that systolic arrays are very suitable for certain high-speed computations. Using a formal methodology, we present a design for a single simple programmable linear systolic array capable of solving large numbers of problems drawn from a variety of applications. The methodology is applicable to problems solvable by sequential algorithms that can be specified as nested for-loops of arbitrary depth. The algorithms of this form that can be computed on the array presented in this paper include 25 algorithms dealing with signal and image processing, algebraic computations, matrix arithmetic, pattern matching, database operations, sorting, and transitive closure. Assuming bounded I/O, for 18 of those algorithms the time and storage complexities are optimal, and therefore no improvement can be expected by using dedicated special-purpose linear systolic arrays designed for individual algorithms. We also describe another design which, using a sufficient large local memory and allowing data to be preloaded and unloaded, has an optimal processor/time product.

Original languageEnglish (US)
Pages (from-to)223-249
Number of pages27
JournalThe Journal of Supercomputing
Volume4
Issue number3
DOIs
StatePublished - Sep 1990

Keywords

  • Parallel processing
  • Programmable systolic array
  • VLSI
  • algebraic computations
  • algorithm transformations
  • database operations
  • matrix arithmetic
  • nested loop algorithms
  • pattern matching
  • signal and image processing
  • sorting
  • transitive closure

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'On high-speed computing with a programmable linear array'. Together they form a unique fingerprint.

Cite this