Some results concerning linear iterative (systolic) arrays

Oscar H. Ibarra, Michael A. Palis, Sam M. Kim

Research output: Contribution to journalArticlepeer-review

59 Scopus citations


Characterizations of various types of linear iterative (systolic) arrays in terms of single processor sequential machines are given. Using these characterizations, new or improved results concerning the properties, power, and limitations of the different linear array models are proved. For example, a speed-up theorem is proved that is stronger than what has previously appeared in the literature and, moreover, works for arrays with one-way communication lines. Also investigated are the effects of augmenting the array with a supplemental control mechanism called global control. It is shown that in many cases arrays with global control can be simulated in real-time by arrays without global control. The result remains true even if one of the processors is augmented by a stack. Cases are also exhibited where the addition of global control makes the array strictly more powerful, even if the control lines are restricted to only a few processors of the array.

Original languageEnglish (US)
Pages (from-to)182-218
Number of pages37
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - May 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Some results concerning linear iterative (systolic) arrays'. Together they form a unique fingerprint.

Cite this