Article

Free access

Folding and unrolling systolic arrays (Preliminary Version)

Authors:

K. Culik, II,

Jan K. PachlAuthors Info & Claims

PODC '82: Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 254 - 261

https://doi.org/10.1145/800220.806704

Published: 18 August 1982 Publication History

PDF eReader

Abstract

This paper is about two constructions for transforming planar systolic arrays. By a systolic array we mean a uniformly structured processor configuration that allows only local communication (between neighbour processors) and supports high throughout by pipelining. Such configurations are suitable for VLSI implementation [4, 5].

We show how new connections in a systolic array can be established by folding the array along a line; and how computations in one-dimensional arrays unroll to two-dimensional structures resembling trellis automata [2]. We construct systolic arrays for computing large powers of a matrix; for matching keywords; for recognizing square-free words; and for finding the controlled product of matrices.

References

[1]

S.N. Cole: Real-time computation by n-dimensional iterative arrays of finite-state machines, IEEE 7th Annual Symp. Switching Automata Theory (October 1966), 53-77.

Digital Library

Google Scholar

[2]

K. Culik II, J. Gruska and A. Salomaa: Systolic trellis automata (for VLSI), University of Waterloo Research Report CS-81-34 (December 1981).

Google Scholar

[3]

C.E. Leiserson and J.B. Saxe: Optimizing synchronous systems, 22nd Annual Symp. FOCS (October 1931), 23-36.

Google Scholar

[4]

C. Mead and L. Conway: Introduction to VLSI Systems, Addison-Wesley (1980).

Digital Library

Google Scholar

[5]

H.T. Kung: Why systolic architectures? Carnegie-Mellon University Research Report CMU-CS-81-148 (November 1981).

Google Scholar

[6]

A. Salomaa: Jewels of Formal Language Theory, Computer Science Press (1981).

Google Scholar

[7]

K. Culik II and J.K. Pachl: Folding and unrolling systolic arrays, University of Waterloo Research Report CS-82-11 (1982).

Google Scholar

Cited By

View all

Bucher WCulik II K(2011)On real time and linear time cellular automataRAIRO. Informatique théorique10.1051/ita/198418040307118:4(307-325)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1984180403071
Culik KJürgensen H(2007)Programmable finite automata for VLSI†International Journal of Computer Mathematics10.1080/0020716830880339014:3-4(259-275)Online publication date: 20-Mar-2007
https://doi.org/10.1080/00207168308803390
Culik KYu S(1984)Iterative tree automataTheoretical Computer Science10.1016/0304-3975(84)90043-432:3(227-247)Online publication date: 1984
https://doi.org/10.1016/0304-3975(84)90043-4
Show More Cited By

Index Terms

Folding and unrolling systolic arrays (Preliminary Version)
1. Hardware
  1. Emerging technologies
  2. Very large scale integration design

Recommendations

Translating systolic arrays into instruction systolic arrays
CSC '88: Proceedings of the 1988 ACM sixteenth annual conference on Computer science

An instruction systolic array is a programmable systolic array. Instructions and mask bits are pumped through the array as well as data. It offers cost-benefit advantages over systolic arrays because one array can be used for multiple applications. This ...
Programmable systolic arrays
Techniques for design and testing of iterative and systolic arrays

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '82: Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing

August 1982

261 pages

ISBN:0897910818

DOI:10.1145/800220

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 August 1982

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
274
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)12

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bucher WCulik II K(2011)On real time and linear time cellular automataRAIRO. Informatique théorique10.1051/ita/198418040307118:4(307-325)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1984180403071
Culik KJürgensen H(2007)Programmable finite automata for VLSI†International Journal of Computer Mathematics10.1080/0020716830880339014:3-4(259-275)Online publication date: 20-Mar-2007
https://doi.org/10.1080/00207168308803390
Culik KYu S(1984)Iterative tree automataTheoretical Computer Science10.1016/0304-3975(84)90043-432:3(227-247)Online publication date: 1984
https://doi.org/10.1016/0304-3975(84)90043-4
Gruska J(1984)Systolic automata — power, characterizations, nonhomogeneityMathematical Foundations of Computer Science 198410.1007/BFb0030288(32-49)Online publication date: 1984
https://doi.org/10.1007/BFb0030288
Choffrut CCulik K(1984)On real-time cellular automata and trellis automataActa Informatica10.1007/BF0026461721:4(393-407)Online publication date: Nov-1984
https://doi.org/10.1007/BF00264617
Choffrut CCulik K(1983)Folding of the plane and the design of systolic arraysInformation Processing Letters10.1016/0020-0190(83)90055-817:3(149-153)Online publication date: Oct-1983
https://doi.org/10.1016/0020-0190(83)90055-8

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Translating systolic arrays into instruction systolic arrays

Programmable systolic arrays

Techniques for design and testing of iterative and systolic arrays