IEICE TRANSACTIONS on transactions
Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays
Summary :
Mesh-connected computers (MCC's for short) are an important class of physically realizable parallel processors, since many scientific problems can be naturally mapped on them and because their regular structures and simple nearest-neighbour interconnections are particularly suitable for VLSI implementations. In former days iterative arrays and cellular automata were studied and recently special attention has been paid to the study of systolic arrays as a model of parallel computation on VLSI implemented MCC's. These abstract computational models constitute a family of MCC's. In this paper we study the effects of broadcasting bus systems augmented with a mesh-connected computer. First we develop a direct proof technique for the elimination of broadcasting buses. Then, as an application of the technique, we will show that a rich variety of broadcasting bus systems on one- and two-dimensional arrays can be eliminated without any loss of time efficiency. No-time-loss elimination of broadcasting buses on one-dimensional arrays has been shown by a different technique by Ibarra et al., but without our technique, it would be more difficult, but not impossible, to get the same results that we presented newly in this paper.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E72-E No.5 pp.647-655
- Publication Date
- 1989/05/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Computer Systems
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, Thomas WORSCH, Roland VOLLMAR, "Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays" in IEICE TRANSACTIONS on transactions,
vol. E72-E, no. 5, pp. 647-655, May 1989, doi: .
Abstract: Mesh-connected computers (MCC's for short) are an important class of physically realizable parallel processors, since many scientific problems can be naturally mapped on them and because their regular structures and simple nearest-neighbour interconnections are particularly suitable for VLSI implementations. In former days iterative arrays and cellular automata were studied and recently special attention has been paid to the study of systolic arrays as a model of parallel computation on VLSI implemented MCC's. These abstract computational models constitute a family of MCC's. In this paper we study the effects of broadcasting bus systems augmented with a mesh-connected computer. First we develop a direct proof technique for the elimination of broadcasting buses. Then, as an application of the technique, we will show that a rich variety of broadcasting bus systems on one- and two-dimensional arrays can be eliminated without any loss of time efficiency. No-time-loss elimination of broadcasting buses on one-dimensional arrays has been shown by a different technique by Ibarra et al., but without our technique, it would be more difficult, but not impossible, to get the same results that we presented newly in this paper.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e72-e_5_647/_p
Copy
@ARTICLE{e72-e_5_647,
author={Hiroshi UMEO, Thomas WORSCH, Roland VOLLMAR, },
journal={IEICE TRANSACTIONS on transactions},
title={Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays},
year={1989},
volume={E72-E},
number={5},
pages={647-655},
abstract={Mesh-connected computers (MCC's for short) are an important class of physically realizable parallel processors, since many scientific problems can be naturally mapped on them and because their regular structures and simple nearest-neighbour interconnections are particularly suitable for VLSI implementations. In former days iterative arrays and cellular automata were studied and recently special attention has been paid to the study of systolic arrays as a model of parallel computation on VLSI implemented MCC's. These abstract computational models constitute a family of MCC's. In this paper we study the effects of broadcasting bus systems augmented with a mesh-connected computer. First we develop a direct proof technique for the elimination of broadcasting buses. Then, as an application of the technique, we will show that a rich variety of broadcasting bus systems on one- and two-dimensional arrays can be eliminated without any loss of time efficiency. No-time-loss elimination of broadcasting buses on one-dimensional arrays has been shown by a different technique by Ibarra et al., but without our technique, it would be more difficult, but not impossible, to get the same results that we presented newly in this paper.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays
T2 - IEICE TRANSACTIONS on transactions
SP - 647
EP - 655
AU - Hiroshi UMEO
AU - Thomas WORSCH
AU - Roland VOLLMAR
PY - 1989
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E72-E
IS - 5
JA - IEICE TRANSACTIONS on transactions
Y1 - May 1989
AB - Mesh-connected computers (MCC's for short) are an important class of physically realizable parallel processors, since many scientific problems can be naturally mapped on them and because their regular structures and simple nearest-neighbour interconnections are particularly suitable for VLSI implementations. In former days iterative arrays and cellular automata were studied and recently special attention has been paid to the study of systolic arrays as a model of parallel computation on VLSI implemented MCC's. These abstract computational models constitute a family of MCC's. In this paper we study the effects of broadcasting bus systems augmented with a mesh-connected computer. First we develop a direct proof technique for the elimination of broadcasting buses. Then, as an application of the technique, we will show that a rich variety of broadcasting bus systems on one- and two-dimensional arrays can be eliminated without any loss of time efficiency. No-time-loss elimination of broadcasting buses on one-dimensional arrays has been shown by a different technique by Ibarra et al., but without our technique, it would be more difficult, but not impossible, to get the same results that we presented newly in this paper.
ER -
English
