Designing systolic algorithms using sequential machines

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We offer a methodology for simplifying the design and analysis of systolic systems. Speciflcally, we give characterizations of systolic arrays in terms of (single processor) sequential machines which are easier to analyze and to program. We give several examples to illustrate the design methodology. In particular, we show how systolic arrays can be easily designed to implement priority queues, integer bitwise multiplication, dynamic programming, etc.. Because the designs are based on the sequential machine, the constructions we obtain are much simpler than those that have appeared in the literature. We also give some results concerning the properties and computational power (e.g., speed-up, hierarchy, etc.) of systolic arrays.

Original languageEnglish (US)
Title of host publication25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PublisherIEEE Computer Society
Pages46-55
Number of pages10
ISBN (Electronic)081860591X
StatePublished - 1984
Externally publishedYes
Event25th Annual Symposium on Foundations of Computer Science, FOCS 1984 - Singer Island, United States
Duration: Oct 24 1984Oct 26 1984

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1984-October
ISSN (Print)0272-5428

Conference

Conference25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Country/TerritoryUnited States
CitySinger Island
Period10/24/8410/26/84

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Designing systolic algorithms using sequential machines'. Together they form a unique fingerprint.

Cite this