IEICE TRANSACTIONS on transactions
A Time-Optimum Systolic Simulation of Two-Way Linear-Time Cellular Automata
Summary :
In the design of systolic algorithms, optimizing the speed of I/O operations and computations is an important problem. In this paper we develop a time-optimum systolic simulation algorithm which converts any two-way cellular algorithm into systolic one, where the former separates the computations from its I/O operations, on the other hand, the latter overlaps them. It is shown that, for any kn linear-time two-way cellular automaton M, there exists a systolic array which can simulate M in (k+2)n+O(1) steps. The parallel steps required for the simulation are optimum.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E69-E No.3 pp.196-199
- Publication Date
- 1986/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Algorithm, Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroshi UMEO, "A Time-Optimum Systolic Simulation of Two-Way Linear-Time Cellular Automata" in IEICE TRANSACTIONS on transactions,
vol. E69-E, no. 3, pp. 196-199, March 1986, doi: .
Abstract: In the design of systolic algorithms, optimizing the speed of I/O operations and computations is an important problem. In this paper we develop a time-optimum systolic simulation algorithm which converts any two-way cellular algorithm into systolic one, where the former separates the computations from its I/O operations, on the other hand, the latter overlaps them. It is shown that, for any kn linear-time two-way cellular automaton M, there exists a systolic array which can simulate M in (k+2)n+O(1) steps. The parallel steps required for the simulation are optimum.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e69-e_3_196/_p
Copy
@ARTICLE{e69-e_3_196,
author={Hiroshi UMEO, },
journal={IEICE TRANSACTIONS on transactions},
title={A Time-Optimum Systolic Simulation of Two-Way Linear-Time Cellular Automata},
year={1986},
volume={E69-E},
number={3},
pages={196-199},
abstract={In the design of systolic algorithms, optimizing the speed of I/O operations and computations is an important problem. In this paper we develop a time-optimum systolic simulation algorithm which converts any two-way cellular algorithm into systolic one, where the former separates the computations from its I/O operations, on the other hand, the latter overlaps them. It is shown that, for any kn linear-time two-way cellular automaton M, there exists a systolic array which can simulate M in (k+2)n+O(1) steps. The parallel steps required for the simulation are optimum.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - A Time-Optimum Systolic Simulation of Two-Way Linear-Time Cellular Automata
T2 - IEICE TRANSACTIONS on transactions
SP - 196
EP - 199
AU - Hiroshi UMEO
PY - 1986
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E69-E
IS - 3
JA - IEICE TRANSACTIONS on transactions
Y1 - March 1986
AB - In the design of systolic algorithms, optimizing the speed of I/O operations and computations is an important problem. In this paper we develop a time-optimum systolic simulation algorithm which converts any two-way cellular algorithm into systolic one, where the former separates the computations from its I/O operations, on the other hand, the latter overlaps them. It is shown that, for any kn linear-time two-way cellular automaton M, there exists a systolic array which can simulate M in (k+2)n+O(1) steps. The parallel steps required for the simulation are optimum.
ER -
English
